Object Oriented Compiler Construction

drh@world.std.com (Richard Hipp) writes:
> It occurs to me that inheritance should be especially useful in the
> construction of a parse tree. In a traditional compiler (written in C),
> each node of a parse tree is usually a structure with a large variant
> section which depends upon the type of the node. For example:
>
> struct parse_tree_node {
> int type;
> union {
> struct {}; /* Information when type==1 */
> struct {}; /* Information when type==2 */
> struct {}; /* Information when type==3 */
> /* And so forth... */
> } u;
> };
>
> A better way to do this, it seems to me, is to define an abstract class
> for parse tree nodes, and then subclass specific node types from the
> abstract base class. I envision member functions like SanityCheck(),
> Optimize(), and GenerateCode() which take very different (though
> conceptually identical) actions for each node subclass.
>
> It also seems to me that something other than yacc and lex should be used
> for the parser. This venerable old tools have served us well, but their
> design is beginning to show its age. Upgrades like yacc++ and lex++ don't
> seem to help much since it is the basic design of the tools, not their
> implementations, which seems to be at fault.


Your conceptual approach is sound and was first described (to my
knowledge) by Steve Johnson in the paper "Yacc meets C++", which describes
roughly how to modify yacc to generate the classes you propose
automatically by extending the annotations to the grammar. One of the
companies I work for is readying a commercial release of a product which
incorporates these ideas (and many other object-oriented ideas--perhaps
the moderator can add a reference to one of the preceeding posts in the
comp.compilers archives which outlined them). A related idea "visitors"
which I learned of from Ralph Johnson, shows how to separate some of the
member functions into classes not related to the parse tree, making the
adding of additional tree traversal passes easier.


On a related note, I presume the "yacc++" you refer to was supplied to you
by the vendor of your C++ compiler or by your OS vendor. That tool is
misnamed. "Yacc++" is registered trademark and is only available from its
authors and authorized resellers. (I don't mean to flame you by the
comment. I'm just trying to correct a common misapprehension caused by
vendors adding a few prototypes (and/or class wrappers) to yacc and then
calling it "yacc++" and thus infringing on our trademark. I think I
understand how the Kleenex and Xerox people must feel.)


Best regards,
Chris Clark


Disclaimer: I work on "Yacc++(R) and the Language Objects Library" and I
work for
Compiler Resources, Inc.
85 Main St, Suite 310
Hopkinton, MA 01748
(508) 435-5016 (voice)
(508) 435-4847 (fax)
bz%compres.UUCP@primerd.cv.com (internet)
--

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