[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