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

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

Et comment montrer si une grammaire est LR, SLR ou LALR? Pour une grammaire LL, il suffit de montrer qu'aucune cellule de la table d'analyse ne doit contenir plusieurs règles de production. Des règles similaires pour LALR, SLR et LR?

Par exemple, comment 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 quelle est la différence entre LALR et LR. Les tables de LALR sont donc plus petites mais ne peuvent reconnaître qu'un sous-ensemble de grammaires LR. Quelqu'un peut-il expliquer plus en détail la différence entre LALR et LR s'il vous plaît? LALR (1) et LR (1) suffiront pour une réponse. Les deux utilisent 1 jeton d'anticipation et les deux sont pilotés par table! En quoi sont-ils différents?

Les analyseurs SLR, LALR et LR peuvent tous être implémentés en utilisant exactement les mêmes machines pilotées par table.

Fondamentalement, l'algorithme d'analyse collecte le jeton d'entrée suivant T et consulte l'état actuel S (et les tables d'anticipation, GOTO et de réduction associées) pour décider de la marche à suivre:

• SHIFT: Si la table actuelle dit SHIFT sur le jeton T, la paire (S, T) est poussée sur la pile d'analyse, l'état est changé 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
• RÉDUIRE: chaque état a 0, 1 ou plusieurs réductions possibles qui peuvent se produire dans l'état. Si l'analyseur est LR ou LALR, le jeton est vérifié par rapport aux ensembles d'anticipation pour toutes les réductions valides pour l'état. Si le jeton correspond à un ensemble d'anticipation pour une réduction de la règle de grammaire G = R1 R2 .. Rn, une réduction et un décalage de pile se produisent: l'action sémantique pour G est appelée, la pile est sautée n (à partir de Rn) fois, la paire ( S, G) est poussé sur la pile, le nouvel état S 'est mis à 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 le état et ainsi l'action de réduction peut être effectuée aveuglément sans chercher à voir quelle réduction s'applique. Il est utile pour un analyseur SLR de savoir s'il y a aune réduction ou non; il est facile de 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.

Alors, s'ils utilisent tous les mêmes machines, à quoi ça sert?

La valeur prétendue dans SLR est sa simplicité de mise en œuvre; vous n'avez pas à parcourir les réductions possibles en vérifiant les ensembles d'anticipation car il y en a au plus un, et c'est la seule action viable s'il n'y a pas de sorties 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 rechercher. En pratique, les analyseurs L (AL) R gèrent un ensemble de langages utilement plus grand, et sont si peu de travail supplémentaire à implémenter que personne n'implémente SLR sauf comme exercice académique.

La différence entre LALR et LR a à voir avec la table générateur de. Les générateurs d'analyseurs LR gardent une trace de toutes les réductions possibles des états spécifiques et de leur ensemble d'anticipation précis; vous vous retrouvez avec des états dans lesquels chaque réduction est associée à son ensemble d'anticipation exact à partir de son contexte gauche. Cela tend à créer des ensembles d'états assez volumineux. Les générateurs d'analyseurs LALR sont prêts à combiner des états si les tables GOTO et les ensembles de têtes de recherche pour les réductions sont compatibles et ne sont 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 ensemble de langages que les analyseurs LALR, mais ont des tables d'analyseurs 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 d'état mérite d'être optimisée;

Donc: Tous les trois utilisent les mêmes machines. SLR est "facile" dans le sens où vous pouvez ignorer un tout petit peu de la machinerie, mais cela ne vaut tout simplement pas la peine. LR analyse un ensemble plus large de langages mais les tables d'état ont tendance à être assez grandes. Cela laisse LALR comme le choix pratique.

Cela dit, il vaut la peine de savoir que les analyseurs GLR peuvent analyser n'importe quel langage sans contexte, en utilisant des machines plus compliquées mais exactement les mêmes tables (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 analysera selon elle. La différence dans la machinerie est que GLR est prêt à essayer plusieurs analyses en cas de conflit entre la table GOTO et / ou les ensembles d'anticipation. (Comment GLR le fait efficacement est un pur génie [pas le mien] mais ne rentrera pas dans ce message SO).

C'est pour moi un fait extrêmement utile. Je construis des analyseurs de programmes et des transformateurs de code et des analyseurs 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 post-analyse. L'utilisation de GLR signifie que je peux relativement facilement créer des grammaires fonctionnelles, par rapport au piratage d'une grammaire pour obtenir une forme utilisable par LALR. Cela compte beaucoup lorsque vous essayez de gérer 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 l'ensemble du langage, et vous ne voulez pas passer votre vie à essayer de pirater les règles de grammaire pour répondre aux limitations de LALR (ou même LR).

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

[EDIT Novembre 2011: Nous avons étendu notre analyseur pour gérer l'ensemble de C ++ 11. GLR a rendu cela beaucoup plus facile à faire. EDIT août 2014: gère maintenant tout C ++ 17. Rien ne s'est cassé ou n'a empiré, GLR est toujours le miaulement du chat.]

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

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

Addenda

La réponse courte est que les tables d'analyse LALR sont plus petites, mais 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 (presque identiques).

Les tables LALR sont plus petites car les états similaires (redondants) sont fusionnés, jetant efficacement les informations de contexte / d'anticipation codées par les états séparés. L'avantage est que vous obtenez des tables d'analyse beaucoup plus petites pour la même grammaire.

L'inconvénient est que toutes les grammaires LR ne peuvent pas être codées en tant que tables LALR car les grammaires plus complexes ont des anticipations de lecture plus compliquées, ce qui entraîne deux états ou plus au lieu d'un seul état fusionné.

La principale différence est que l'algorithme de production de tables LR transporte plus d'informations entre les transitions d'un état à l'autre, contrairement à l'algorithme LALR. Ainsi, l'algorithme LALR ne peut pas dire si un état fusionné donné doit vraiment être laissé en tant que deux ou plusieurs états séparés.

Encore une autre réponse (YAA).

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

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

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

Un générateur d'analyseur canonique LR calcule une machine à états LR (1) et les anticipations font déjà partie de la machine à états LR (1). Ces tables d'analyseurs peuvent être très volumineuses.

Un générateur d'analyseur minimal LR calcule une machine à états LR (1), mais fusionne les états compatibles pendant le processus, puis calcule les anticipations à partir de la machine à états LR (1) minimale. Ces tables d'analyseurs sont de la même taille ou légèrement plus grandes que les tables d'analyseurs LALR, ce qui donne la meilleure solution.

LRSTAR 10.0 peut générer des analyseurs LALR (1), LR (1), CLR (1) ou LR (*) en C ++, tout ce qui est nécessaire pour votre grammaire. Voir ce diagramme qui montre la différence entre les analyseurs LR.

[Divulgation complète: LRSTAR est mon produit]

Supposons qu'un analyseur sans anticipation analyse les chaînes pour votre grammaire.

En utilisant votre exemple donné, il tombe sur une chaîne dc, que fait-il? Le réduit-il à S, car dcune chaîne valide est-elle produite par cette grammaire? OU peut-être que nous essayions d'analyser bdcparce que même c'est une chaîne acceptable?

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

Puisqu'un analyseur SLR (1) avait la puissance supplémentaire sur LR (0) pour effectuer une recherche anticipée, nous savons que toute quantité d'anticipation ne peut pas nous dire quoi faire dans ce cas; au lieu de cela, nous devons regarder en arrière dans notre passé. Ainsi vient l'analyseur canonique LR à 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, que chaque fois qu'il rencontrera un b, il commencera à marcher sur un chemin vers la lecture bdc, comme une possibilité. Ainsi, quand il voit un, dil sait s'il suit déjà un chemin. Ainsi, un analyseur CLR (1) peut faire des choses qu'un analyseur SLR (1) ne peut pas faire!

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

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

Ceci est votre analyseur 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 de réduction de décalage dans deux états. Pour les supprimer, vous voudrez peut-être envisager un SLR (1), qui prend des décisions en regardant un suivi, mais vous remarquerez qu'il ne sera toujours pas en mesure de le faire. Ainsi, vous dessinez à nouveau les ensembles de configuration, mais cette fois avec une restriction selon laquelle chaque fois que vous calculez la clôture, les productions supplémentaires ajoutées doivent avoir des suivis stricts. Référez-vous à n'importe quel manuel sur ce que devraient être ceux-ci.

La différence fondamentale entre les tables d'analyseur générées avec SLR et LR, est que les actions de réduction sont basées sur l'ensemble Suit pour les tables SLR. Cela peut être trop restrictif, provoquant en fin de compte un conflit de réduction de quart de travail.

Un analyseur LR, par contre, ne réduit les décisions que sur l'ensemble des terminaux qui peuvent effectivement suivre le non-terminal en cours de réduction. Cet ensemble de terminaux est souvent un sous-ensemble approprié de l'ensemble Suit d'un tel non-terminal, et a donc moins de chance d'entrer en conflit avec les actions de décalage.

Les analyseurs LR sont plus puissants pour cette raison. Les tables d'analyse LR peuvent cependant être extrêmement volumineuses.

Un analyseur LALR commence par l'idée de créer une table d'analyse LR, mais combine les états générés de manière à réduire considérablement la taille de la table. L'inconvénient est qu'une petite chance de conflits serait introduite pour certaines grammaires qu'une table LR aurait autrement évitées.

Les analyseurs LALR sont légèrement moins puissants que les analyseurs LR, mais toujours plus puissants que les analyseurs SLR. YACC et d'autres générateurs d'analyseurs de ce type ont tendance à utiliser LALR pour cette raison.

PS Par souci de concision, SLR, LALR et LR ci-dessus signifient vraiment SLR (1), LALR (1) et LR (1), donc un jeton anticipé est implicite.

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).

Chacun de ceux-ci est construit comme une machine à états, chaque état représentant un ensemble de règles de production de la grammaire (et leur position dans chacune) lors de l'analyse de l'entrée.

L' exemple Dragon Book d'une grammaire LALR (1) qui n'est pas SLR est le suivant:

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

Voici l'un des états de cette grammaire:

S → L•= R
R → L•

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

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

Un analyseur SLR (alias LR (0)) déterminerait s'il pourrait réduire en vérifiant si le symbole d'entrée suivant est dans l' ensemble suivant de R(c'est-à-dire l'ensemble de tous les terminaux de la grammaire qui peuvent suivre R). Puisque= fait également partie de cet ensemble, l'analyseur SLR rencontre un conflit de réduction de décalage.

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). Donc, pas de conflit.

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

Dans votre exemple , l'état LALR (1) suivant provoque un conflit de réduction de décalage dans une implémentation SLR:

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

Le symbole après /est le jeu suivant pour chaque production dans l'analyseur LALR (1). Dans SLR, follow ( A) inclut a, qui pourrait également être décalé.

En plus des réponses ci-dessus, ce diagramme montre comment différents analyseurs sont liés:

Une réponse simple est que toutes les grammaires LR (1) sont des grammaires LALR (1). Comparé à LALR (1), LR (1) a plus d'états dans la machine à états finis associée (plus du double des états). Et c'est la raison principale pour laquelle les grammaires LALR (1) nécessitent plus de code pour détecter les erreurs de syntaxe que les grammaires LR (1). Et une autre chose importante à savoir concernant ces deux grammaires est que dans les grammaires LR (1), nous pourrions avoir moins de conflits de réduction / réduction. Mais dans LALR (1), il y a plus de possibilité de réduire / réduire les conflits.