[antlr-interest] Feature request: Predicates that turn off predictive look-ahead

Ron Hunter-Duvar ron.hunter-duvar at oracle.com
Thu Apr 29 09:57:03 PDT 2010


Hi,

I keep running into difficult look-ahead problems, due to the nature of 
the language I'm dealing with (a combination of non-reserved keywords 
and sheer language complexity). In many cases I can specify a relatively 
straightforward syntactic or semantic predicate that can resolve a 
conflict. This stops Antlr from turning off the alternatives that it 
considers conflicting. But it doesn't stop Antlr from trying to generate 
predictive look-ahead. When it generates a DFA, it simply incorporates 
any semantic predicate calls into the DFA, generating special states. 
Worse, it does so in a way that sometimes creates a single method too 
big to compile. Instead of doing something like:

    if (predicate) {
       lookup mapping from token type to state
    }

it generates:

    if (token1 && predicate) state=x;
    else if (token2 && predicate) state=y;
    ...

In one recent case, there were 4,000 lines of code like this in a single 
DFA that could have been handled in less than 100. Some improvements to 
the code generation could reduce the size in these cases. But it would 
be nice for such weird cases to have a special type of predicate that 
says "trust me, I know what I'm doing, just use my predicate, don't 
generate a DFA".

Somewhat related to this I've run into times that Antlr generated 
incorrect look-ahead (due to confusion caused by non-reserved keywords), 
but with no conflict warnings. Again, an "I know what I'm doing" 
predicate would be nice for fixing this. But when Antlr doesn't detect a 
conflict, it ignores any predicates that are provided, making it 
impossible to force the correct behaviour.

I remember that when working with JavaCC this was the behaviour for all 
predicates. It assumed that the developer knew better and turned off all 
conflict warnings and generated look-ahead when a predicate was 
provided. This was a little too sweeping, and led to all kinds of parser 
bugs where the predicate wasn't specificied correctly. I wouldn't 
suggest going to this extreme, but some type of fallback for corner 
cases would be great. As it is now, when I hit one of these situations, 
I simply have to try re-arranging things to avoid the problem. In 
several cases this has so far proven impossible, and I've had to simply 
not support those features of the language.

Ron

-- 
Ron Hunter-Duvar | Software Developer V | 403-272-6580
Oracle Service Engineering
Gulf Canada Square 401 - 9th Avenue S.W., Calgary, AB, Canada T2P 3C5

All opinions expressed here are mine, and do not necessarily represent
those of my employer.



More information about the antlr-interest mailing list