Linke Faktorisierung einer Grammatik in LL(1)

Question

Ich habe eine Hausaufgabe, bei der ich eine Grammatik in LL(1) umwandeln muss.Ich habe die Linksrekursion bereits entfernt, habe aber Probleme beim Linksfaktorisieren.Alle Beispiele, die ich gefunden habe, sind einfach und sehen in etwa so aus:

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

Ich verstehe das.Allerdings sieht meine Grammatik eher so aus:

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

Ich bin mir nicht sicher, wie ich das einfachere Beispiel darauf anwenden soll.Ich versuche es seit mindestens ein paar Stunden und habe den Überblick über all die Dinge verloren, die ich versucht habe.Im Allgemeinen sahen meine Versuche ungefähr so ​​aus:

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

Und ich versuche dann, die E-Regeln in solche umzuwandeln, die nur eine Produktion haben, die mit + oder - beginnt:

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

Und dann...

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

Und so weiter.Aber am Ende habe ich immer wieder eine Menge zusätzlicher Nichtterminals und einige sehr lange Produktionen/Produktionsketten, ohne dass ich sie tatsächlich linksfaktorisiert habe.Ich bin mir nicht sicher, wie ich das angehen soll – ich kann es scheinbar nicht beseitigen manche Nichtterminal mit mehreren Produktionen, die mit einem + und einem - beginnen.

Answer 1

Werfen wir einen Blick auf Ihre Grammatik:

$ qquad begin {align} x & to ae Mid ixe mid (x) e e & bis IE Mid Bxe Mid varepsilon i & to text {++} Mid text {-} b & to text {+} mid text {-} mid varepsilon end {Align} $

Beachten Sie, dass $X$ keine Linksfaktorisierung benötigt:Alle Regeln haben disjunkte ERSTE Mengen¹.Wenn Sie dies deutlich machen möchten, können Sie $I$ weglassen und einbinden:

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

Ebenso können wir $B$ einbinden:

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

Jetzt sehen wir, dass wir tatsächlich eine Linksfaktorisierung für $E$ durchführen müssen:wir haben offensichtliche Konflikte und wir bekommen zusätzliche Konflikte über $XE$.Also lasst uns $X$ einmal bei $XE$ einbinden:

$ qquad begin {align} x & to ae mid text {++} xe mid text {-} xe mid (x) e e & bis 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} $

Und jetzt können wir den Linksfaktor genauso einfach wie in Ihrem Beispiel durchführen:

$ 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 to Text {-} e Mid Xe Mid Text {-} xee end {align} $

Mittlerweile sehen wir, dass wir nicht weiterkommen:Indem wir $ ext{+}$ oder $ ext{-}$ aus den Alternativen herausrechnen, graben wir ein weiteres $X$ aus, das wiederum sowohl $ ext{+}$ als auch $ ext{-}$ enthält Erstes Set.

Werfen wir also einen Blick auf Ihre Sprache.Über

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

Und

$\qquad \displaystyle X ightarrow aE ightarrow^* aI^n E ightarrow aI^nIE$

du hast beliebig lang Präfixe der Form $+^+$ welche anders enden, semantisch:Ein LL (1) -Parser kann nicht entscheiden, ob ein gegebenes (nächstes) $ text {+} $ zu a gehört Paar – was bedeuten würde, die Alternative $IE$ zu wählen – oder kommt allein – was bedeuten würde, $BXE$ zu wählen.

Folglich sieht es nicht wie Ihres aus Sprache kann ausgedrückt werden durch beliebig LL(1)-Grammatik, daher ist der Versuch, Ihre in eine solche umzuwandeln, sinnlos.

Es ist noch schlimmer:B. $BXE ightarrow BIXEE ightarrow^* BI^n X E^n E$, können Sie sich nicht für die Auswahl von $BXE$ mit entscheiden beliebig endlicher Ausblick.Dies ist kein formaler Beweis, aber es deutet stark darauf hin, dass Ihre Sprache nicht einmal LL ist.

Wenn Sie darüber nachdenken, was Sie tun – die polnische Notation mit unären Operatoren zu mischen – ist es nicht sehr überraschend, dass das Parsen schwierig sein sollte.Grundsätzlich muss von links gezählt werden Und von rechts, um auch nur ein einzelnes $B$-$ ext{+}$ in einer langen Kette von $ ext{+}$ zu identifizieren.Wenn ich an mehrere $B$-$ ext{+}$ in einer Kette denke, bin ich mir nicht einmal sicher, in welcher Sprache (bei zwei semantisch unterschiedlich aber syntaktisch gleich $ ext{+}$) überhaupt deterministisch (ohne Backtracking) geparst werden können.

---

1. Das wären die Sätze von Terminals, die bei Ableitungen einer Nicht-Terminal-/Regelalternative an erster Stelle stehen können.