Come trovare gli insiemi FIRST e FOLLOW di una grammatica ricorsiva?

Question

Supponiamo di avere il seguente CFG.

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

Ora, se cerco di trovare

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

Cioè, sto andando in un ciclo. Quindi presumo di doverlo convertire in una forma con ricorsione a sinistra immediata, che posso fare come segue.

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

Ora, se provo a calcolare i PRIMI set, penso di poterlo fare come segue.

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 } 

Sono corretto lì?

Ma anche se sono a posto, continuo a riscontrare un problema quando provo a calcolare SEGUI insiemi da questa grammatica.

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

Ottengo SEGUIRE (B) dalla seconda regola e SEGUI (C) dalla terza regola. Ma ora per calcolare FOLLOW (B), ho bisogno di SEGUIRE (A) (dalla prima regola della grammatica) quindi di nuovo sono bloccato in un ciclo.

Qualsiasi aiuto? Grazie in anticipo!

Answer 1

Poiché FIRST e FOLLOW sono (normalmente) ricorsivi, è utile considerarli come sistemi di equazioni da risolvere; la soluzione può essere ottenuta utilizzando un semplice algoritmo incrementale consistente nell'applicare ripetutamente tutti i lati della mano destra fino a quando nessun set è cambiato durante un ciclo.

Così diamo la relazione seguire per la grammatica data:

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

possiamo ricavare direttamente le equazioni:

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

Così abbiamo impostato inizialmente tutti i set successivi a {}, e procedere .

Primo turno:

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

Secondo turno:

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

Terzo turno:

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

Quarto turno:

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

Qui ci fermiamo perché non sono state apportate modifiche nell'ultimo round.

Questo algoritmo deve terminare perché esiste un numero finito di simboli e ogni round può solo aggiungere simboli ai passaggi. Non è la tecnica più efficiente, anche se in pratica è abbastanza buona.