Optimally Streaming Greedy Regular Expression Parsing

Abstract

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(2^mlogm + 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.

@inproceedings{grathwohl2014,
  author = {Niels Bjørn Bugge Grathwohl, Fritz Henglein, Ulrik Terp Rasmussen},
  title = {Optimally Streaming Greedy Regular Expression Parsing},
  abstract = {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(2^{m \log m} + m n)$ 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.},
  year = {2014},
  month = {September},
  publisher = {Springer},
  booktitle = {Theoretical Aspects of Computing - ICTAC 2014},
  pages = {224-240},
  editor = {Gabriel Ciobanu, Dominique Méry},
  doi = {10.1007/978-3-319-10882-7_14},
}