Ответ на эти вопросы (и они действительны для LL (k) для любого конечного k) связан с тем, как стек синтаксического анализа работает в синтаксическом анализаторе LL.
В точке, где каждый находится в начале нетерминала в грамматике, синтаксический анализатор должен определить, оглядываясь в будущее только на жетоны случая k (1 в LL (1)), прежде чем решить, помещать ли в стек a конкретное правило или для разбора текста с использованием других правил. Итак, давайте рассмотрим каждый из этих случаев и посмотрим, как это влияет на это решение.
левая рекурсия. Есть два леворекурсивных случая.
а. У левой рекурсии нет жетонов после рекурсии. Правило что-то вроде:
нетермический: нетермальный;
Такое правило не действует и независимо от того, сколько вы набираете, не меняет то, что вы анализируете.
b. The left-recursion has tokens in it after the recursion. A rules something like:
нетермический: нетермальный «X»;
В этом правиле вам нужно помещать нетермические правила в стек столько раз, сколько следует за нетермом. Вы не можете определить, сколько существует X, только с k токенами. Если вы угадаете и догадаетесь слишком малым, у вас останется X, и для любого предположения в языке будет случай с большим количеством X-токенов. Если вы угадаете, а угадаете слишком большое, вы получите внешние нетермические правила в стеке. Вы не можете удалить их. В любом случае, вы просто не правы.
Non-детерминированным. Недетерминированная грамматика имеет те же характеристики, что и леворекурсивная. Это недетерминировано, следует ли вам подталкивать или нет. Языки палиндрома являются типичными недетерминированными примерами, но не единственными. На языке палиндрома вы не знаете, следует ли помещать в стек другого нетерминала или использовать токен, который вы видите, чтобы помочь вам вернуться обратно в стек. Если вы сделаете неправильный выбор, вы снова пропустите ввод.
Неоднозначный. Опять проблема похожая. В этом случае возможны два анализа. Тот, который выдвигает один нетерминал и успешно анализирует ввод, а другой - нет (возможно, вместо этого проталкивает другой нетерминал, сейчас или позже при разборе). Любой из них даст правильный анализ. Теперь, в неоднозначном случае, нажатие на нетерминал не обязательно вызовет ошибку синтаксического анализа, вы просто выберете один из возможных синтаксических разборов, игнорируя другой. Если ваша семантика требует, чтобы был выбран другой синтаксический анализ, проблема возникнет позже. Обратите внимание, конечно, что самые неоднозначные грамматики также являются недетерминированными.
Теперь, если вы посмотрите на эти случаи, вы увидите, что, если бы вы могли как-то одновременно поместить и не поместить нетерминал в стек, вы могли бы проанализировать ввод с помощью грамматики. И, в неоднозначном случае, создайте набор разборов, которые соответствуют входным данным. Есть методы, которые делают это, я полагаю, они считаются GLL (обобщенным LL) - эквивалентный метод с генератором синтаксического анализатора LR называется GLR. Результирующий вывод часто рассматривается как «лес синтаксического анализа» (или иногда синтаксический анализ, направленный ациклический граф).
[Примечание: я впервые увидел вышеупомянутый вопрос на Quora, и этот ответ скопирован оттуда.]