Wed, 14 Apr 1993 20:06:03 GMT

Related articles |
---|

Re: Wanted: Regular Expression -> Finite Automata C code =- tdh6t@helga3.acc.virginia.edu (Todd Hodes) (1993-04-05) |

Re: Wanted: Regular Expression -> Finite Automata C code =- megatest!plethorax!djones@uu2.psi.com (1993-04-09) |

Re: Wanted: Regular Expression -> Finite Automata C code =- henry@zoo.toronto.edu (1993-04-12) |

Re: Wanted: Regular Expression -> Finite Automata C code =- tdh6t@onyx.cs.virginia.edu (Todd Hodes) (1993-04-14) |

Newsgroups: | comp.compilers |

From: | Todd Hodes <tdh6t@onyx.cs.virginia.edu> |

Keywords: | DFA, books |

Organization: | University of Virginia Computer Science Department |

References: | 93-04-023 93-04-041 |

Date: | Wed, 14 Apr 1993 20:06:03 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.