45

In learning Regular Expressions it had me wondering how the underlying engine works. Probably more specifically, I'd like to know more about how it evalutates, prioritizies and parses the expression. I feel the RegEx engine is a blackbox to me, and I would really enjoy deciphering it.

So I'd like to ask if there are some great resources that I could read up on that discuss RegEx engine theory.

*Note: I am not interested in building an engine, just learning the inner workings of it.

Improve this question
6
  • 1
    Regular Expression engines are based on finite-state machines. A nice article about how fast regular expression matching works is http://swtch.com/~rsc/regexp/regexp1.html. Commented Sep 1, 2010 at 21:56
  • Take some book about Authomata Theory. Also good articles can be found there: swtch.com/~rsc/regexp Commented Sep 1, 2010 at 21:57
  • 1
    Mastering Regular Expressions is a great book though it's not focused on that subject, it does have several chapters dealing with how each regex engine behaves. (though it's more of a practical manner rather than analyzing the details of the engine itself) Commented Sep 1, 2010 at 22:56
  • I've actually been poking around that book but didn't know about those chapters. Thanks! Commented Sep 2, 2010 at 0:26
  • 1
    An excellent artile is: How RegEx works Commented Nov 14, 2012 at 17:02

1 Answer 1

Reset to default
49

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:

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

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

It looks like I have some work cut out for me with the posted links but I believe this is more what I was looking for. Even further if you know of an actual book that could be purchased, that would be fantastic.
I haven't read many books on the subject, but one I liked is "Introduction to the Theory of Computation" by Michael Sipser. It is not just about Regular Expressions, but goes all the way to Turing Machines and NP-completeness, etc.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.