Regular Expression Part - 1

Introduction

Many people don�t use Regular Expressions because they 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 a certain pattern. A bit of "put into practice" is an easy way to get specialized in these intricate expressions. This article covers how a regular expression engine works internally.

How a Regular Expression engine works internally?

Basically, Regular Expressions are made up of normal characters and meta characters. Normal characters include upper and lower case letters and digits. The meta characters are special characters and have special meanings. Understanding meta characters really make good use of regular expressions.

More than the output, it is the internal operation of how a particular expression works which is important, because 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 while 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 back references, and because it does not construct an explicit expansion, it cannot capture sub expressions.

The features of text-directed engine are:

• Searching is fast.
• Search time depends on the length of the string.
• Takes more memory (state explosion in NFA to DFA construction) than NFA.
• Takes longer to compile the regex.
  • 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).

For example:

Regular Expression: (a | b)*abb

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, accepting the first match. Because a NFA constructs a specific expansion of the regular expression for a successful match, it can capture sub expression matches and matching of back references. However, since a NFA backtracks, it can visit exactly the same state multiple times if the state is arrived at over different paths. As a result, it runs slowly in the worst case. Since a 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 the DFA engine. Although in the worst case they can run slowly, we can steer them up 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 while 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 with the first character of the string. It will try all possible permutations of the regular expression with 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.

The features of a regex-directed engine are:

• Searching can be slow (more on this later).
• Search time depends on regex.
• Takes less memory than DFA (how much depends on regex).
• Compiles more quickly than DFA (how much depends on regex).
• Needs to explore paths.
  • Uses backtracking algorithm to "try out the guesses".
  • Different flavors of backtracking give different performance.
    • when there are options, what order do we try them in?
  • Can add in "extras" with no serious costs.
    • Sub-expression trapping.
    • Back-references (non-regular!).

For example:

Regular Expression: (a | b)*abb

What is Backtracking?

Backtracking is like leaving a pile of bread crumbs at every fork in the road. If the path 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 two 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 to 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.