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

Question

Je travaille sur mes concepts de compilateurs mais je suis un peu confus ... La recherche sur Google ne m'a permis de trouver aucune réponse définitive.

Les analyseurs SLR et LR (0) sont-ils identiques?Sinon, quelle est la différence?

Answer 1

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

• Les analyseurs tentent d'appliquer les productions en sens inverse pour ramener la phrase d'entrée au symbole de départ ( de bas en haut )
• Les analyseurs analysent l'entrée de gauche à droite ( directionnelle )
• Les analyseurs tentent de prédire les réductions à appliquer sans nécessairement voir toutes les entrées ( prédictives )

LR (0) et SLR (1) sont des analyseurs de décalage / réduction , ce qui signifie qu'ils traitent les jetons du flux d'entrée en les plaçant sur une pile, et à chaque point soit déplacer un jeton en le poussant sur la pile ou réduire une séquence de terminaux et de non terminaux au sommet de la pile vers un symbole non terminal. On peut montrer que n'importe quelle grammaire peut être analysée de bas en haut en utilisant un analyseur shift / reduction, mais cet analyseur peut ne pas être déterministe . Autrement dit, l'analyseur peut avoir à "deviner" s'il doit 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. Quelle que soit la puissance d'un analyseur de décalage / réduction déterministe que vous construisez, il ne pourra jamais analyser toutes les grammaires.

Lorsqu'un analyseur de décalage / réduction déterministe est utilisé pour analyser une grammaire qu'il ne peut pas gérer, il en résulte déplacer / réduire les conflits ou réduire / réduire les conflits , où le l'analyseur peut entrer dans un état dans lequel il ne peut pas dire quelle action entreprendre. Dans un conflit de décalage / réduction, 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 de réduction / réduction, l'analyseur sait qu'il doit remplacer les symboles du haut de la pile par des symboles non terminaux, mais il ne peut pas dire quelle réduction utiliser.

Je m'excuse s'il s'agit d'une longue exposition, mais nous en avons besoin pour pouvoir résoudre la différence entre l'analyse syntaxique LR (0) et SLR (1). Un analyseur LR (0) est un analyseur de décalage / réduction qui utilise zéro jeton d'anticipation pour déterminer l'action à entreprendre (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, soit applique une réduction spécifique. S'il y a jamais deux choix ou plus à faire, l'analyseur échoue et nous disons que la grammaire n'est pas LR (0).

Rappelez-vous que les deux conflits LR possibles sont le décalage / réduction et la réduction / réduction. Dans ces deux cas, il y a au moins deux actions que l'automate LR (0) pourrait effectuer, et il ne peut pas dire lesquelles utiliser. Étant donné qu'au moins une des actions en conflit 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 est autorisé à regarder le prochain jeton d'entrée pour déterminer s'il doit décaler ou réduire. Si nous ne permettons à l'analyseur de réduire que lorsque cela "a du sens" de le faire (pour une certaine 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 déplacer ou de étape particulière.

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

La seule différence entre LR (0) et SLR (1) est thi

s capacité supplémentaire d'aider à décider des mesures à prendre en cas de 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. Plus communément, vous verrez des analyseurs LALR (1) ("Lookahead LR (1)") utilisés. Ils fonctionnent 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 SLR (1). Pour être un peu plus précis, les analyseurs SLR (1) tentent de résoudre les conflits en examinant la structure de la grammaire pour en savoir plus sur le moment de décaler 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 spécifiques sur le moment de décaler et de réduire. Puisque LALR (1) peut examiner la structure de l'analyseur LR (0), il peut identifier plus précisément quand certains conflits sont faux. Les utilitaires Linux yacc et bison, par défaut, produisent 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 constaté qu'il a atteint la fin d'une production, il sait essayer de réduire. Cependant, l'analyseur peut ne pas être en mesure de dire si c'est à la fin d'une production et au milieu d'une autre, ce qui conduit à un conflit de décalage / réduction, ou de laquelle des deux productions différentes il a atteint la fin (une réduction / réduire les conflits). 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 prochain jeton d'anticipation.

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 qui, selon l'analyseur, est utilisée, il garde une trace des jetons possibles qui pourraient apparaître une fois la production terminée. Parce que l'analyseur garde une trace de ces informations à chaque étape, et pas seulement quand il a besoin de prendre la décision, l'analyseur LR (1) est nettement plus puissant et précis que n'importe lequel des LR (0), SLR (1) ou Analyseurs LALR (1) 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 délicates que tout langage qui pourrait être analysé de manière déterministe par tout parseur de décalage / réduction 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 signifie 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 vrai langage de programmation, 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) ("Generalized 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 à la place 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 toute grammaire sans contexte a

t tous , même les grammaires qui ne peuvent pas être analysées par un analyseur LR (k) pour tout k.D'autres analyseurs sont également capables de le faire (par exemple, l'analyseur Earley ou un analyseur CYK), bien que GLR (0) ait tendance à être plus rapide en pratique.

Si vous souhaitez en savoir plus, j'ai donné cet été 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 puissantes, vous pouvez profiter de mes diapositives de cours et de mes devoirs sur l'analyse.Tous les supports de cours sont disponibles ici sur mon site personnel .

J'espère que cela vous aidera!

Answer 2

Voici ce que j'ai appris.En général, l'analyseur LR (0) peut avoir une ambiguïté, c'est-à-dire qu'une case de la table (que vous dérivez pour créer l'analyseur) peut avoir plusieurs valeurs (ou) pour mieux le dire: l'analyseur conduit à deux états finaux avec la même entrée.L'analyseur SLR est donc créé pour supprimer cette ambiguïté.Pour le construire, trouvez toutes les productions qui mènent à des états goto, trouvez le symbole de production suivant sur le côté gauche et n'incluez que les états goto qui sont présents dans la suite.Ce retour signifie que vous n'incluez pas une production qui n'est pas possible en utilisant le grammeur d'origine (car cet état n'est pas dans l'ensemble suivant)