ANALYSE SYNTAXIQUE DESCENDANTE
- Pour vérifier qu'on a un program, on décide la production
de la grammaire utilisée pour remplacer program dans la dérivation
et on cherche les composants dans le bon ordre
- quand le composant souhaité est un terminal, on vérifie
que c'est effectivement le prochain token (et on l'avale)
- quand on a fini de vérifier la partie droite de la production
on revient en arrière
- Nécessite une structure de données pour toutes les vérifications
en cours
- Accepte si production initiale vérifiée à la
fin des entrées
UN ``ALGORITHME'' NONDETERMINISTE
- Pour "décider" la production utilisée, on devine
- Echec si le bon token n'est pas trouvé quand cherché
- Utiliser une pile pour les vérifications en cours
DESCENTE RECURSIVE
- méthode utilisée souvent pour produire un analyseur
en peu de temps (mais pas forcément très efficace)
- Une fonction pour chaque lettre auxiliaire (fonctions mutuellement
récursives)
- Une fonction lit une partie du program générée
de sa lettre et renvoie reussi (ou renvoie echec)
- Regarde un (ou quelques) tokens pour décider la production
utilisée
- Utilise la pile de son langage comme structure de données
L'ALGORITHME LL(1)
- Une version non-récursive de descente récursive
- Utilise une pile explicite des productions en cours d'être vérifées
c-à-d les lettres qu'il doit encore trouver pour achever l'analyse
- Décide l'action en fonction de la tête de la pile et
le prochain token
- Action peut être: lire un token et l'enlever de la pile,
- enlever la tête de la pile et rajouter k symboles (k > =0)
- erreur
- LL(1) parce que: lecture Gauche à droite, trouve une dérivation
Gauche, regarde 1 token pour prendre sa décision
LES TABLEAUX ET LEUR CONSTRUCTION
- Le choix d'action peut être dirigé par un tableau M[,]
avec une action pour chaque paire (lettre auxiliaire de la grammaire, token)
- déterminé par deux fonctions calculées préalablement:
Premier(X) tous les tokens qui peuvent être le premier d'un mot dérivé
de X, Suivre(X) tous les tokens qui peuvent suivre X dans un programme de
la grammaire
(et si le mot vide peut être dérivé de X, Premier(X)
contient aussi tout Suivre(X) et Suivre(X) contient aussi e
- dans la suite X::=a est une production:
- si a est dans Premier(a), M[X,a] contient
X:: = a
- si e est dans Premier(a) et b est dans Suivre(X), M[X,b] contient X:: = a
- Une case vide représente l'action Erreur
- Une case avec plus d'une action veut dire que l'algorithme n'est pas
valable pour cette grammaire (sauf un cas ...)
- X:: = a comme action veut dire enlever
X de la pile et ajouter les lettres de a (en ordre
inversé)
LES CONDITIONS POUR QU'UNE
GRAMMAIRE SOIT LL(1)
On peut décider en regardant le prochain token quelle production
a été utilisée pour remplacer toute lettre auxiliaire
X
- Si 2 productions X::=a et X::=b, a et b ne peuvent pas donner deux mots avec la même
première lettre
- et au plus un de a et b donne e
- et si b donne e,
a ne peut pas donner un mot qui commence avec
une lettre de Suivre(X).
RECURSION A GAUCHE
- Une production du type X:: = Xa
- Forcément il y a une autre production X:: = b
- Et donc, la grammaire n'est pas LL(1)
- Techniques pour supprimer cette récursion à gauche peuvent
rendre la grammaire complexe et obscure
GRAMMAIRES INTRINSEQUEMENT
NON LL(1)
Quelques langages ne possèdent pas de grammaires LL(1)
Par exemple le langage des instructions
if then else et if then.
L'ALGORITHME D'EARLEY
Valable pour toute grammaire
- Essayer toutes les analyses possibles en parallèle!
- Pour chaque position i dans le programme, construire un ensemble Si
d'états s; un état consiste en une production de la
grammaire avec un point . ajouté quelque part dans le mot
à droite, et un indicateur de l'origine.
- Par exemple: X:: = AB.CD (5) veut dire: nous cherchons
un X de la forme ABCD; nous avons commencé cette recherche à
la position 5 et trouvé déjà AB entre position 5 et
la position actuelle i.
- Prévision: si lettre auxiliaire après le point (C dans
l'exemple), ajouter à Si
C::=.a (i) pour chaque production
C::=a
- Lecture: Si la lettre après le point est un terminal (ex. Y::
= P.qR), et le prochain symbole du programme (symbole i+1) est cette lettre
(q), ajouter cet état à Si+1 mais avec le point
bougé à droite (Y:: = Pq.R) et la même origine
- Achever: si Si a un état avec le point à
l'extremité droite, on a trouvé le mot souhaité; si
l'origine de cet état était j et la production était
Y::=a, chercher dans Sj tous les états
avec Y après le point; les rajouter à Si mais avec
le point après le Y.
- Continuer tant que possible
TEMPS DE CALCUL
- L'algorithme a l'air d'être compliqué
- utilise les origines pour construire un arbre d'analyses possibles
- Mais: le nombre total de tous les états est majoré par
(nombre de positions dans les productions) ×
(n+1)2 pour un programme de longueur n.
- Pour le mêmes raisons que l'algorithme de programmation dynamique,
le temps est O(n3)
- et O(n2) pour les grammaires non-ambigues
- probablement meilleur que l'algorithme de programmation dynamique,
parce qu'il ne cherche que les les analyses de sous-mots qui pourraient être
utiles donné le contexte gauche
- sans avoir à modifier la grammaire de départ
File translated from TEX by
TTH,
version 3.05.
On 7 Feb 2005, 16:05.