Comment déterminer si une grammaire est LR (n), LL (n)

Question

Pour une langue qui n'est pas LL(1) ou LR(1) comment peut-on essayer de savoir si un certain nombre n existe de telle sorte que la grammaire peut être LL(n) ou LR(n)?

Vous vérifiez si une grammaire est LR(0) en regardant la collection canonique de LR(0) éléments. Ensuite, en supposant que ce ne soit pas LR(0), vous pouvez vérifier s'il s'agit du LR(1) en introduisant le symbole de lookahead. Mon raisonnement simple me dit que, pour vérifier si c'est LR(2) ou non, vous devez probablement faire en sorte que le lookahead contienne les deux symboles suivants au lieu d'un seul.

Même si c'est le cas, même si j'en doute, je me bats pour penser à comment peut-on essayer n, ou la non-existence de celui-ci, pour lequel une grammaire spécifique peut être LR(n) et/ou LL(n) sans vérifier de manière incrémentielle à partir d'un LR(m) arbitraire vers le haut.

Answer 1

1. Si une langue estLR (k ) pour certains k > 1, alors il est LR (1). (Ce n'est pas vrai pour une grammaire, bien sûr.) Autrement dit, si vous avez une grammaire LR (k) pour une langue, alors vous pouvez construire mécaniquement une grammaire LR (1) qui vous permet de récupérer l'arbre d'analyse original . Ceci n'est pas vrai de LL (k); LL (k) les langues sont un sous-ensemble strict de LL (k +1).

2. Le test que vous proposez sera en effet vous permettre de décider si une grammaire est LR (k ) pour un k donné (ou LL (k )). Malheureusement, il n'y a aucun moyen de trouver la plus petite valeur possible de k autre que la recherche successive que vous proposez, et il n'y a aucune garantie que la recherche se terminera jamais. Bien que le problème soit difficile (ou impossible) dans le cas général, il peut souvent être répondu pour des grammaires spécifiques, en considérant les éventuels successeurs valides d'un état de grammaire qui présente des conflits.

Dans la plupart des grammaires du monde réel, il n'y aura que quelques conflits, de sorte qu'un examen manuel des états conflictuels est possible. En termes généraux, il faut déterminer le chemin qui mène à l'état conflictuel, et les continuations possibles. Dans de nombreux cas, il sera clair que le conflit d'analyse pourrait être résolu avec un peu plus d'anticipation.

Une grande classe de grammaires où cela échouera est l'ensemble des grammaires ambiguës. Une grammaire ambiguë ne peut pas être LR (k) (ou LL (k)) pour k. Encore une fois, la question de savoir si une grammaire est ambiguë n'est pas décidable mais il existe des heuristiques efficaces, dont certaines sont incluses dans les produits commerciaux. Encore une fois, il est souvent facile de trouver des ambiguïtés dans les grammaires du monde réel, soit par inspection visuelle (comme ci-dessus), ou en alimentant beaucoup de textes valides dans un analyseur GLR (tel que celui produit par bison) jusqu'à une ambiguïté est signalée.(Alternativement, vous pouvez énumérer des textes valables de la grammaire avec un algorithme simple, et voir si un texte apparaît deux fois dans l'énumération.)

Voici quelques questions de SO possibles illustrant des techniques d'analyse. Je suis sûr qu'il y en a plus.

A yacc shift/reduce conflict on an unambiguous grammar

Bison reduce/reduce situation

yacc shift-reduce for ambiguous lambda syntax

How to understand and fix conflicts in PLY