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

Richard Musiol mail at richard-musiol.de
Sat Aug 19 15:36:42 PDT 2006


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