Sinistra-Factoring una grammatica in LL (1)

Question

ho un compito a casa dove ho bisogno di convertire una grammatica in LL (1). Ho già rimosso la ricorsione sinistra, ma sto avendo difficoltà a fare sinistra-factoring. Tutti gli esempi che ho trovato sono semplici, e aspetto simile a questo:

A -> aX | aY
diventa:
A -> aZ
Z -> X | Y

lo capisco. Tuttavia, il mio aspetto di grammatica più simile a questo:

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

Non sono sicuro di come applicare l'esempio più semplice di questo. Ho cercato per almeno un paio d'ore e ho perso traccia di tutte le cose che ho provato. In generale, i miei tentativi hanno guardato qualcosa di simile:

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

E poi tenta di convertire le regole E in quelle che hanno un solo produzione a partire con + o -:

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

E poi ...

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

E così via. Ma io continuo a finire con un sacco di non terminali in più, e alcune molto lunghe produzioni / catene di produzioni, senza in realtà aver lasciato-scomposto esso. Non sono sicuro di come affrontare questo - io non riesco ad eliminare alcuni non terminale avere più produzioni che iniziano con un + e con un -.

Answer 1

Diamo uno sguardo alla vostra grammatica:

$ \ qquad \ begin {align} X & \ per aE \ metà IXE \ metà (X) E \\ E & \ a IE \ metà BXE \ metà \ varepsilon \\ I & \ a \ text {} ++ \ metà \ text {-} \\ B & \ per \ text {+} \ metà \ text {-} \ mid \ varepsilon \ End {align} $

Si noti che $ X $ non ha bisogno di sinistra-factoring: tutte le regole hanno disgiunto PRIMA sets¹. Se si vuole fare questa ovvia, è possibile eliminare $ I $ e inline è:

$ \ qquad \ begin {align} X & \ per aE \ metà \ text {} ++ XE \ metà \ text {-} XE \ metà (X) E \\ E & \ per \ text {} ++ E \ metà \ text {-} E \ metà BXE \ metà \ varepsilon \\ B & \ per \ text {+} \ metà \ text {-} \ mid \ varepsilon \ End {align} $

Allo stesso modo, siamo in grado di inline $ B $:

$ \ qquad \ begin {align} X & \ per aE \ metà \ text {} ++ XE \ metà \ text {-} XE \ metà (X) E \\ E & \ per \ text {} ++ E \ metà \ text {-} E \ metà \ text {+} XE \ metà \ text {-} XE \ metà XE \ mid \ varepsilon \ End {align} $

Ora vediamo che in realtà abbiamo a che fare sinistra-factoring $ E $: abbiamo conflitti evidenti, e noi ottenere i conflitti aggiuntive tramite $ XE $. Quindi, cerchiamo di Inline $ X $ una volta a $ XE $:

$ \ qquad \ begin {align} X & \ per aE \ metà \ text {} ++ XE \ metà \ text {-} XE \ metà (X) E \\ E & \ per \ text {} ++ E \ metà \ text {-} E \ metà \ text {+} XE \ metà \ text {-} XE \ metà AEE \ metà \ text {} ++ XEE \ mid \ text {-} XEE \ metà (X) EE \ mid \ varepsilon \ End {align} $

E ora possiamo lasciato fattore facilmente come nel tuo esempio:

$ \ qquad \ begin {align} X & \ per aE \ metà \ text {} ++ XE \ metà \ text {-} XE \ metà (X) E \\ E & \ per \ text {+} P \ metà \ text {-} M \ metà AEE \ metà (X) EE \ mid \ varepsilon \\ P & \ per \ text {+} E \ metà XE \ metà \ text {+} XEE \\ M & \ per \ text {-} E \ metà XE \ metà \ text {-} XEE \ End {align} $

Per ora possiamo vedere che non stiamo andando da nessuna parte: dal factoring via $ \ text {+} $ o $ \ text {-} $ tra le alternative, abbiamo scavare un altro $ X $, che ha ancora una volta sia $ \ text {+} $ e $ \ text {-}. $ nel suo primo set

Quindi, diamo uno sguardo alla vostra lingua. Via

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * aI ^ n E \ Rightarrow aI ^ nBXE $

e

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * aI ^ n E \ Rightarrow aI ^ no $

hai arbitrariamente lungo i prefissi della forma $ + ^ + $ che fine diverso , semantico-saggio: un LL (1) parser non può decidere se un determinato (prossimo) $ \ text {+} $ appartiene ad un coppia - il che significherebbe la scelta di $ alternativa IE $ - o viene da solo -. il che significherebbe la scelta di $ BXE $

Di conseguenza, non sembra come il tuo lingua può essere espresso da qualsiasi LL (1) grammatica, in modo da cercare di convertire la vostra in uno è inutile.

E 'ancora peggio: da $ BXE \ Rightarrow BIXEE \ Rightarrow ^ * BI ^ n X E ^ n E $, non si può decidere di scegliere $ BXE $ con qualsiasi finito look-ahead. Questa non è una prova formale, ma suggerisce fortemente che la lingua non è nemmeno LL.

Se si pensa a quello che state facendo - mescolando la notazione polacca con gli operatori unari - non è molto sorprendente che l'analisi dovrebbe essere difficile. In sostanza, si deve contare da sinistra e da destra per identificare anche un solo $ B $ - $ \ text {+} $ in una lunga catena di $ \ text {+} $. Se penso di molteplici $ B $ - $ \ text {+} $ in una catena, non sono nemmeno sicuro della lingua (con due semanticamente differenti , ma sintatticamente uguale a $ \ text {+} $ ) può essere analizzato in modo deterministico (senza backtracking) a tutti.

---

1. Questo sarebbe il set di terminali che possono venire prima in derivazioni di un non terminale regola / alternative.