Quelle est la différence entre les analyseurs syntaxiques LR, SLR et LALR ?

Question

Quelle est la différence réelle entre les analyseurs LR, SLR et LALR ? Je sais que SLR et LALR sont des types de parsers LR, mais quelle est la différence réelle en ce qui concerne leurs tables de parsing ?

Et comment montrer si une grammaire est LR, SLR, ou LALR ? Pour une grammaire LL, il suffit de montrer que toute cellule de la table d'analyse ne doit pas contenir plusieurs règles de production. Existe-t-il des règles similaires pour LALR, SLR, et LR ?

Par exemple, comment pouvons-nous montrer que la grammaire

S --> Aa | bAc | dc | bda
A --> d

est LALR(1) mais pas SLR(1) ?

---

EDIT (ybungalobill) : Je n'ai pas obtenu de réponse satisfaisante pour savoir quelle est la différence entre LALR et LR. Les tableaux de LALR sont donc plus petits en taille mais il ne peut reconnaître qu'un sous-ensemble de grammaires LR. Quelqu'un peut-il nous en dire plus sur la différence entre LALR et LR ? LALR(1) et LR(1) seront suffisants pour une réponse. Elles utilisent toutes deux un jeton d'anticipation et un jeton de réponse. les deux sont axés sur les tables ! En quoi sont-ils différents ?

Answer 1

Les analyseurs SLR, LALR et LR peuvent tous être mis en œuvre en utilisant exactement la même machinerie pilotée par des tables.

Fondamentalement, l'algorithme d'analyse syntaxique recueille le prochain jeton d'entrée T, et consulte l'état actuel S (et les tables de lookahead, de GOTO et de réduction associées) pour décider de ce qu'il faut faire :

• SHIFT : Si la table actuelle dit de SHIFT sur le jeton T, la paire (S,T) est poussée sur la pile d'analyse, l'état est modifié en fonction de ce que la table GOTO dit pour le jeton actuel (par exemple, GOTO(T)), un autre jeton d'entrée T' est récupéré et le processus se répète.
• REDUCE : Chaque état a 0, 1, ou plusieurs réductions possibles qui peuvent se produire dans l'état. Si l'analyseur syntaxique est LR ou LALR, le jeton est vérifié par rapport aux ensembles lookahead pour toutes les réductions valides pour l'état. Si le jeton correspond à un ensemble de lookaheads pour une réduction pour la règle de grammaire G = R1 R2 Rn, une réduction et un décalage de la pile se produisent : l'action sémantique pour G est appelée, la pile est sortie n (de Rn) fois, la paire (S,G) est poussée sur la pile, le nouvel état S' est défini comme GOTO(G), et le cycle se répète avec le même jeton T. Si l'analyseur est un analyseur SLR, il y a au plus une règle de réduction pour l'état et donc l'action de réduction peut être faite aveuglément sans chercher à savoir quelle réduction s'applique. Il est utile pour un analyseur SLR de savoir s'il existe une règle de réduction pour l'état. es une réduction ou non ; cela est facile à dire si chaque état enregistre explicitement le nombre de réductions qui lui sont associées, et ce compte est de toute façon nécessaire pour les versions L(AL)R en pratique.
• ERREUR : Si ni SHIFT ni REDUCE ne sont possibles, une erreur de syntaxe est déclarée.

Donc, s'ils utilisent tous les mêmes machines, quel est l'intérêt ?

La valeur supposée de SLR est sa simplicité d'implémentation ; il n'est pas nécessaire de parcourir les réductions possibles en vérifiant les ensembles de lookahead car il n'y en a qu'un seul, et c'est la seule action viable s'il n'y a pas de sortie SHIFT de l'état. La réduction qui s'applique peut être attachée spécifiquement à l'état, de sorte que la machine d'analyse SLR n'a pas à la chercher. Dans la pratique, les analyseurs L(AL)R gèrent un ensemble de langages beaucoup plus important, et il y a si peu de travail supplémentaire à faire que personne n'implémente SLR sauf comme un exercice académique.

La différence entre LALR et LR concerne le tableau. générateur . Les générateurs d'analyseurs LR gardent la trace de toutes les réductions possibles à partir d'états spécifiques et de leur ensemble précis de lookahead ; vous obtenez des états dans lesquels chaque réduction est associée à son ensemble exact de lookahead à partir de son contexte de gauche. Cela tend à construire des ensembles d'états plutôt grands. Les générateurs d'analyse syntaxique LALR sont disposés à combiner des états si les tables GOTO et les ensembles de lookahead pour les réductions sont compatibles et n'entrent pas en conflit ; cela produit un nombre d'états considérablement plus petit, au prix de ne pas pouvoir distinguer certaines séquences de symboles que LR peut distinguer. Ainsi, les analyseurs LR peuvent analyser un plus grand nombre de langues que les analyseurs LALR, mais ont des tables d'analyse beaucoup plus grandes. En pratique, on peut trouver des grammaires LALR qui sont suffisamment proches des langages cibles pour que la taille de la machine à états vaille la peine d'être optimisée ; les endroits où l'analyseur LR serait meilleur sont gérés par une vérification ad hoc en dehors de l'analyseur.

Donc : Les trois utilisent les mêmes machines. Le reflex est "facile" dans le sens où vous pouvez ignorer une petite partie de la machinerie, mais cela n'en vaut pas la peine. LR analyse un ensemble plus large de langues mais les tables d'état ont tendance à être assez grandes. Cela laisse LALR comme le choix pratique.

Ceci dit, il faut savoir que Analyseurs GLR peut analyser n'importe quel langage sans contexte, en utilisant des mécanismes plus compliqués. mais exactement les mêmes tableaux (y compris la version plus petite utilisée par LALR). Cela signifie que GLR est strictement plus puissant que LR, LALR et SLR ; à peu près si vous pouvez écrire une grammaire BNF standard, GLR l'analysera en fonction de celle-ci. La différence dans la machinerie est que GLR est prêt à essayer plusieurs analyses lorsqu'il y a des conflits entre la table GOTO et les ensembles lookahead. (La façon dont GLR fait cela de manière efficace est un pur génie [pas le mien] mais n'a pas sa place dans ce billet).

Pour moi, c'est un fait extrêmement utile. Je construis des analyseurs de programmes et des transformateurs de code et les analyseurs syntaxiques sont nécessaires mais "inintéressants" ; le travail intéressant est ce que vous faites avec le résultat analysé et donc l'accent est mis sur le travail de post-séparation. L'utilisation de GLR signifie que je peux construire relativement facilement des grammaires fonctionnelles, par rapport au piratage d'une grammaire pour obtenir une forme utilisable par LALR. Ceci est très important lorsqu'on essaie de traiter des langages non académiques tels que C++ ou Fortran, où vous avez littéralement besoin de milliers de règles pour bien gérer le langage entier, et vous ne voulez pas passer votre vie à essayer de modifier les règles de grammaire pour répondre aux limitations de LALR (ou même LR).

Pour citer un exemple célèbre, le C++ est considéré comme extrêmement difficile à analyser... par les personnes qui font de l'analyse LALR. Le C++ est facile à analyser en utilisant la machinerie GLR en utilisant à peu près les règles fournies à la fin du manuel de référence du C++. (J'ai précisément un tel analyseur, et il gère non seulement le C++ classique, mais aussi une variété de dialectes de fournisseurs. Ceci n'est possible en pratique que parce que nous utilisons un analyseur GLR, IMHO).

[EDIT novembre 2011 : Nous avons étendu notre analyseur pour gérer tout le C++11. GLR a rendu cela beaucoup plus facile à faire. EDIT Août 2014 : Gère maintenant tout le C++17. Rien de cassé ou d'aggravé, GLR est toujours le miaou du chat].

Answer 2

Les analyseurs syntaxiques LALR fusionnent les états similaires au sein d'une grammaire LR pour produire des tables d'états d'analyse qui ont exactement la même taille que la grammaire SLR équivalente, qui sont généralement un ordre de grandeur plus petit que les tables d'analyse LR pures. Cependant, pour les grammaires LR qui sont trop complexes pour être LALR, ces états fusionnés entraînent des conflits d'analyseurs ou produisent un analyseur qui ne reconnaît pas entièrement la grammaire LR originale.

BTW, je mentionne quelques éléments à ce sujet dans mon algorithme de table d'analyse MLR(k) ici .

Addendum

La réponse courte est que les tables d'analyse LALR sont plus petites, mais que la machinerie de l'analyseur est la même. Une grammaire LALR donnée produira des tables d'analyse beaucoup plus grandes si tous les états LR sont générés, avec beaucoup d'états redondants (quasi-identiques).

Les tables LALR sont plus petites parce que les états similaires (redondants) sont fusionnés ensemble, ce qui élimine les informations de contexte et d'anticipation que les états séparés encodent. L'avantage est que vous obtenez des tables de passement beaucoup plus petites pour la même grammaire.

L'inconvénient est que toutes les grammaires LR ne peuvent pas être codées comme des tables LALR, car les grammaires plus complexes ont des lookaheads plus compliqués, résultant en deux ou plusieurs états au lieu d'un seul état fusionné.

La principale différence réside dans le fait que l'algorithme qui produit les tables LR transporte plus d'informations entre les transitions d'un état à l'autre, alors que l'algorithme LALR ne le fait pas. Ainsi, l'algorithme LALR ne peut pas dire si un état fusionné donné doit vraiment être laissé comme deux ou plusieurs états séparés.

Answer 3

Encore une autre réponse (YAA).

Les algorithmes d'analyse syntaxique pour SLR(1), LALR(1) et LR(1) sont identiques, comme l'a dit Ira Baxter,
Cependant, les tables d'analyse syntaxique peuvent être différentes en raison de l'algorithme de génération de l'analyse syntaxique.

Un générateur d'analyseur SLR crée une machine à états LR(0) et calcule les look-aheads à partir de la grammaire (ensembles FIRST et FOLLOW). Il s'agit d'une approche simplifiée qui peut signaler des conflits qui n'existent pas réellement dans la machine à états LR(0).

Un générateur d'analyseur LALR crée une machine d'état LR(0) et calcule les look-aheads à partir de la machine d'état LR(0) (via les transitions terminales). Cette approche est correcte, mais elle signale parfois des conflits qui n'existeraient pas dans une machine d'état LR(1).

Un générateur d'analyseur syntaxique LR canonique calcule une machine d'état LR(1) et les look-aheads font déjà partie de la machine d'état LR(1). Ces tables d'analyse syntaxique peuvent être très grandes.

Un générateur d'analyseur LR minimal calcule une machine d'état LR(1), mais fusionne les états compatibles au cours du processus, puis calcule les look-aheads à partir de la machine d'état LR(1) minimale. Ces tables d'analyse syntaxique sont de la même taille ou légèrement plus grandes que les tables d'analyse syntaxique LALR, ce qui donne la meilleure solution.

LRSTAR peut générer des analyseurs syntaxiques LALR(1), Minimal LR(1), Canonical LR(1) et LR(k) en C++.

Answer 4

Les analyseurs SLR reconnaissent un sous-ensemble approprié de grammaires reconnaissables par les analyseurs LALR(1), qui à leur tour reconnaissent un sous-ensemble approprié de grammaires reconnaissables par les analyseurs LR(1).

Chacune d'entre elles est construite comme une machine à états, chaque état représentant un ensemble de règles de production de la grammaire (et la position dans chacune d'elles) lors de l'analyse de l'entrée.

Le site Livre du Dragon Voici un exemple d'une grammaire LALR(1) qui n'est pas SLR :

S → L = R | R
L → * R | id
R → L

Voici l'un des états pour cette grammaire :

S → L•= R
R → L•

Le site • indique la position de l'analyseur dans chacune des productions possibles. Il ne sait pas dans laquelle des productions il se trouve réellement jusqu'à ce qu'il atteigne la fin et essaie de réduire.

Ici, l'analyseur syntaxique pourrait soit décaler un = ou réduire R → L .

Un analyseur syntaxique SLR (aka LR(0)) déterminerait s'il peut réduire en vérifiant si le prochain symbole d'entrée se trouve dans la classe suivre l'ensemble de R (c'est-à-dire l'ensemble de tous les terminaux dans la grammaire qui peuvent suivre R ). Puisque = est également dans cet ensemble, l'analyseur SLR rencontre un conflit shift-reduce.

Cependant, un analyseur LALR(1) utiliserait l'ensemble de tous les terminaux qui peuvent suivre cette production particulière de R, qui est seulement $ (c'est-à-dire la fin de l'entrée). Il n'y a donc pas de conflit.

Comme l'ont noté les précédents commentateurs, les analyseurs syntaxiques LALR(1) ont le même nombre d'états que les analyseurs syntaxiques SLR. Un algorithme de propagation de lookaheads est utilisé pour ajouter des lookaheads aux productions d'états SLR à partir des états LR(1) correspondants. L'analyseur LALR(1) résultant peut introduire des conflits de réduction-réduction qui ne sont pas présents dans l'analyseur LR(1), mais il ne peut pas introduire de conflits de décalage-réduction.

Dans votre exemple l'état LALR(1) suivant provoque un conflit shift-reduce dans une implémentation SLR :

S → b d•a / $
A → d• / c

Le symbole après / est l'ensemble de suivi pour chaque production dans l'analyseur LALR(1). Dans SLR, suivre( A ) comprend a qui pourrait également être déplacée.

Answer 5

Supposons qu'un analyseur sans lookahead analyse joyeusement des chaînes de caractères pour votre grammaire.

En utilisant votre exemple donné, il tombe sur une chaîne dc Que fait-il ? Est-ce qu'il le réduit à S parce que dc est une chaîne valide produite par cette grammaire ? Ou peut-être que nous essayons d'analyser bdc parce que même cela est une chaîne acceptable ?

En tant qu'humains, nous savons que la réponse est simple, nous devons juste nous rappeler si nous venions d'analyser b ou pas. Mais les ordinateurs sont stupides :)

Puisqu'un analyseur SLR(1) avait le pouvoir supplémentaire par rapport à LR(0) d'effectuer un lookahead, nous savons que toute quantité de lookahead ne peut pas nous dire quoi faire dans ce cas ; au lieu de cela, nous devons regarder dans notre passé. C'est ainsi que l'analyseur syntaxique LR canonique vient à la rescousse. Il se souvient du contexte passé.

La façon dont il se souvient de ce contexte est qu'il se discipline lui-même, qu'à chaque fois qu'il rencontrera un b il commencera à marcher sur le chemin de la lecture. bdc comme une possibilité. Ainsi, lorsqu'il voit un d il sait s'il est déjà en train de parcourir un chemin. Ainsi, un analyseur CLR(1) peut faire des choses qu'un analyseur SLR(1) ne peut pas faire !

Mais maintenant, comme nous avons dû définir tant de chemins, les états de la machine deviennent très grands !

Nous fusionnons donc des chemins de même apparence, mais comme prévu, cela peut donner lieu à des problèmes de confusion. Cependant, nous sommes prêts à prendre ce risque au prix d'une réduction de la taille.

C'est votre analyseur syntaxique LALR(1).

---

Maintenant, comment le faire de manière algorithmique.

Lorsque vous dessinez les ensembles de configuration pour la langue ci-dessus, vous verrez un conflit shift-reduce dans deux états. Pour les supprimer, vous pourriez envisager un SLR(1), qui prend des décisions en regardant un suiveur, mais vous observeriez qu'il ne pourra toujours pas le faire. Ainsi, vous dessineriez à nouveau les ensembles de configuration, mais cette fois avec une restriction selon laquelle, chaque fois que vous calculez la fermeture, les productions supplémentaires ajoutées doivent avoir un ou plusieurs follow stricts. Référez-vous à n'importe quel manuel sur ce que devraient être ces suivis.