Re: OOP Parse tree generation?

Well here goes my first reply ever :)


You could have a base node of which you derive all other nodes. This
base node then could have an identifier of what kind of node it is, as
well as virtual functions for comparisons (maybe used for CSE?)
The downside to this design is that you need to possible typecast from
the base class up to a child of this base class, of which the type is
determined by the identifier in the base class. HM, maybe i lost myself
here :)


( all real functionality ommited for simplicity )


class NodeBase
        {
protected:
        enum typeId
                {
                ntNone=0
                /* all kinds of types here..
                        - if/then/else
                        - operations (+ - / * = | & )
                        - function (call)
                        - while
                */


                ntConstant,
                ntOperator
                }type;
public:
        NodeBase(typeId t) { type=t; }
        virtual ~NodeBase() {} // possible pure virtual


        virtual bool operator == (NodeBase *comparenode)
        // could be used for getting CSE's and create a DAG
                {
                return type==comparenode->type;
                }
        };


Then for example an 'operator node' would be:


class NodeOperater:public NodeBase
        {
        char operator; // for our example just '+' '-' '=' etc
        NodeBase *arg1; // x + y => x = arg1
        NodeBase *arg2; // x + y => y = arg2
public:
        NodeOperator(char op,NodeBase *leaf1,NodeBase *leaf2):
                NodeBase(ntOperator)
                {
                arg1=leaf1;
                arg2=leaf2;
                }
        bool operator == (NodeBase *t)
        // this function assumes you have a DAG and each 'argument'
        // (identifier/constant) can only appear once.
                {
                if (!(*((NodeBase *)this)==t))
                        return false;


                // previous compare made sure it's a correct type
                NodeOperator *to=(NodeOperator *)t;


                if (operator!=to->operator ||
                        arg1!=to->arg1 ||
                        arg2!=to->arg2)
                        return false;


                return true;
                }
        };


In this design each individual node only knows how to handle it's own
type, and of course the result (ie variable/constant/nothing) of
possible child-nodes, but not it's implementation. Also the storage-size
per node is reasonable as each node does not occupy more than needed.


Then inserting a x+a would result in:
(simplified example, you would probably have some 'insert_leaf()'
function that makes sure nodes dont occur multiple times etc)


NodeBase *arg1=new NodeIdentifier("x"); // guess ;-)
NodeBase *arg1=new NodeIdentifier("a");
NodeOperator *op=new NodeOperator('+',arg1,arg2);


The Parser itself can have a modified version of Term()/Factor() (most
people seem to be using something similair like this :) that returns a
NodeBase * (which can be a complete tree of Node's, but that doesn't
matter at all). Then the parser itself gets simplified as well in the
process.


A nice touch would be to have a node retrieve it's final result by
itself, so that for example:


startnode->RetrieveResult()


would compile/interpret/typecheck/whatever your entire parse tree.


I'm not saying it's the best or ultimate way, but it IS a way :-)


  Floris


PS: i wrote this in my email client for this reply, so uuh.. if there's
an error.. there's an error :)


Nicolas wrote:
>
> Hi,
>
> How would you implement parse tree structures for a language that has
> statements and expressions (a la Pascal), in an object oriented fashion ?
>
> TIA,
>
> Nicolas
> [Good question. I've never seen a very satisfactory OOP design for a
> parser. -John]

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