[antlr-interest] How to resolve nondeterminism in treeparser ?

Subhobroto Sinha subhobrotosinha at rediffmail.com
Mon Jul 4 11:00:58 PDT 2005


  
Consider the grammar : http://www.geocities.com/subhobrotosinha/dsd.txt
Driver : http://www.geocities.com/subhobrotosinha/dsddriver.txt

Here's dsd.txt for the lazybones out there :
////////////////////////////////////////
/*
	Parser for Input like : lowpass(3, 2.0, 4.56, 1.29, 4.78, 9, 4.99, 5.67, 4.89)
	Produces Output : float a[8] = {2.0, 4.56, 1.29, 4.78, 9, 4.99, 5.67, 4.89 };
*/
header { #include <iostream> }

options { language = Cpp; }

/* Start of tree parser */

class DSDTreeParser extends TreeParser;

{
	unsigned int m_uiCoeffCount;
	bool m_bFirstPass;
}

firstPass
{
	m_uiCoeffCount = 0;
	m_bFirstPass = true;
}
: functionName order (csvCoeffs)+
{
	std::cout<<"\nfloat a["<<m_uiCoeffCount<<"] = {";
}
;

secondPass
{
	m_bFirstPass = false;
}
: functionName order (csvCoeffs)+
;

functionName : ID;

order : INT;

csvCoeffs : (coefficient)+;

coefficient :	(i : INT
			{
				if(m_bFirstPass) ++m_uiCoeffCount;
				else
				{
					--m_uiCoeffCount;
					std::cout<<i->getText()<<((0 == m_uiCoeffCount) ? " };" : ", ");
				}
						
			}
			|
			f : FLOAT
			{
				if(m_bFirstPass) ++m_uiCoeffCount;
				else
				{
					--m_uiCoeffCount;
					std::cout<<f->getText()<<((0 == m_uiCoeffCount) ? " };" : ", ");
				}
			}
			)+;

/** Start of parser */

class DSDParser extends Parser;

options {
	genHashLines = true; // include line number information
	buildAST = true; // uses CommonAST by default
}

startRule : functionName LPAREN! order COMMA! (csvCoeffs)+ RPAREN!;

functionName : ID;

order : INT;

csvCoeffs : coefficient (COMMA! coefficient)*;

coefficient :	(INT | FLOAT);

/** Start of lexer */

class DSDLexer extends Lexer;

FLOAT_OR_INT :
			( INT '.' ) => FLOAT { $setType(FLOAT); }
			|
			INT { $setType(INT); }
			;

protected INT
options {
	testLiterals = true;
	paraphrase = "a constant integer";
}

: ('0' .. '9')+;

protected FLOAT
options {
	testLiterals = true;
	paraphrase = "a floating point value";
}

: INT '.' INT;

ID
options {
	testLiterals = true;
	paraphrase = "a variable";
}
	:	('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*
	;

COMMA : ',';

SEMI : ';';

PLUS : '+';

MINUS : '-';

LPAREN : '(';

RPAREN : ')';

WS : (
	options { greedy = true; }

	: '\r' '\n' {newline();}
	| '\n' 	{newline();}
	| '\t'
	| ' '
	)+
	{ $setType(antlr::Token::SKIP); }
;
/* EOF */
////////////////////////////////////////

ANTLR is currently angry :

DSD.g:40: warning:nondeterminism upon
DSD.g:40:     k==1:INT,FLOAT
DSD.g:40:     between alt 1 and exit branch of block
DSD.g:42: warning:nondeterminism upon
DSD.g:42:     k==1:INT
DSD.g:42:     between alt 1 and exit branch of block
DSD.g:42: warning:nondeterminism upon
DSD.g:42:     k==1:FLOAT
DSD.g:42:     between alt 2 and exit branch of block

Altough my test cases are passing allright, I feel bad about ANTLR being so grumpy.

Please clear my misconceptions ?

PS : If anything above makes you feel queasy, let me know ! You can do it better ? Let me know !

Regards

Subhobroto Sinha
http://www.geocities.com/subhobrotosinha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20050704/e96f9265/attachment.html


More information about the antlr-interest mailing list