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

megatest!plethorax!djones@uu2.psi.com (Dave Jones) writes:
>
>Last month I posted an article pointing out two bugs in Sedgewick's Pascal
>algorithm for matching the NFA against an input string. The bug Todd
>reports is in the algorithm for building the NFA, in the "C" book, which I
>have never seen.


They are exactly identical.


>Helpful suggestion: Don't try to salvage the Sedgewick algorithms. See
>the New Dragon Book ... Both procedures are sketched out almost correctly
>in algorithms 3.3 and 3.4.


I just have the old one. From what I understand, it's treatment
of this topic is the same. There is no implementation in it, just as
there was no implementation in the book I was originally working from,
Hopcroft & Ullman's "Intro to Automata Theory, Languages, & Computation"
(or some such). This problem must have been implemented bunches of time
in the past, and is obviously tricky. Algorithm 3.3 is correct -- the
problem is parsing the string into it's constituents, which is equivalent
to parsing a CFG. I was hoping to find working code, rather than reinvent
the wheel.


Thanks for the pointer, although it wasn't exactly what I needed.


T.
--
Todd Hodes, hodes@cs.Virginia.edu
--

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