[antlr-interest] Re: Lexer nondeterminism

[Xue Yong Zhi]

The answer is antlr uses "linear approximate lookahead".

If you look at the generated code you may find the clue. For example, 
GTE will match "==", ">>", ">=" and "=>", and of course it conflicts 
with EQ.

Please read this:
http://www.antlr.org/doc/glossary.html#Linear_approximate_lookahead
and related entries in antlr's FAQ.

You may find my blog usefully as well:
http://seclib.blogspot.com/2005/11/linear-approximate-lookahead.html


Laurent Debacker wrote:
> Hi,
> 
> There is something I do not understand:
> 
> I have the following operators:
> AND		: ("and" | "&&") ;
> OR		: ("or" | "||") ;
> EQ		: '=' | "==" ;
> LT		: '<' ;
> LTE		: ("<=" | "=<") ;
> GT		: '>' ;
> GTE		: (">=" | "=>") ;
> NEQ		: ("!=" | "<>") ;
> NOT		: '!' ;
> IMPLIES		: "->" ;
> ASSIGN		: ":=" ;
> 
> ANTLR says there are lexical nondeterminisms with (EQ,LTE), (EQ, GTE),
> (LTE, GTE) and (LTE, NEQ). k is 2.
> 
> But why doesn't he complains about LT and NEQ?
> 
> Also in the C# grammar I found and which is compiling fine I found:
> 
> SL: "<<";
> LTHAN: "<";
> 
> Why is ANTLR happy with that? Well maybe because ANTLR is greedy, but
> then my =< should also be matched even with the = rule.
> 
> Also, is there any good page that explains what testLiterals is? I
> looked around, but it was really vague.
> 
> Thanks for your help!
> Laurent.
> 


-- 
Xue Yong Zhi
http://seclib.blogspot.com