[antlr-interest] Weird problem with semantic predicates. Incorrect warning message

Gabriel Petrovay gabriel.petrovay at 28msec.com
Thu Apr 30 14:51:37 PDT 2009


Hi!

Thank you Jim, John and Gavin for making it clear and providing also
the explanatory solutions.

You must see that here it is not the IF nor the predicate the problem.
Both are successfully treated by ANTLR (see the grammar that does not
include the p_ReplaceExpr rule). The only wrong thing here is is the
ambiguous grammar generated by the p_ReplaceExpr. I need this rule,
therefore I cannot delete it (it is just this sample grammar that
you've got that I don't use it). The complete grammar is the grammar
of XQuery Scripting Extensions 1.0
(http://www.w3.org/TR/xquery-sx-10/). Due to this problem I was able
to point out to the W3C guys that in this working draft the grammar is
ambiguous. (They will correct this in the next draft and my problem
will disappear).

Although it is not the best practice to have ambiguous grammar and nor
to work with predicates, this is not my choice. Predicates,
unfortunately, I can't avoid, since I have to enable/disable rules
(make a configurable parser) based on outside input.


ANTLR Improvement Suggestion

As I see the problem, ANTLR tries to guess the lookahed. Of course,
the problematic rule messes up this guessing since, being ambiguous,
ANTLR fails to guess a proper k, if such k exist (probably not because
the grammar is recursive and also ambiguous). And therefore if this
ambiguous rule is present ANTLR sets k to 1. And there you go, the IF
problem. Of course in the original grammar I had tons of warnings and
it was tedious enough to provide such a small example. I am not
complaining, that is my job. ;)

ANTLR could either ignore ambiguous rules (if the computed k is toooo
large, give up) and proceed with normal computation. Another thing
ANTLR could do is be to compute k per-rule and not per grammar.


I might be wrong in some of the assumptions made above, but this is
what I think happens behind the curtains. You might know better.


Regarding the proposed solutions, I like Gavin's since this has
minimal performance side-effects. This is a good workaround until, as
I said, W3C publishes the new working draft for XQuery Scripting
Extensions.

Thanks for helping me (understand). I hope I did not spent too much of
your time. (It is for a good cause anyway ;) )


Regards,
Gabriel Petrovay
www.28msec.com
mobile: +41(0)787978034


More information about the antlr-interest mailing list