## Converting NFA to DFA

From: "andrew cooke" <andrew@...>

Date: Sun, 22 Mar 2009 14:07:07 -0400 (CLT)

Generating an NFA from a regular expression is fairly easy (it's only
taken me a couple of weeks and a rewrite to work out what to do!).  But I
couldn't see how to go from NFAs to DFAs.  It's explained nicely in these
slides -
http://www.mit.edu/~6.035/lectures-2004/RegularExpressionsandGrammars.ppt
(slides 25 and 26).

Apparently it's called "Thompson's Construction".

However, it seems that it's n^2, while the Dragon book describes a nlog(n)
approach.

The Rex toolkit extends the Dragon book approach further with the "tunnel
algorithm", described in
ftp://www.cocolab.com/products/cocktail/doc.pdf/scangen.pdf

That last paper is very specific to lexers (the only choice, at least in
the example, is at the start), but that's exactly what I want.

Andrew

### Python Code to Compile Regexps

From: andrew cooke <andrew@...>

Date: Fri, 4 Dec 2009 17:40:44 -0300

This page gets a surprising number of hits.  I don't know if it's any
use, but the code I wrote (which just follows the basic Thompson's
algorithm - nothing special) is visible at
Andrew