@Yaroslav_Schekin @zukaboo Как называются грамматики, поддерживаемые lex? То есть, регулярные,

Question

Compiler Development

Konstantin Romanov

@Yaroslav_Schekin @zukaboo Как называются грамматики, поддерживаемые lex? То есть, регулярные,

с жадным выбором альтернатив, а если жадный дал одно и то же, то выбирается первая.

#compilerdev #it #programming #russian

0

08.10.2023

4 ответов

23 просмотра

Konstantin Romanov Автор вопроса

suhr
Я не видел, чтобы это кто-то называл, но в PEG впи...

Ну, то есть, если убрать обратную связь от bison к flex, то flex — это парсер урезанной PEG грамматики. Так?

0

08.10.2023

suhr

Konstantin Romanov
Ну, то есть, если убрать обратную связь от bison к...

Не берусь утверждать такое.

0

08.10.2023

Yaroslav Schekin

Хмм... во-первых, это же не грамматики, строго говоря (несмотря на то, что NFA/DFA, регулярные грамматики и регулярные выражения эквивалентны в recognition power (распознают то же множество языков), это не одно и то же). Во-вторых — это, скорее, способ применения регулярных выражений (я точно помню, что где-то видел тот же способ применения контекстно-свободных грамматик... но вот где?). Т.е., на практике, lexer решает не задачу recognition, т.е. "распознаёт ли данное регулярное выражение (или автомат, построенный из всех заданных правил) данную строку", а совсем другую задачу — нахождение длиннейшего префикса заданной строки, который распознаётся данным регулярным выражением. Lexer возвращает идентификатор правила (альтернативы), соответствующего этому префиксу. Вот что касается того, что я упоминал выше — CFG так тоже можно применять (для лексического анализа), и получится, что этот язык "длиннейших префиксов" тоже может быть не контекстно-свободным.

0

08.10.2023

suhr · Accepted Answer

suhr

Я не видел, чтобы это кто-то называл, но в PEG впихнуть можно.

0

08.10.2023

185 похожих чатов

@Yaroslav_Schekin @zukaboo Как называются грамматики, поддерживаемые lex? То есть, регулярные,

4 ответов

Похожие вопросы