[antlr-interest] Optional keyword causes ambiguity in parser

[Ramon Verbruggen]

OK, judging from the total lack of reactions, I either asked a really
stupid question (been there, done that, didn't get the t-shirt), or I
asked something that's been explained so often that no one could be
bothered to explain it again (in this case I suck at searching the
internet, which would kind of surprise me)

Generally, if I have a largish grammar in perfect working order, and I
want to make one keyword optional, but this causes ANTLR to have
ambiguity in the parser (Input such as 'Identifier' can be matched in
multiple ways), how would you solve this?

ANTLR hints at backtracking, left factoring and syntactic predicates.
Backtracking is not really an option for performance reasons (that, and
backtracking feels like a last resort for when nothing else really
works).

Left factoring could be an option. Unfortunately, the paths through the
grammar that ANTLR takes to arrive at the ambiguity (as visualized by
ANTLRWorks), are rather long, since they go through all the expressions
in the 'precedence ladder', so these paths involve 20+ parser rules. I
don't really see how to left factor that big a chunk of my grammar.

So, I guess this leaves predicates as an option. The grammar I'm trying
to change is rather clean, it just builds an AST and does not use any
predicates so far, which (partially) explains my lack of knowledge on
the predicates. 

After this longwinded prose, the real question would then be: How could
I use predicates to solve the ambiguity in my grammar?

Any input is appreciated!

Ramon Verbruggen



>>> "Ramon Verbruggen" <Ramon.Verbruggen at quintiq.com> wrote:
> I am working on a grammar for a Delphi/Java like programming
language.
> In a statementbody the return statement can only be the last
statement,
> if it is present at all.
> 
> I have made a small grammar to illustrate the problem:
> 
> grammar ANTLRQuill;
> 
> statementBody:	statementList returnStatement? EOF;
> returnStatement:	'return' expression ';'*; // <= 'return' should
be optional
> statementList:	(statement ';'*)*;
> statement:	addressable;
> expression:	addressable( '*' addressable)*;
> addressable:	Identifier ( '.' Identifier '()' )*;
> Identifier:	('a'..'z')+;
> 
> 
> Now, I would like to make the 'return' keyword optional, but when I
> just put " 'return' ?", ANTLR rightfully
> complains that it has several ways of matching Identifier, and that
it
> will always choose alternative one. I understand the warning, and I
see
> that ANTLR's right, but I don't see how else to solve this problem.
> 
> I've tried a lot of different possibilities already, and searched
the
> archives and the ANTLR book, but haven't been able to find a way to
make
> the return keyword optional. Obviously, the actual grammar is much
> bigger and a bit more complex than the example above, so especially
> rules statement, expression and addressableElement have more
> alternatives, and the expression hierarchy has the usual 'ladder' of
> expression types to obtain the correct levels of precedence.



This message contains information that may be privileged or confidential
and is the property of Quintiq. It is only intended for the person to
whom it is addressed. If you are not the intended recipient, you are not
authorized to read, print, retain, copy, disseminate, distribute or use
this message or any part thereof. If you have received this message in
error, please notify the sender immediately and delete all copies of
this message. Please note that e-mails are susceptible to change,
therefore they are not binding.