Est-il plus facile d'écrire un analyseur récursif-descendant en utilisant un EBNF ou un BNF?

Question

J'ai un BNF et un EBNF pour une grammaire. La BNF est évidemment plus verbeuse. J'ai une assez bonne idée en ce qui concerne l'utilisation de la BNF pour construire un analyseur récursif-descendant; il y a beaucoup de ressources pour cela. J'ai du mal à trouver des ressources pour convertir un EBNF en un analyseur récursif-descendant. Est-ce parce que c'est plus difficile? Je me souviens de mes cours de théorie CS que nous avons passés en revue les EBNF, mais nous ne les avons pas convertis en un analyseur récursif-descendant. Nous avons fait passer sur la conversion de BNF en un analyseur récursif-descente.

La raison pour laquelle je demande est parce que le EBNF est plus compact. En regardant les EBNF en général, je remarque que les termes inclus entre { et } peuvent être convertis en une boucle while. Y a-t-il d'autres directives ou règles?

Answer 1

Aucun des deux n'est plus dur que l'autre. C'est vraiment la différence entre implémenter quelque chose de manière itérative et implémenter quelque chose de manière récursive. Dans BNF, tout est récursif. Dans EBNF, une partie de la récursivité est exprimée itérativement. Il y a différentes variations dans la syntaxe EBNF, donc je vais juste utiliser l'anglais ... "zero or more" est une simple boucle while comme vous l'avez découvert. "Un ou plusieurs" est le même que celui suivi par "zéro ou plus". "Zéro ou une fois" est une simple instruction if. Cela devrait couvrir la plupart des cas.

Answer 2

Vous devriez étudier ce qu'on appelle metacompilers, qui compile essentiellement EBNF dans des analyseurs de descente récursifs. Comment ils le font est exactement la réponse à votre question. (Son assez straightfoward, mais bon à comprendre les détails).

Un papier vraiment merveilleux est le papier "MetaII" de Val Schorre. Il s'agit de la technologie métacompiler de 1964. En 10 pages, il vous montre comment construire un métacompilateur, et fournit non seulement cela, mais aussi un autre compilateur et la sortie des deux! Il y a un moment étonnant où vous venez aussi si vous allez en construire un, où vous avez réalisé comment le méta-compilateur se compile en utilisant sa propre grammaire. Ce moment m'a attrapé accroché sur le compilateur dans environ 1970 quand j'ai d'abord trébuché sur ce papier. C'est un de ces papiers d'informatique que tout le monde dans le logiciel devrait lire. James Neighbours (l'inventeur du terme «domaine» en génie logiciel, et constructeur du premier système de transformation de programme [basé sur ces métacompilers] a un grand MetaII tutorial en ligne, pour ceux d'entre vous qui ne veulent pas le faire -IT-from-scratch expérience. (Je n'ai rien à voir avec cette exception que Neighbours et moi étions étudiants de premier cycle en même temps).

Les deux façons sont une bonne façon d'en apprendre davantage sur metacompilers et générer des parseurs de EBNF.

Les idées clés sont que le côté gauche d'une règle crée une fonction qui analyse cette non-terminale et renvoie true si elle correspond et avance le flux d'entrée, false si aucune correspondance et le flux d'entrée ne progresse pas. Le contenu de la fonction est déterminé par le côté droit. Les jetons littéraux sont appariés directement. Les non-terminaux provoquent des appels à d'autres fonctions générées pour les autres règles. Kleene * est mappé aux boucles while, les alternatives sont mappées aux branches conditionnelles. Qu'est-ce que EBNF ne traite pas, et les méta-compilateurs font, est-ce que l'analyse syntaxique fait autre chose que de dire "apparié" ou non? Le secret est le tissage des opérations de sortie dans l'EBNF. Le papier MetaII rend tout ce cristal clair.

Answer 3

Les premiers méta-compilateurs META II et TREEMETA et leurs parents ne sont pas exactement l'analyseur syntaxique correct récursif. Ils ont été déclarés comme utilisant des fonctions récursives. Cela signifiait juste qu'ils pourraient s'appeler eux-mêmes. Nous n'appelons pas C un langage récursif. Une fonction C ou C++ est récursive de la même manière que les premiers méta-compilateurs sont récursifs.

La récursivité peut être utilisée. Ils étaient des langages de programmation. La récursivité est généralement utilisée uniquement lors de l'analyse des constructions de langage suivant. Par exemple expression entre parenthèses et blocs suivis.

Plus d'une combinaison LR récursive décente. Le CWIC, le dernier documenté, possède de nombreuses fonctions de retour en arrière et d'anticipation. L'opérateur '-' not peut correspondre à n'importe quelle construction de langage. Et inverse le succès ou l'échec. -term échoue si un terme est apparié par exemple. L'entrée n'est jamais avancée. Le '?' regarde vers l'avant et correspond à n'importe quelle construction de langage? expr par exemple essayerait d'analyser une expression. L'avenir "?" la construction appariée n'est pas conservée ou est l'entrée avancée.