Wie finde ich FIRST und FOLLOW-Sätze einer rekursiven Grammatik?

Question

Angenommen, ich habe die folgende CFG.

A -> B | Cx | EPSILON 
B -> C | yA 
C -> B | w | z 

Jetzt, wenn ich versuche,

FIRST(C) = FIRST(B) U FIRST(w) U FIRST(z) 
     = FIRST(C) U FIRST(yA) U {w, z} 

zu finden, das heißt, ich bin in einer Schleife gehen. Also nehme ich an, ich muss es in eine Form konvertieren, die sofortige Links Rekursion hat, was ich tun kann, wie folgt.

Wenn ich jetzt versuche, ERSTE Sätze zu berechnen, denke ich, dass ich es wie folgt machen kann.

FIRST(C) = FIRST(C) U FIRST(yA) U FIRST(w) U FIRST(z) 
     = { y, w, z } // I ignore FIRST(C) 
FIRST(B) = FIRST(C) U FIRST(yA) 
     = { y, w, z } 
FIRST(A) = FIRST(B) U FIRST(Cx) U FIRST(EPSILON) 
     = { y, w, z, EPSILON } 

Bin ich richtig dort?

Aber selbst wenn ich genau dort bin, stoße ich immer noch auf ein Problem, wenn ich FOLLE Sätze aus dieser Grammatik berechnen will.

FOLLOW(A) = { $ } U FOLLOW(B) U FOLLOW(C) 

Ich bekomme FOLGEN (B) von der 2. Regel und FOLGE (C) von der 3. Regel. Aber jetzt, um FOLLOW (B) zu berechnen, muss ich FOLGEN (A) (von der ersten Grammatikregel), also bin ich wieder in einer Schleife fest.

Irgendwelche Hilfe? Vielen Dank im Voraus!

Answer 1

Da FIRST und FOLLOW (normalerweise) rekursiv sind, ist es sinnvoll, sie als zu lösende Gleichungssysteme zu betrachten; Die Lösung kann unter Verwendung eines einfachen inkrementellen Algorithmus erreicht werden, der darin besteht, wiederholt alle rechten Seiten anzuwenden, bis sich während eines Zyklus kein Satz geändert hat.

wir also den FOLLOW Beziehung für die gegebene Grammatik nehmen:

A → B | Cx | ε 
B → C | yA 
C → B | w | z 

Wir direkt die Gleichungen ableiten:

FOLLOW(A) = FOLLOW(B) ∪ {$} 
FOLLOW(B) = FOLLOW(A) ∪ FOLLOW(C) 
FOLLOW(C) = FOLLOW(B) ∪ {x} 

So wir anfänglich alle Folgesätze {}, und gehen Sie .

Erste Runde:

FOLLOW(A) = {} ∪ {$} = {$} 
FOLLOW(B) = {$} ∪ {} = {$} 
FOLLOW(C) = {$} U {x} = {$,x} 

Zweite Runde:

FOLLOW(A) = {$} ∪ {$} = {$} 
FOLLOW(B) = {$} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

Dritte Runde:

FOLLOW(A) = {$,x} ∪ {$} = {$,x} 
FOLLOW(B) = {$} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

Vierte Runde:

FOLLOW(A) = {$,x} ∪ {$} = {$,x} 
FOLLOW(B) = {$,x} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

Hier stoppen wir, weil in der letzten Runde keine Änderungen vorgenommen wurden.

Dieser Algorithmus muss beendet werden, da eine endliche Anzahl von Symbolen vorhanden ist und jede Runde nur Symbole zu Schritten hinzufügen kann. Es ist nicht die effizienteste Technik, obwohl es in der Praxis in der Regel gut genug ist.