The Brief Guide to Regular Expressions

Regular expressions is a DSL (Domain-specific Language), which is used to match patterns of text. They are everywhere. All major programming languages have a built-in library that supports a flavor of regular expressions. The following article attempts to explore the origins of regular expressions and present their basic syntactic variations.

Origins of Regular Expressions

The theoretical background of regular expressions lies within automaton theory and formal languages. Regular expressions belong to a type 3 grammar of the Chomsky hierarchy. This hierarchy, described by Chomsky in 1956 [1], provides a categorization of grammars that describe formal languages.

In 1943 Warren McCulloch and Walter Pitts described the human neural system using automata [2]. The mathematician Stephen Kleene described the proposed models with a mathematical notation named regular sets [3]. Later Brzozowski [4] provided mathematical definitions for the Kleene regular expressions formalism, and introduced ways to convert regular expressions in to state diagrams. In the late 1960s, Ken Thompson proposed a compiler that translated a regular expression into the assembly language of an IBM 7094 processor [5]. Later on, he implemented the regular sets in his text editor named qed, and afterwards on ed, which became part of the UNIX distribution. From then on, regular expressions became widely used in almost all UNIX variants.

Ehrenfeucht and Zeiger [6] provided the academic community with four metrics that measured the complexity of regular expressions. In 1980, Ernst Leiss [7] presented an algorithm for constructing a finite automaton from a given regular expression, and two years later Floyd and Ullman [8] proposed an approach for compiling regular expressions into integrated circuits. Sensory Networks [Net04] constructed a content classification accelerator that implements a regular expression engine in hardware.

Regular expressions have also become a standard feature in many programming languages. Programming languages like Java, Ruby and Python contain regular expression engines as part of their API, and, as shown in Section 3, Perl also defines a set of operators and integrates regular expressions into its syntax [9]. In addition, Perl permits a grammar definition with syntactic rules expressed with regular expressions [10]. SQL was extended to use regular expressions patterns in its syntax [11, 12]. Most modern UNIX variants provide regular expression facilities built into the C library (libc).

In 1992, Wu and Manber [13] introduced bit-parallel searching. Navarro and Raffinot introduced in 2005 two new techniques for regular expression searching that produce faster results [NR05]. Their idea is based in bit-parallel matching [13, 14] and Gluskhov’s NFA construction algorithm [15]. This approach is implemented in the NRGrep tool [16]. Navarro [17] also introduced a way of searching text patterns on compressed data.

Regular expressions are mainly used in a variety of software projects as a standard way to perform pattern matching and text validation. Lex [18] introduced a method to write lexical analyzers based on regular expressions and automatically generate their code. Nowadays, lex is considered a classic lexical analysis tool [19, 20]. Clarke and Cormack [21] demonstrate a practical way to parse structured text using regular expressions. They also provide an extension rule to regular expressions and a prototype implementation for testing. Spinellis [22] also used regular expressions in his assembly optimizer.

Research to expand regular expressions is also found in literature, usually trying to generate test data that obey specific patterns. Hamilton [23] introduces an algorithm to expand generalized regular expressions, and Wentworth [24] demonstrates a prototype implementation in Haskell.

Although many scientists have worked on improving the performance of regular expression engines, sometimes the bottlenecks lie elsewhere. Hume’s Grep Wars [25] is a classic example. In this publication, Hume describes a new I/O library (fio) that was used in the grep utility and improved its performance by a factor of 8.

Regular Expression Mechanics

A typical regular expression engine is defined by two main characteristics: (1) engine type and (2) syntax standard. According to their engine type, regular expression implementations can be divided into two main categories [26, 27]:

NFA (Non-deterministic Finite Automaton) The engine represents the regular expressions as a non- deterministic finite automaton. NFA-based libraries are generally slower, but allow syntactically richer regular expressions. NFA based engines are categorized into Traditional NFA and POSIX NFA engines. NFA engines have typically slower execution time than DFA [27]. NFA-based engines are known as “regular expression-directed”, indicating that the engine dictates the matching process.

DFA (Deterministic Finite Automaton) DFA-based implementations construct a deterministic automaton to represent the regular expression. Deterministic automaton based engines are generally faster and predictable, returning always the longest leftmost match. They are more difficult to implement and lack certain features, such as backtracking. DFA based engines are known as “text-directed”.

Regular expressions come in three dominant syntax standards. We emphasize here that the syntax does not imply a corresponding engine type. These are:

• Traditional UNIX regular expressions
• POSIX (extended) modern regular expressions
• Perlcompatibleregularexpressions(PCRE)

The traditional UNIX regular expression was the first syntax that was defined and implemented. It has now been replaced by the POSIX standard, although most UNIX applications and utilities, such as sed and grep, provide support for it. Notably, its syntax does not provide the union operator (“|”). POSIX extended regular expressions provide an extension to the aforementioned syntax. Three new operators are introduced: (1) union (“|”), (2) zero or one matching (“?”) and (3) one or more matching (“+”). Table II illustrates the most common operators of traditional UNIX and POSIX standards.

POSIX also provides a protable way to define character classes. e.g. [:: lower ::] is [a−z]. These classes provided a quick and compact way to solve internationalization problems. For example, the Greek language features an alphabet different than the Latin, so in order to write a generic regular expression that matches non-capital alphanumeric characters, an abstract form of character representation is needed to transparently match text according to the system’s locale.

Perl compatible regular expressions (PCRE) extend the syntax to provide functions for backreferencing, assertions and conditional subexpressions.

Some Examples

• [1–9][1–9]* matches numbers like 1,2,3,4 …
• [a-f] matches the characters a,b,c,d,e and f
• a+ matches infinite sequences of “a” characters
• (m|n|kn|r)ight matches “might”, “night”, “knight” and “right”

Epilogue

I always felt that talking about regular expressions is a bit baroque, but I think it is a still important part of computer science, which is neglected in my opinion, in favor of more modern approaches.

My opinion is that regular expressions should get more attention, in terms of syntantic expression, but also in terms of performance. They are still a diamond in the rough.

Bibliography

[1] Noam Chomsky. Three Models For the Description of Language. IEEE Transactions On Information Theory, 2(3):113–124, 1956

[2] Warren S. McCulloch and Walter Pitts. A Logical Calculus of the Ideas Immanent in Nervous Activity. 5:18–27, 1943

[3] Stephen C. Kleene. Represenations of Events in Nerve Nets and Finite Automata, volume 34 of Annals of Mathematics Studies, pages 3–42. Princeton University Press, Princeton, NJ, 1956

[4] J. A. Brzozowski. Derivatives of Regular Expressions. Journal of the ACM, 11(4):481–494, 1964

[5] Ken Thompson. Regular Expression Search Algorithm. Communications of the ACM, 11(6):419–422, June 1968

[6] Andrzej Ehrenfeucht and Paul Zeiger. Complexity Measures For Regular Expressions. In STOC ’74: Proceedings of the Sixth Annual ACM Symposium On Theory of Computing, pages 75–79, New York, NY, USA, 1974. ACM Press

[7] Ernst Leiss. Constructing a Finite Automaton For a Given Regular Expression. ACM SIGACT News, 12(3):81–87, 1980

[8] Robert W. Floyd and Jeffrey D. Ullman. The compilation of Regular Expressions Into Integrated Circuits. Journal of the ACM, 29(3):603–622, 1982

[9] Larry Wall, Tom Christiansen, and Jon Orwant. Programming Perl. O’Reilly, Sebastopol, CA, 2000

[10] Teodor Zlatanov. Perl 6 Grammars and Regular Expressions, 2004

[11] Knut Stolze. Bringing the Power of Regular Expression Matching to Ssql, January 2003

[12] Andrew Eisenberg and Jim Melton. SQL:1999, Formerly Known As SQL3, 2003

[13] Sun Wu and Udi Manber. Fast text searching: allowing errors. Communications of the ACM, 35(10):83–91, 1992

[14] Ricardo Baeza-Yates and Gaston H. Gonnet. A new approach to text searching. Communications of the ACM, 35(10):74–82, 1992

[15] V-M. Glushkov. The Abstract Theory of Automata,. Russian Mathematical Surveys, 16:1–53, 1961

[16] G. Navarro. NR-Grep: a Fast and Flexible Pattern-Matching Tool. Softw. Pract. Exper., 31(13):1265–1312, 2001

[17] G. Navarro. Regular Expression Searching On Compressed Text. J. of Discrete Algorithms, 1:423–443, 2003

[18] Michael E. Lesk. Lex — A Lexical Analyzer Generator. Computer Science Technical Report 39, Bell Laboratories, Murray Hill, NJ, October 1975

[19] Stephen C. Johnson and Michael E. Lesk. Language Development Tools. Bell System Technical Journal, 56(6):2155–2176, July-August 1987

[20] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA, 1985

[21] Charles L. A. Clarke and Gordon V. Cormack. On the Use of Regular Expressions for Searching Text. ACM Transactions on Programming Languages and Systems, 19(3):413–426, 1997

[22] Diomidis Spinellis. Declarative Peephole Optimization using String Pattern Matching. ACM SIGPLAN, 34(2):47– 51, February 1999

[23] Eric Hamilton. Literate Programming — Expanding Generalized Regular Expressions. Commucations of the ACM, 31(12):1376–1385, December 1988

[24] E. P. Wentworth. Generalized Regular Expressions: a Programming Exercise in Haskell. SIGPLAN Not., 28(5):49– 54, 1993

[25] Andrew Hume. Grep Wars: The Strategic Search Initiative. In Peter Collinson, editor, Proceedings of the EUUG Spring 88 Conference, pages 237–245, Buntingford, UK, 1988. European UNIX User Group

[26] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA, 1985

[27] Jeffrey E. F. Friedl. Mastering Regular Expressions 2nd Edition. O’Reilly and Associates, Inc., Sebastopol, CA, 2002