Re: Object Oriented Compiler Design Problem

On 5 Sep 1998 01:20:58 -0400, mayurnaik@my-dejanews.com wrote:


>#1 term : term '+' primary { ??? }
>I want a suitable Object Oriented Solution to this problem. I want to avoid
>the solution using 'a union with a type field'. Also, would RTTI be a
>suitable solution? Does it not impose a large overhead?


In other words, you want to know what kind of objects were returned
by $1 and $3. You haven't asked to know this elsewhere in your
code, but you will probably need to - how else would you know
what to do with the AST leaves? But anyway, to answer your
question directly:


      return a pair from "term" and "primary". Right now you're
      return just a symbol object. Instead, return a tuple that
      contains as its first part an enum that gives the kind of
      returned value, and what you're returning now as its
      second part.


      In other words, use that data structure that you apparently
      detest - the tagged union - not as part of your tree, but
      as the $$ returned value. Then, in the "term" action
      routine, you can make the test for the kind of value
      you have, and store it anonymously into the symbol
      table.


If this is not to your liking, or if you realize that what you are
eventually going to need is just exactly what you are shuning (the
tagged union, or RTTI) - then you can implement it by hand in your
class, without needing to bring in all the RTTI overhead (which is not
really all that bad, if you use it everywhere, but which is a waste if
you use it in just one or two classes). I do this when I'm stuck with
C++ as an implementation language and am forced to use it by
unenlightened management. Here's the basic idea:


class Symbol
{
public:
        enum SYMBOL_TYPE { CONSTANT, VARIABLE };
        virtual SYMBOL_TYPE Type() = 0;
        ....
};


class Constant : public Symbol
{
public:
        SYMBOL_TYPE Type() { return CONSTANT; }
        ....
};


class Variable : public Symbol
{
public:
        SYMBOL_TYPE Type() { return VARIABLE; }
        ....
};


In other words, you implement RTTI by hand for just the classes that
need it. What you are really doing, of course, is using the vtable to
hold a dynamic type identifier that can't get out of sync with its
data.


And this is the only problem with using tagged unions in C++: what's
to make the tag be the right one for the contained data? If there
were a way to do that, then tagged unions would be great - in fact,
they are just exactly what you need in cases like this, that abound in
compiler implementation. One reason I like ML and Ocaml so much is
that they implement tagged unions correctly - in a way that guarantees
that the contained data is the right stuff:


      let symbol = Constant of int | Variable of (string, int);


When you look at a symbol, if it says it's a Constant, then by God,
it's a Constant. No two ways about it. C++, on the other hand, lets
you down bigtime. That's why I do the trick above: it doesn't take
much runtime space or time, it's easy to do, it works.


But give me a decent language any day over forced hacks like this.


Dwight
--

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