Analyse non canonique
L'analyse non canonique a une approche différente des méthodes LR
régulières pour permettre une analyse déterministe de
grammaires non LR(k) : au lieu d'explorer le contexte
droit d'une poignée à l'aide d'un automate à états finis, cette
exploration va être faite par l'automate à pile lui-même, qui
pourra de ce fait effectuer des réductions dans ce contexte
droit. Le texte d'entrée est considéré comme une seconde pile pour
l'automate, qui peut ainsi revenir sur ses pas et effectuer des
réductions qui avaient été suspendues plus tôt au cours de l'analyse.
Bibliographie
- [Col70]
- Alain Colmerauer. Total precedence relations.
Journal of the ACM, 17(1):14–30, 1970.
- [FFG04]
- Jacques Farré and José Fortes Gálvez. Bounded-connect noncanonical
discriminating-reverse parsers. Theoretical Computer
Science, 313(1):73–91, 2004.
- [Knu65]
- Donald E. Knuth.
On the translation of languages from left to right.
Information and Control, 8:607-639, 1965.
- [SW76]
- Thomas G. Szymanski and John H. Williams. Noncanonical extensions
of bottom-up parsing techniques. SIAM Journal of
Computing, 5(2):231–250, 1976.
- [Tai79]
- Kuo-Chung Tai. Noncanonical SLR(1)
grammars. ACM Transactions on Programming Languages
and Systems (TOPLAS), 1(2):295–320, 1979.
- [Wil72]
- John H. Williams. Bounded context parsable
grammars. Technical Report 72-127, Department of Computer
Science, Cornell University, Ithaca, New York, 1972.