TY - JOUR AU - Grobauer, Bernd AU - Lawall, Julia L. PY - 2000/06/01 Y2 - 2024/03/28 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 SP - AB - Specializing string matchers is a canonical example of partial evaluation.<br /> A naive implementation of a string matcher repeatedly matches a<br />pattern against every substring of the data string; this operation should<br />intuitively benefit from specializing the matcher with respect to the pattern.<br /> In practice, however, producing an efficient implementation by <br />performing this specialization using standard partial-evaluation techniques<br />has been found to require non-trivial binding-time improvements. Starting<br /> with a naive matcher, we thus present a derivation of a binding-time<br />improved string matcher. We prove its correctness and show that specialization<br /> with respect to a pattern yields a matcher with code size linear<br />in the length of the pattern and running time linear in the length of its<br />input. We then consider several variants of matchers that specialize well,<br />amongst them the first such matcher presented in the literature, and we<br />demonstrate how variants can be derived from each other systematically. ER -