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

[indhu bharathi]

I guess this can be solved more elegantly. Modify 'subroutineBlock' rule to
force k=1
subroutineBlock
options {k=1;}
: external
| forward
| asmBlock
;

Now since we are forcing "k=1" (k=2 is needed to look-ahead SEMICOLON) ,
ANTLR wont lookahead for SEMICOLON and instead use our predicate.


On Thu, Jan 1, 2009 at 4:34 PM, indhu bharathi <indhubharathi at gmail.com>wrote:

> 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
>



-- 
- Cheers
Indhu Bharathi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090101/5a898471/attachment.html