[BNF] Левая/правая рекурсия

http://ru.wikipedia.org/wiki/Грамматика,_разбирающая_выражение#.D0.9D.D0.B5.D...

и? я там нашёл описание такого же факта...

причём с РВ-граматикой вроде всё ясно, так как там оператор '+' двигается по анализируемой строке, насколько я понял

BNF это нотация, а не алгоритм.

Алгоритмы это LL(1), LL(k), LL(*), LALR, LR(0), LR(1), GLR...

И они все ведут себя по-разному.

И что характерно ни один из них не пригоден для практического использования.

И если семейство LL еще можно использовать для простеньких язычков, то семейство LR просто не адекватно. Получить от них внятное сообщение об ошибки задачка не для слабонервных.

я же не про особенности алгоритмов

Ты про алгоритмы. Причем про алгоритмы разбора.

А БНФ мало того что не алгоритм. Так еще и описывает _генерацию_, а не разбор текста.

Это кстати один из самых больших маразмов компутерсайнс. Толпа учёных пытается построить алгоритмы разбора по порождающей грамматике. :)))

Не удивительно, что у них получаются либо обрубки, либо тормоза.

И что характерно разбирающие грамматики игнорируются чуть менее чем полностью.

В книге дракона о них даже не упоминается.

Толпа учёных пытается построить алгоритмы разбора по порождающей грамматике.

Прямо-таки толпа? И bnf часто используется для формализации синтаксиса, в разбирающей грамматике это было малоудобно, али я не прав?

Прямо-таки толпа?

Чуть менее чем все кто занимается алгоритмами анализа текста.

И bnf часто используется для формализации синтаксиса, в разбирающей грамматике это было малоудобно, али я не прав?

Я не понял что тут написано.

Могу лишь еще раз повторить, что БНФ порождающая грамматика.

И использовать порождающую грамматику для создания системы разбора занятие противоестественное.

Чето ты по-моему немножко не так понял.

К эквивалентности алгоритмов разбора у старой и новой грамматик это всё отношения не имеет(Да и меняют то как раз чтобы поменять набор применимых алгоритмов для разбора грамматики. И да, например, при таких финтах ушами может запросто поменяться приоритет операторов, и т.п. т.к. грамматика становится праворекурсивной). Тут фишка именно в том, что мы изменяем саму грамматику на _эквивалентную_. И тут надо подумать - на эквивалентную в каком плане? А в таком, как выше уже сказали - мы заменяем на грамматику, которая может _генерировать_ те же строки, что и предыдущая. Ну типа, строки из новой грамматики получаются те же, а вот парсеры мы для распознавания(именно для распознавания!! а не разбора.) этих строк можем написать уже попроще.

Ну и да, CFG это все стремная фигня. Используй вон PEG. В них все просто и детерминированно.

lovesan

Так еще и описывает _генерацию_, а не разбор текста.

я пока не вижу _сильной_ разницы между разбором и генерацией.

Вот как я пока всё это понимаю: транслятор поглащает термы входной строки используя описание граматики(продукции нетерминалов), если нет подходящей продукции, он считает строку неверной. Также, строя дерево разбора мы можем добавлять аттрибутам узлов дерева генерируемые значения(ну или, как в примере книги дракона, делая print). Тогда у нас уже не просто разбор, но и генерация.

Фундаментальное отличие РВ-грамматики от КС-грамматики заключается в том, что оператор выбора РВ-грамматики является упорядоченным. Если первая альтернатива срабатывает, то все последующие — игнорируются. Таким образом, упорядоченный выбор некоммутативен, в отличие от книжных определений контекстно-свободных грамматик и регулярных выражений.

РВ-грамматики не могут содержать леворекурсивных правил, которые содержат вызов самих себя без продвижения по строке.

как я понял это значит, что стоит устранять такие правила, а не то, что их просто в принципе невозможно написать

string-of-a ← string-of-a 'a' | 'a' Это можно переписать в РВ-грамматике, используя оператор +: string-of-a ← 'a'+

Как в РВ-г устраняется бесконечная левая рекурсия понятно.

А как в КС-г непонятно...

Тут фишка именно в том, что мы изменяем саму грамматику на _эквивалентную_.

вот у меня и вопрос, как? Вот к примеру такую продукцию

expr -> expr + term

expr -> expr + term | term

Ну и да, CFG это все стремная фигня. Используй вон PEG. В них все просто и детерминированно.

Я сначала разбирусь в книге дракона, а потом уже...

Ты немного не так на это смотришь.

КС-Грамматики(в отличие от PEG, например), сами по себе не «работают». Они это просто декларативное описание допустимых в языке строк. Причем описание _не_детерминированное_ (т.е. «|» в CFG означает - вот в тексте на таком-то языке могут быть такие то строки, а могут быть и такие. Строки, да, линейного текста.).

Т.е. ты смотришь на все это с точки зрения извлечения структуры из текста компьютером. А CFG сами по себе специфицируют _генерацию_ обычного _текста_.

Кстати, замена левой рекурсии не совсем так работает, насколько я помню - там надо чтобы в изначальном правиле был выбор. Соответственно, не все правила с левой рекурсией можно заменить на правую.

Т.е. это значит, что в описании граматики мы заменяем правила с левой рекурсией на правила с выбором, типа «expr -> expr + term | term», а трансляторы этой граматики уже сами должны разобраться в каком порядке выбирать продукции чтобы не уйти в бесконечную рекурсию?

Нене, грамматики пишутся под трансляторы.

Я имею ввиду, чтобы устранить левую рекурсию, нужно чтобы была возможность ее устранить. Т.е. вот правило вида

Expr <- Expr '+' Term
Expr <- Term
(или что то же самое: Expr <- Expr '+' Term| Term)

Мы можем заменить на

Expr <- Term RestExpr
RestExpr <- '+' Expr
RestExpr <- { пусто, т.е. напр. рекурсивно-нисходящий парсер, не сумей сматчить '+', все равно выходит из подпроцедуры с успехом }

В то же время, правило типа

Expr <- Expr '+' Term

Короче - почему для LL надо заменять левую рекурсию? Потому что надо чтобы он продвигался по строке, а не циклился. Но, при преобразованиях надо чтобы консистентность грамматики оставалась той же - то есть чтобы из нее те же строки получались.

Общее правило такое: Мы можем заменить левую рекурсию только в случаях когда у нас есть

A <- A a1 | A a2 | ... | A an | b1 | b2 | ... | bn

A <- b1 A' | b2 A' | ... | bn A'
A' <- a1 A | a2 A | ... | an A

Но, кстати, устранять левую рекурсию обычно надо ручками только в случае сложной непрямой левой рекурсии, путем рефакторинга грамматики. Это вообще NP-полная задача, и не факт что в любом случае успешно разрешаемая. Вышеописанный алгоритм генераторы LL парсеров(да и packrat-парсеров из PEG) обычно и сами умеют применять.

Потому что надо чтобы он продвигался по строке, а не циклился.

Если еще подробнее - LL продвигается вперед по строке, но вместе с тем он продвигается по грамматике «Сверху-вниз», и поэтому строит налево ветвящееся дерево. Поэтому он не может то же правило распарсить если оно есть в самом себе слева в одной из продукций.

А вот LR парсеры продвигаются по дереву «снизу-вверх», и поэтому к левой рекурсии индифферентны.

Кстати, есть еще такая штука как неоднозначность. Ее могут только GLR распарсить. Суть в том, что так как CFG правила не указывают в каком порядке парсить подпродукции, грамматика может содержать правила, которые могут интерпретироваться по разному, и выдавать разные строки в зависимости от порядка просмотра подпродукций. Это гораздо более серьезная проблема, чем левая рекурсия, так как она алгоритмически неразрешима в общем виде. А вот PEG порядок разбора указывают, и поэтому в них неоднозначности не может быть просто в принципе.

(да и packrat-парсеров из PEG) обычно и сами умеют применять.

Я больше скажу. Есть алгоритм разбора PEG, который поддерживает неограниченную левую рекурсию. Без изменения грамматики.

Google: Packrat Parsers Can Support Left Recursion

А вот PEG порядок разбора указывают, и поэтому в них неоднозначности не может быть просто в принципе.

Так то оно так. Вот только я бы не стал говорить, что ПЕГ это панацея.

Указать правильный порядок руками задача не простая. И на сложных грамматиках люди путаются. Проверено практикой.

В этой грамматике есть несколько ошибок связанных с приоритетным выбором https://github.com/rsdn/nemerle/blob/master/snippets/csharp-parser/CSharpPars... попробуй найди.

Есть более интересная технология https://github.com/rampelstinskin/ParserGenerator/blob/master/Test/Main.n