Qual è la definizione precisa di un set lookahead?

Question

Mi diverto a scrivere con i compilatori e sto imparando la teoria dietro l'analisi della sintassi. Ho scoperto che anche se è un concetto chiave per la comprensione degli algoritmi di riconoscimento, le informazioni su di esso in rete sono piuttosto scarse. Sembra che StackOverflow si trovi in ​​una posizione unica per risolvere questo problema.

Answer 1

L'impostazione lookahead per una grammatica è definita in termini di set di lookahead per ciascuno dei suoi non-terminal, che a loro volta si basano sul look lookhead impostato per ogni produzione. Determinare i set lookahead può aiutarci a determinare se una grammatica è LL (1), e se lo è, quali informazioni abbiamo bisogno per costruire un parser ricorsivo-discendente per questo.

Definizioni:LOOKAHEAD (X -> α) e LOOKAHEAD (X):

LOOKAHEAD(X -> α) = FIRST(α) U FOLLOW(X), if NULLABLE(α) 
LOOKAHEAD(X -> α) = FIRST(α), if not NULLABLE(α) 
LOOKAHEAD(X) = LOOKAHEAD(X -> α) U LOOKAHEAD(X -> β) U LOOKAHEAD(X -> γ) 

dove FIRST (α) è l'insieme di terminali che α può cominciare, FOLLOW (X) è l'insieme di terminali che possono arrivare dopo un X ovunque nella grammatica e NULLABLE (α) è se α può derivare una sequenza vuota di terminali (indicato con ε). Le seguenti definizioni sono tratte dal libro gratuito di Torben Mogensen, Basics of Compiler Design. Vedere sotto per un esempio.

Definizione:NULLABLE (X):

NULLABLE(ε) = true 
NULLABLE(x) = false, if x is a terminal 
NULLABLE(αβ) = NULLABLE(α) and NULLABLE(β) 
NULLABLE(P) = NULLABLE(α_1) or NULLABLE(α_2) or ... or NULLABLE(α_n), 
       if P is a non-terminal and the right-hand-sides 
       of all its productions are α_1, α_2, ..., α_n. 

Definizione:FIRST (X):

FIRST(ε) = Ø 
FIRST(x) = {x}, assuming x is a terminal 
FIRST(αβ) = FIRST(α) U FIRST(β), if NULLABLE(α) 
      = FIRST(α), if not NULLABLE(α) 
FIRST(P) = FIRST(α_1) U FIRST(α_2) U ... U FIRST(α_n), 
       if P is a non-terminal and the right-hand-sides 
       of all its productions are α_1, α_2, ..., α_n. 

Definizione:FOLLOW (X):

Un simbolo terminale a è in FOLLOW (X) se e solo se v'è una derivazione dal simbolo iniziale S della grammatica tale che S ⇒ αX Ap, dove α e β sono (possibilmente vuoto) sequenze di simboli grammaticali.

Intuizione:FOLLOW (X):

guardare dove X si verifica nella grammatica. Tutti i terminali che potrebbero seguono (direttamente o con qualsiasi livello di ricorsione) è in FOLLOW (X). Inoltre, se X avviene al termine di una produzione (es A -> foo X), o è seguito da qualcos'altro che può ridurre a ε (es A -> foo X B e B -> ε), allora qualsiasi Un può essere seguito da, X può anche essere seguito da (cioè FOLLOW(A) ⊆ FOLLOW(X)).

vedere il metodo di determinazione SEGUE (X) nel libro di Torben e una dimostrazione di appena sotto.

Un esempio:

E -> n A 
A -> E B 
A -> ε 
B -> + A 
B -> * A 

Innanzitutto, NULLABLE e FIRST e sono determinati:

NULLABLE(E) = NULLABLE(n A) = NULLABLE(n) ∧ NULLABLE(A) = false 
NULLABLE(A) = NULLABLE(E B) ∨ NULLABLE(ε) = true 
NULLABLE(B) = NULLABLE(+ A) ∨ NULLABLE(* A) = false 

FIRST(E) = FIRST(n A) = {n} 
FIRST(A) = FIRST(E B) U FIRST(ε) = FIRST(E) U Ø = {n} (because E is not NULLABLE) 
FIRST(B) = FIRST(+ A) U FIRST(* A) = FIRST(+) U FIRST(*) = {+, *} 

Prima SEGUIRE è determinato, si aggiunge la produzione E' -> E $, dove $ è considerato il "fine del file" non terminale. Poi SEGUITO è determinato:

FOLLOW(E): Let β = $, so add the constraint that FIRST($) = {$} ⊆ FOLLOW(E) 
      Let β = B, so add the constraint that FIRST(B) = {+, *} ⊆ FOLLOW(E) 
FOLLOW(A): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(E) ⊆ FOLLOW(A). 
      Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A). 
      Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A). 
FOLLOW(B): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(B). 
      Because NULLABLE(ε), add the constraint that FOLLOW(A) ⊆ FOLLOW(B). 

soluzione di tali vincoli (potrebbe essere ottenuta anche con iterazione di punto fisso),

{+, *, $} ⊆ FOLLOW(E) 
    FOLLOW(E) ⊆ FOLLOW(A) 
    FOLLOW(A) = FOLLOW(B) 

    FOLLOW(E) = FOLLOW(A) = FOLLOW(B) = {+, *, $}. 

Ora LOOKAHEAD per ogni produzione può essere determinato:

LOOKAHEAD(E -> n A) = FIRST(n A) = {n}  because ¬NULLABLE(n A) 
LOOKAHEAD(A -> E B) = FIRST(E B)   because ¬NULLABLE(E B) 
        = FIRST(E) = {n}  because ¬NULLABLE(E) 
LOOKAHEAD(A -> ε) = FIRST(ε) U FOLLOW(A) because NULLABLE(ε) 
        = Ø U {+, *, $} = {+, *, $} 
LOOKAHEAD(B -> + A) = FIRST(+ A)   because ¬NULLABLE(+ A) 
        = FIRST(+) = {+}  because ¬NULLABLE(+) 
LOOKAHEAD(B -> * A) = {*}     for the same reason 

Infine, LOOKAHEAD per r ogni non terminale può essere determinato:

LOOKAHEAD(E) = LOOKAHEAD(E -> n A) = {n} 
LOOKAHEAD(A) = LOOKAHEAD(A -> E B) U LOOKAHEAD(A -> ε) = {n} U {+, *, $} 
LOOKAHEAD(B) = LOOKAHEAD(B -> + A) U LOOKAHEAD(B -> * A) = {+, *} 

Con questa conoscenza possiamo stabilire che questa grammatica non è LL (1) perché i suoi non-terminali hanno insiemi lookahead sovrapposti. (Ad esempio, non possiamo creare un programma che legge un simbolo alla volta e decide inequivocabilmente quale produzione utilizzare.)