Quelle est la différence entre LR(0) et l'analyse SLR?

Les analyseurs LR(0) et SLR(1) sont des analyseurs prédictifs directionnels ascendants. Cela signifie que

• Les analyseurs tentent d'appliquer des productions à l'envers pour ramener la phrase d'entrée au symbole de départ ( bottom-up )
• Les analyseurs analysent l'entrée de gauche à droite (directionnel )
• Les analyseurs tentent de prédire les réductions à appliquer sans nécessairement voir toutes les entrées ( predictive )

Les Deux LR(0) et SLR (1) sont des analyseurs shift/reduce, ce qui signifie qu'ils traitent les jetons du flux d'entrée en les plaçant sur une pile, et à chaque point décalant un jeton en le poussant sur la pile ou réduisant une séquence de terminaux et de non-terminaux au sommet de la pile Il peut être montré que toute grammaire peut être analysée de bas en haut en utilisant un analyseur shift/reduce, mais cet analyseur peut ne pas être déterministe. Qui est, le l'analyseur peut devoir "deviner" s'il faut appliquer un décalage ou une réduction, et peut finir par devoir revenir en arrière pour se rendre compte qu'il a fait le mauvais choix. Peu importe la puissance d'un analyseur déterministe shift/reduce que vous construisez, il ne pourra jamais analyser toutes les grammaires.

Lorsqu'un déterministe décaler/réduire l'analyseur est utilisé pour analyser une grammaire qu'il ne peut pas gérer, il en résulte décaler/réduire les conflits ou réduire/réduire les conflits, où l'analyseur peut entrer dans un état dans lequel il ne peut pas dire quelles mesures prendre. Dans un conflit shift/reduce, il ne peut pas dire s'il doit ajouter un autre symbole à la pile ou effectuer une réduction sur les symboles supérieurs de la pile. Dans un conflit reduce/reduce, l'analyseur sait qu'il doit remplacer les symboles supérieurs de la pile par un non-terminal, mais il ne peut pas dire quelle réduction utiliser.

Je m'excuse si c'est une longue exposition, mais nous en avons besoin pour pouvoir traiter la différence entre l'analyse LR(0) et SLR(1). Un analyseur LR(0) est un analyseur shift/reduce qui utilise zéro tokens de lookahead pour déterminer quelle action prendre (d'où le 0). Cela signifie que dans n'importe quelle configuration de l'analyseur, l'analyseur doit avoir une action non ambiguë à choisir - soit il déplace un symbole spécifique ou applique une réduction spécifique. S'il y a deux ou Plusieurs choix à faire, l'analyseur échoue et nous disons que la grammaire N'est pas LR (0).

Rappelons que les deux conflits LR possibles sont shift / reduce et reduce / reduce. Dans ces deux cas, il y a au moins deux actions que l'automate LR(0) pourrait prendre, et il ne peut pas dire lequel d'entre eux à utiliser. Étant donné qu'au moins l'une des actions conflictuelles est une réduction, une ligne d'attaque raisonnable serait d'essayer de faire en sorte que l'analyseur soit plus prudent lorsqu'il effectue une réduction particulière. Plus précisément, supposons que l'analyseur soit autorisé à regarder le jeton d'entrée suivant pour déterminer s'il doit être décalé ou réduit. Si nous autorisons seulement l'analyseur pour réduire quand cela "a du sens" de le faire (pour une définition de "A du sens"), alors nous pouvons être en mesure d'éliminer le conflit en faisant en sorte que l'automate choisisse spécifiquement de changer ou de réduire dans une étape particulière.

Dans SLR (1) ("Simplified LR (1)"), l'analyseur est autorisé à regarder un jeton de lookahead lorsqu'il décide s'il doit être décalé ou réduit. En particulier, lorsque l'analyseur veut essayer de réduire quelque chose de la forme A → w (pour non terminal A et chaîne w), il regarde le prochain jeton d'entrée. Si ce jeton peut légalement apparaître après le non terminal A dans une dérivation, l'analyseur réduit. Sinon, il ne le fait pas. L'intuition ici est que dans certains cas, cela n'a aucun sens de tenter une réduction, car compte tenu des jetons que nous avons vus jusqu'à présent et du jeton à venir, il n'y a aucun moyen possible que la réduction puisse être correcte.

La seule différence entre LR(0) et SLR(1) est cette capacité supplémentaire pour aider à décider quelle action prendre quand il y a conflit. Pour cette raison, toute grammaire qui peut être analysée par un analyseur LR(0) peut être analysée par un analyseur SLR(1). Cependant, les analyseurs SLR(1) peuvent analyser un plus grand nombre de grammaires que LR(0).

En pratique, cependant, SLR (1) est encore une méthode d'analyse assez faible. Le plus souvent, vous verrez LALR(1) ("Anticipation LR(1)") analyseurs utilisés. Ils travaillent aussi en essayant de résoudre les conflits dans un analyseur LR (0), mais les règles qu'ils utilisent pour résoudre les conflits sont beaucoup plus précises que celles utilisées dans SLR (1), et par conséquent un nombre beaucoup plus grand de grammaires sont LALR (1) Que sont SLR (1). Pour être un peu plus précis, les analyseurs SLR(1) tentent de résoudre les conflits en regardant la structure de la grammaire pour en savoir plus sur le moment de changer et le moment de réduire. Les analyseurs LALR(1) examinent à la fois la grammaire et l'analyseur LR(0) pour obtenir des informations encore plus précises sur le moment de changer et le moment de réduire. Parce que LALR (1) peut regarder la structure de l'analyseur LR(0) , Il peut plus précisément identifiez quand certains conflits sont faux. Les utilitaires Linux yacc et bison produisent par défaut des analyseurs LALR(1).

Historiquement, les analyseurs LALR(1) étaient généralement construits par une méthode différente qui reposait sur l'analyseur LR(1) beaucoup plus puissant, donc vous verrez souvent LALR(1) décrit de cette façon. Pour comprendre cela, nous devons parler des analyseurs LR(1). Dans un analyseur LR(0), l'analyseur fonctionne en gardant une trace de l'endroit où il pourrait se trouver au milieu d'une production. Une fois qu'il a trouvé qu'il a atteint la fin d'une production, il sait essayer de réduire. Cependant, l'analyseur pourrait ne pas être en mesure de dire s'il est à la fin d'une production et au milieu d'une autre, ce qui conduit à un conflit shift/reduce, ou lequel de deux productions différentes il a atteint la fin (un conflit reduce/reduce). Dans LR (0), cela conduit immédiatement à un conflit et l'analyseur échoue. Dans SLR (1) ou LALR (1), l'analyseur prend alors la décision de décaler ou de réduire en fonction du jeton suivant de prospection.

Dans un analyseur LR(1), l'analyseur garde une trace des informations supplémentaires pendant son fonctionnement. En plus de garder une trace de la production que l'analyseur croit être utilisée, il garde une trace des jetons possibles qui pourraient apparaître après la fin de la production. Parce que l'analyseur garde une trace de ces informations à chaque étape, et pas seulement quand il doit prendre la décision, l'analyseur LR(1) est sensiblement plus puissant et précis que n'importe lequel des LR(0), SLR(1) ou LALR (1) analyseurs dont nous avons parlé jusqu'à présent. LR (1) est une technique d'analyse extrêmement puissante, et il peut être montré en utilisant des mathématiques difficiles que n'importe quel langage qui pourrait être analysé de manière déterministe par any Shift/reduce parser a une grammaire qui pourrait être analysée avec un automate LR(1). (Notez que cela ne signifie pas que toutes les grammaires qui peuvent être analysées de manière déterministe sont LR (1); cela dit seulement qu'un langage qui pourrait être analysé de manière déterministe a une certaine grammaire LR(1)). Cependant, cette puissance a un prix, et un analyseur LR(1) généré peut nécessiter tellement d'informations pour fonctionner qu'il ne peut pas être utilisé dans la pratique. Un analyseur LR(1) pour un langage de programmation réel, par exemple, peut nécessiter des dizaines à des centaines de mégaoctets d'informations supplémentaires pour fonctionner correctement. Pour cette raison, LR (1) n'est généralement pas utilisé dans la pratique, et des analyseurs plus faibles comme LALR(1) ou SLR(1) sont utilisés à la place.

Plus récemment, un nouvel algorithme D'analyse appelé GLR (0) ("Généralisée LR(0)") a gagné en popularité. Plutôt que d'essayer de résoudre les conflits qui apparaissent dans un analyseur LR(0), L'analyseur GLR(0) fonctionne plutôt en essayant toutes les options possibles en parallèle. En utilisant quelques astuces intelligentes, cela peut être fait pour fonctionner très efficacement pour de nombreuses grammaires. De plus, GLR(0) peut Analyser n'importe quelle grammaire sans contexte , même les grammaires qui ne peuvent pas être analysées par un analyseur LR(k) pour n'importe quel K. D'autres analyseurs sont capables de le faire aussi (par exemple, le Earley Parser ou un analyseur CYK), bien que GLR (0) ait tendance à être plus rapide en pratique.

Si vous êtes intéressé à en apprendre plus, cet été, j'ai enseigné un cours d'Introduction aux compilateurs et j'ai passé un peu moins de deux semaines à parler des techniques d'analyse. Si vous souhaitez obtenir une introduction plus rigoureuse à LR (0), SLR(1), et une foule d'autres techniques d'analyse puissante, vous pourriez profiter de mes diapositives de cours et devoirs sur l'analyse. Tout le matériel de cours est disponible tiens sur mon site personnel.

Espérons que cela aide!