Re: Wanted: Regular Expression -> Finite Automata C code =-

I wanted to use the code in Sedgewick's 'Algorithms in C' book,
but found the following bug:


        When it parses REs of the form a(b+c), i.e. a terminal concatenated
with a union clause, the output is as follows:


  State : 0 1 2 3 4 5 6
  Char : a b c -
  Next1 : 1 2 3 6 5 6 0
  Next2 : 1 2 3 6 2 6 0


                Weeeeell, this ain't quite right. State #1 should go on an input
of "a" to state #4 in addition to or instead of state #2.


        Anyone with an idea how to salvage his code or new code would be quite
a savior. This is for a technical report to be given to the world before
summer. It is a teaching tool implementing Hopcraft and Ullmans RE ->
NFA-w-epsilons -> NFA -> DFA "circle of equivalence" transforms with a
graphical interface in SUIT under X. Everything works except Sedgewick's
code, and I dread rewriting it, figuring that if Sedgewick got it wrong,
it must be HARD! (I haven't even found his bug yet.) I already tried
writing it once (iteratively, even). Figures that the only code I steal
doesn't work. :)


I've already had the following ideas tossed at me:


1) Use Henry Spencer's regexp [not exactly what I need -
just union, concatenation and closure is fine]


2) Pillage source from Unix utilities (flex, lex, grep)
[ughh -- haven't tried this yet... again, full Unix REs
are too much]


3) Give up ;>


(Thanks to Jonathan A. Chandross <jac@yoko.rutgers.edu> for the pointer to
this group and some additional info about how bugs have been found in the
code before and posted here.)


Thanks,


T.
--
Todd Hodes, tdh6t@virginia.edu
[This came up last month, but without a whole lot of helpful suggestions.
-John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.