Convertir la grammaire BNF en Java

Question

Comment puis-je convertir cette grammaire simple (récursive) en Java?

C --> a | not C | C and C | C or C ; 

Cette question ne vise pas quel outil je dois utiliser pour analyser une grammaire (comme javacc ou Antlr), mais la façon de modèle cette grammaire simple en utilisant le paradigme orienté objet.

Answer 1

Je ne pense pas qu'il existe une seule façon de modéliser ceci en utilisant la POO et qu'il existe de nombreux moyens tout aussi valables d'aborder cette question. Ce qui suit est une stratégie raisonnable pour penser à quoi cela pourrait ressembler dans le code.

Habituellement, lors de l'analyse d'une expression, votre objectif est de reconstruire un arbre de syntaxe abstraite pour l'entrée. Cette structure arborescente a différents types de nœuds basés sur les différentes productions possibles, et en Java, vous les représenteriez probablement avec un type polymorphe. Par exemple, vous pouvez avoir une classe de base ASTNode qui a des enfants ANode, NotNode, AndNode et OrNode. Ces trois derniers types stockent des pointeurs vers les sous-expressions qui composent l'expression composée. Une fois que vous avez ces types, vous devez alors assembler une sorte d'analyseur - et éventuellement un scanner - qui prendrait l'entrée et construirait l'arbre approprié à partir de celui-ci. Puisque vous regardez une grammaire qui consiste en différents opérateurs avec des priorités différentes, vous pouvez utiliser un analyseur de précédence simple comme Dijkstra's shunting-yard algorithm pour faire l'analyse. Cet algorithme est relativement simple à mettre en œuvre.

À ce stade, cela dépend vraiment de ce que vous voulez faire avec l'AST. Si vous souhaitez évaluer l'expression en fonction des entrées fournies, par exemple, vous pouvez ajouter une méthode abstraite evaluate au type ASTNode, puis demander à chaque type dérivé de fournir une implémentation qui effectue l'opération appropriée. Vous pouvez également envisager d'utiliser le modèle de visiteur pour générer des visiteurs qui parcourent l'AST et effectuer les opérations appropriées à chaque étape.Je ne sais pas si cela serait utile, mais il y a quelques temps, j'ai écrit quelque chose de très similaire à ce que vous cherchez à générer des tables de vérité pour la logique propositionnelle pour une classe que j'enseigne souvent. L'outil lui-même est available here et les fichiers source, qui sont correctement commentés, sont available here. Il est écrit en JavaScript plutôt qu'en Java, mais il montre toutes les pièces décrites ci-dessus - le type de nœud AST, l'algorithme de shunt-yard pour faire l'analyse, et les méthodes surchargées pour évaluer les différentes expressions.

Answer 2

Ceci est une question très large à répondre sans mentionner réellement des outils spécifiques car votre implémentation de n'importe quelle grammaire pourrait se produire d'un grand nombre de façons selon la langue que vous choisissez pour implémenter votre analyseur dans ... si vous regardez le source d'outils tels que ceux que vous avez mentionnés ANTLR et Javacc, il révélera comment les autres ont mis en œuvre leurs outils et les techniques qu'ils ont utilisées pour développer des analyseurs top-down, mais juste parce que c'est la seule façon.

La BNF est utilisé seulement pour donner une manière formelle de décrire la structure de la langue:

Ils sont appliqués chaque fois que des descriptions exactes des langues sont nécessaires: par exemple, dans les spécifications de langue officielle, dans les manuels , et dans manuels sur la théorie du langage de programmation.

Comme ils ne sont utilisés que pour donner une ventilation de ce qu'on attend d'entrée son au programmeur de décider comment cela est mis en œuvre avec les outils linguistiques et APIs pour les mettre à disposition que ce soit regex est dans java ou chaîne recherches ou tokenisation fourni par une autre langue son malheureusement malheureusement votre choix de décider alors vous travaillez avec un outil spécifiquement pour générer un analyseur pour votre langue à quel point nous pourrions répondre à cette question si cela a du sens.