Thursday, January 06, 2005
Regular Expression Internals - I
Introduction:
Many people don’t use Regular Expressions because they can look confusing and complicated and nothing written here is going to change that. A Regular Expression is basically a formula for matching strings that follow some pattern. A bit of ‘put into practice’ is an easy way to get specialized in these intricate expressions. This article covers how regular expression engine works internally.
How a Regular Expression Engine works internally?
Basically, Regular expressions are made up of normal characters and metacharacters. Normal characters include upper and lower case letters and digits. The metacharacters are special characters and have special meanings. Understanding metacharacters really make good use of regular expressions. More than the output, when we know the internals operations of how a particular expression works, then it becomes easy for us to formulate any simple or a complex expression. This will also save us from lots of guesswork and confusions when formulating an expression.
There are basically two kinds of regular expression engines: text-directed engines and regex-directed engines.
Text-directed engine is a DFA (Deterministic Finite Automation) which runs in linear time because they do not require backtracking (and thus they never test the same character twice). They also match the longest possible string. However, since a DFA engine contains only finite state, it cannot match a pattern with backreferences, and because it does not construct an explicit expansion, it cannot capture subexpressions.
The features of text-directed engine are:
- might be done when program is compiled
- might be done at runtime (just before string matching is needed)
- some implementations even compile the regex in the midst of matching (if a match is found before the entire DFA is constructed, they can just stop)
Regex-directed engine is a NFA (Non-deterministic Finite Automation) and this algorithm tests all possible expansions of a regular expression in a specific order and accepting the first match. Because a NFA constructs a specific expansion of the regular expression for a successful match, it can capture subexpression matches and matching backreferences. However, since an NFA backtracks, it can visit exactly the same state multiple times if the state is arrived at over different paths. As a result, it can run slowly in the worst case. Since an NFA accepts the first match it finds, it can also leave other (possibly longer) matches undiscovered.
Regex-directed engines are much favored by programmers because they are more expressive than DFA engine. Although in the worst case they can run slowly, we can steer them to find matches in linear or polynomial time using patterns that reduce ambiguities and limit backtracking.
The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl.
Note : A very important point that has to be understood when using a regex-directed engine is that it will always return the leftmost match, even if a "better" match could be found later. When applying a regular expression to a string, the engine will start at the first character of the string. It will try all possible permutations of the regular expression at the first character. Only if all possibilities have been tried and found to fail, will the engine continue with the second character in the text. Again, it will try all possible permutations of the expression, in exactly the same order. The result is that the regex-directed engine will return the leftmost match.
- use backtracking algorithm to "try out the guesses"
- different flavors of backtracking give different performance
- can add in "extras" with no serious costs
- sub-expression trapping
- Back-references (non-regular!)
Sample diagram is given below:
What is Backtracking ?
Backtracking is like basically leaving a pile of bread crumbs at every fork in the road. If the path that we choose turns out to be a dead end, then we can retrace our steps giving up ground until we come across a pile of crumbs that indicates an untried path. Should that path, too, turn out to be a dead end, we can continue to backtrack, retracing our steps to the next pile of crumbs, and so on, until we eventually find a path that leads to our goal or until we run out of untried paths.
There are basically 2 points on backtracking: The general idea of how backtracking works is fairly simple, but some of the details are quite important for real-world use. Specifically, when faced with multiple choices, which choice should be tried first? And Secondly, when forced to backtrack, which saved choice should the engine use?
In situations where the decision is between "make an attempt'' and "skip an attempt,'' as with items governed by a question, the engine always chooses to first make the attempt. It will return later (to try skipping the item) only if forced by the overall need to reach a global expression-wide match.
This simple rule has far-reaching repercussions. For starters, it helps explain regex greediness, but not completely. To complete the picture, we need to know which (among possibly many) saved options to use when we backtrack. To simply put: the most recently saved option is the one returned to when a local failure forces backtracking. It's LIFO (last in first out).
This is easily understood in the crummy analogy -- if your path becomes blocked, you simply retrace your steps until you come across a pile of bread crumbs. The first you'll return to is the most recently laid. The traditional analogy for describing LIFO also holds: like stacking and unstacking dishes, the most-recently stacked will be the first you'll unstack .
Conclusion:
To sum up, a simple regular expression engine applying an expression once will outperform a state of the art plain text search algorithm searching through the data five times. Regular expressions also reduce development time. With a regular expression engine, it takes only one line (e.g. in Perl, PHP, Java or .NET) or a couple of lines (e.g. in C using PCRE) of code to say, check if the user's input looks like a valid email address.
We will see the concepts in regular expressions and how to formulate an expression in the next article.
Happy Programming....
Monday, January 03, 2005
Happy New Year ...
