[antlr-interest] another nondeterminism question

[Alan Oursland]

I am having problems with lookahead in the parser now. Is this another
problem with linear approximation? The grammar and warnings are at the
bottom of this message.

I think that k=2 should have resolved any nondeterminism here.
In expression, (cond_clause)+ should loop on ("(" "(" | "(" "EXPR"),
transition to else_clause on ("(" "else"), and skip the else_clause on
(")").

I also tried doing (options{greedy=false;}: cond_clause)+, but that gave me:
	TestParser.g:15: warning:nongreedy block may exit incorrectly due
	TestParser.g:15:     	to limitations of linear approximate lookahead (first
k-1 sets
	TestParser.g:15:     	in lookahead not singleton).

The following changes do remove the nondeterminism, but change the language:
	- remove (else_clause)?
	- make else_clause nonoptional (no '?')
	- remove opening parenthesis in else_clause

Is this another error or am I missing something in my understanding of
nondeterminism?
Does anyone have any suggestions for resolving this?

Alan

This grammar:
	class SampleParser extends Parser;
	options {
		k=6;	// set to 6 to see where conflicts stabilize
	}
	startRule
		:	expression
		;
	expression
		:	"("
			"cond"
			(cond_clause)+ // Line 15
			(else_clause)?
			")"
		|	"EXPR"
		;
	cond_clause
		:	"(" (expression)+ ")"
		;
	else_clause
		:	"(" "else" (expression)+ ")"
		;

Generates these warnings:
	ANTLR Parser Generator   Version 2.7.2   1989-2003 jGuru.com
	TestParser.g:15: warning:nondeterminism upon
	TestParser.g:15:     k==1:"("
	TestParser.g:15:     k==2:"(","EXPR"
	TestParser.g:15:     k==3:"(","cond",")","EXPR"
	TestParser.g:15:     k==4:"(","cond",")","EXPR"
	TestParser.g:15:     k==5:EOF,"(","cond",")","EXPR","else"
	TestParser.g:15:     k==6:EOF,"(","cond",")","EXPR","else"
	TestParser.g:15:     between alt 1 and exit branch of block



 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/