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 que n'importe quelle cellule de la table d'analyse ne doit pas contenir plusieurs règles de production. 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 eu de réponse satisfaisante pour quelle est la différence entre LALR et LR. Les tables de LALR sont donc plus petites mais elles ne peuvent reconnaître qu'un sous-ensemble de grammaires LR. Quelqu'un peut-il élaborer plus sur la différence entre LALR et LR s'il vous plait? LALR (1) et LR (1) suffiront pour une réponse. Les deux utilisent 1 token look-ahead et les deux sont pilotés par une table! Comment ils sont différents?
7 réponses
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 lookahead, GOTO et reduction associées) pour décider quoi faire:
- SHIFT: si la table actuelle indique 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
- réduire: chaque État a 0, 1 ou plusieurs réductions possibles qui pourraient se produire dans l'état. Si l'analyseur 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 lookahead pour une réduction de la règle de grammaire G = R1 R2 .. Rn, une réduction de pile et un décalage se produit: l'action sémantique pour G est appelée, la pile est sauté n (de Rn) fois, la paire (S, G) est poussé sur la pile, le nouvel état S ' est défini sur 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 à voir quelle réduction s'applique. Il est utile pour un analyseur SLR de savoir s'il y a une réduction ou non; c'est facile de dire si chaque État enregistre explicitement le nombre de réductions qui lui sont associées, et que count est nécessaire pour les versions L(AL)R dans la pratique de toute façon.
- ERROR: Si Ni SHIFT ni REDUCE n'est possible, une erreur de syntaxe est déclarée.
Donc, s'ils utilisent tous la même machine, à quoi bon?
La valeur supposée dans SLR est sa simplicité dans la mise en œuvre; vous n'avez pas à parcourir les réductions possibles en vérifiant les ensembles de lookahead car il y en a au plus un, et c'est la seule action viable s'il n'y a pas de sorties de décalage de l'état. Qui de réduction s'applique peut être attaché spécifiquement à l'état, de sorte que les machines D'analyse SLR n'ont pas à le chasser. 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 un exercice académique.
La différence entre LALR et LR A à voir avec la table Générateur . Les générateurs d'analyseur LR gardent une trace de toutes les réductions possibles à partir d'états spécifiques et de leur ensemble de lookahead précis; vous finissez par avec des États dans lesquels chaque réduction est associée à son ensemble de lookahead exact à partir de son contexte de gauche. Cela tend à construire des ensembles d'États plutôt importants. Les générateurs D'analyseurs LALR sont prêts à combiner des États si les tables GOTO et les ensembles lookhead pour les réductions sont compatibles et ne sont pas en conflit; cela produit des nombres d'États considérablement plus petits, 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 langues que les analyseurs LALR, mais ont des tables d'analyseurs beaucoup plus grandes. En pratique, on peut trouver des grammaires LALR suffisamment proches des langages cibles pour que la taille de la machine d'état mérite d'être optimisée; les endroits où l'analyseur LR serait le mieux sont gérés par une vérification ad hoc en dehors de l'analyseur.
Donc: tous les trois utilisent la même machine. SLR est "facile" dans le sens où vous pouvez ignorer un tout petit peu de la machine, mais il est tout simplement pas la peine. LR analyse un ensemble plus large de langues mais les tables d'état ont tendance à être assez grande. Cela laisse LALR comme le choix pratique.
Cela dit, il est bon 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 en fonction de cela. Le 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 ou les ensembles lookahead. (Comment GLR fait cela efficacement est un génie pur [pas le mien] mais ne rentre pas dans ce post SO).
C'est pour moi un fait extrêmement utile. Je construis des analyseurs de programme 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 de post-analyse. L'utilisation de GLR signifie que je peux relativement facilement construire des grammaires de travail, par rapport au piratage d'une grammaire pour entrer dans la forme utilisable de LALR. Cela compte beaucoup lorsque vous essayez 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 la langue entière, et vous ne voulez pas passer votre vie à essayer de pirater les règles de grammaire pour répondre aux limites de LALR (ou même LR).
Comme une sorte d'exemple célèbre, le C++ est considéré comme extrêmement difficile à analyser... par les gars qui font LALR parsing. C++ est simple à analyser en utilisant des machines 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 vanilla C++, mais aussi une variété de dialectes fournisseurs. Ceci est seulement possible dans la pratique parce que nous utilisons un analyseur GLR, à mon humble avis).
[EDIT novembre 2011: nous avons étendu notre analyseur pour gérer tout C++11. GLR a rendu cela beaucoup plus facile à faire. Modifier août 2014: maintenant gestion de tout C++17. Rien n'a 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 d'analyseur qui ont exactement la même taille que la grammaire SLR équivalente, qui sont généralement d'un ordre de grandeur inférieur aux 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 ma table D'analyse MLR(k) algorithme ici.
Additif
La réponse courte est que les tables D'analyse LALR sont plus petites, mais la machine d'analyse 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, ce qui élimine efficacement les informations de contexte/lookahead encodé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 tables LALR car les grammaires plus complexes ont des lookaheads plus compliqués, ce qui entraîne deux états ou plus au lieu d'un seul État fusionné.
La principale différence est que l'algorithme pour produire des tables LR transporte plus d'informations entre les transitions d'état en état alors que l'algorithme LALR ne le fait pas. Donc L'algorithme LALR ne peut pas dites si un État fusionné donné devrait vraiment être laissé comme 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 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 D'état LR(0) et calcule les look-aheads à partir de la grammaire (First et FOLLOW sets). C'est une approche simplifiée et peut signaler des conflits qui n'existent pas vraiment dans la machine D'état LR(0).
An LALR le générateur d'analyseur crée une machine D'état LR(0) et calcule les têtes de regard à 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 d'état LR(1).
Un générateur d'analyseur LR canonique calcule une machine D'état LR(1) et les têtes de regard font déjà partie de la machine D'état LR(1). Ces tables d'analyse peuvent être très grandes.
Un générateur D'analyseur LR Minimal calcule un État LR (1) machine, mais fusionne les États compatibles pendant le processus, puis calcule les têtes de look à partir de la machine à État minimal LR(1). Ces tables d'analyse sont de la même taille ou légèrement plus grandes que les tables D'analyse LALR, ce qui donne la meilleure solution.
LRSTAR 9.1 peut générer des analyseurs LR(1) et LR(*) minimaux en C++. Voir ce diagramme qui montre la différence entre les analyseurs LR.
[divulgation complète: LRSTAR est mon produit]
Supposons qu'un analyseur sans lookahead analyse joyeusement les chaînes 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, car dc est une chaîne valide produite par cette grammaire? Ou peut-être que nous essayions 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 venons d'analyser b ou non. Mais les ordinateurs sont stupides :)
Comme un analyseur SLR(1) avait le pouvoir supplémentaire sur LR(0) pour effectuer un lookahead, nous savons que toute quantité de lookahead ne peut pas nous dire quoi faire dans ce cas; à la place, nous devons regarder en arrière dans notre passé. Ainsi vient l'analyseur LR canonique à la rescousse. Il se souvient du contexte passé.
La façon dont il se souvient de ce contexte est qu'il se discipline, que chaque fois qu'il rencontrera un b, il commencera à marcher sur un chemin vers la lecture bdc, comme une possibilité. Alors, quand il voit un {[7] } Il sait s'il marche 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 avons dû définir tant de chemins, Les états de la machine deviennent très grands!
Nous fusionnons donc les mêmes chemins, mais comme prévu cela pourrait donner lieu à des problèmes de confusion. Cependant, nous sommes prêts à prendre le risque au prix de réduire la taille.
C'est votre analyseur LALR (1).
Maintenant comment le faire algorithmiquement.
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 pouvez envisager un reflex(1), qui prend des décisions en regardant un suivi, mais vous remarquerez qu'il ne sera toujours pas capable de le faire. Ainsi, vous dessinez à nouveau les ensembles de configuration, mais cette fois avec une restriction que chaque fois que vous calculez la fermeture, les productions supplémentaires ajoutées doivent avoir un suivi strict. Consulter un manuel sur ce que devraient suivre être.
La différence fondamentale entre les tables d'analyse générées avec SLR vs LR, est que les actions de réduction sont basées sur L'ensemble suivant pour les tables SLR. Cela peut être trop restrictif, provoquant finalement un changement-réduire les conflits.
Un analyseur LR, d'autre part, les bases réduisent les décisions uniquement sur l'ensemble des terminaux qui peuvent réellement suivre la réduction du non-terminal. Cet ensemble de terminaux est souvent un sous-ensemble approprié de L'ensemble suivant d'un tel non-terminal, et a donc moins risque de conflit avec les actions de changement.
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 construire une table D'analyse LR, mais combine les États générés d'une manière qui entraîne une taille de table nettement inférieure. L'inconvénient est qu'une petite chance de conflits serait introduite pour certaines grammaires qu'un LR table autrement auraient évité.
Les analyseurs LALR sont légèrement inférieurs puissant que les analyseurs LR, mais toujours plus puissant que les analyseurs SLR. YACC et d'autres générateurs d'analyseurs de ce type ont tendance à utiliser LALR pour cette raison.
P.S. pour la brièveté, SLR, LALR et LR ci-dessus signifient vraiment SLR(1), LALR(1) et LR(1), donc un lookahead symbolique 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 d'entre eux est construit comme une machine d'état, chaque État représentant un ensemble de règles de production de la grammaire (et la position dans chacune) lors de l'analyse de l'entrée.
LeDragon Book exemple D'une grammaire LALR(1) qui N'est pas SLR est la suivante:
S → L = R | R
L → * R | id
R → L
Voici L'un des pour 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éplacer une = ou réduire R → L.
Un analyseur SLR (AKA LR(0)) déterminerait s'il pouvait réduire en vérifiant si le symbole d'entrée suivant est dans le follow set de R (c'est-à-dire l'ensemble de tous les terminaux dans la grammaire qui peut 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, 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 lookahead est utilisé pour capter les lookaheads sur Productions d'état SLR à partir des États LR correspondants(1). L'analyseur LALR(1) résultant peut introduire des conflits reduce-reduce qui ne sont pas présents dans l'analyseur LR(1), mais il ne peut pas introduire des conflits shift-reduce.
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 le jeu suivant pour chaque production dans L'analyseur LALR(1). Dans les REFLEX, suivre(A) comprend a, qui pourrait également être déplacé.
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 chose plus 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 conflit.