[antlr-interest] Two More Bugs in ANTLRv4

[Jan Finis]

Of course the grammar is ambiguous, but there are conventions to resolve 
this: Without specification, any operation is left-associative, so x x x 
should parse as ((x x) x). I see that there is no way of specifying 
right associativity in this case, but this is rather a problem of the 
grammar specification language than of the top down parser generator.

Your suggestion from github:

|exprs
     : expr+
     ;

expr
     : 'x'
     ;
|


works for this example, but this is only a small example for showing the 
issue. In the real application, there are more left recursive 
alternatives in expr. Thus, your suggestion would produce a mutual left 
recursion between exprs and expr. For example, consider this grammar for 
matching regular expressions

expr :
     | ID
     | expr ('?' | '*' | '+')
     | expr expr
     | expr '|' expr

Of course, this grammar can be transformed into one that has no double 
left recursion, but the resulting grammar would look a lot more ugly.


Regards,
Jan

On 02/29/2012 06:43 PM, Sam Harwell wrote:
> The ambiguity in these rules lies in the shape of the parse tree as opposed
> to the actual set of inputs which can be matched. I gave a more detailed
> explanation and possible solutions as comments on the issue at github:
>
> https://github.com/antlr/antlr4/issues/26
>
> --
> Sam Harwell
> Owner, Lead Developer
> http://tunnelvisionlabs.com
>
>
> -----Original Message-----
> From: Jan Finis [mailto:finis at in.tum.de]
> Sent: Wednesday, February 29, 2012 11:13 AM
> To: Ron Burk
> Cc: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] Two More Bugs in ANTLRv4
>
> The funny thing is that Honey Badger DID support this kind of grammar (see
> my earlier mail with a running example). Maybe due to a bug, but that shows
> that it must be somehow possible in a top-down manner.
>
>