Почему леворекурсивная, недетерминированная или неоднозначная грамматика не может быть LL(1)?

Я провел еще несколько исследований и думаю, что нашел решение для 1-го и 2-го вопросов, что касается 3-го, я нашел для него существующее решение здесь, на SO, попытки доказательства написаны ниже:

Начнем с написания трех правил определения грамматики LL(1):

Для каждого производства A -> α | β с α ≠ β:

1. FIRST(α) ∩ FIRST(β) = Ø.
2. Если β =>* ε, то FIRST(α) ∩ FOLLOW(A) = Ø (также, если α =>* ε, то FIRST(β) ∩ FOLLOW(A) = Ø).
3. Включение ε в правило (1) подразумевает, что не более одного из α и β может быть получено ε.

Предложение 1. Нефакторизованная грамматика не является LL(1).

Доказательство:

Если грамматика G не факторизована, то существует продукция в G вида:

A -> ωα1 | ωα2 | ... | ωαn

(где αi — это i-th α, а не символы α и i), с α1 ≠ α2 ≠ ... ≠ αn. Тогда мы можем легко показать, что:

∩(i=1,..,n) FIRST(ωαi) ≠ Ø

что противоречит правилу (1) определения, поэтому нефакторизованная грамматика не является LL(1). ∎

Предложение 2. Леворекурсивная грамматика не является LL(1).

Доказательство:

Если грамматика леворекурсивна, то в G существует продукция вида:

S -> Sα | β

Здесь возникают три случая:

1. Если FIRST(β) ≠ {ε} то:

       FIRST(β) ⊆ FIRST(S)

   =>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

   что противоречит правилу (1) определения.

2. Если FIRST(β) = {ε} то:

   2.1. Если ε ∈ FIRST(α) то:

   ε ∈ FIRST(Sα)

   что противоречит правилу (3) определения.

   2.2. Если ε ∉ FIRST(α) то:

       FIRST(α) ⊆ FIRST(S) (потому что β =>* ε)

   =>  FIRST(α) ⊆ FIRST(Sα) ........ (I)

   мы также знаем, что:

   FIRST(α) ⊆ FOLLOW(S) ........ (II)

   по (I) и (II) имеем:

   FIRST(Sα) ∩ FOLLOW(S) ≠ Ø

   а поскольку β =>* ε, это противоречит правилу (2) определения.

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

Предложение 3. Неоднозначная грамматика не является LL(1).

Доказательство:

Хотя приведенные выше доказательства принадлежат мне, это не мое, это Kevin A. Naudé который я получил из его ответа, ссылка на который приведена ниже:

https://stackoverflow.com/a/18969767/6275103

Ответ на эти вопросы (и они справедливы для LL(k) для любого конечного k) связан с тем, как стек синтаксического анализа работает в синтаксическом анализаторе LL.

В точке, где один находится в начале нетерминала в грамматике, синтаксический анализатор должен определить, просматривая вперед только k (1 в LL(1)) токенов case, прежде чем решить, следует ли помещать в стек конкретное правило или для разбора текста по другим правилам. Итак, давайте рассмотрим каждый из этих случаев и посмотрим, как это повлияет на это решение.

1. Лево-рекурсивный. Имеются два леворекурсивных случая.

   а. В левой рекурсии нет токенов после рекурсии. Правило что-то вроде:

бессрочный: бессрочный;

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

b. The left-recursion has tokens in it after the recursion.  A rules something like:

бессрочный: бессрочный «X»;

В этом правиле вам нужно поместить в стек несрочные правила на столько X, сколько следует за нетерминальными. Вы не можете определить, сколько X имеется, имея только k токенов просмотра вперед. Если вы угадаете и угадаете слишком мало, у вас останутся X, и для любого предположения в языке будет случай с большим количеством X токенов. Если вы угадали, и вы угадали слишком много, в стеке окажутся внешние нетерминальные правила. Вы не можете их удалить. В любом случае вы просто не правы.

2. Недетерминированный. Недетерминированная грамматика имеет те же характеристики, что и леворекурсивная. Это не детерминировано, следует ли вам нажимать или нет. Языки-палиндромы являются типичными недетерминированными примерами, но не единственными. В языке палиндрома вы не знаете, следует ли вам поместить в стек другой нетерминал или использовать токен, который вы видите, чтобы помочь вам вернуться обратно в стек. Если вы сделаете неправильный выбор, вы снова неправильно проанализируете ввод.

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

Теперь, если вы посмотрите на эти случаи, вы увидите, что если бы вы могли каким-то образом одновременно помещать и не помещать нетерминал в стек, вы могли бы анализировать ввод с помощью грамматики. И, в неоднозначном случае, создайте набор синтаксических анализов, соответствующих входным данным. Есть методы, которые делают это, я полагаю, что они считаются GLL (обобщенный LL) — эквивалентный метод с генератором синтаксического анализатора LR называется GLR. Полученный результат часто называют «лесом синтаксического анализа» (или иногда dag синтаксического анализа, ориентированным ациклическим графом).

[Примечание: я впервые увидел этот вопрос на Quora, и этот ответ скопирован оттуда.]