Principe de l'analyse itérative -- LL(1)
Algorithme utilisé:
- un pointeur sur la chaine de tokens (la chaine est terminée par
$) - une pile contenant des non-terminaux et des terminaux
- une table dont
- chaque ligne correspond à un non-terminal
- chaque colonne identifie un terminal. Intuitivement, l'élément T[X,a] contient la règles à utiliser lorsque X est au sommet de la pile et
aest l'élément courant de la chaine.
Initialement, pointeur sur premier élément de la chaine et la pile contient $ et S (S se trouve au sommet de la pile).
A chaque itération, on examine l'élément X au somment de la pile et l'élément courant de la chaine:
- si X est un terminal
- si X==
a==$alors terminer avec succès - si X==
a!=$alors on dépile X et on avance le pointeur - sinon terminer avec erreur
- si X est un non-terminal
- si T[X,
a] = {X→ y1y2…yn} alors on dépile X est on empile yn…y2y1. - si T[X,
a] = \emptyset alors terminer avec erreur
Exemple: arithmétique dérécursivée G0' obtenu en supprimant la récursivité de G0:
| E → TE' |
| E' → +TE' | e |
| T → FT' |
| T' → *FT' | e |
| F → (E) | id |
Une Table d'Analyse pour Cette Grammaire G0'
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| E | E→TE' | E→TE' | ||||
| E' | E'→+TE' | E'→e | E'→e | |||
| T | T→FT' | T→FT' | ||||
| T' | T'→e | T'→*FT' | T'→e | T'→e | ||
| F | F→id | F→(E) |
Exemple : déroulons l'algorithme avec cette table pour la chaine id + id * id :
| Pile | Chaine | Remarques |
|---|---|---|
| $ E | id + id * id $ | Démarrage |
| $ E' T | id + id * id $ | Règle E→TE' empilé |
| $ E' T' F | id + id * id $ | Règle T→FT' empilé |
| $ E' T' id | id + id * id $ | Règle F→id empilé |
| $ E' T' | + id * id $ | traitement du terminal, passage au token suivant |
| $ E' | + id * id $ | règle T' → e |
| $ E' T + | + id * id $ | règle E' → +TE' empilé |
| $ E' T | id * id $ | traitement du terminal +, passage au token suivant |
| $ E' T' F | id * id $ | règle T' → FT' |
| $ E' T' id | id * id $ | règle F→id |
| $ E' T' | * id $ | traitement du terminal id, passage au token suivant |
| $ E' T' F * | * id $ | règle T'→*FT' |
| $ E' T' F | id $ | règle F→ id |
| $ E' T' id | id $ | traitement du terminal *, passage au token suivant |
| $ E' T' | $ | règle T' → e |
| $ E' | $ | règle E' → e |
| $ | $ | terminer avec succès |
La table d'analyse peut être remplie en utilisant deux fonctions associées à la grammaire: FIRST et FOLLOW.
- Soit \alpha une chaine non-terminale ou terminale
- soit A un non-terminal
Alors, on définit:
- FIRST(\alpha) = ensemble des terminaux qui peuvent se trouver au début des chaines dérivées de \alpha.
- FOLLOW(A) = ensemble des terminaux qui peuvent se trouver juste après A dans une chaine de dérivation.
Plus formellement, pour une grammaire \left(\Sigma, V, R, S\right) où \Sigma est l'ensemble des terminaux, V l'ensemble des non-terminaux, R les règles et S l'axiome (les axiomes?)
- FIRST\left(\alpha\right) = \left\{a\in\Sigma | \exists \beta\in\left(V \cup \Sigma\underbrace{\cup \left\{\epsilon\right\}}_{si \alpha\Rightarrow^* \epsilon}\right)^* \quad \alpha\Rightarrow^* \; a\beta\right\}
- FOLLOW\left(A\right) = \left\{ a\in \Sigma | \exists \alpha, \beta\in \left(V\cup \Sigma\right)^* ,\quad S^* \Rightarrow^* \alpha A \beta \right\} et \cup \left\{$\right\} si \exists \alpha\in\left(V\cup\right)^* | S\Rightarrow^*\alpha A
Utilisation de FIRST & FOLLOW
Pour construire la table d'analyse avec FIRST et FOLLOW, l'idée est que pour toute règle de grammaire A \rightarrow \alpha, si \alpha\in FIRST(A) alors on va utiliser cette règle pour développer A par \alpha quand le token courant dans la chaine est \alpha. Une complication arrive lorsque \alpha = \epsilon ou bien \alpha \Rightarrow^* \epsilon; dans ce cas, on doit également développer A par \alpha si le token courant dans la chaine est un élément de FOLLOW(A).
Calcul des ensembles FIRST & FOLLOW
- Pour calculer FIRST(X):
- si X est un terminal, FIRST(X) = {X}
- si X est un non-terminal, pour toutes les règles de la forme X\rightarrow X_1 X_2 \ldots X_n ajouter FIRST\left(X_1 X_2 \ldots X_n\right)
- Pour calculer/construire FIRST\left(X_1 X_2 \ldots X_n\right),
- ajouter FIRST\left(X_1\right)
- si \epsilon \in FIRST\left(X_1\right) ajouter FIRST\left(X_2\right)
- si \epsilon \in FIRST\left(X_1\right)\cap FIRST\left(X_2\right) ajouter FIRST\left(X_3\right)
- …
- si \epsilon\in \cap_{i=1}^{n-1} FIRST\left(X_i\right) ajouter FIRST\left(X_n\right)
Démonstration
| FIRST(F) | ={ | (, id | } |
| FIRST(T') | ={ | *, e | } |
| FIRST(T)=FIRST(F) | ={ | (, id | } |
| FIRST(E') | ={ | +, e | } |
| FIRST(E)=FIRST(T) | ={ | (, id | } |
Pour calculer FOLLOW
- mettre
$dans FOLLOW(S) - s'il existe une règle de la forme A\rightarrow \alpha B \beta mettre FIRST\left(B\right)=\setminus \left\{\epsilon\right\} dans FOLLOW(B).
- s'il existe une règle de la forma A\rightarrow \alpha B ou bien de la forme A\rightarrow \alpha B \beta puis \beta \Rightarrow^* \epsilon mettre tout FOLLOW(A) dans FOLLOW(B).
Exemple :
- FOLLOW(E) = { $, ) }
- FOLLOW(E') = FOLLOW(E) = { $, ) }
- FOLLOW(T) = FIRST(E') \setminus \left\{\epsilon\right\} \cup FOLLOW(E)1) = { +, $, ) }
- FOLLOW(T') = FOLLOW(T) = { +, $, ) }
- FOLLOW(F) = \left(FIRST\left(T\prime\right)\setminus \left\{\epsilon\right\}\right) \cup FOLLOW(T) = { * , + , $ , ) }
Algorithme de construction de la table d'analyse
- Pour chaque règle de grammaire A \rightarrow \alpha, pour tout a \in FIRST(\alpha = \setminus \left\{\epsilon\right\}, placer cette règle dans T[A,a].
- Si \epsilon \in FIRST(\alpha ), placer cette règle dans T{A,b] pour tout b \in FOLLOW(A) .
| id | + | * | ( | ) | $ | |
| E | E→TE' | E→TE' | ||||
| E' | E'→+TE' | E'→ | E'→ | |||
| T | T→FT' | T→FT' | ||||
| T' | T'→ | T→*FT' | T'→ | T'→ | ||
| F | F→id | F→(E) |
il faudrait vérifier cette table, je ne suis pas certain de l'avoir bien notée.
N.B. Si chaque case de la table contient au plus une règle on dit la grammaire non-ambiguë. Elle est dite LL(1). Explication:
- L parce qu'on lit la chaine de gauche à droite
- L parce qu'on s'appuie sur une dérivation gauche
- (1) parce qu'on lit un token en avance.
Si une case de la table contient plusieurs règles la grammaire est ambiguë : il y a plusieurs arbres de syntaxe possibles pour certaines production de la grammaire.