Re: Question: Symbolic Mathematical Processing (Parsing) Methodologies

v148rb5b@ubvms.cc.buffalo.edu (COLLIN MCCULLEY) writes:
> The goal here is to allow these expressions to be
> entered interactively and changed at will, without having the functions
> being optimized built in to the code and recompiled each time these
> functions change.


> [I'd suggest compiling into a tokenized reverse polish and interpreting that.
> -John]


I agree with John that interpreting a stack-based intermediate form is a
good idea, but thought I might suggest an equally reasonable approach:


When you parse the input, build a tree with the operators at the root.
Then, walk the trees to compute the value. For example,


3+4*5 would yield:


                      +
                    / \
                  3 *
                        / \
                      4 5


Writing a function that walks this tree to compute "23" is trivial.


Collin, for you info, there are many tools to help you automate this
process. Tools like Puma, COCOL, Ox, NewYacc can be incorporated into
your application (there are many other cool tools that cannot be as easily
integrated). Check the monthly listing of languages and language tools in
this newsgroup for details on the tools. SORCERER (to be released this
coming weekend) is also well suited to this problem. For example, a
description to walk simple trees of the type I gave above can be done as
follows:


/* tell me what an AST node looks like */
#header <<typedef { int token, val; struct _ast *down, *right; } AST;>>


<<#include "mytokendefs.h">>


/* read: "eval is a rule w/no args returning an int" */
eval > [int]
        : <<int a, b;>> /* define local variables */
                #(Plus eval>[a] eval>[b]) <<_RETURNVAL(a+b);>>


        | <<int a, b;>>
                #(Mult eval>[a] eval>[b]) <<_RETURNVAL(a*b);>>


        | v:Int <<_RETURNVAL(v->val);>>
        ;


where actions are in <<...>> and #(root child1 ... child2) is a tree
specification in LISP-like notation and "eval>[a]" calls rule 'eval' and
puts the result into variable 'a'.


By the way, our parser generator ANTLR builds expression trees
particularly easily:


#header <<
#include "charbuf.h"
/* define what's in an AST node and how to make one */
#define AST_FIELDS int val;
#define zzcr_ast(node, cur, _tok, _text) {(node)->val=atoi(_text);}
>>


expr : mexpr ( "\+"^ mexpr )* ;
mexpr: atom ( "\*"^ atom )* ;
atom : "[0-9]+" ;


where the ^ suffix-operator indicates that the preceding token should be
made the root of the current subtree. Any other token is made a sibling
of the current subtree as it's matched.


Hope this helps,


Terence Parr
U of MN
--

Return to the comp.compilers page.
Search the comp.compilers archives again.