Strange nondeterminism with simple k=2 grammar
3 posts in topic
Flat View  Flat View
Older Post First |   Reply to Topic
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
Report | Quote This | Send private message | Reply | Print

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.
Report | Quote This | Send private message | Reply | Print

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
Report | Quote This | Send private message | Reply | Print

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.
Report | Quote This | Send private message | Reply | Print
About | Sitemap | Contact