[antlr-interest] ambiguous grammar

[jbb at acm.org]

On Tue, 07 Oct 2003 00:42:17 +0700, jagad <jagad at enciety.com> wrote:
>Hi All,
>
>I have simple grammar:
>
>rule1  : '(' rule2 (COMMA rule2)* ')'
>rule2  : rule1 | expr
>
>expr   : factor (op factor)*
>factor : INTEGER | '(' expr ')'
>op     : '+' | '-'
>
>the grammar is conflicting because the input like: ((1),(2)) is
>undetermine. "(1)" is could be rule1 or expr.
>If I force rule1 using:
>
>rule1  : ('(')=>'(' rule2 (COMMA rule2)* ')' | expr
>
>the grammar will valid for "((1),(2))" but fail for: "((1)+1, (2))"
>which it should be valid according that "(1)+1" is should be an expr.
>
>Anybody knows how to overcome this problem?

I haven't actually tried running this through the antlr.Tool, but I
think it is unambigous:

rule1  : '(' expr (COMMA expr)* ')'
expr   : factor (op factor)*
factor : INTEGER | rule1
op     : '+' | '-'

But the above accepts "(1,2)+3" or "3+(2,1)" while your original
grammar does not. I think a simple semantic error check for the
presence of a COMMA when an op is encountered would be easy to add if
that restriction is important...

Hope this helps.
	-jbb

 

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