Analyse LALR
La méthode d'analyse LR
produit les automates à pile les plus puissants pour une analyse
déterministe de gauche à droite. Que demander de plus ? Le
problème, insurmontable à l'époque où LR a été mis au point, et
encore assez délicat de nos jours, est la taille des automates
produits : celle-ci augmente exponentiellement quand le
longueur k de la fenêtre augmente.
L'idée alors avancée est de dissocier le calcul des états de
l'automate et celui de la fenêtre : étant donné un automate à
pile LR(0), on calcule les ensembles de fenêtres possibles
modulo l'équivalence LR(0) pour tenter de déterminiser
l'automate. Dans l'immense majorité des cas, cette approximation
est suffisante pour obtenir un automate à pile LALR(k)
déterministe.
Bibliographie
- [And72]
- T. Anderson. Syntactic Analysis of LR(k)
Languages, PhD thesis, Department of Computing Science,
University of Newcastle upon Tyne, 1972.
- [DeR69]
- Franklin Lewis DeRemer. Practical Translators for
LR(k) Languages, PhD thesis, Massachusetts Institute
of Technology, Cambridge, Massachusetts, 1969.
- [DP82]
- Frank DeRemer and Thomas Pennello. Efficient computation of
LALR(1) look-ahead sets. ACM Transactions on
Programming Languages and Systems (TOPLAS), 4(4):615–649,
1982.
- [KM81]
- Bent Bruun Kristensen and Ole Lehrmann Madsen. Methods for computing
LALR(k) lookahead. ACM Transactions on
Programming Languages and Systems (TOPLAS), 3(1):60–82,
1981.
- [Kor69]
- A. J. Korenjak. A practical method for
constructing LR(k) processors. Communications of
the ACM, 12(11):613–623, 1969.