ANALYSE SYNTAXIQUE ASCENDANTE
- Construire l'arbre syntaxique à partir des feuilles
- Opération des base est réduction: si X-->
ABC est une production de la grammaire et on a déjà trouvé
ABC, on ajoute X comme père des sommets
A B C.
- les A B C sont soit des tokens (feuilles), soit les résultats
d'autres réductions.
- Plusieurs algorithmes selon les méthodes utilisées pour
savoir quelles réductions il faut effectuer.
LA PILE THEORIQUE
- contient des symboles de la grammaire:
terminaux lus du programme (ou l'analyse lexicale), ou auxiliaires construits
par des réductions
- une réduction supprime la partie droite de sa production
- quand un terminal est lu, il est ajouté à la pile (décalage)
(mais peut être imédiatement supprimé par une réduction)
- cette pile théorique est utile pour comprendre les algorithmes
mais nous allons voir qu'elle n'est pas, en fait, stockée
LES ALGORITHMES LR
- Ces algorithmes s'appellent LR parce qu'ils lisent toujours
le programme de gauche à droit (L) mais ils réproduisent
une dérivation droite (R)
- Ils utilisent toujours le contenu de la pile pour éviter de
faire des réductions inutiles; seules les réductions sont à
considérer qui donnent sur la pile une préfixe d'une forme
dérivée par la grammaire
- Mais comment décider ça efficacement?
UN AGORITHME NONDETERMINISTE
POUR DECIDER
QUELLES REDUCTIONS SONT POSSIBLES
- Lire la pile du début jusqu'à la tête
- Garder un état possible de la dérivation:
un item: une production avec un point
- D'abord une production de l'axiome de la grammaire (avec le point
à gauche)
- action possible: X-->a.Ab avec A prochain élément de
la pile, avancez à X-->aA.b
- action possible: X-->a.Ab avec A auxiliaire, changez à A-->.g pour une production A-->g
L'ALGORITHME LR(0):
LA VRAIE PILE
- L'``algorithme'' est un automate nondéterministe
- Déterminiser le!
- Ensuite stocker (dans une pile) les états de l'automate déterministe
et la première pile n'est plus utile; supprimer la!
- Ca donne l'algorithme LR(0); une grammaire pour laquelle ça
marche est LR(0)
- Echec si deux réductions ou une réduction et un décalage
possibles dans le même état
REGARDER UN CARACTERE PLUS
LOIN
LR(1)
- LR(0) est déjà un algorithme utile mais échec
reste possible
- Essayer de supprimer les conflits par regarder le caractère
d'après
- calcul des ensembles de prévision pour
l'automate nondéterministe
- Algorithme applicable à beaucoup plus de grammaires
- Mais maintenant la taille de l'automate
déterministe peut être trop grande
REDUIRE LA TAILLE DES TABLEAUX
SLR(1)
- Premier essai de garder la taille de l'automate LR(0) mais incorporer
l'utilité des ensembles de prévision
- Pour chaque production X-->a
utiliser
l'ensemble Suivre(X)
- Déjà amélioration par rapport à LR(0)
REDUIRE LA TAILLE DES TABLEAUX
LALR(1)
- Meilleure idée: calculer les ensembles pour l'automate déterminisé
- équivaut à amalgamer des états de l'automate
LR(1) qui ont le même ensemble d'items; avec union des prévisions
- Même taille que LR(0) mais prévisions plus fines que
SLR(1)
- Algorithme performant utilisé en pratique.
File translated from TEX by
TTH,
version 3.05.
On 15 Feb 2005, 09:39.