Strange nondeterminism with simple k=2 grammar
3 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Fernando_Colombo
Posted On:   Friday, February 18, 2005 08:15 AM

The following grammar (k=2) -- code: statement; statement: ID "(" ")" | (ID ":")? "while" "(" ")" statement; generates a nondeterminism warning: nondeterminism between alts 1 and 2 of block upon k==1:ID k==2:"(" and is generating the following Java code: if ((LA(1)==ID) && (LA(2)==5)) { match(ID); match(5); match(6); } // Strange generation decision: else if ( (LA(1)==ID||LA(1)==LITERAL_while) && (LA(2)==5||LA(2)==7)) { ... I think ANTLR should not think it's a nondeterminism and should gen   More>>

The following grammar (k=2) --

			
code: statement;
statement: ID "(" ")" | (ID ":")? "while" "(" ")" statement;

generates a nondeterminism warning:
			
nondeterminism between alts 1 and 2 of block upon
k==1:ID
k==2:"("

and is generating the following Java code:
			
if ((LA(1)==ID) && (LA(2)==5)) {
match(ID);
match(5);
match(6);
}
// Strange generation decision:
else if (
(LA(1)==ID||LA(1)==LITERAL_while) &&
(LA(2)==5||LA(2)==7)) {
...

I think ANTLR should not think it's a nondeterminism and should generate Java lines under comment this way:
			
else if (
(LA(1)==ID&&LA(2)==5)) {
... // match ID ":"
} else if (
(LA(1)==LITERAL_while&&LA(2)==7)) {
... // match "while" "("
}


So, questions are:
1. What is the good reason for ANTLR works this way?
2. How can I remove warning without increasing k?

Thanks!    <<Less

Re: Strange nondeterminism with simple k=2 grammar

Posted By:   valentin_tihomirov  
Posted On:   Saturday, February 19, 2005 02:46 PM

--- 2. How can I remove warning without increasing k?

statement: {true}? ID LP RP | (ID COLON)? "while" LP RP statement;


Seems that your grammar will be working properly despite of the warnings which you get due to the ID&&LA(5) conflict. The priority is given to the first alternative; this is what you imply. You can suppress the warnings by adding {true}? disambiguating predicate to the priority rule. The predicates complement the synthax lookahead logic making the parser absolutely sure that taking the otherwise ambiguous alternative production is a right decision. Hope, you can recognize my english.

Please note, that the [":", "(" and ")"] marks will not be delivered to the parser as the literal tokens are derived from known lexer rules.

Re: Strange nondeterminism with simple k=2 grammar

Posted By:   valentin_tihomirov  
Posted On:   Saturday, February 19, 2005 01:45 PM

http://www.antlr.org/doc/glossary.html#Linear_approximate_lookahead

Re: Strange nondeterminism with simple k=2 grammar

Posted By:   Fernando_Colombo  
Posted On:   Friday, February 18, 2005 08:25 AM

Please, consider last code snipet as:

else if (
(LA(1)==ID&&LA(2)==7)) {
... // match ID ":"
} else if (
(LA(1)==LITERAL_while&&LA(2)==5)) {
... // match "while" "("
}

Sorry for the inconvenience.
About | Sitemap | Contact