[antlr-interest] Linear approximate lookahead question

shmuel siegel antlr at shmuelhome.mine.nu
Wed Aug 17 01:35:59 PDT 2005


Ingo Maier wrote:
> Hi,
> 
> due to linear approximate lookahead the following grammar gives a
> non-determinism warning:
> 
> a: z S P;
> b: z T Q;
> z: P (T P)*;
> 
> because z can be followed by (T Q | S P) which leads to a possible T P
> in the approximation.
> 
> How can I resolve this, besides pasting z into a and b rules? Sorry, if
> this has been asked before.
> 
> Thanks,
> Ingo
> 

If I remember correctly, Terence said that he generally gets bit by this 
problem at least once per real grammar. The pasting of z into a and b 
will only work in this case because a and b are top level rules. I added

x: a | b;

and generated this code

try {      // for error handling
	if ((LA(1)==LITERAL_P) && (LA(2)==LITERAL_T||LA(2)==LITERAL_S))
	{
		a();
		astFactory.addASTChild(currentAST, returnAST);
		x_AST = (AST)currentAST.root;
	}
	else if ((LA(1)==LITERAL_P) && (LA(2)==LITERAL_T))
	{
		b();
		astFactory.addASTChild(currentAST, returnAST);
		x_AST = (AST)currentAST.root;
	}
	else
	{
		throw new NoViableAltException(LT(1), getFilename());
	}
			
}

as you can see you can't get to rule 'b';

At least this should be fixed in Antlr 3 which handles LL(*)


-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.338 / Virus Database: 267.10.10/73 - Release Date: 8/15/2005



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.338 / Virus Database: 267.10.10/73 - Release Date: 8/15/2005



More information about the antlr-interest mailing list