INTRODUCTION INTRODUCTION
APERCU
En finir avec l'analyse syntaxique
Récapitulation des algorithmes < X > LR(1)
Toujours le même principe
L'algorithme LALR(1)
Construction de l'automate LALR(1) Algorithme utile et utilisé (yacc, gag,...)
Comment le LALR(1) peut-il être différent du SLR(1)
Les items pareils de plusieurs états de l'automate LALR peuvent avoir des ensembles de prévision différents; dans l'automate SLR, le même item a partout le même ensemble de prévision; la différence peut servir à résoudre une ambigüité.
Un très petit exemple concret
du Dragon
S ® Aa | bAc | dc | bda
A ® d
Le problème pour SLR(1) vient d'un ``programme'' comme dc

LALR(1) est moins puissant que LR(1)
un exemple
S® Aa | bAc | Bc | bBa
A ® d
B ® d
est LR(1) mais pas LALR(1).

Mais LALR(1) suffit pour permettre des grammaires raisonnables pour les langages de programmation.

Complexité des algorithmes XLR(1)
Complexité Théorique de l'analyse pour une grammaire non contextuelle




File translated from TEX by TTH, version 3.05.
On 24 Jan 2003, 10:17.