Fwd: [antlr-interest] v3: semantic predicates in parser

[Terence Parr]

 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
>