Re: References to object oriented design of compilers?

newton@cs.utexas.edu (Peter Newton):
> Does anybody know of any publications on the subject of object-oriented
> design applied to compilers?


johnson@cs.uiuc.edu (Ralph Johnson) writes:
> The idea that every rule in the abstract syntax becomes a class is a
> classic one, but doesn't seem to be documented anywhere.


> A common problem with this approach is that the classes representing AST
> nodes get cluttered with a lot of code that is very specialized. In
> Smalltalk, for example, there is code for pretty printing, flow analysis,
> and so on. One way to move this code out of the main AST classes and into
> applications is to use a design technique called a Visitor, or tree
> walker, or tree node enumerator. This technique is a form of double
> dispatching. The idea is to give each node a "handle:" method, which a
> node of type Foo implements as:


> handle: aVisitor
> ^aVisitor handleFoo: self


> The Visitor object then implements a handleX: method for each AST node
> class X.


> Thus, an operation on an AST is represented by a Visitor object, and you
> apply an operation to an AST by traversing it, sending the handle: message
> to each node with the Visitor as an argument.


johno@lucinda.lat.oz.au (John Ophel) writes:
> Interesting. The basic argument for object oriented design as been that an
> object should contain the methods that relate to that object, thus
> encouraging modular design. The above example describes a situation where
> we don't want the methods relating to an object contained in the object
> but stored separately on a per function basis. By using double dispatching
> and complicated structure we can have a solution that would be more
> naturally expressed in a function-oriented solution.
[ actual code deleted ]


I'm not really all that Object-oriented, so forgive me if I'm besides the
point. [ Usually I'm of the opinion that OO is not in the language, but
in the usuage. Making it possible to do OO stuff in more that just the
traditional OO languages ]


This discussion starts to look a little like the feeling I get from using
the Cocktail attribute evaluator (AG) and pattern recogniser (PUMA).


In both tools is it possible to specify the attributes on an AST node and
the actions to perform. (In Puma one can even specify an
AST-subtree+attributes). In no way does it look like the operational OO
way, where a message is send to a node.


But two OO properties are eminent in this:
  - The AST can be specified in a Class like way, including some way of
action inheritance.
  - The relation Object and actions is a very strong one.


What is not very OO, is the way the actions get executed:
  - If one uses AG then an evaluator is constructed by the toolbox, which
calculates a visit sequence. This visit sequence will go through the AST
in a way that attributes are only calculated once all prerequisites are
done. It might require several visits to a node.
  - Using PUMA, the object is not a node in the AST, but a small tree with
attributes that has to match. Once the match is done the specified code
is executed.


A small extract from what I hacked in my PASCAL compiler: The symbol table
is defined as an AST ( attributes are in '[]' ) and a piece of it looks
like: ( TType is a like wise specification of the Type definitions )


Objects = <
    ONoObject = .
    Object = ONext: Objects REVERSE [ Level :int ] <
        OLabel = [ LabelNum :int ].
        OVField = Objects -> [ Vindex :tIntSet ] .
        ONamedObj = [ Name :tIdent ] [ Pos :tPosition ] <
            OValue = -> TType <
                OConst = [ Val :tValue ].
                OEnum = [ EnumVal :int ].
            >.
            OTypeDecl = -> TType .
            OStore = TType <
                ONoStore= .
                OVar = .
OField = .
                OParam = [IsVar :Boolean].
            >.
            OProcs = <
                OProg = /* kept are the full lists of objects declared in
/* The objects declared as predefined.
                                    /* global scope of the program.
                                      */
StdObjs :Objects
                                    MyObjs :Objects
.
                ORoutines = TType <
                    OStdProc = [ StdProcKey :tStdProcKey ].
                    OProc = [ ProcType :tProcType ]
                                            -> ParTypes
                                          /* kept is the full list of objects declared in
                                          /* this routine.
                                            */
                                          MyObjs:Objects
                                .
                >. /* ORoutines */
            >. /* OProcs */
        >. /* ONamedObj */
    >. /* Object */
>. /* Objects */


Specification of the symbol table allows the specification of actions to
happen in a simple way. EG:


    The rule (or class) OStore has additional attributes but one of them is
        [paramsize,varsize :int INHERIT]
    which means that the attribute behaves as an inherited attribute and
    is propagated down in every OStore subtree.
    This is per default. This can be overruled (overloaded in OO way) by
    specification of other actions to perform.


    Now a OStore list would look a little like:
OProc.MyObjects -> OParam.ONext -> OParam.ONext ....> OStore.ONext --+
                                                                                                                                                          |
                                                                                              ONoStore <- OStore.ONext<.....+


    Now to obtain the total storage in the scope of OProc the following
    AG rules are needed:


OProc = { MyObjects:paramsize := 0; /* Nothing allocated yet */
MyObjects:varsize := 0;
                }.
OVar = { ONext:varsize := varsize + mysize;
}.
OParam = { ONext:paramsize := paramsize + mysize;
}.
    The default copy rules need not be specified, AG automatically copies
    the INHERITED attributes 'down' the tree.


    After the evaluation of these rules, the ONoObject will 'know' the sizes.
    But it is more usefull to know this, at the OProc node. Thus the values
    have to be back propagated to the OProc-node:


    Two attributes take care of this:
OStore = [paramsum,varsum :int SYNTHESISED]
And two simple rules takes care of the whole problem:
ONoStore = { varsum :- varsize;
                                          paramsum :- paramsize;
}.
OStore = { /* This is default inserted by AG due to the SYNTHESISED */
varsum :- ONext:varsum;
paramsum :- ONext:paramsum;
}.
Afterwards they can be collected in OProc:
OProc = { /* do something with ONext:paramsize, ONext:varsize */
}.


No I look upon this as being sort of OO-ish: I specify the relation
between an object and the actions that have to be performed. And what I
do at the top level is sending the message(ALLOCATE) to the symbol table.
(to speak in OO terms)


[ In some of the manuals/papers in/on the Cocktail documentation Josef
Grosch discusses this behaviour much deeper. And he does call it Object
Oriented. ]


Willem Jan
--
Digital Information Systems Group, Tel: +31-40-473401, Fax: +31-40-448375
Room EH 10.35 Eindhoven University of Technology
P.O. 513, 5600 MB Eindhoven, The Netherlands
Internet:wjw@eb.ele.tue.nl,
X400:C=nl;A=400net;P=surf;O=tue;OU=ele;OU=eb;S=WJW;
--

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