Re: OOP Parse tree generation?

"Floris 'Tamama' van Gog" <>
23 Mar 2000 03:28:14 -0500

          From comp.compilers

Related articles
OOP Parse tree generation? (Nicolas) (2000-03-11)
Re: OOP Parse tree generation? (Quinn Tyler Jackson) (2000-03-21)
Re: OOP Parse tree generation? (Floris 'Tamama' van Gog) (2000-03-23)
Re: OOP Parse tree generation? (Tom Payne) (2000-03-23)
Re: OOP Parse tree generation? (Nicolas Ojeda Bar) (2000-03-23)
Re: OOP Parse tree generation? (2000-03-23)
Re: OOP Parse tree generation? (George Nelan) (2000-03-23)
Re: OOP Parse tree generation? (Daniel C. Wang) (2000-03-25)
Re: OOP Parse tree generation? (Chris F Clark) (2000-04-03)
[1 later articles]
| List of all articles for this month |

From: "Floris 'Tamama' van Gog" <>
Newsgroups: comp.compilers
Date: 23 Mar 2000 03:28:14 -0500
Organization: XS4ALL Internet BV
References: 00-03-074
Keywords: parse, OOP

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
        enum typeId
                /* all kinds of types here..
                        - if/then/else
                        - operations (+ - / * = | & )
                        - function (call)
                        - while

        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
        NodeOperator(char op,NodeBase *leaf1,NodeBase *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 ||
                        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

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


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 :-)


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]

Post a followup to this message

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