See also: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/

See also: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/regexp/regexp3.html http://swtch.com/~rsc/regexp/regexp3.html http://en.wikipedia.org/wiki/Thompson%27s_construction_algorithm http://en.wikipedia.org/wiki/Thompson%27s_construction_algor... I implemented a sort of micro-grep in the past using the Thompson's algorithm, it was a great exercise in practical applications of heavily-theoretical CS stuff, with recursive-descent parsing of the regular expression, then using Thompsons algorithm to create a NFA out of the parse tree, then a simulation of an NFA with a DFA using two stacks. I used the Dragon Book for reference on this, all pretty awesome stuff.