Compilateurs: Quelle est la différence entre les analyseurs LL (0) et LR (0). Existe-t-il une chose telle que les analyseurs LL (0)?


Réponse 1:

Cette question semble se concentrer sur les analyseurs LL (0), alors définissons-les. Un analyseur LL (0), analyse de gauche à droite en utilisant 0 jetons au début de la production pour déterminer la production à appliquer. Que signifie ce 0 jeton, cela signifie que l'analyseur ne peut pas utiliser le texte analysé pour déterminer la production à appliquer. Cela signifie que l'analyseur ne peut faire aucun choix. Il doit savoir avant de commencer à analyser exactement la séquence de jetons qu'il analysera. La séquence de jetons doit être fixe, ce qui signifie qu'il ne peut y avoir qu'une seule séquence que l'analyseur analysera. Ainsi, vous pourriez avoir un analyseur qui accepte "Bonjour tout le monde!" avec une grammaire comme celle-ci:

objectif: point d'exclamation "Bonjour" espace "monde";

Notez que les seules variations autorisées sont la façon dont le lexer correspond aux jetons.

(J'espère que la notation est évidente - c'est essentiellement celle que j'utilise dans Yacc ++. Les chaînes entre guillemets sont des jetons, tout comme les identificateurs qui ne sont pas définis.)

L'analyseur attend toujours la même séquence exacte de jetons. Il n'a pas besoin d'avoir une seule règle, comme notre premier exemple. Cela pourrait ressembler à ça.

objectif: hello-part whitespace end-part;

bonjour-partie: bonjour1;

hello1: "Bonjour";

partie finale: partie mondiale dernière partie;

partie du monde: "monde";

dernière partie: "!";

Cependant, notez qu'aucune des règles n'a d'opérateur "ou" (|) et qu'il n'y a qu'une seule règle par non-terminal. C'est ce qui permet à l'analyseur de savoir comment faire correspondre chaque règle sans utiliser de jetons discriminants (jetons qui choisissent la direction de l'analyseur), ce qui rend la grammaire LL (0).

Maintenant, est-il possible d'utiliser une production récursive tout en ayant une grammaire LL (0)? La réponse est non". Voyons ce qui se passe si nous avons une règle récursive.

objectif: "x" objectif "y";

Rappelez-vous, nous ne sommes autorisés qu'à une règle par non-terminal, et aucun opérateur "ou". Ainsi, lorsque nous arrivons à l'invocation récursive du but, nous devons nous emmener sur un chemin où nous reviendrons à cette invocation récursive, boucle infinie. Prouvez-vous, peu importe comment nous imbriquons cette invocation ou si la récursivité est indirecte. Il en résultera toujours une boucle infinie.

Ainsi, une grammaire LL (0) doit analyser une liste finie de jetons, exactement une liste finie (la même liste à chaque fois).

Notez la différence avec la signification de LR (0). Un analyseur LR (k) est autorisé à utiliser n'importe quel (autant qu'il le souhaite) jetons au sein d'une production pour discriminer, plus jusqu'à k jetons du contexte lorsque la production diminue pour déterminer s'il doit réduire. Dans le cas LR (0), il ne peut pas utiliser de jetons supplémentaires pour déterminer s'il doit réduire. Il doit simplement décider en fonction des jetons de la règle réduite. Voici une grammaire LR (0) simple:

objectif: "x" | "(" objectif ")";

Cette grammaire analyse un "x" entouré d'un certain nombre de parenthèses. Notez qu'il peut utiliser le jeton "x" et le jeton "(" pour décider de la règle à appliquer. Le 0 dans LR (0) ne restreint pas l'utilisation des jetons dans une règle, comme le 0 dans LL (0). La seule chose qu'elle restreint est l'utilisation de jetons (de contexte, après la règle dans une certaine utilisation du non-terminal) pour décider de réduire. Cette grammaire n'a pas besoin de contexte pour décider de réduire. Sur la première alternative, elle réduit en voyant un "x" sur le second il réduit après avoir vu un ")". Les jetons d'une règle déterminent exactement quand la règle doit être réduite.


Réponse 2:

Les analyseurs LL (0) signifient qu'ils traitent le flux de jetons de gauche à droite, en utilisant la dérivation la plus à gauche sans regarder en avant. Théoriquement, les analyseurs LL (0) sont possibles, mais même s'ils existent, je ne les vois pas très utiles. Les analyseurs LL (0) devraient prévoir les productions à appliquer en se basant sur le non-terminal actuel avec une perspective zéro. Dans de telles grammaires, chaque non-terminal ne peut avoir qu'une seule production associée et il ne devrait pas y avoir de récursivité.

Les analyseurs LR (0) signifient qu'ils traitent le flux de jetons de gauche à droite, en utilisant la dérivation la plus à droite avec un regard nul vers l'avant. Cela signifie qu'ils construisent l'arbre d'analyse de bas en haut, tandis que les analyseurs LL (0) construisent l'arbre d'analyse de haut en bas.