## nondeterminism warning

Expand Messages
• Could someone tell me how I can get something like the following to work without warnings? b: B ; c: C ; abc: ((b)+ c) | (b)*; That rule states that every c
Message 1 of 7 , Jul 1, 1999
• 0 Attachment
Could someone tell me how I can get something like the following to work without warnings?

b: "B";
c: "C";
abc: ((b)+ c) | (b)*;

That rule states that every c must be preceded by one or more b, but if there's no c, multiple b are legal but not required.

For this, ANTLR 2.6 gives the warning:
warning: line 15: nondeterminism upon
k==1:"B"
between alts 1 and 2 of block
• ... abc: ((b)+ (c)?)?; appears what you are really saying is possibly one or more b s optionally followed by a c. ... alternatively abc: b ( c | abc ); and use
Message 2 of 7 , Jul 1, 1999
• 0 Attachment
geoff.d.fortytwo@... wrote:
>
> From: geoff.d.fortytwo@...
>
> Could someone tell me how I can get something like the following to work without warnings?
>
> b: "B";
> c: "C";
> abc: ((b)+ c) | (b)*;
>
> That rule states that every c must be preceded by one or more b, but if there's no c, multiple b are legal but not required.
>
> For this, ANTLR 2.6 gives the warning:
> warning: line 15: nondeterminism upon
> k==1:"B"
> between alts 1 and 2 of block
>
>
> How has ONElist changed your life?
> Share your story with us at http://www.onelist.com
>
> ------------------------------------------------------------------------
-------------
abc: ((b)+ (c)?)?;

appears what you are really saying is possibly one or more b's
optionally followed by a c.
-------------
alternatively

abc: b ( c | abc );

and use it as

x: (abc)? ;

--------------

another possibility is

abc: (b)+ (c)?;

and again use it as

x: (abc)?

or

x: abc | def;

or
x: abc | ;

Sinan
• hello all, I am very new to parser generators and ANTLR. I am trying to get my first Lexer compiled. The Lexer should recognize expressions for a search query:
Message 3 of 7 , Jan 16, 2003
• 0 Attachment
hello all,

I am very new to parser generators and ANTLR. I am trying to get my
first Lexer compiled.

The Lexer should recognize expressions for a search query:

- Phrases: in double quotes (like "one phrase"), any white space shall
be escaped (like "one\\ phrase").
- boolean operators: "AND", "OR", "NOT"
- single words (not "AND", "OR", "NOT" *sigh*)

outside a phrase white space shall be ignored.

this is my current Lexer which I am not able to improve further to get
rid of the warnings:

/******************** LEXER **************************/

class QueryLexer extends Lexer;

options
{
charVocabulary = '\3'..'\377';
k=3;
}

{
private boolean isPhrase = false;
}

TERM
: PHRASE
| ( AND ) => { \$setType(Token.AND); }
| WORD
| WS { \$setType(Token.SKIP); }
| { System.out.println("error: " + \$getText()); }
;

AND
: { this.isPhrase == false }? "AND"
;

OR
: { this.isPhrase == false }? "OR"
;

NOT
: { this.isPhrase == false }? "NOT"
;

protected PHRASE
: '"'! { this.isPhrase = true; } WORD ( WS! { \$append("\\ "); } WORD
)* (WS!)?
'"'! { this.isPhrase = false; }
;

protected WORD
: (LETTER)+
;

protected WS
: (' ' | '\t')+
;

protected LETTER
: '\u0024' |
'\u0041'..'\u005a' |
'\u005f' |
'\u0061'..'\u007a' |
'\u00c0'..'\u00d6' |
'\u00d8'..'\u00f6' |
'\u00f8'..'\u00ff' |
'\u0100'..'\u1fff' |
'\u3040'..'\u318f' |
'\u3300'..'\u337f' |
'\u3400'..'\u3d2d' |
'\u4e00'..'\u9fff' |
'\uf900'..'\ufaff'
;

/***************** LEXER END **********************/

I get these warnings:

antlr:
[antlr] ANTLR Parser Generator Version 2.7.2rc2 (20030105)
1989-2003 jGuru.com
[antlr] QueryParser.g: warning:lexical nondeterminism between
rules TERM and AND upon
[antlr] QueryParser.g: k==1:'A'
[antlr] QueryParser.g: k==2:'N'
[antlr] QueryParser.g: k==3:'D'
[antlr] QueryParser.g: warning:lexical nondeterminism between
rules TERM and OR upon
[antlr] QueryParser.g: k==1:'O'
[antlr] QueryParser.g: k==2:'R'
[antlr] QueryParser.g: k==3:<end-of-token>
[antlr] QueryParser.g: warning:lexical nondeterminism between
rules TERM and NOT upon
[antlr] QueryParser.g: k==1:'N'
[antlr] QueryParser.g: k==2:'O'
[antlr] QueryParser.g: k==3:'T'
[antlr] warning: public lexical rule TERM is optional (can match
"nothing")
[antlr] QueryParser.g:75: warning:lexical nondeterminism upon
[antlr] QueryParser.g:75: k==1:'\t',' '
[antlr] QueryParser.g:75: k==2:'\t',' '
[antlr] QueryParser.g:75: k==3:'\t',' ','"'
[antlr] QueryParser.g:75: between alt 1 and exit branch of block

+++++++++++++++++++++++

I changed k to 3 in hope it would solve the nondeterminism but that
changes basically nothing. It adds only the lines with k==2 and k==3
to the warning output.

I do understand that "AND", "OR", "NOT" can match as WORD but I'am not
able to tell antlr to first try to match AND, OR, NOT and then WORD. I
tried with syntactic predicates in different places, but that didn't
change anything.

The last warning is annoying: where is the error in the WS rule? I
can't find anything wrong in it?

I would greatly appreciate any hint, tip, suggestion, solution...!

regards,
Chantal
• try the following // test.in test c and b or c not d C: temp antlrTest java -cp .;c: antlr antlr.jar Main ,line=1,col=1]
Message 4 of 7 , Jan 18, 2003
• 0 Attachment
try the following
// test.in

"test c" and b or c not "d"

C:\temp\antlrTest>java -cp .;c:\antlr\antlr.jar Main <test.in
["test\ c",<7>,line=1,col=1]
["and",<7>,line=1,col=10]
["b",<7>,line=1,col=14]
["or",<7>,line=1,col=16]
["c",<7>,line=1,col=19]
["not",<7>,line=1,col=21]
["d",<7>,line=1,col=25]

// Main.java
import java.io.*;
import antlr.Token;

class Main implements QueryLexerTokenTypes {
public static void main(String[] args) {
try {
QueryLexer lexer = new QueryLexer(new DataInputStream(System.in));
Token t=lexer.nextToken();
while (t.getType() != EOF) {
System.out.println(t);
t=lexer.nextToken();
}
} catch(Exception e) {
System.err.println("exception: "+e);
throw new RuntimeException(e);
}
}
}

//QueryLexer.g
class QueryLexer extends Lexer;

options
{
charVocabulary = '\3'..'\377';
k=3;
}

tokens {
AND = "AND";
OR = "OR";
NOT = "NOT";
}

TERM
: PHRASE
| WORD
| (WS { \$setType(Token.SKIP); })+
;

protected PHRASE
: '"'! WORD ( WS! {\$append("\\ ");} (WORD)? )*
'"'!
;

protected WORD
: (LETTER)+
;

protected WS
: (' ' | '\t')
;

protected LETTER
: '\u0024' |
'\u0041'..'\u005a' |
'\u005f' |
'\u0061'..'\u007a' |
'\u00c0'..'\u00d6' |
'\u00d8'..'\u00f6' |
'\u00f8'..'\u00ff' |
'\u0100'..'\u1fff' |
'\u3040'..'\u318f' |
'\u3300'..'\u337f' |
'\u3400'..'\u3d2d' |
'\u4e00'..'\u9fff' |
'\uf900'..'\ufaff'
;

----- Original Message -----
From: <chantal.ackermann@...>
To: <antlr-interest@yahoogroups.com>
Sent: Thursday, January 16, 2003 9:21 PM
Subject: [antlr-interest] nondeterminism warning

> hello all,
>
> I am very new to parser generators and ANTLR. I am trying to get my
> first Lexer compiled.
>
> The Lexer should recognize expressions for a search query:
>
> - Phrases: in double quotes (like "one phrase"), any white space shall
> be escaped (like "one\\ phrase").
> - boolean operators: "AND", "OR", "NOT"
> - single words (not "AND", "OR", "NOT" *sigh*)
>
> outside a phrase white space shall be ignored.
>
> this is my current Lexer which I am not able to improve further to get
> rid of the warnings:
>
> /******************** LEXER **************************/
>
> class QueryLexer extends Lexer;
>
> options
> {
> charVocabulary = '\3'..'\377';
> k=3;
> }
>
> {
> private boolean isPhrase = false;
> }
>
> TERM
> : PHRASE
> | ( AND ) => { \$setType(Token.AND); }
> | WORD
> | WS { \$setType(Token.SKIP); }
> | { System.out.println("error: " + \$getText()); }
> ;
>
> AND
> : { this.isPhrase == false }? "AND"
> ;
>
> OR
> : { this.isPhrase == false }? "OR"
> ;
>
> NOT
> : { this.isPhrase == false }? "NOT"
> ;
>
> protected PHRASE
> : '"'! { this.isPhrase = true; } WORD ( WS! { \$append("\\ "); } WORD
> )* (WS!)?
> '"'! { this.isPhrase = false; }
> ;
>
> protected WORD
> : (LETTER)+
> ;
>
> protected WS
> : (' ' | '\t')+
> ;
>
> protected LETTER
> : '\u0024' |
> '\u0041'..'\u005a' |
> '\u005f' |
> '\u0061'..'\u007a' |
> '\u00c0'..'\u00d6' |
> '\u00d8'..'\u00f6' |
> '\u00f8'..'\u00ff' |
> '\u0100'..'\u1fff' |
> '\u3040'..'\u318f' |
> '\u3300'..'\u337f' |
> '\u3400'..'\u3d2d' |
> '\u4e00'..'\u9fff' |
> '\uf900'..'\ufaff'
> ;
>
> /***************** LEXER END **********************/
>
> I get these warnings:
>
> antlr:
> [antlr] ANTLR Parser Generator Version 2.7.2rc2 (20030105)
> 1989-2003 jGuru.com
> [antlr] QueryParser.g: warning:lexical nondeterminism between
> rules TERM and AND upon
> [antlr] QueryParser.g: k==1:'A'
> [antlr] QueryParser.g: k==2:'N'
> [antlr] QueryParser.g: k==3:'D'
> [antlr] QueryParser.g: warning:lexical nondeterminism between
> rules TERM and OR upon
> [antlr] QueryParser.g: k==1:'O'
> [antlr] QueryParser.g: k==2:'R'
> [antlr] QueryParser.g: k==3:<end-of-token>
> [antlr] QueryParser.g: warning:lexical nondeterminism between
> rules TERM and NOT upon
> [antlr] QueryParser.g: k==1:'N'
> [antlr] QueryParser.g: k==2:'O'
> [antlr] QueryParser.g: k==3:'T'
> [antlr] warning: public lexical rule TERM is optional (can match
> "nothing")
> [antlr] QueryParser.g:75: warning:lexical nondeterminism upon
> [antlr] QueryParser.g:75: k==1:'\t',' '
> [antlr] QueryParser.g:75: k==2:'\t',' '
> [antlr] QueryParser.g:75: k==3:'\t',' ','"'
> [antlr] QueryParser.g:75: between alt 1 and exit branch of block
>
> +++++++++++++++++++++++
>
> I changed k to 3 in hope it would solve the nondeterminism but that
> changes basically nothing. It adds only the lines with k==2 and k==3
> to the warning output.
>
> I do understand that "AND", "OR", "NOT" can match as WORD but I'am not
> able to tell antlr to first try to match AND, OR, NOT and then WORD. I
> tried with syntactic predicates in different places, but that didn't
> change anything.
>
> The last warning is annoying: where is the error in the WS rule? I
> can't find anything wrong in it?
>
> I would greatly appreciate any hint, tip, suggestion, solution...!
>
> regards,
> Chantal
>
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
• Hi: In my language, I have the following rules: parent_list: class_type (feature_adaption)?
Message 5 of 7 , Aug 25, 2003
• 0 Attachment
Hi:

In my language, I have the following rules:

parent_list:
class_type
(feature_adaption)? <---- *nondeterminism in this line
;

class_type:
class_name
(actual_generics)?
;

~("end") "end"
;

I am getting a nondeterminism warning using antlreclipse on the line denoted by (*)

Can someone help me fix this please?

Cheers,

Dave

-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/
• ... Just a guess, as the grammar you provide is incomplete, do you have the same warning if you increase the k in the option, such as k=2 ? If you don t want
Message 6 of 7 , Aug 26, 2003
• 0 Attachment
> De : dm@... [mailto:dm@...]

> I am getting a nondeterminism warning using antlreclipse on
> the line denoted by (*)
> Can someone help me fix this please?

Just a guess, as the grammar you provide is incomplete, do you have the same
warning if you increase the k in the option, such as k=2 ? If you don't want
check.

Bests,
Rodrigo
• (actual_generics)? and ~( end ) conflict. Antlr should handle it correctly though. Monty ... From: dm@cs.yorku.ca [mailto:dm@cs.yorku.ca] Sent: Monday, August
Message 7 of 7 , Aug 27, 2003
• 0 Attachment
(actual_generics)? and ~("end") conflict. Antlr should handle it correctly
though.

Monty

-----Original Message-----
From: dm@... [mailto:dm@...]
Sent: Monday, August 25, 2003 12:11 PM
To: antlr-interest@yahoogroups.com
Subject: [antlr-interest] nondeterminism warning

Hi:

In my language, I have the following rules:

parent_list:
class_type
(feature_adaption)? <---- *nondeterminism in this line
;

class_type:
class_name
(actual_generics)?
;

~("end") "end"
;

I am getting a nondeterminism warning using antlreclipse on the line denoted
by (*)

Can someone help me fix this please?

Cheers,

Dave

-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Your message has been successfully submitted and would be delivered to recipients shortly.