Re: Avoiding inherited attributes in bottom-up parsing

Tobias Carlsson <toca@serop.abb.se> writes:


>In the dragon book one can read about evaluation of inherited attributes
>in bottom-up parsing. I think that inherited attributes should be
>avoided in bottom up parsing.
>To get access to inherited attributes (without using globals), one must
>index the parser stack, that compromises the principles of the stack
>machine and is a great place for bugs to hide, because when indexing the
>parser stack, one must always have the same symbols on the stack. This
>makes the grammar hard to change or reuse.


If you use a functional language, inherited attributes can easily be
emulated by using higher order functions. If nonterminal N has an
inherited attribute of type A and a synthesized attribute of type B,
this is emulated by giving N a (synthesized) attribute of type (A -> B).


For example, the following is an extract from a simple expression
evaluator written using MosML-yacc. Expr, conceptually, has a symbol
table as inherited attribute and a number as syntehsized attribute.
This is handled by making the actual attribute a function from symbol
table to number.




Expr:
                    Expr PLUS Expr { fn st => $1 st + $3 st }
                | Expr MINUS Expr { fn st => $1 st - $3 st }
                | LPAREN Expr RPAREN { $2 }
                | INT { fn st => $1 }
                | ID { fn st => lookup($1,st) }
;


There is nothing at all that encourages bugs in this code. The type
checker will (almost) ensure that the attributes are used correctly.


Note, however, that the evaluation of the bodies of the functions are
postponed until the symbol table is applied to them farther up in the
parse tree. This means that one should be very careful about side
effects. This is not normally a problem in functional languages,
though, as side effects are used sparingly (if at all).


Related to this, if you try to use this technique in other languages,
you must be careful to check how the generated parsers access
attribute variables ($1, $2 etc.). If this is done by direct access to
a stack which is modified by side effects, then packing these
"variables" into a function body which is activated later may cause
the wrong attributes to be accessed. In this case, the attributes must
first be transferred to "real" variables which survive. This will make
the first rule look like this:


                    Expr PLUS Expr { let val a1 = $1
                                                                                        a3 = $3
                                                                        in
                                                                            fn st => a1 st + a3 st
                                                                        end
                                                                    }


a1 and a3 will now be evaluated immediately and the body of the
function will not refer explicitly to attribute variables.


Torben Mogensen (torbenm@diku.dk)

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