|Re: Wanted: Regular Expression -> Finite Automata C code =- email@example.com (Todd Hodes) (1993-04-05)|
|Re: Wanted: Regular Expression -> Finite Automata C code =- firstname.lastname@example.org (1993-04-09)|
|Re: Wanted: Regular Expression -> Finite Automata C code =- email@example.com (1993-04-12)|
|Re: Wanted: Regular Expression -> Finite Automata C code =- firstname.lastname@example.org (Todd Hodes) (1993-04-14)|
|From:||Todd Hodes <email@example.com>|
|Organization:||University of Virginia Computer Science Department|
|Date:||Wed, 14 Apr 1993 20:06:03 GMT|
firstname.lastname@example.org (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
Thanks for the pointer, although it wasn't exactly what I needed.
Todd Hodes, hodes@cs.Virginia.edu
Return to the
Search the comp.compilers archives again.