[antlr-interest] Two More Bugs in ANTLRv4

Jan Finis finis at in.tum.de
Wed Feb 29 10:06:31 PST 2012

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:

     : 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.


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.

More information about the antlr-interest mailing list