LINUX.ORG.RU

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


0

2

A - нетерминал
a,b - последовательности терминалов и нетерминалов, которые не начинаются с A

Предположим есть леворекурсивная продукция вида A -> Aa, где «+ term» есть «a» :

expr -> expr + term
в книге дракона предлагают устранить эту бесконечную рекурсию изменением продукции до вида A -> Aa | b:
expr -> expr + term | term
Из книги:

Когда A, наконец, заменяется на b, за ним следует последовательность из нуля или большего количества a

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

Ответ на: комментарий от anonymous

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

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

pseudo-cat ★★★ ()

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

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

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

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

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

winduzyatnik ()
Ответ на: комментарий от pseudo-cat

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

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

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

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

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

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

winduzyatnik ()
Ответ на: комментарий от winduzyatnik

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

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

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

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

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

winduzyatnik ()

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

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

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

lovesan

anonymous ()
Ответ на: комментарий от winduzyatnik

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

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

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

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

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

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

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

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

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

pseudo-cat ★★★ ()
Ответ на: комментарий от anonymous

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

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

expr -> expr + term
предлагается заменить на такую -
expr -> expr + term | term
это реально работает? Как? Если нет, то в принципе понятно, что нужно менять что-то другое, к примеру с помощью дополнителного нетерменала

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

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

pseudo-cat ★★★ ()
Ответ на: комментарий от pseudo-cat

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

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

anonymous ()
Ответ на: комментарий от pseudo-cat

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

pseudo-cat ★★★ ()
Ответ на: комментарий от pseudo-cat

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

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

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

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

Expr <- Term RestExpr
RestExpr <- '+' Expr
RestExpr <- { пусто, т.е. напр. рекурсивно-нисходящий парсер, не сумей сматчить '+', все равно выходит из подпроцедуры с успехом }
Потому что строки из правил будут выходить одни и те же. Но это строки - потому что, как можно заметить - AST из второго, преобразованного, правила, получается другое(ветвящееся вправо)(хотя _строки_ оба правила генерируют те же).

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

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) обычно и сами умеют применять.

anonymous ()
Ответ на: комментарий от anonymous

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

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

Google: Packrat Parsers Can Support Left Recursion

winduzyatnik ()
Ответ на: комментарий от anonymous

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

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

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

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

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

winduzyatnik ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.