Re: ML-Yacc shift/reduce

Jon Riehl wrote:
> 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.
>
>   

That was very helpful. Thanks a lot, 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