[antlr-interest] v3: semantic predicates in parser

Richard Musiol mail at richard-musiol.de
Mon Aug 21 09:37:15 PDT 2006


Wow great! It works.
I didn't know that gates are also possible for rewrites. This solution 
is great and has a much cleaner structure than my attempt. I hope that 
the new documentation will cover this too. The new ANTLR is really 
powerful if you know how to use it.

Thanks,
Richard



Jim Idle schrieb:
> Though there is a bug, it might be that it is not telling you have not covered all rewrite cases or similar. I think you will have more luck by placing the rewrites as conditionals rather than trying to control this via rules. You shudl really be parsing the elements, then saying "OK, now I have eveyhing, how do I want the tree to look:
> 
> theA
> 	: (
> 		A
> 		( options { k=1; } 
> 			: { someCondition }?=> subrule
> 			| // quit the rule
> 		)
> 	   )
> 		-> { someCondition &&   thirdCondition }? -> ^(A subrule)
> 		-> { someCondition && ! thirdCondition }? -> A subrule
> 		->
> 	;
> 
> I am assuming that you want an empty tree if 'someCondition' is not set however if you just want A then that last rewrite rule would be:
> 
> -> A
> 
> Remember that the production you are expressing is what is valid syntactically and you are mixing gated semantic predicates for parsing with how the tree should luck after you have parsed it. Documentation is a little sparse of course at the moment ;-)
> 
> Also, given the gate there, I don't think that you need the epsilon production (// quit the rule) as the gate will either allow that parse or not), but I have not looked at that too closely.
> 
> Jim
> 
> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Richard Musiol
> Sent: Saturday, August 19, 2006 3:37 PM
> To: Antlr-Interest
> Subject: [antlr-interest] Re: v3: semantic predicates in parser
> 
> Thanks!
> 
> The k=1 solution works and in my case there is no need for a greater 
> lookahead in this rule.
> 
> But now I've got an even more difficult case. I want to change the AST 
> creation based on a condition:
> 
> subrule1
> subrule2
> ( { condition }?=>
> 	-> ^(subrule1 subrule2)
> |
> 	-> subrule1 subrule2
> )
> 
> In ANTLR 2 I had done this with much plain Java code, but I thought that 
> the new AST syntax could do this in ANTLR 3. Normally it seems to work, 
> but in my special case it doesn't. It took me some time to create a test 
> grammar - the following is needed to reproduce the error (nothing more, 
> but also nothing less - every condition is needed!):
> 
> grammar Test;
> 
> options { output =AST; }
> 
> @members
> {
> 	boolean someCondition;
> 	boolean anotherCondition;
> 	boolean thirdCondition;
> }
> document : (element)* EOF ;
> element  : theA | B | C    ;
> 
> theA
> 	:
> 		A
> 		( options { k=1; } :
> 			{ someCondition }?=>
> 			subrule
> 			(
> 				{ thirdCondition }?=>
> 					-> ^(A subrule)
> 				|
> 					-> A subrule
> 				)
> 			|
> 			// quit the rule
> 		)
> 	;
> 
> subrule
> 	:
> 		( options { k=1; } :
> 			{ anotherCondition }?=>
> 			element subrule
> 		|
> 			// quit the rule
> 		)
> 	;
> 
> A : 'a' ;
> B : 'b' ;
> C : 'c' ;
> 
> Currently the result is a StackOverflowError with the loop in 
> org.antlr.analysis.NFAToDFAConverter.closure
> (the comment "// Avoid infinite recursion" doesn't seem to work :-) )
> This seems to be a bug, so please fix it. Maybe the grammar looks crazy, 
> but I promise you that it makes sense.
> 
> Bye,
> Richard
> 
> 
> 
> Terence Parr schrieb:
>>  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