How a RegEx engine works

Question

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.

Answer 1

Read:

http://www.regular-expressions.com

Try:

http://www.regexbuddy.com/

RegexBuddy is highly recommended. It will show you how the regex engines processes an input and also breaks down regexes so they are easy to understand.

Answer 2

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.

Answer 3

Take some book about Authomata Theory.

Also good articles can be found there: http://swtch.com/~rsc/regexp/