[antlr-interest] Resolving ambiguity

Martijn Reuvers martijn.reuvers at gmail.com
Sat Apr 25 11:23:09 PDT 2009


Hello everyone,

I've been playing around with antlr and I am running into something I
don't know how to fix. Below this mail follow resp. the grammar and
tree grammar, which I've simplified to show the issue I have. Sample
input for this grammar is:

int a;

a = a+10;

String s = "hello!";

s = s + "ok";

s = a;

The problem is somewhere in the 'str_method_var' and 'int_method_var'
rules. They both have a NAME = expression semicolon . So there's the
ambiguity. I tried using a predicate in str_method_var (it now just
says {true}? as you can see) and this resolves the warning for the
grammar. Not sure if that's the right way though.

But now, the tree grammar is complaining:

[java] error(211): src/antlr/basic/test08/TestTree.g:20:2: [fatal]
rule classdef_content has non-LL(*) decision due to recursive rule
invocations reachable from alts 1,2.  Resolve by left-factoring or
using syntactic predicates or using backtrack=true option.
[java] Java Result: 1

Then if I try the same trick in the tree grammar (adding {true}? in
str_method_var), it does complain:

 [java] warning(203): src/antlr/basic/test08/TestTree.g:20:2: Input
such as "VARDEF" is insufficiently covered withicates at locations:
alt 2: line 40:6 at VARDEF, line 41:6 at VARDEF
 [java] warning(200): src/antlr/basic/test08/TestTree.g:20:2: Decision
can match input such as "VARDEF" using multiplternatives: 1, 2
 [java] As a result, alternative(s) 2 were disabled for that input
 [java] error(201): src/antlr/basic/test08/TestTree.g:20:2: The
following alternatives can never be matched: 2
 [java]
 [java] Java Result: 1"

I am a bit lost on what to do now. I hope someone can help me out or
put me on the right track!

Thanks a lot!
Martijn

p.s. Adding {true}? predicate in the grammar unfortunately makes
antlrworks fail with a very long error dialog when trying to debug,
but I think that is this bug:
http://www.antlr.org/jira/browse/ANTLR-378.

----------------------------------------------------------------------------------
grammar Test;

options {
	output=AST;
}

tokens {
	VARDEF;
}

start
	:	classdef_content+
	;

classdef_content
	:		int_method_var
	|		str_method_var
	;

int_global_var
	:	MEMBER_TYPE_INT NAME SEMICOLON 													-> ^(VARDEF MEMBER_TYPE_INT NAME)
	| MEMBER_TYPE_INT NAME '=' int_expression_calc SEMICOLON 	-> ^(VARDEF
MEMBER_TYPE_INT NAME int_expression_calc)
	;
	
int_method_var
	:	int_global_var
	| NAME '=' int_expression_calc SEMICOLON 		-> ^(VARDEF NAME
int_expression_calc)
	;

int_expression_calc
	:	d=int_mult_expr_calc (('+'^ | '-'^) e=int_mult_expr_calc)*
	;

int_mult_expr_calc
	:	int_atom ('*'^ int_atom)*
	;

int_atom
	:	INT
	|	NAME
	| '('! int_expression_calc ')'!	
	;
	
str_global_var
	:	MEMBER_TYPE_STR NAME SEMICOLON													-> ^(VARDEF MEMBER_TYPE_STR NAME)
	| MEMBER_TYPE_STR NAME '=' str_expression_calc SEMICOLON	-> ^(VARDEF
MEMBER_TYPE_STR NAME str_expression_calc)
	;
	
str_method_var
	:	str_global_var
	| {true}? NAME '=' str_expression_calc SEMICOLON 	-> ^(VARDEF NAME
str_expression_calc)
	;	

str_expression_calc
	:	d=str_atom (('+'^ | '-'^) e=str_atom)*
	;
	
str_atom
	:	TEXT
	| NAME
	;

MEMBER_TYPE_INT
	: 'int'
	;
	
MEMBER_TYPE_STR
	:	'String'
	;	

SEMICOLON
	:	';'
	;

INT
	: ('0'..'9')+
	;
	
TEXT
	:	'"' .* '"'
	;
	
NAME
	:	('a'..'z' | 'A'..'Z' | '0'..'9' | '_' )+
	;
	
WS	
	:	(' '|'\t'|'\n'|'\r')+ { $channel=HIDDEN; }
	;	
----------------------------------------------------------------------------------

tree grammar TestTree;

options {
	tokenVocab=Test;
	ASTLabelType=CommonTree;	
}

start
	:	classdef_content+
	;

classdef_content
	:		int_method_var
	|		str_method_var
	;

int_global_var
	:	^(VARDEF MEMBER_TYPE_INT NAME)
	| ^(VARDEF MEMBER_TYPE_INT NAME int_expression_calc)
	;
	
int_method_var
	:	int_global_var
	| ^(VARDEF NAME int_expression_calc)
	;

int_expression_calc [int value]
	:	^('+' a=int_expression_calc b=int_expression_calc) {  $value=a+b;  }
	| ^('-' a=int_expression_calc b=int_expression_calc) {  $value=a-b;  }
	;
	
str_global_var
	:	^(VARDEF MEMBER_TYPE_STR NAME)
	| ^(VARDEF MEMBER_TYPE_STR NAME str_expression_calc)
	;
	
str_method_var
	:	str_global_var
	| {true}? ^(VARDEF NAME str_expression_calc)
	;	

str_expression_calc
	:	^('+' a=str_expression_calc  b=str_expression_calc) { $value=a+b; }
	| ^('-' a=str_expression_calc  b=str_expression_calc) {  /*$value=a-b;  */  }
	;


More information about the antlr-interest mailing list