Premium
A text pattern‐matching tool based on Parsing Expression Grammars
Author(s) -
Ierusalimschy Roberto
Publication year - 2008
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.892
Subject(s) - regular expression , computer science , parsing , pattern matching , programming language , rule based machine translation , scripting language , string searching algorithm , artificial intelligence , top down parsing language , expression (computer science) , natural language processing , theoretical computer science , top down parsing , bottom up parsing
Abstract Current text pattern‐matching tools are based on regular expressions. However, pure regular expressions have proven too weak a formalism for the task: many interesting patterns either are difficult to describe or cannot be described by regular expressions. Moreover, the inherent non‐determinism of regular expressions does not fit the need to capture specific parts of a match. Motivated by these reasons, most scripting languages nowadays use pattern‐matching tools that extend the original regular‐expression formalism with a set of ad hoc features, such as greedy repetitions, lazy repetitions, possessive repetitions, ‘longest‐match rule,’ lookahead, etc. These ad hoc extensions bring their own set of problems, such as lack of a formal foundation and complex implementations. In this paper, we propose the use of Parsing Expression Grammars (PEGs) as a basis for pattern matching. Following this proposal, we present LPEG, a pattern‐matching tool based on PEGs for the Lua scripting language. LPEG unifies the ease of use of pattern‐matching tools with the full expressive power of PEGs. Because of this expressive power, it can avoid the myriad of ad hoc constructions present in several current pattern‐matching tools. We also present a Parsing Machine that allows a small and efficient implementation of PEGs for pattern matching. Copyright © 2008 John Wiley & Sons, Ltd.