Re: LL, LR debate

scott@cs.rochester.edu (Michael Scott) writes:
> (5) In table-driven parsers, management of space for attributes has
> a very different "feel" in the top-down and bottom-up worlds,
> and different programmers seem to have different preferences.
> The "natural" attribute stack for bottom-up parsers is intuitive
> and easy to automate, but inherited attributes are a hack. Automatic
> management of space for top-down attributes is also possible,
> but forces you to use a *lot* of copy rules. Ad-hoc, explicit
> pushing and popping of a semantic stack is probably preferable in
> top-down parsers; many programmers find it elegant, once they
> get the hang of it.


Explicit pushing and popping of the semantic stack is especially elegant
in Forth, where the language's data stack can be used as the semantic
stack. I have implemented this approach in Gray, a parser generator that
accepts an extended BNF and produces recursive descent parsers (Gray is
freely available, mail me to get it).


With this approach it is easy and natural to handle left-associative
operators. The equivalent of yacc's


Expr ->
    Expr K_MINUS Term
    { $$ = MakeNode(MINUS_TAG, $1, $3); }


is


    (( Term
          (( "-" Term {{ MINUS_TAG MakeNode }} )) **
    ))
<- Expr ( -- node )


A few words of explanation are probably needed here: You find the defined
nonterminal 'Expr' near the end (Everything in Forth is reversed :-).
Gray's delimiters are double, because the single versions are already used
in Forth. The curly braces delimit actions. The '**' works like the '*'
in lex, meaning zero or more occurences of the preceding item. 'Term'
parses a term and pushes a node. '"-"' just parses a '-'. 'MakeNode' pops
two nodes and a tag and pushes a node. So the overall stack effect of
'Expr' is to push a node; this is documented by the comment '( -- node )'.


Right-associativity is slightly harder; it requires recursion:


    (( Base "**" Exponent {{ POWER_TAG MakeNode }} ))
<- Exponent ( -- node )


Some advantages over yacc: It is easy to keep information local to a rule
and to pass information around. When you add syntactic sugar, changes in
the actions (renumbering) are unnecessary.
--
M. Anton Ertl anton@mips.complang.tuwien.ac.at
--

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