Two-pass greedy regular expression parsing

Niels Bjørn Bugge Grathwohl; Fritz Henglein; Lasse Nielsen; Ulrik Terp Rasmussen

doi:10.1007/978-3-642-39274-0_7

Two-pass greedy regular expression parsing

Niels Bjørn Bugge Grathwohl, Fritz Henglein, Lasse Nielsen, Ulrik Terp Rasmussen

6 Citations (Scopus)

Abstract

We present new algorithms for producing greedy parses for regular expressions (REs) in a semi-streaming fashion. Our lean-log algorithm executes in time O(mn) for REs of size m and input strings of size n and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only O(m) words of random-access memory (independent of n); requiring only k n bits of sequentially written and read log storage, where k < 1/3m is the number of alternatives and Kleene stars in the RE; processing the input string as a symbol stream and not requiring it to be stored at all. Previous RE parsing algorithms do not scale linearly with input size, or require substantially more log storage and employ 3 passes where the first consists of reversing the input, or do not or are not known to produce a greedy parse. The performance of our unoptimized C-based prototype indicates that our lean-log algorithm has also in practice superior performance and is surprisingly competitive with RE tools not performing full parsing, such as Grep.

Original language	English
Title of host publication	Implementation and Application of Automata : 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings
Editors	Stavros Konstantinidis
Number of pages	12
Publisher	Springer
Publication date	2013
Pages	60-71
ISBN (Print)	978-3-642-39273-3
ISBN (Electronic)	978-3-642-39274-0
DOIs	https://doi.org/10.1007/978-3-642-39274-0_7
Publication status	Published - 2013
Event	18th International Conference on Implementation and Application of Automata - Halifax, Canada Duration: 16 Jul 2013 → 19 Jul 2013 Conference number: 18

Conference

Conference	18th International Conference on Implementation and Application of Automata
Number	18
Country/Territory	Canada
City	Halifax
Period	16/07/2013 → 19/07/2013

Access to Document

10.1007/978-3-642-39274-0_7

Cite this

Two-pass greedy regular expression parsing. / Grathwohl, Niels Bjørn Bugge; Henglein, Fritz; Nielsen, Lasse et al.
Implementation and Application of Automata: 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings. ed. / Stavros Konstantinidis . Springer, 2013. p. 60-71.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Grathwohl, NBB, Henglein, F, Nielsen, L & Rasmussen, UT 2013, Two-pass greedy regular expression parsing. in S Konstantinidis (ed.), Implementation and Application of Automata: 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings. Springer, pp. 60-71, 18th International Conference on Implementation and Application of Automata, Halifax, Canada, 16/07/2013. https://doi.org/10.1007/978-3-642-39274-0_7

@inproceedings{792c8e79119342e3a291c4372b6f37b9,

title = "Two-pass greedy regular expression parsing",

abstract = "We present new algorithms for producing greedy parses for regular expressions (REs) in a semi-streaming fashion. Our lean-log algorithm executes in time O(mn) for REs of size m and input strings of size n and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only O(m) words of random-access memory (independent of n); requiring only k n bits of sequentially written and read log storage, where k < 1/3m is the number of alternatives and Kleene stars in the RE; processing the input string as a symbol stream and not requiring it to be stored at all. Previous RE parsing algorithms do not scale linearly with input size, or require substantially more log storage and employ 3 passes where the first consists of reversing the input, or do not or are not known to produce a greedy parse. The performance of our unoptimized C-based prototype indicates that our lean-log algorithm has also in practice superior performance and is surprisingly competitive with RE tools not performing full parsing, such as Grep.",

author = "Grathwohl, {Niels Bj{\o}rn Bugge} and Fritz Henglein and Lasse Nielsen and Rasmussen, {Ulrik Terp}",

year = "2013",

doi = "10.1007/978-3-642-39274-0_7",

language = "English",

isbn = "978-3-642-39273-3",

pages = "60--71",

editor = "{Konstantinidis }, Stavros",

booktitle = "Implementation and Application of Automata",

publisher = "Springer",

note = "18th International Conference on Implementation and Application of Automata, CIAA 2013 ; Conference date: 16-07-2013 Through 19-07-2013",

}

TY - GEN

T1 - Two-pass greedy regular expression parsing

AU - Grathwohl, Niels Bjørn Bugge

AU - Henglein, Fritz

AU - Nielsen, Lasse

AU - Rasmussen, Ulrik Terp

N1 - Conference code: 18

PY - 2013

Y1 - 2013

N2 - We present new algorithms for producing greedy parses for regular expressions (REs) in a semi-streaming fashion. Our lean-log algorithm executes in time O(mn) for REs of size m and input strings of size n and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only O(m) words of random-access memory (independent of n); requiring only k n bits of sequentially written and read log storage, where k < 1/3m is the number of alternatives and Kleene stars in the RE; processing the input string as a symbol stream and not requiring it to be stored at all. Previous RE parsing algorithms do not scale linearly with input size, or require substantially more log storage and employ 3 passes where the first consists of reversing the input, or do not or are not known to produce a greedy parse. The performance of our unoptimized C-based prototype indicates that our lean-log algorithm has also in practice superior performance and is surprisingly competitive with RE tools not performing full parsing, such as Grep.

AB - We present new algorithms for producing greedy parses for regular expressions (REs) in a semi-streaming fashion. Our lean-log algorithm executes in time O(mn) for REs of size m and input strings of size n and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only O(m) words of random-access memory (independent of n); requiring only k n bits of sequentially written and read log storage, where k < 1/3m is the number of alternatives and Kleene stars in the RE; processing the input string as a symbol stream and not requiring it to be stored at all. Previous RE parsing algorithms do not scale linearly with input size, or require substantially more log storage and employ 3 passes where the first consists of reversing the input, or do not or are not known to produce a greedy parse. The performance of our unoptimized C-based prototype indicates that our lean-log algorithm has also in practice superior performance and is surprisingly competitive with RE tools not performing full parsing, such as Grep.

U2 - 10.1007/978-3-642-39274-0_7

DO - 10.1007/978-3-642-39274-0_7

M3 - Article in proceedings

SN - 978-3-642-39273-3

SP - 60

EP - 71

BT - Implementation and Application of Automata

A2 - Konstantinidis , Stavros

PB - Springer

T2 - 18th International Conference on Implementation and Application of Automata

Y2 - 16 July 2013 through 19 July 2013

ER -

Two-pass greedy regular expression parsing

Abstract

Conference

Access to Document

Fingerprint

Cite this