Левая грамматика в LL (1)

Question

У меня есть домашнее задание, где мне нужно преобразовать грамматику в LL (1). Я уже удалил левую рекурсию, но у меня возникли проблемы с выполнением левой части. Все примеры, которые я нашел, просты и выглядят примерно так:

A -> aX | aY
становится:
A -> aZ
Z -> X | Y

Я это понимаю. Однако моя грамматика больше похожа на это:

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

Я не уверен, как применить более простой пример к этому. Я пытался по крайней мере пару часов, и я потерял след всех вещей, которые я пробовал. Как правило, мои попытки выглядели примерно так:

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

И затем я пытаюсь преобразовать правила E в те, которые имеют только одну производство, начиная с + или::

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

А потом...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

И так далее. Но я постоянно получаю много дополнительных непонмеров и некоторых очень длинных постановок / цепочек производства, не имея его левой части. Я не уверен, как подходить к этому - я не могу устранить немного Непосмертный, имеющий несколько постановки, начиная с A + и с A -.

Answer 1

Давайте посмотрим на вашу грамматику:

$ qquad begin {align} x & to ae mid ixe mid (x) e e & to ie mid bxe mid varepsilon i & to text {++} mid text {-} b & to text {+} mid text {-} mid varepsilon end {align} $

Обратите внимание, что $ x $ не нуждается в левой части: все правила имеют непересекающиеся первые наборы. Если вы хотите сделать это очевидным, вы можете сбросить $ i $ и встроить это:

$ qquad begin {align} x & to ae mid text {++} xe mid text {-} xe mid (x) e e & to text {++} e mid text {-} e mid bxe mid varepsilon b & to text {+} mid text {-} mid varepsilon end {align} $

Точно так же мы можем внедрить $ b $:

$ qquad begin {align} x & to ae mid text {++} xe mid text {-} xe mid (x) e e & to text {++} e mid text {-} e mid text {+} xe mid text {-} xe mid xe mid varepsilon end {align} $

Теперь мы видим, что нам на самом деле нужно сделать левый фактор на $ e $: у нас есть очевидные конфликты, и мы получаем дополнительные конфликты через $ Xe $. Итак, давайте встроем $ x $ один раз в $ Xe $:

$ qquad begin {align} x & to ae mid text {++} xe mid text {-} xe mid (x) e e & to text {++} e mid text {-} e mid text {+} xe mid text {-} xe mid aee mid text {++} xee mid text {-} xee mid (x ) Ee mid varepsilon end {align} $

И теперь мы можем так же легко налево, как в вашем примере:

$ qquad begin {align} x & to ae mid text {++} xe mid text {-} xe mid (x) e e & to text {+} p mid text {-} m mid aee mid (x) ee mid varepsilon p & to text {+} e mid xe mid text {+} xee m & to Text {-} e mid xe mid text {-} xee end {align} $

К настоящему времени мы видим, что мы никуда не добираемся: с учетом $ text {+} $ или $ text {-} $ из альтернатив, мы выкапываем еще одну $ x $, которая снова имеет оба text {+ } $ и $ text {-} $ в его первом наборе.

Итак, давайте посмотрим на ваш язык. С помощью

$ qquad displaystyle x rightarrow ae rightarrow^* ai^n e rightarrow ai^nbxe $

а также

$ qquad displaystyle x rightarrow ae rightarrow^* ai^n e rightarrow ai^nie $

у вас есть произвольно длинный Префиксы формы $+^+$, которая заканчиваться по -другому, Семантическая поводка: анализатор ll (1) не может решить, принадлежит ли какой-либо заданный (следующий) $ text {+} $ пара - Это означало бы выбор альтернативного $ IE $- или приходит в одиночку- что означало бы выбор $ bxe $.

В результате это не похоже на ваше язык может быть выражен Любые LL (1) Грамматика, поэтому попытка преобразовать свою в одну бесполезно.

Это еще хуже: как $ bxe rightarrow bixee rightarrow^* bi^n xe^n e $, вы не можете решить выбрать $ bxe $ с Любые Конечный взгляд. Это не формальное доказательство, но он настоятельно предполагает, что ваш язык даже не является LL.

Если вы подумаете о том, что делаете - смешивая польские нотации с неарию операторов - не очень удивительно, что диапазон должен быть трудным. По сути, вы должны сосчитать слева а также Из права идентифицировать даже единый $ b $-$ text {+} $ в длинной цепочке $ text {+} $. Если я думаю о нескольких $ b $-$ text {+} $ в цепочке, я даже не уверен язык (с двумя Семантически отличается но синтаксически равные $ text {+} $) могут быть определены детерминистически (без возврата) вообще.

---

1. Это были бы наборы терминалов, которые могут на первом месте в производстве альтернативы, не являющейся терминалом/правилом.