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

[indhu bharathi]

This might not be an elegant fix. But it does fix the problem
13c13
<       : PROCEDURE IDENTIFIER SEMICOLON subroutineBlock SEMICOLON
---
>       : PROCEDURE IDENTIFIER SEMICOLON subroutineBlock
17,19c17,19
<       : external
<       | forward
<       | asmBlock
---
>       : external SEMICOLON
>       | forward SEMICOLON
>       | asmBlock SEMICOLON

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> 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
>
>
> PROCEDURE Proc; FORWARD;
> grammar keywords;
>
> options {
>        language=Java;
>        k=*;
> }
>
> procedureDecl
>        : PROCEDURE IDENTIFIER SEMICOLON subroutineBlock SEMICOLON
>        ;
>
> subroutineBlock
>        : external
>        | forward
>        | asmBlock
>        ;
>
> asmBlock
>        : assembler SEMICOLON ASM END
>        ;
>
> external: {input.LT(1).getText().toLowerCase().equals("external")}?
> IDENTIFIER;
> forward: {input.LT(1).getText().toLowerCase().equals("forward")}?
> IDENTIFIER;
> assembler: {input.LT(1).getText().toLowerCase().equals("assembler")}?
> IDENTIFIER;
>
> SEMICOLON: ';';
> PROCEDURE: 'PROCEDURE';
> ASM: 'ASM';
> BEGIN: 'BEGIN';
> END: 'END';
> IDENTIFIER: ('a'..'z'|'A'..'Z')+;
> WS: (' '|'\r'|'\n')+ {$channel = HIDDEN;};
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>


-- 
- Cheers
Indhu Bharathi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090101/52f59afc/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: keywords.g
Type: application/octet-stream
Size: 943 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20090101/52f59afc/attachment.obj