J'ai besoin d'analyser les expressions algébriques pour une application que je travaille sur et espérez-vous garnir un peu de sagesse collective avant de prendre une fissure et, éventuellement, en descendant la mauvaise route.
Ce que je dois faire est assez simple: étant donné une expression algébrique textuelle (3 * x - 4 (y-péché (PI))) créer une représentation d'objet de l'équation. Les objets personnalisés existent déjà, j'ai donc besoin d'un analyseur qui crée un arbre que je peux marcher pour instancier les objets dont j'ai besoin.
Les exigences de base seraient:
Capacité à exprimer l'algèbre en tant que grammaire, donc j'ai le contrôle et peut personnaliser / l'étendre si nécessaire.
La syntaxe initiale comprendra des entiers, des nombres réels, des constantes, des variables, des opérateurs arithmétiques (+, -, *, /), des pouvoirs (^), des équations (=), des parenthèses, une priorité et des fonctions simples ( péché (PI)). J'espère étendre mon application assez rapidement pour prendre en charge les fonctions propres (f (x) = 3x +2).
doit compiler en C car elle doit être intégrée à mon code.
Je n'ai pas besoin d'évaluer l'expression mathématiquement, de sorte que les logiciels qui résolvent pour une variable ou effectuent l'arithmétique est le bruit.
J'ai fait mes devoirs Google et il semble que la meilleure approche consiste à utiliser une grammaire et un logiciel BNF pour générer un compilateur en C. Donc, mes questions:
Une grammaire BNF avec un générateur d'analyseurs correspondant pour expressions algébriques (ou mieux encore, la latex) existe déjà? Quelqu'un doit déjà l'avoir fait. Je veux vraiment éviter de rouler le mien, principalement parce que je ne veux pas le tester. Je serais prêt à payer un montant raisonnable pour une bibliothèque (moins de 50 $)
Sinon, quel générateur de parser pour c es-tu pensez-vous est le plus facile à apprendre / utiliser ici? Lex? YACC? Flex, Bison, Python / Sympty, Autres? Je ne connais aucun de ceux-ci.
4 Réponses :
J'ai eu de très bonne chance avec antlr . Il a des actes de temps pour de nombreuses langues différentes, y compris C, et possède une très belle syntaxe pour spécifier des grammaires et des arbres de construction. J'ai récemment écrit une grammaire similaire (expressions algébriques) dans 131 lignes, qui est définitivement gérable.
J'ai passé du temps à regarder Antlr aujourd'hui. Avez-vous pu travailler autour de questions «mutuellement restrutives» pour les équations imbriquées? Par exemple. Le dénominateur d'une fraction peut lui-même être un terme complexe (4 / (c * (((1 + 1) / 2)), etc.
L'analyseur que j'ai en fait analyser cette expression très bien. Fondamentalement, au niveau supérieur, vous avez les opérateurs de la priorité les plus faibles, puis vous passez votre chemin dans la production d'Atom, qui peut être un nombre, un identifiant ou une expression parententhèses. Étant donné que le dénominateur de la fraction avec le numérateur "4" s'ouvre avec une paren gauche, il n'y a pas d'ambiguïté.
Les outils Linux standard Flex et Bison seraient probablement très appropriés ici. IIRC Les échantillons d'analgésiques et de lexeurs utilisés dans ces outils font quelque chose de près de ce que vous voulez, vous pourrez peut-être simplement modifier ce code pour obtenir ce dont vous avez besoin.
Ces outils semblent avoir répondu à vos spécifications. Vous pouvez personnaliser les grammaires, compiler jusqu'à C et utiliser n'importe quel opérateur que vous souhaitez.
Vous pouvez construire vous-même un analyseur simple vous-même ou utiliser l'un des " compiler-compilateur " (Certains d'entre eux ont été répertoriés par d'autres messages). Décidez simplement si votre analyseur sera suffisamment compliqué pour utiliser (et apprendre) un outil externe. En tout état de cause, vous devrez définir la grammaire, il s'agit généralement de la tâche intense la plus du cerveau si vous n'avez pas d'expérience préalable. Le moyen formel de définir les grammaires syntaxiques est BNF ou ebnf
J'ai utilisé le code (trouvé sur le net) parmi les suivants:
Principes fondamentaux de la traduction du programme "de Peter Calingaert
Je l'ai amélioré pour gérer les fonctions, ce qui vous permet de mettre en œuvre des choses comme "si (a, b, c)" (genre comme comment Excel fait des choses).
Comme alternative à lexx / YACC, vous pouvez essayer l'algorithme de coureurs de la cour de Dijkstra: en.wikipedia.org/ wiki / shunting-yard_algorithm Cet article de Wikipedia contient un exemple dans C.
J'ai trouvé ce dont j'avais besoin ici: http://www.codeproject.com/kb/recipes / Sota_Expression_evalua Tor.aspx Merci à tous pour les commentaires réfléchis! -David
En fait, cela a fini par être beaucoup plus utile que cela montre comment construire l'arborescence: cs.man.ac.uk/~pjj/cs211/ho/node8.html
Lorsque vous incluant des liens vers des sources externes dans votre réponse, assurez-vous toujours d'inclure les parties importantes de cette source ainsi que de votre réponse, car les liens pourraient mourir au fil du temps.