Почему плохая рекурсия?

20

В дизайне компилятора, почему левая рекурсия должна быть исключена в грамматике? Я читаю, что это потому, что это может вызвать бесконечную рекурсию, но разве это не так и для правильной рекурсивной грамматики?

formal-grammars compilers left-recursion Рафаэль
источник

2

Обычно компиляторы используют синтаксический анализ сверху вниз. Если у вас левая рекурсия, то парсер переходит в бесконечную рекурсию. Однако в рекурсии справа парсер может видеть префикс строки, которая у него есть. Таким образом, он может проверить, зашел ли вывод «слишком далеко». Вы, конечно, можете поменяться ролями и интерпретировать выражения справа, сделав плохую рекурсию плохой, а левую рекурсию хорошей.

Шалл

6

Левая рекурсия плоха, потому что в старые времена, когда у компьютеров было 16 КБ ОЗУ, наиболее часто используемый генератор парсеров не мог с этим справиться.

Андрей Бауэр

15

Левые рекурсивные грамматики не обязательно являются плохой вещью. Эти грамматики легко анализируются с использованием стека, чтобы отслеживать уже проанализированные фразы, как это имеет место в LR-анализаторе .

Напомним, что левое рекурсивное правило CF-грамматики имеет вид: $G = (V,\Sigma,R,S)$

$\alpha \rightarrow \alpha \beta$

с элементом и элементом . (См. Полное формальное определение для кортежа там ). $\alpha$ $V$ $\beta$ $V \cup \Sigma$ $(V,\Sigma,R,S)$

$\beta$ $\alpha$ $\alpha$

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

Каждый раз, когда правая часть правила сопоставляется группой последовательных элементов в верхней части стека, эта группа заменяется одним элементом, представляющим вновь сопоставляемую фразу. Эта замена называется сокращением .

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

didierc
источник

Было бы полезно, если бы вы определили свои переменные.

Андрей С

12

Рассмотрим это правило:

example : 'a' | example 'b' ;

Теперь рассмотрим анализатор LL, пытающийся сопоставить несоответствующую строку, как 'b'это правило. Так 'a'как не совпадает, он будет пытаться соответствовать example 'b'. Но для того, чтобы это сделать, оно должно соответствовать example... что именно оно и пыталось сделать в первую очередь. Он может застрять, пытаясь навсегда увидеть, может ли он соответствовать, потому что он всегда пытается сопоставить один и тот же поток токенов с одним и тем же правилом.

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

Chao
источник

3

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

reinierpost

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

cHao

Да, это более конструктивный и полезный способ выразить это.

reinierpost

4

(Я знаю, что этот вопрос довольно старый, но в случае, если у других людей тот же вопрос ...)

Вы спрашиваете в контексте парсеров рекурсивного спуска? Например, для грамматики expr:: = expr + term | term, почему-то вроде этого (оставлено рекурсивным):

// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

проблематично, но не это (правильно рекурсивно)?

// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

Похоже, обе версии expr()сами себя называют. Но важным отличием является контекст - то есть текущий токен, когда выполняется этот рекурсивный вызов.

В левом рекурсивном случае expr()постоянно вызывает себя с одним и тем же токеном, и никакого прогресса не происходит. В правильном рекурсивном случае он потребляет часть входных данных в вызове term()и токен PLUS до достижения вызова expr(). Таким образом, в этот момент рекурсивный вызов может вызвать термин и затем завершиться, прежде чем снова достигнет теста if.

Например, рассмотрим синтаксический анализ 2 + 3 + 4. Левый рекурсивный синтаксический анализатор вызывает expr()бесконечно, когда застрял на первом токене, в то время как правый рекурсивный анализатор потребляет «2 +» перед expr()повторным вызовом . Второй звонок expr()соответствует "3 +" и звонит expr()только с 4 слева. 4 соответствует условию, и синтаксический анализ завершается без дополнительных вызовов expr().

user65808
источник

2

Из руководства Bison:

«Любая последовательность может быть определена с использованием левой или правой рекурсии, но вы всегда должны использовать левую рекурсию , потому что она может анализировать последовательность любого числа элементов с ограниченным пространством стека. Правая рекурсия занимает место в стеке Bison в пропорционально количеству элементов в последовательности, потому что все элементы должны быть сдвинуты в стек, прежде чем правило может быть применено хотя бы один раз. См. Алгоритм синтаксического анализатора Bison, для дальнейшего объяснения этого. "

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

Так что это зависит от алгоритма парсера, но, как указано в других ответах, некоторые парсеры могут просто не работать с левой рекурсией

Эдуардо Вада
источник

Почему плохая рекурсия?

Ответы: