Thursday, June 02, 2005

Regular Expressions

Ever since college my favorite subject was regular expressions. What I really loved was Thompson's Construction, so powerful. Many tools gained from them and became popular due to their support of RE's, for example

  1. SED
  2. AWK
  3. KSH/SH
  4. VI

I implemented an RE engine with the capability to display its internal state as it does string matching.

Here is the output of the RE "a*b" matching the string "ab"

The first image is RE engine representation. In the subsequent images the red lines show the possible paths that can be taken after looking at the current character in the string being matched. All the photos are links, you can finder better sizes by browsing the links, if you so desire

1 comment:

Gops said...
This comment has been removed by a blog administrator.

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...