[antlr-interest] Problem with disambiguating semantic predicates and the decision DFA

Markus Stoeger spamhole at gmx.at
Fri Jan 2 16:02:31 PST 2009


I think "the option to ask ANTLR to forcefully use my predicate" ;-) is 
to simply replace the disambiguating semantic predicates {...}? with 
gated semantic predicates {...}?=>. And this seems to work!

I haven't tested it enough yet and the book recommends disambiguating 
semantic predicates on page 287 (Keywords as Variables), but I think it 
should work as the gated semantic predicates are always hoisted into the 
decision DFA, while disambiguating semantic predicates are only hoisted 
when ANTLR finds a syntactic disambiguity in the production rules. There 
is no syntactic disambiguity in the case of my asmBlock so it doesn't 
add the disambiguating semantic predicate, but it cannot skip my gated 
semantic predicate.

So while this seems to be a simple and almost elegant work around to my 
problem, I'm still wondering if ANTLR's behaviour with my previous 
example code is correct or if there is some bug. To me it seems like it 
generates an insufficient prediction DFA. It believes that an Identifier 
followed by a Semicolon is enough to predict an asmBlock.. but that's 
wrong, it needs at least three symbols - Identifier, Semicolon, Asm - to 
correctly identify the asmBlock in that case.

I have slightly modified my example grammar's subroutineBlock and 
removed all semantic predicates. Without the semantic predicates it gets 
the prediction DFA right (see attachment) - it uses the required three 
symbols of lookahead now. But as soon as I add the disambiguating 
semantic predicates again, it's back to two symbols lookahead and fails.

Markus


indhu bharathi schrieb:
> The season for the problem is, a look ahead is needed at 
> 'subroutineBlock' to decide which production to use. ANTLR notes that 
> 'asmBlock' has a semicolon while the other two don't. So now the 
> confusion is between the other two. It is only at this instance (after 
> deciding lookahead(';') as the deciding factor for asmBlock), ANTLR 
> looks for the predicates. Predicates is used to decide between 
> 'external' and 'forward'. Unfortunaly in our case what follows 
> 'subroutineBlock' (in proceureDecl) is also a SEMICOLON and that 
> semicolon is looked-ahead and a wrong decision (for asmBlock) is being 
> made.
>
> In the new modified productions (in the fix), even 'external' and 
> 'forward' has SEMICOLON following it. So ANTLR cannot now use 
> SEMICOLON as deciding factor :-)
>
> That said this is only a hackish fix. I would prefer ANTLR using my 
> own predicates to decide when I have explicitly mentioned the predicate. 
>
> Is there an option to ask ANTLR to forcefully use my predicate when I 
> have specified one?
>
> Cheers,
> Indhu Bharathi
>
> PS: I've attached the fixed grammar file with this mail
>
>
> On Wed, Dec 31, 2008 at 10:52 PM, Markus Stoeger <spamhole at gmx.at 
> <mailto:spamhole at gmx.at>> wrote:
>
>     First of all, a happy new year to everyone!
>
>     I'm writing a grammar for one of those twisted languages, written
>     by social deviants, that allow keywords to be used as variables.
>
>     The solution provided in the ANTLR Reference book on page 287
>     ("Keywords as Variables") seems to work fine in most cases.
>
>     However I have found one case where my tests fail:
>
>     Please have a look at the attached grammar in keywords.g. Debug it
>     with the start symbol "procedureDecl" and feed it the input
>     "PROCEDURE Proc; FORWARD;"
>
>     The problem happens in "subroutineBlock" where the decision dfa
>     chooses the wrong alternative 3 (asmBlock) instead of 2 (forward).
>
>     To me the generated decision DFA for the symbol "subroutineBlock"
>     (also attached) looks erroneous. It correctly evaluates the
>     disambiguating semantic predicates for alternatives 1 (external)
>     and 2 (forward), but it skips the evaluation for alternative 3
>     (asmBlock) and makes its decision based on the SEMICOLON token,
>     which is wrong because the semicolon can belong to the outer
>     procedureDecl.
>
>     I have tested this with the latest stable version of the
>     ANTLRWorks bundle (1.2.2).
>
>     thanks for any hints,
>     Markus
>

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: test2.g
Url: http://www.antlr.org/pipermail/antlr-interest/attachments/20090103/cef9985b/attachment.pl 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test2dfa.png
Type: image/png
Size: 6679 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20090103/cef9985b/attachment.png 


More information about the antlr-interest mailing list