Programming Perl, 4th Edition

The Little Engine That /Could(n’t)?/

And now we’d like to tell you the story of the Little Regex Engine that says, “I think I can. I think I can. I think I can.”

In this section, we lay out the rules used by Perl’s regular expression engine to match your pattern against a string. The Engine is extremely persistent and hardworking. It’s quite capable of working even after you think it should quit. The Engine doesn’t give up until it’s certain there’s no way to match the pattern against the string. The Rules below explain how the Engine “thinks it can” for as long as possible, until it knows it can or can’t. The problem for our Engine is that its task is not merely to pull a train over a hill. It has to search a (potentially) very complicated space of possibilities, keeping track of where it has been and where it hasn’t.

The Engine uses a nondeterministic finite-state automaton (NFA, not to be confused with NFL, a nondeterministic football league) to find a match. That just means that it keeps track of what it has tried and what it hasn’t, and when something doesn’t pan out, it backs up and tries something else. This is known as backtracking. (Er, sorry—we didn’t invent that term. Really.) The Engine is capable of trying a million subpatterns at one spot, then giving up on all those, backing up to within one choice of the beginning, and trying the million subpatterns again at a different spot. The Engine is not terribly intelligent—just persistent, and thorough. If you’re cagey, you ...