Fwd: [antlr-interest] v3: semantic predicates in parser
Terence Parr
parrt at cs.usfca.edu
Fri Aug 18 12:15:38 PDT 2006
From Jim Idle.
Begin forwarded message:
> From: "Jim Idle" <Jim.Idle at intersystems.com>
> Date: August 18, 2006 11:26:08 AM PDT
> To: "Terence Parr" <parrt at cs.usfca.edu>, "Antlr-Interest" <antlr-
> interest at antlr.org>
> Subject: RE: [antlr-interest] v3: semantic predicates in parser
>
> Ter,
>
> Faced with a similar issue, that I sent you a few weeks back, but
> with gated semantic predicates covering both alts, I discovered
> that just telling antlr that this was k=1 allowed it to do the
> right thing:
>
> options {k=1;}
>
> Makes this go away. I had not had occasion to try this with non
> gated semantic predicates, so I tried it using the example below
> and it seems to work fine. Whether you would want to unravel this
> to k=1
>
> Also, in the example provided, theElement=element will not work
> unless using option output=AST, as it is assigning the value of a
> rule and this results in declaring theElement as void, which
> obviously fails. If this is not an AST output, then the rule
> element needs to return something as would theA.
>
> For simplicity, I have turned on output=AST here so it compiles.
> The following example will work correctly then I think:
>
> grammar Test;
>
> options { output =AST; }
>
> @members
> {
> boolean someCondition;
> }
> document : (element)* EOF ;
> element : theA | B | C ;
>
> theA
>
> :
>
> A
> (
> options {
> k=1; // Allows ANTLR to derive the DFA for
> // the following, despite recursion
> }
> :
> { someCondition }?=> theElement=element
> {
> // do something with theElement
> }
> |
> // quit the rule
> )
> ;
>
> A : 'a' ;
> B : 'b' ;
> C : 'c' ;
>
> Please note that I haven’t really looked at the code output for the
> example above, so please verify.
>
> Jim
>
> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Terence Parr
> Sent: Friday, August 18, 2006 10:58 AM
> To: Antlr-Interest
> Subject: Re: [antlr-interest] v3: semantic predicates in parser
>
> interesting...this in fact has 2 alts that lead to the same recursive
> rule invocation. I need to modify this message so it shuts up with
> predicates, but it will have to unravel back to k=1. When you get
> that message, it means ANTLR will never be able to build the DFA.
>
> Ter
>
> On Aug 18, 2006, at 5:25 AM, Richard Musiol wrote:
>
>> Hi,
>>
>> semantic predicates in the parser don't seem to work in beta 3 as
>> they did in ANTLR 2. Will they be supported in the final?
>>
>> For example the following grammar:
>>
>> grammar Test;
>>
>> document : (element)* EOF ;
>> element : theA | B | C ;
>>
>> theA
>> :
>> A
>> (
>> { someCondition }?=>
>> theElement=element
>> {
>> // do something with theElement
>> }
>> |
>> // quit the rule
>> )
>> ;
>>
>> A : 'a' ;
>> B : 'b' ;
>> C : 'c' ;
>>
>> ANTLR can't handle it:
>> "[fatal] rule theA has non-LL(*) decision due to recursive rule
>> invocations in alts 1,2. Resolve by left-factoring or using
>> syntactic predicates with fixed k lookahead or using backtrack=true
>> option."
>>
>> At my opinion, ANTLR should use the first alternative if
>> someCondition is true and the second one if not.
>>
>> My second approach was to swap the alternatives:
>>
>> theA
>> :
>> A
>> (
>> { !someCondition }?=>
>> // quit the rule
>> |
>> theElement=element
>> {
>> // do something with the element
>> }
>> )
>> ;
>>
>> ANTLR compiles this without any errors, but the resulting code is
>> really stange:
>>
>> [...]
>> else if ( (LA3_0==A) ) {
>> else {
>> NoViableAltException nvae = [...];
>> throw nvae;
>> }
>> }
>> [...]
>>
>> It seems that there is a bug in the code generation. But also the
>> decisions are wrong:
>>
>> [...]
>> int alt3=2;
>> int LA3_0 = input.LA(1);
>> if ( (LA3_0==EOF) && ( !someCondition )) {
>> alt3=1;
>> }
>> [...]
>>
>> Why should it only quit the rule if an EOF is following? There may
>> be an A, B or C too.
>>
>> I hope this will get fixed until the final, because semantic
>> predicates are a really powerful feature.
>>
>> Regards,
>> Richard
>>
>
>
> --
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.1.405 / Virus Database: 268.11.3/423 - Release Date:
> 8/18/2006
>
>
> --
> No virus found in this outgoing message.
> Checked by AVG Free Edition.
> Version: 7.1.405 / Virus Database: 268.11.3/423 - Release Date:
> 8/18/2006
>
More information about the antlr-interest
mailing list