Regular Expression Talk
A week or a so ago I gave a talk at CWRU Hacker Society on how to implement a regular expression engine. The inspiration for the talk came from two things: first, I have long held a fascination for regular expressions, and second was an excellent article by Russ Cox which inspired me to create my own engine [1]. Regular expression matching is largely a black block box today. Rarely will a programmer need to implement their own matching algorithm. However, there are times when it cannot be avoided, such as when the match needs to be executed on many string simultaneously.
This talk assumes minimal knowledge of regular expression, indeed it starts by defining the syntax, and the semantics, before explaining finite automatons and the matching algorithms themselves. To explain the matching algorithms I wrote simple implementations in Go (Google's new programming language) which are now hosted on github [2]. These implementations also serve to highlight using Go in less trivial way than in a Go tutorial I gave last month. The slides and audio from the talk should be attached to this post.
[1] http://swtch.com/~rsc/regexp/regexp2.html
[2] http://github.com/timtadh/regex-machines
Audio:
Slides:
Computer Science Ph.D. student at Case Western Reserve University. Likes to tinker and crunch crunchy looking leaves.
