Optimally streaming greedy regular expression parsing

TY - GEN

T1 - Optimally streaming greedy regular expression parsing

AU - Grathwohl, Niels Bjørn Bugge

AU - Henglein, Fritz

AU - Rasmussen, Ulrik Terp

N1 - Conference code: 11

PY - 2014

Y1 - 2014

N2 - We study the problem of streaming regular expression parsing: Given a regular expression and an input stream of symbols, how to output a serialized syntax tree representation as an output stream during input stream processing. We show that optimally streaming regular expression parsing, outputting bits of the output as early as is semantically possible for any regular expression of size m and any input string of length n, can be performed in time O(2mlogm + mn) on a unit-cost random-access machine. This is for the wide-spread greedy disambiguation strategy for choosing parse trees of grammatically ambiguous regular expressions. In particular, for a fixed regular expression, the algorithm’s run-time scales linearly with the input string length. The exponential is due to the need for preprocessing the regular expression to analyze state coverage of its associated NFA, a PSPACE-hard problem, and tabulating all reachable ordered sets of NFA-states. Previous regular expression parsing algorithms operate in multiple phases, always requiring processing or storing the whole input string before outputting the first bit of output, not only for those regular expressions and input prefixes where reading to the end of the input is strictly necessary.

AB - We study the problem of streaming regular expression parsing: Given a regular expression and an input stream of symbols, how to output a serialized syntax tree representation as an output stream during input stream processing. We show that optimally streaming regular expression parsing, outputting bits of the output as early as is semantically possible for any regular expression of size m and any input string of length n, can be performed in time O(2mlogm + mn) on a unit-cost random-access machine. This is for the wide-spread greedy disambiguation strategy for choosing parse trees of grammatically ambiguous regular expressions. In particular, for a fixed regular expression, the algorithm’s run-time scales linearly with the input string length. The exponential is due to the need for preprocessing the regular expression to analyze state coverage of its associated NFA, a PSPACE-hard problem, and tabulating all reachable ordered sets of NFA-states. Previous regular expression parsing algorithms operate in multiple phases, always requiring processing or storing the whole input string before outputting the first bit of output, not only for those regular expressions and input prefixes where reading to the end of the input is strictly necessary.

U2 - 10.1007/978-3-319-10882-7_14

DO - 10.1007/978-3-319-10882-7_14

M3 - Article in proceedings

SN - 978-3-319-10881-0

T3 - Lecture notes in computer science

SP - 224

EP - 240

BT - Theoretical Aspects of Computing – ICTAC 2014

A2 - Ciobanu, Gabriel

A2 - Méry, Dominique

PB - Springer

T2 - 11th International Colloquium on Theoretical Aspects of Computing

Y2 - 17 September 2014 through 19 September 2014

ER -