TY - JOUR
AU - Bernd Grobauer
AU - Julia Lawall
PY - 2000/06/01
Y2 - 2020/12/04
TI - Partial Evaluation of Pattern Matching in Strings, revisited
JF - BRICS Report Series
JA - BRICS
VL - 7
IS - 31
SE - Articles
DO - 10.7146/brics.v7i31.20165
UR - https://tidsskrift.dk/brics/article/view/20165
AB - Specializing string matchers is a canonical example of partial evaluation. A naive implementation of a string matcher repeatedly matches apattern against every substring of the data string; this operation shouldintuitively benefit from specializing the matcher with respect to the pattern. In practice, however, producing an efficient implementation by performing this specialization using standard partial-evaluation techniqueshas been found to require non-trivial binding-time improvements. Starting with a naive matcher, we thus present a derivation of a binding-timeimproved string matcher. We prove its correctness and show that specialization with respect to a pattern yields a matcher with code size linearin the length of the pattern and running time linear in the length of itsinput. We then consider several variants of matchers that specialize well,amongst them the first such matcher presented in the literature, and wedemonstrate how variants can be derived from each other systematically.
ER -