Is there a book that explain the algorithm used by regular expression functions?

Question

Is there a book that explains the algorithm used by the regular expression functions, and optionally shows an implementation in some high level language?

Answer 1

http://swtch.com/~rsc/regexp/

Not a book, but has some stuff you could use...

Answer 2

Pattern Matching is a staple of Functional Programming Languages like Haskell, Scala and ML. There is a nice book by Simon Peyton Jones, original author and current maintainer of the Glorious Glasgow Haskell Compiler (GHC), called The Implementation of Functional Programming Languages which contains three entire chapters just on Pattern Matching.

Answer 3

Not a book, but Russ Cox's work here gives an overview.

You might also want to reference Ken Thompson's original work (found in the link I listed above):

Ken Thompson, ‘‘Regular Expression Search Algorithm’’, CACM11(6), June 1968, pp. 419-422.

Answer 4

I'm relatively certain there're some examples in CLRS' Introduction to Algorithms.