Extending regular expressions
Steven M. Kearns · University Microfilms International eBooks · 1991
Regular expressions are used in many applications to specify patterns because they can be compiled into very efficient one-pass pattern matchers; at the same time, they can specify a wide range of patterns of practical interest. The thesis extends regular expressions in 4 ways. First, we give a simple, efficient algorithm for matching an extended regular expression language. The language includes a number of new operators for expressing patterns, including operators that specify the context of a match, and operators that can require arbitrary lookahead. The new operators make it feasible to specify many more patterns than practical before, but the new matching algorithm retains the efficient of one-pass pattern matching. Second, we show how to extract a parse from a successful match, which provides significantly more information from a match than possible before. Third, we describe practical optimizations for efficiently implementing the matching and parse extraction algorithms. Fourth, we demonstrate how the new pattern matching capabilities can be integrated with an existing programming language, by describing a program generator for pattern matching applications. The program generator is called TLex. We describe the results of its use in several real-life applications.