In this article, I propose an alternative implementation of regular expression pattern matching using Partial Derivatives.

In a similar idea, we can also use partial derivative to perform inequality/equality test among regexs. See Martin's post here.

What is the regular expression pattern matching problem?

Let's consider an example. Given a regular expression pattern, say

(x : A*, y : A*)

which matches a sequence of alphabets A and binding zero or more As to the pattern variable x and sending the rest (of As) to the other pattern variable y.

Suppose we have an input sequence

AA

(or we will call it "a word" subsequently) which matches with the above pattern and producing

one of the following possible bindings.

{ x -> AA, y -> () }

{ x -> A, y -> A }

{ x -> (), y -> AA }

The first solution is called the

*longest matched*, because the first sub pattern consumes the longest possible prefix of the word and the remaining goes to the second pattern. On the other hand, the third solution is referred to the

*shortest matched*, because the first sub pattern consumes the shortest possible prefix. In most of this article we will talk about the longest match.

## No comments:

Post a Comment