Re: ML-Yacc shift/reduce

On Tue, Feb 3, 2009 at 1:00 AM, Boris D <[email protected]> wrote:
...
> My grammar definition has the following rule for vardeclseq:
>
> vardeclseq : (* empty *) ([]) | vardecl vardeclseq (vardecl :: vardeclseq)
> vardecl    : typ Id SEMI (Ast.VarDecl(typ, Id))
>
> Interestingly, a slight change to the above rule eliminates the conflicts,
> but I end up with my variable declarations in reverse order:
>
> vardeclseq : (* empty *) ([]) | vardeclseq vardecl (vardecl :: vardeclseq)
>
> I don't understand why this change eliminates the conflicts, since nothing
> in the grammar definition has been changed other than the order in which I
> build the list. And also, if this is the way to deal with these conflicts,
> how can I get the variable declarations in the right order?

This is one of the "gotchas" with LL and LR parsers.  Your original
grammar was right recursive (the left-hand non-terminal also appears
on the right hand of the right-hand side), which a LR parser generator
is going to have problems with.  The transformed rule is left
recursive, which a LL parser generator would have trouble with (but
not the LR parser generator).  When I have to deal with this, I
usually have the action code cons the reversed list, but then reverse
it back in productions that use the recursive non-terminal.

> Do you guys have good references on how to handle conflicts in LR parsers?
> The best I've come across so far is
> http://www.sable.mcgill.ca/listarchives/sablecc-list/msg00238.html but I'm
> still at a loss how to handle this problem.

IIRC, the O'Reilly Yacc book attempts to discuss this somewhat.  I
also seem to recall the "Dragon book" (Aho, Sethi, Ullman) discussing
syntax transformations like right and left factoring.  I recommend
both books for reference.  You might also mine Usenet archives of
comp.compilers, since this is a frequently asked question there.

Hope this helps,
-Jon

------------------------------------------------------------------------------
Create and Deploy Rich Internet Apps outside the browser with Adobe(R)AIR(TM)
software. With Adobe AIR, Ajax developers can use existing skills and code to
build responsive, highly engaging applications that combine the power of local
resources and data with the reach of the web. Download the Adobe AIR SDK and
Ajax docs to start building applications today-http://p.sf.net/sfu/adobe-com