Konvertieren eine Grammatik in LL (1) Grammatik: einige Probleme

Question

Dies ist nicht gerade Hausaufgaben, aber es ist meine Studien im Zusammenhang:

Eine Grammatik zum Beispiel ist wie:

E -> E + E | E * E | -E | (E) | id

Nach Mehrdeutigkeit zu entfernen wird es (beginnend von der niedrigsten Priorität Operator)

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

und nach der Linksrekursion und linken Factoring (in diesem Fall nicht erforderlich) zur Entfernung der letzte LL1 Grammatik ist:

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

, die eine fehlerfreie Parsertabelle gibt, der gut arbeitet. Jetzt über das Problem nehme an, ich bin vor, die Grammatik ist wie folgt:

E -> E + E | E * E | id = E | (E) | id

Now I Ich bin nicht in der Lage, eine Parsing-Tabelle ohne Konflikte zu generieren, was bedeutet, dass meine letzte Grammatik nicht LL1 ist. Hier sind die Schritte:

nach dem Entfernen Mehrdeutigkeit:

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

und nach der Linksrekursion und linken Factoring entfernen, die Grammatik wird:

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Aber es gibt einen Konflikt in der Parser-Tabelle die ich nicht entfernen kann, was bedeutet, dass es einen Schritt gibt, den ich verpasst habe, oder dass es einen Fehler in den Schritten gibt, die ich nicht finden kann. Bitte sagen Sie mir, was ich falsch gemacht habe und wie ich das beheben kann. Ich arbeite schon lange an diesem Problem.

Answer 1

Lasst uns sagen:

E -> E+E|E*E|id=E|(E)|id 

werden wird:

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

dann können Sie mit dem Entfernen von Mehrdeutigkeit und linken Rekursion gehen und:

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

Natürlich Das Problem besteht darin, dass Sie die Priorität des angegebenen Operators verlieren.

Die Grammatik wird nicht LL (1), wenn für jede nicht terminaleN, wird es alle gemeinsamen Elemente werden inFIRST(N -> a) und FIRST(N -> b) für N -> a, N -> b verschieden Produktionen aus N.

Wie Sie sehen, würde das Hinzufügen einer Produktion N -> id= in jeden anderen Ort diese Regel brechen.

Sie können eine LL(2) Grammatik erstellen (aber das ist wahrscheinlich nicht das, was Sie wollen), die id=E Produktion an jedem Ort haben kann. (FIRST2 Sets bestehen aus 2-Element-Strings).

Auch, wenn man sich die präsentierten Grammatik ein weiteres Mal: ​​

E -> E+E|E*E|id=E|(E)|id 

Es ist eine hohe Wahrscheinlichkeit, dass der Fahrer Vorrang ich in der Lösung oben gemacht ist die richtige für reale Anwendung. Hör zu!