Re: Object-oriented compiler construction: ideas?

>> a class for each non-terminal in the grammar.
>> The problems that I saw with this approach is the proliferation of
>> lots on non-important classes corresponding to the needs of the
>> concrete syntax to be LALR(1) (I was using yacc). I got into a maze
>> of lots of little methods all alike, but syntactically dispersed
>> because each of them needed to be a method.


>I am using the polymorphic approach myself, one class for each type of
>node occuring in the parse tree. The problem stated by Darius Blasbans
>is handled best by using the `Visitor pattern'. The node classes then
>need only one method: `accept(Visitor)'. The burden is moved to the
>abstract visitor class and its concrete derived classes, but the logic
>of the code gets less dispersed.


The idea of object oriented parsing and attribute evaluation has been
around quite awhile. We (Ribbit Software Systems Inc) have done quite abit
of investigation into these designs and have found that the most effective
method is to create a class for each nonterminal and a class for each rhs
of a nonterminal with appropriate derived classes for specific instances
in the grammar of each. The problem of too many methods arising due to
using yacc is easily avoided: don't use yacc. The actual parsing code is
part of each object. It knows how to choose its own right hand side by
looking ahead zero or more tokens. This turns out to be much faster
(when optimized) than a table driven parser such as yacc or bison.


The attribute evaluation can then easily be demand or
data driven. For an outline of this, I refer to the invited address by
Dr. Watson ("Trends in Compiler Construction", ISBN 0869819097) at the
Conference of the South African Institute for Computer Scientists and
Information Technologists 1995 (SAICSIT'95). These ideas have bbeen
implemented and benchmarked over the past year here at Ribbit and we have
found it possible to make such an approach at least as fast as traditional
compiler techniques after some profiling showed the problem areas.
If you have any comments on this approach please post or email me.


------------------------------------------------------------------------------
Richard E. Watson (Compiler Architect) | E-mail: rwatson@RibbitSoft.com
Ribbit Software Systems Inc. | Tel: + 1 (604) 762-6591
| FAX: + 1 (604) 762-6511
| or + 1 (514) 938-9308
| Address: Box 24040, 297 Bernard
| Kelowna, B.C.
| V1Y 9P9, Canada


--

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