evaluating parse tree's
Author
im wondering what the best way to evaluate a parse tree is.
im writting my own script language just for the hell of it, and im stuck wondering the best way to evaulate it.
my first thought was to provide a function Evaluate on my parse tree nodes but im thinking im gonna need to return some value in some cases so this value can be used higher up the tree to calulate the final result.
any one have any suggestions?
What's wrong with Evaluate returning a value in every case? For a simple evaluator this can work fine:
Although I'm sure that there are many more advantages to using the Visitor pattern here, I think it could be overkill for a simple expression evaluator.
class node{public: node(node *l=0,node *r=0) : ln(l),rn(r) { } virtual ~node(){ delete ln; delete rn; } virtual int eval()=0; node *ln,*rn;};class lit_n : public node{public: lit_n(int v) : val(v) { } int eval(){ return val; } int val;};class add_n : public node{public: add_n(node *l,node *r) : node(l,r) { } int eval(){ return ln->eval()+rn->eval(); }};class neg_n : public node{public: neg_n(node *l) : node(l) { } int eval(){ return -ln->eval(); }};Although I'm sure that there are many more advantages to using the Visitor pattern here, I think it could be overkill for a simple expression evaluator.
Author
in your example you return an int, i want always want to return an int, but i do have a 'variable' structure which supports all types. Problem is will evaluate always return a 'variable'?
I'll briefly mention boost.spirit and move on. Everyone mentioned the OO way, I’ll suggest another way possible in C++ (well just about), the functional way to represent a parse tree/AST is to use algebraic data types (instead of sub typing), case analysis & pattern matching (instead of using the visitor pattern), and representing parsers with functions who have first-class status.
So how can you emulate that in C++?
Algebraic data types & case analysis using boost::variant with "static visitors" or do it the fugly way with your own hand crafted tagged unions. Go through the boost::variant examples and it will eventually click for you.
Parsers as (higher-order) functions with first-class like status. You can use techniques such as expression templates to emulate higher-order functions which can also be combined and passed around, use functional objects (a user-defined type with the functional call operator overloaded).
So how can you emulate that in C++?
Algebraic data types & case analysis using boost::variant with "static visitors" or do it the fugly way with your own hand crafted tagged unions. Go through the boost::variant examples and it will eventually click for you.
Parsers as (higher-order) functions with first-class like status. You can use techniques such as expression templates to emulate higher-order functions which can also be combined and passed around, use functional objects (a user-defined type with the functional call operator overloaded).
Quote:Original post by EasilyConfused
What's wrong with Evaluate returning a value in every case? For a simple evaluator this can work fine:
*** Source Snippet Removed ***
Although I'm sure that there are many more advantages to using the Visitor pattern here, I think it could be overkill for a simple expression evaluator.
Problem with that little psuedo code is that: a useful tree will be more than binary, and if you have types other than int's your screwed.
Consider a node for WHILE construct. It would have a child node for the relational expression, a child node for the statement nodes in the loop, and a pointer to the statement node immediately following the WHILE loop. A FOR construct would have four children.
If you want to execute from the parse tree, then you'll have to setup some kind of execution environment: like 'registers' to hold intermediate values of different types OR pass have each node return a UNION of some form or another.
This is the place I'm at in my language explorations.
Quote:Original post by Anonymous PosterQuote:Original post by EasilyConfused
What's wrong with Evaluate returning a value in every case? For a simple evaluator this can work fine:
*** Source Snippet Removed ***
Although I'm sure that there are many more advantages to using the Visitor pattern here, I think it could be overkill for a simple expression evaluator.
Problem with that little psuedo code is that: a useful tree will be more than binary, and if you have types other than int's your screwed.
Consider a node for WHILE construct. It would have a child node for the relational expression, a child node for the statement nodes in the loop, and a pointer to the statement node immediately following the WHILE loop. A FOR construct would have four children.
If you want to execute from the parse tree, then you'll have to setup some kind of execution environment: like 'registers' to hold intermediate values of different types OR pass have each node return a UNION of some form or another.
This is the place I'm at in my language explorations.
So you'd move the nodes into each derived class instead of the base:
class node{public: virtual ~node(){ } virtual int eval()=0;};class lit_n : public node{private: int val;public: lit_n(int v) : val(v) { } int eval(){ return v; }};class add_n : public node{private: node *ln,*rn;public: add_n(node *l,node *r) : ln(l),rn(r) { } ~add_n(){ delete ln; delete rn; } int eval(){ return ln->eval()+rn->eval(); }};class neg_n : public node{private: node *nn;public: neg_n(node *n) : nn(n) { } ~neg_n(){ delete nn; } int eval(){ return -nn->eval(); }};In terms of the return value, I believe snk_kid has already mentioned the boost::variant or the joy of hand-coding your own union statement with a type-switching field.
To be honest, my code is based more on my experience of writing compilers that spit out virtual assembly to resolve the expression later in a virtual machine in which case the eval() function requires no return value and you just add a virtual get_type() member that is delegated down to leaf nodes by the operator nodes.
This has the advantage that you can build an expression tree first, then check it for type-compatibility errors as a second stage via a virtual and recursive check() method rather than worring about types as you are parsing. It's just my approach though.
Perhaps if writing a tree to evaluate from directly, a different approach with the return value is required.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
