theory - How a RegEx engine works

Question

question from:https://stackoverflow.com/questions/3622398/how-a-regex-engine-works

Answer 1

There are two main classes of regex engines.

1. Those based on Finite State Automaton. These are generally the fastest. They work by building a state machine, and feeding it characters from the input string. It is difficult, if not impossible, to implement some more advanced features in engines like this.

   Examples of FSA based engines:

   • Posix/GNU ERE/BRE — Used in most unix utilities, such as grep, sed and awk.
   • Re2 — A relatively new project for trying to give more power to the Automata based method.
      

2. Those based on back-tracking. These often compile the pattern into byte-code, resembling machine instructions. The engine then executes the code, jumping from instruction to instruction. When an instruction fails, it then back-tracks to find another way to match the input.

   Examples of back-tracking based engines:

   • Perl — The original. Most other engines of this type try to replicate the functionality of regexes in the Perl language.
   • PCRE — The most successful implementation. This library is the most widely used implementation. It has a rich set of features, some of which can't be considered as "Regular" any more.
   • Python, Ruby, Java, .NET — Other implementations I don't intend to describe further.

For more information:

• regular-expressions.info - Tutorial
• regular-expressions.info - Flavor comparison
• swtch.com - Implementing Regular Expressions — A good set of articles about effective, Automata based, regular expressions.

If you want me to expand on something, post a comment.