Analyseur SLR
En informatique, un analyseur SLR ou LR simple est un analyseur LR avec une petite table de données et un algorithme d'analyse relativement simple.
Description[modifier | modifier le code]
Comme d'autres types d'analyseurs LR(1), un analyseur SLR est assez efficace pour trouver l'unique analyse ascendante correcte en un seul balayage de gauche à droite sur le flux d'entrée, sans anticipation ni retour en arrière. L'analyseur syntaxique est engendré algorithmiquement à partir d'une grammaire formelle pour le langage.
L'analyseur SLR et les méthodes plus générales analyseur LALR et analyseur LR canoniques ont des méthodes identiques et des tableaux similaires au moment de l'analyse syntaxique ; ils ne diffèrent que par les algorithmes d'analyse de la grammaire mathématique utilisés par l'outil de génération de l'analyseur. Les générateurs SLR et LALR créent des tables de taille identique et des états d'analyseur identiques. Les générateurs SLR acceptent moins de grammaires que les générateurs LALR comme yacc et Bison. De nombreux langages informatiques ne s'adaptent pas facilement tels quels aux restrictions de SLR. La transformation de la grammaire naturelle du langage en grammaire SLR nécessite davantage d'adaptations grammaticales. C'est pourquoi les générateurs LALR sont plus largement utilisés que les générateurs SLR, bien qu'il s'agisse d'outils un peu plus compliqués.
SLR et LALR ont tous deux été développés par Frank DeRemer[1] comme les premières utilisations pratiques de la théorie de l'analyseur LR de Donald Knuth. Les tables créées pour les grammaires réelles par les méthodes LR complètes sont bien plus grandes.
Ensembles d'anticipation[modifier | modifier le code]
La différences entre SLR et LALR est la façon ils prennent tous deux des décisions de shift-reduce. Les générateurs calculent les ensembles d'anticipation (lookahead) de symboles d'entrée qui susceptible de suivre, chaque fois qu'une règle de production est trouvée et réduite.
Les générateurs SLR calculent ce lookahead par une méthode d'approximation facile basée directement sur la grammaire, en ignorant les détails des états et des transitions des analyseurs. Cette méthode ne tient pas compte du contexte particulier de l'état actuel de l'analyseur. Si un certain symbole non terminal S est utilisé à plusieurs endroits dans la grammaire, SLR traite ces endroits de la même manière plutôt que de les traiter séparément. Le générateur SLR calcule l'ensemble Follow(S), de tous les symboles terminaux qui peuvent suivre immédiatement une occurrence de S. Dans la table d'analyse, chaque réduction à S utilise Follow(S) comme son ensemble d'anticipation LR(1). De tels ensembles d'anticipation sont également utilisés par les générateurs pour les analyseurs descendants LL. Une grammaire qui n'a pas de conflits shift/reduce ou reduce/reduce lorsqu'elle utilise des ensembles Follow est appelée une grammaire SLR.
Les générateurs LALR en revanche calculent les ensembles d'anticipation par une méthode plus précise basée sur l'exploration du graphe des états de l'analyseur et de leurs transitions. Cette méthode tient compte du contexte particulier de l'état actuel de l'analyseur. Elle adapte le traitement de chaque occurrence grammaticale d'un non-terminal S. L'article Analyse LALR donne plus de détails sur ce calcul. Les ensembles de lookahead calculés par les générateurs LALR sont un sous-ensemble des ensembles approximatifs calculés par les générateurs SLR. Une grammaire peut avoir des conflits de table lorsqu'elle utilise des ensembles de Follow SLR, mais être sans conflit lorsqu'elle utilise des ensembles de Follow LALR.
Exemple[modifier | modifier le code]
Une grammaire qui peut être analysée par un analyseur SLR mais pas par un analyseur LR(0) est la suivante :
- (0) S → E
- (1) E → 1 E
- (2) E → 1
La construction d'une table d'action et de goto pour l'analyse LR(0) donne les items et tables suivants :
- Ensemble d'items 0
- S → • E
- + E → • 1 E
- + E → • 1
- Ensemble d'items 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Ensemble d'items 2
- S → E •
- Ensemble d'items 3
- E → 1 E •
Les tables d'action et de goto sont:
action goto état 1 $ E 0 s1 2 1 s1/r2 r2 3 2 acc 3 r1 r1
On observe qu'il y a un conflit shift-reduce pour l'état 1 et le symbole terminal '1' (souligné en rouge). Ce conflit apparaît parce que lors de la création de la table d'actions pour un analyseur, les action reduce sont insérées ligne par ligne. En utilisant plutôt un ensemble Follow, des actions peuvent être ajoutées plus finement. L'ensemble Follow pour cette grammaire est :
Symbole S E 1 Follow $ $ 1,$
Une réduction ne doit être ajoutée à une colonne d'action particulière que si cette action se trouve dans l'ensemble de Follow associé à cette réduction. Le résultat est une table d'action sans conflits :
action goto état 1 $ E 0 s1 2 1 s1 r2 3 2 acc 3 r1
Notes et références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Simple LR parser » (voir la liste des auteurs).
- Franklin L. DeRemer, « Simple LR(k) grammars », Communications of the ACM, vol. 14, no 7, , p. 453–460 (ISSN 0001-0782, DOI 10.1145/362619.362625).
Bibliographie[modifier | modifier le code]
- Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman (trad. Philippe Deschamp, Bernard Lorho, Benoît Sagot et François Thomasset), Compilateurs : principes, techniques et outils, France, Pearson Éducation, , 2e éd., 923 p. (ISBN 978-2-7440-7037-2), Section 4.6 : Introduction to LR parsing : Simple LR. — « Dragon book »
- Romain Legendre et François Schwarzentruber, Compilation : analyse lexicale et syntaxique - Du texte à sa structure en informatique, ellipses, coll. « Références sciences », , 312 p. (ISBN 978-2-340-00366-8, présentation en ligne).
- Smaïl Aït-El-Hadj, Théorie des langages et compilation : Brefs résumés de cours et exercices corrigés, ellipses, coll. « Technosup », , 304 p. (ISBN 978-2-340-02796-1).
- Roberto Di Cosmo, « Analyse Syntaxique ascendante », Course Notes — Compilation (consulté le ).
- C.Moulin, « Théorie des langages », UTC — Université de technologie Compiègne (consulté le ).
- Analyse syntaxique ascendante — Université Lille 1
- SLR 1 parsing — JavaTPoint
