Левый рекурсивный разбор

Question

Описание:

Читая книгу " Дизайн компилятора в Си", я наткнулся на следующие правила для описания контекстно-свободной грамматики:

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

А вот и грамматика:

1. statements ::= expression;
2.                | expression; statements
3. expression ::= expression + term
4.                | term
5. term       ::= term * factor
6.                | factor
7. factor     ::= number
8.                | (expression)

В книге говорится, что эта рекурсивная грамматика имеет большую проблему. Правая часть нескольких производств отображается слева, как в производстве 3 (И это свойство называется левой рекурсией), и некоторые парсеры, такие как парсер рекурсивного спуска, не могут обрабатывать левые рекурсии. Они просто петли навсегда.

Вы можете понять проблему, рассмотрев, как синтаксический анализатор решает применить конкретную продукцию, когда он заменяет нетерминал, имеющий более одной правой стороны. Простой случай очевиден в Productions 7 и 8. Парсер может выбрать, какую продукцию применять при расширении фактора, посмотрев на следующий входной символ. Если этот символ является числом, то компилятор применяет Production 7 и заменяет коэффициент на число. Если бы следующий входной символ представлял собой открытую скобку, парсер использовал бы Production 8. Однако выбор между Productions 5 и 6 не может быть решен таким образом. В случае Производства 6 правая часть термина начинается с коэффициента, который, в свою очередь, начинается либо с числа, либо с левой круглой скобки. Следовательно, синтаксический анализатор хотел бы применить Production 6, когда термин заменяется, а следующий входной символ - число или левая скобка. Производство 5- другая правая сторона - начинается с термина, который может начинаться с коэффициента, который может начинаться с цифры или левой круглой скобки, и это те же символы, которые использовались для выбора "Производство 6".

---

Вопрос:

Эта вторая цитата из книги полностью потеряла меня. Таким образом, используя пример некоторых утверждений, как (например) 5 + (7*4) + 14:

1. В чем разница между фактором и термином? используя тот же пример
2. Почему парсер рекурсивного спуска не может обрабатывать левые рекурсии? (Объясните вторую цитату).

Answer 1

1. В чем разница между фактором и термином? используя тот же пример

Я не приведу тот же пример, поскольку он не даст вам четкого представления о том, в чем вы сомневаетесь!

Дано,

term       ::= term * factor | factor
factor     ::= number | (expression)

Теперь предположим, что если я попрошу вас найти факторы и термины в выражении 2*3*4. Теперь умножение, оставленное ассоциативным, будет оцениваться как:

(2*3)*4

Как видите, здесь (2*3) - это термин, а коэффициент - это 4(число). Точно так же вы можете расширить этот подход до любого уровня, чтобы нарисовать идею о сроке.

Согласно данной грамматике, если в данном выражении есть цепочка умножения, то ее часть, оставляющая один фактор, является термином, который, в свою очередь, дает другую часть - другой термин, оставляя еще один фактор и скоро. Так оцениваются выражения.

2. Почему парсер рекурсивного спуска не может обрабатывать левые рекурсии? (Объясните вторую цитату).

Ваше второе утверждение совершенно ясно по своей сути. Синтаксический анализатор с рекурсивным спуском - это некий анализатор с нисходящим потоком, построенный из набора взаимно рекурсивных процедур (или нерекурсивного эквивалента), где каждая такая процедура обычно реализует одно из произведений грамматики.

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

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

A-> Ab

Здесь, расширяя нетерминал A, можно продолжать расширяться в

A-> AAb -> AAAb -> ... -> infinite loop of A.

Следовательно, мы предотвращаем леворекурсивное производство при работе с парсерами с рекурсивным спуском.

Answer 2

1. Коэффициент правила соответствует строке "1*3", а термин правила - нет (хотя он соответствует "(1*3)". По сути, каждое правило представляет один уровень приоритета. expression содержит операторы с самым низким приоритетом, factor второй самый низкий и term самый высокий. Если вы находитесь в сроке и хотите использовать оператор с более низким приоритетом, вам нужно добавить скобки.

2. Если вы реализуете парсер рекурсивного спуска с использованием рекурсивных функций, правило, подобное a ::= b "*" c | d может быть реализовано так:

   // Takes the entire input string and the index at which we currently are
   // Returns the index after the rule was matched or throws an exception
   // if the rule failed
   parse_a(input, index) {
     try {
       after_b = parse_b(input, index)
       after_star = parse_string("*", input, after_b)
       after_c = parse_c(input, after_star)
       return after_c
     } catch(ParseFailure) {
       // If one of the rules b, "*" or c did not match, try d instead
       return parse_d(input, index)
     }
   }
   

   Нечто подобное будет работать нормально (на практике вы, возможно, не захотите использовать рекурсивные функции, но подход, который вы используете вместо этого, все равно будет вести себя аналогично). Теперь давайте рассмотрим леворекурсивное правило a ::= a "*" b | c вместо:

   parse_a(input, index) {
     try {
       after_a = parse_a(input, index)
       after_star = parse_string("*", input, after_a)
       after_b = parse_c(input, after_star)
       return after_b
     } catch(ParseFailure) {
       // If one of the rules a, "*" or b did not match, try c instead
       return parse_c(input, index)
     }
   }
   

Теперь первое, что функция parse_a делает, чтобы вызвать себя снова с тем же индексом. Этот рекурсивный вызов снова вызовет сам себя. И это будет продолжаться до бесконечности, точнее, до тех пор, пока стек не переполнится и вся программа не рухнет. Если вместо рекурсивных функций мы используем более эффективный подход, мы фактически получим бесконечный цикл, а не переполнение стека. В любом случае мы не получаем желаемого результата.