[antlr-interest] Solving non determinism

jbb at acm.org jbb at acm.org
Wed Aug 4 07:49:09 PDT 2004


Greetings!

On Tue, 03 Aug 2004 21:43:35 +0000, xdecoret wrote:
>I cannot solve a non determinism problem with my grammar:
>
>ANTLR Parser Generator   Version 2.7.3   1989-2004 jGuru.com
>foo.g:72: warning:nondeterminism upon
>foo.g:72:     k==1:NAME
>foo.g:72:     k==2:EQUAL
>foo.g:72:     k==3:NAME,STRING,VALUE
>foo.g:72:     k==4:COMA,POUND
>foo.g:72:     k==5:NAME,STRING,VALUE
>foo.g:72:     between alt 1 and exit branch of block
>
>I do not understand why antlr 2.7.3 complains.
>
>I copy the .g file below (this is a parser for bibtex format). Note
>that if I use the commented line for fieldValue productions rule, the
>problem does not show up. 
>
...grammar snipped...

I have four suggested changes for your BibTex grammar. They all relate
to transforming the grammar into LL form, e.g left factoring and
eliminating left recursion.

1) change your fields rule (line 71) from:

fields
    : (field COMA)* field (COMA)?
    ;

to be:

fields
    : field ( COMA ( fields )? )?
    ;

[Note: this change directly addresses the nondeterminism you asked about.
       with this change your nondeterminism is solved, you won't need
       my other suggested changes. but I hope they will be of use to
       you anyway...]

2) change your fieldValue rule (line 81) from:


fieldValue returns [std::string v]
{
    string p;
    string q;
}
    : (p=fieldValuePart POUND {v += p;})* q=fieldValuePart {v += q; }
//     : q=fieldValuePart {v += q; }
    ;

to be:

fieldValue returns [std::string v]
{
    string p;
}
    : p=fieldValuePart {v += p;} (POUND q=fieldValuePart {v += p;})*
    ;

3) left factor your stringdef rule (line 35) by changing it from:

stringdef
{
    string i;
    string s;
}
    : STRINGDEF LPARENTHESIS i=id EQUAL
        {
            braceStartsValue_ = true;
        }
        s=fieldValue RPARENTHESIS
        {
            braceStartsValue_ = false;
        }
    | STRINGDEF LBRACE i=id EQUAL
        {
            braceStartsValue_ = true;
        }
        s=fieldValue RBRACE
        {
            braceStartsValue_ = false;
        }        
    ;

to be:

stringdef
{
    string i;
    string s;
}
    : STRINGDEF
	( LPARENTHESIS i=id EQUAL
	    {
		braceStartsValue_ = true;
	    }
	    s=fieldValue RPARENTHESIS
	    {
		braceStartsValue_ = false;
	    }
	| LBRACE i=id EQUAL
	    {
		braceStartsValue_ = true;
	    }
	    s=fieldValue RBRACE
	    {
		braceStartsValue_ = false;
	    }
	)
    ;

4) lastly remove the "k = 5;" from the parser options, no lookahead is
   needed any more.


Hope this helps...
	John B. Brodie (jbb at acm.org)


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
    antlr-interest-unsubscribe at yahoogroups.com

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



More information about the antlr-interest mailing list