Limites des analyseurs LL vs LR?

Question

Je connais les différences fondamentales des analyseurs LL vs LR. Je sais aussi que GLR, SLR et LALR sont toutes des extensions de Parser LR. Donc ma question en plus de détails est ...

Étant donné un analyseur LL (*) et toute variation sur un analyseur LR, y a-t-il une langue qui peut être décrite dans l'un et non dans l'autre? Ou plus simplement y a-t-il une fonctionnalité ou une propriété qui ne peut pas être exprimée non plus?

Comme exemple concret. Si je devais créer une langue à l'aide d'un analyseur LL (*), vais-je jamais rencontrer la fonction / propriété souhaitée que je voudrais ajouter à ma langue qui ne serait possible qu'avec un analyseur LR (ou vice versa)?

Answer 1

Bien sûr. Les analyseurs LL ne peuvent gérer aucune grammaire avec une récursivité gauche. L (al) r (k) analyseurs pour k fixe ne pourra pas analyser certaines choses qu'un ll (*) L'analyseur peut gérer, car k <*.

Answer 2

Voici quelques éléments d'opinion, vous pouvez les considérer comme le point et le contrepoint:

• L'analyse doit être plus facile - en faveur de LL
• Pourquoi je préfère les analyseurs lalr - en faveur de LR

Answer 3

Vous pourriez trouver intéressant ce paragraphe dans Wikipedia, qui dit, que les grammaires LL (*) sont des sous-ensembles de grammaires LR (k):http://en.wikipedia.org/wiki/Context-free_grammar#restrictionsVous pouvez donc analyser plus de langues en utilisant des méthodes d'analyse LR.

Answer 4

Il y a des grammaires qui ne peuvent pas être "réécrites" à analyser par des analyseurs LL qui peuvent être analysés par des analyseurs LR. Un exemple: étant donné une grammaire simple qui construit des termes avec des substractions:

S -> S - S | num

Vous avez évidemment une rémunération à gauche ici, qui ne peut pas être gérée par LL-Parsers. Pour rendre cette grammaire analysée par LL, vous devez éliminer la rémunération à gauche:

S -> num S'

S' -> - num S' | epsilon

Maintenant, votre analyseur peut gérer cette grammaire. Mais lors de la construction de votre syntaxe pour un terme comme 4 - 2 -1, une recherche en profondeur d'abord opérée sur l'arbre vous donnera 4 - (2 - 1) = 3 au lieu de (4 - 2) - 1 = 3 comme vous vous en doutez.

La raison en est que vous devez utiliser des règles de rémunération gauche dans votre grammaire pour gérer les opérateurs d'association gauche (comme le soustraire). Mais les règles de restriction de gauche ne peuvent pas être gérées par des pakichés LL.

Vous avez donc ici une classe de langues qui ne peut pas être gérée par LL.

Answer 5

LR Parser peut accepter une classe de langues plus grande que LL. Dans LL (K) et LR (K), K signifie nombre de symboles de lookahead qu'il doit connaître afin qu'il puisse appliquer une production / réduction appropriée. Le plus gros K Get, plus les tables d'analyse sont plus grandes. Donc, K ne limite pas uniquement les analyseurs LR, il limite également LL. La raison pour laquelle l'analyseur LR peut accepter une plus grande classe de langues est due à une récursivité gauche qui est problématique lorsque vous travaillez avec des analyseurs LL. Mais ce n'est pas entièrement vrai, car la récursivité directe est résoluble, ce qui signifie que vous pouvez réécrire la grammaire pour être la grammaire. La récursivité directe est quelque chose comme un -> ABC. Lorsque vous avez une récursivité indirecte, pour laquelle vous savez maintenant probablement à quoi cela ressemble, vous avez un problème. Les analyseurs LR peuvent résoudre ces problèmes car ils fabriquent l'arbre de l'analyse de manière ascendante. Vous devrez avoir l'air un peu plus profondément dans l'analyse LR pour voir pourquoi c'est exactement. Mais, les analyseurs LR ne sont pas tous puissants, ils ont aussi des limites. Certaines grammaires sont très difficiles à digérer et le facteur K n'aide pas. Pour ce type de grammaire, un analyseur GLR est nécessaire, ce qui simule en fait l'analyseur LR (k) mais utilise du retour en arrière pour analyser l'espace d'analyse entier lorsque l'ambiguïté de production / réduction se produit.

Answer 6

L'analyse ll est théoriquement o (n ^ 4), ou assez dang. L'analyse LR est plus rapide, o (n ^ 3), ou assez lent.https://en.wikipedia.org/wiki/top-down_parsing

Bien que j'aimerais voir la preuve de cela.