Quelle est la définition précise d'un ensemble de lookahead?

Question

Je toying autour avec des compilateurs d'écriture et d'apprentissage sur la théorie derrière l'analyse syntaxique. J'ai trouvé que même si c'est un concept clé pour comprendre les algorithmes de reconnaissance, les informations à ce sujet sur le net sont assez pauvres. Il semble que StackOverflow est dans une position unique pour résoudre ce problème.

Answer 1

Les ensembles de lookahead pour une grammaire est définie en termes d'ensembles de lookahead pour chacun de ses non-terminaux, qui à leur tour dépendent de l'ensemble d'anticipation pour chaque production. La détermination des ensembles lookahead peut nous aider à déterminer si une grammaire est LL (1), et si elle est, quelles sont les informations dont nous avons besoin pour construire un analyseur récursif-descente pour elle.

Définition:LOOKAHEAD (X -> α) et 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 -> γ) 

où premier (α) est l'ensemble des terminaux α peut commencer, FOLLOW (X) est l'ensemble des terminaux qui peuvent venir après un X n'importe où dans la grammaire, et NULLABLE (α) est de savoir si α peut dériver une séquence vide la présence de terminaux (notée ε). Les définitions suivantes sont tirées du livre gratuit de Torben Mogensen, Basics of Compiler Design. Voir ci-dessous pour un exemple.

Définition: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. 

Définition:premier (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. 

Définition:SUIVI (X):

Un symbole terminal A est en SUIVI (X) si et seulement s'il y a une dérivation à partir du symbole de départ S de la grammaire de telle sorte que S ⇒ aX Aß, où α et β sont (éventuellement vide) des séquences de symboles de grammaire.

Intuition:FOLLOW (X):

Regardez où X se produit dans la grammaire. Tous les terminaux qui pourraient suivre il (directement ou par un niveau de récursivité) est en FOLLOW (X). De plus, si X se produit à la fin d'une production (par exemple A -> foo X), ou est suivi par quelque chose d'autre qui peut réduire à e (par exemple A -> foo X B et B -> ε), alors tout ce que A peut être suivie, X peut également être suivi par (par exemple FOLLOW(A) ⊆ FOLLOW(X)).

Voir la méthode de détermination FOLLOW (X) dans le livre de Torben et une démonstration juste au-dessous.

Un exemple:

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

D'abord, NULLABLE et PREMIER et sont déterminés:

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(*) = {+, *} 

Avant SUIVEZ est déterminé, la production E' -> E $ est ajouté, où $ est considéré comme le "non-fin" Terminal. Ensuite FOLLOW est déterminé:

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). 

La résolution de ces contraintes (pourrait aussi être atteint par itération point fixe),

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

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

maintenant LOOKAHEAD pour chaque production peut être déterminée:

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 

Enfin, LOOKAHEAD fo r chaque non-terminal peut être déterminée:

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) = {+, *} 

Par cette connaissance, nous pouvons déterminer que cette grammaire n'est pas LL (1) parce que ses non-terminaux ont des ensembles lookahead qui se chevauchent. (Par exemple, nous ne pouvons pas créer un programme qui lit un symbole à la fois et décide sans ambiguïté quelle production utiliser.)