How do regular expressions work / Regular Expression diagrams
Archive - Originally posted on "The Horse's Mouth" - 2010-12-17 14:58:59 - Graham Ellis
If you want to help yourself work out what a regular expression means, you can draw a regular expression matching flow chart such as this one. I've taken the regular expression .*@.* - a very basic "it might be an email address" filter - and sketched out how the regular expression engine actually matches.Start from the left hand line, and you'll see that the first line leads into the *, and there are two lines leading out. Where there are two lines out of a symbol on these diagrams, the regular expression engine tries the uppermost branch first and only goes on to the lower branch if the upper branch leads it to a dead end. At each and every decision point, the current state of the match is saved away so that the engine can regress as far as need be.
Let's take the example string "graham@wellho.net" and see how that matches ...
a) The lefthand .* loop matches g - r - a - h - a - m - @ - w - e - l - l - h - o - . - n - e - t
b) There are no more characters for the upper branch, so the engine trys the lower brranch where it looks for at @ symbol - which it failes to find because it's an the end of the string. So it keep regressing ... t - e - n - . - o - h - l - l - e - w - @ until it can match
c) The @ now matches
d) The righthand .* loop matches w - e - l - l - h - o - . - n - e - t
e) There are no more characters for the upper branch, so the engine advances down the lower branch and finds that the match is completed, so it returns a success.
Regular expression diagrams such as this can be a big help in seeing what and how matching is done, and it will also help you appreciate where matching is efficient and where it's going to use a very great deal of resources going forward and regressing backward. To help you, here are some of the basic component diagrams for other counts:
Upper diagram - '.+' - one or more characters, greedy match. Lower diagram - '.+?' - one or more characters, sparse match
Upper diagram - '.?' - zero or one characters, greedy match. Lower diagram - '.??' - zero or one characters, sparse match
Upper diagram - '.*' - zero or more characters, greedy match. Lower diagram - '.*?' - zero or more characters, sparse matchSparse and Greedy matching is covered in more detail [here] and there's a source code demonstration of the difference that it makes [here].