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

Post a Comment