[antlr-interest] Understanding nondeterminism warnings: and how to debug them

Bryan Ewbank ewbank at gmail.com
Fri Feb 24 03:30:56 PST 2006


Hi Vladimir,

Ambiguity errors are often very puzzling, as we often see only what we (as
humans) wnat to see, rather than what is actually there.

I hope the following helps to get your grammar working...

- Bryan Ewbank

=== === ===
> grammer.txt:14:75: warning:nondeterminism between alts 1 and 2 of block upon
> grammer.txt:14:75:     k==1:BEGIN

I think one of the problems is with interactions between <program> and
<subprogramDeclarations>.
    <program> says "( subprogramDeclarations )?"
    <subprogramDeclarations> says "( ... )*"
So, if there is no sequence of tokens that match subprogramDeclarations, what
does <program> do? It can either match one <subprogramDeclarations> (that
matches no tokens), or it can match no <subprogramDeclarations>.

If you replace "(...)*" with "(...)+" in <subprogramDeclarations>, you should
fix some of the warnings:

    subprogramDeclarations :
        (
            (procedureDeclaration | functionDeclaration)
            SEMI_COLON
        )+
    ;

=== === ===
> grammer.txt:40: warning:nondeterminism upon
> grammer.txt:40:     k==1:SEMI_COLON
> grammer.txt:40:     between alt 1 and exit branch of block

The error at line #40, from <formalParameterList>, is that when ANTLR sees a
SEMI_COLON it doesn't know if it's supposed to go "around" again, or quit.
Specifically, look at <procedureDeclaration> and you will see that
<formalParameterList is followed immediately by SEMI_COLON.

I would guess that you really want to see parenthesis in the input stream, so
probably <procedureDeclaration> (and <functionDeclaration>) should be using
quoted parenthesis -- '(' and ')' -- around the <formalParameterList>

=== === ===
> grammer.txt:58:21: warning:nondeterminism between alts 1 and 2 of block upon
> grammer.txt:58:21:     k==1:ID

The problem here is that both an assignmentStatement and a procedureStatement
start with an ID; if this is a correct language definition, you may require
k=2.  In procedureStatement, as in the procedureDeclaration, you need to quote
the parenthesis that you want as input tokens.

=== === ===
> grammer.txt:69:56: warning:nondeterminism between alts 1 and 2 of block upon
> grammer.txt:69:56:     k==1:ELSE

This is a classic ambiguity - does ELSE match the most recent IF, or not:
    if (e1)
        if (e2)
            s1
    else
        s2
The easiest solution, to me, is to add the option greedy=true to the (...)?
around ELSE; see the manual for exact syntax.

=== === ===
> grammer.txt:105: warning:nondeterminism between alts 3 and 4 of block upon
> grammer.txt:105:     k==1:ID

This is the same type of ambiguity as at line 51 - both <variable> and
<functionReference> start with an ID.


More information about the antlr-interest mailing list