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

Oliver Zeigermann oliver.zeigermann at gmail.com
Tue Sep 20 15:02:59 PDT 2005


Cool! Your DFA looks much better! Any chance to get the corrected code?

Oliver


2005/9/20, Terence Parr <parrt at cs.usfca.edu>:
> 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:
> 
> 
> 
> 
> 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