[antlr-interest] ANTLR 3: Clueless about DFA prediction

Terence Parr parrt at cs.usfca.edu
Tue Sep 20 14:13:11 PDT 2005


On Sep 20, 2005, at 11:06 AM, Terence Parr wrote:
> On Sep 20, 2005, at 9:05 AM, Oliver Zeigermann wrote:
>> I simply do not understand the DFA based predicion for this very
>> simple lexer grammar:
>>
>> TEXT : (~'<')+ ;
>> TAG : (~'>')+ ;
>>
>> I have attached the generated DFA as a GIF which reads like the TAG
>> rule is predicated if *anywhere in the future input* there is an '<'
>> to be found. This certainly was not my intention...
>>
>
> Hi Oliver, thanks for finding this!  It is a bug in my IntervalSet  
> code I think.  If I change the characters to be adjacent, I get a  
> different DFA!!!!

Wow!  Turns out there was a bug in my subtract and intersection code  
for IntervalSet.  BTW, in case you've never tried, building an  
IntervalSet is nontrivial!  BitSets are trivial in comparison.  Here  
is the new correct DFA:

-------------- next part --------------
A non-text attachment was scrubbed...
Name: t_dec-3.pdf
Type: application/pdf
Size: 14193 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20050920/4efc43ed/t_dec-3.pdf
-------------- next part --------------

New unit tests for IntervalSet and DFA conversion.  All pass green.

Ter
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com



More information about the antlr-interest mailing list