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 Citationer (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 kn
bits of sequentially written and read log storage, where k <
1/3 m 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 the superior
performance of our lean-log algorithm can also be observed in
practice; it is also surprisingly competitive with RE tools
not performing full parsing, such as Grep.

Originalsprog	Engelsk
Titel	Implementation and Application of Automata : 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings
Redaktører	Stavros Konstantinidis
Antal sider	12
Forlag	Springer
Publikationsdato	2013
Sider	60-71
ISBN (Trykt)	978-3-642-39273-3
ISBN (Elektronisk)	978-3-642-39274-0
DOI	https://doi.org/10.1007/978-3-642-39274-0_7
Status	Udgivet - 2013
Begivenhed	18th International Conference on Implementation and Application of Automata - Halifax, Canada Varighed: 16 jul. 2013 → 19 jul. 2013 Konferencens nummer: 18

Konference

Konference	18th International Conference on Implementation and Application of Automata
Nummer	18
Land/Område	Canada
By	Halifax
Periode	16/07/2013 → 19/07/2013

Adgang til dokumentet

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

Citationsformater

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. red. / Stavros Konstantinidis . Springer, 2013. s. 60-71.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Grathwohl, NBB, Henglein, F, Nielsen, L & Rasmussen, UT 2013, Two-pass greedy regular expression parsing. i S Konstantinidis (red.), Implementation and Application of Automata: 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings. Springer, s. 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater