Bit-coded regular expression parsing
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Bit-coded regular expression parsing. / Nielsen, Lasse; Henglein, Fritz.
Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. ed. / Adrian-Horia Dediu; Shunsuke Inenaga; Carlos Martín-Vide. Springer, 2011. p. 402-413 (Lecture notes in computer science, Vol. 6638).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Bit-coded regular expression parsing
AU - Nielsen, Lasse
AU - Henglein, Fritz
N1 - Conference code: 5
PY - 2011
Y1 - 2011
N2 - Regular expression parsing is the problem of producing a parse tree of a string for a given regular expression. We show that a compact bit representation of a parse tree can be produced efficiently, in time linear in the product of input string size and regular expression size, by simplifying the DFA-based parsing algorithm due to Dub ´e and Feeley to emit the bits of the bit representation without explicitly materializing the parse tree itself. We furthermore show that Frisch and Cardelli’s greedy regular expression parsing algorithm can be straightforwardly modified to produce bit codings directly. We implement both solutions as well as a backtracking parser and perform benchmark experiments to gauge their practical performance. We observe that our DFA-based solution can be significantly more time and space efficient than the Frisch-Cardelli algorithm due to its sharing of DFA- nodes, but that the latter may still perform better on regular expressions that are “more deterministic” from the right than the left. (Backtracking is, unsurprisingly, quite hopeless.)
AB - Regular expression parsing is the problem of producing a parse tree of a string for a given regular expression. We show that a compact bit representation of a parse tree can be produced efficiently, in time linear in the product of input string size and regular expression size, by simplifying the DFA-based parsing algorithm due to Dub ´e and Feeley to emit the bits of the bit representation without explicitly materializing the parse tree itself. We furthermore show that Frisch and Cardelli’s greedy regular expression parsing algorithm can be straightforwardly modified to produce bit codings directly. We implement both solutions as well as a backtracking parser and perform benchmark experiments to gauge their practical performance. We observe that our DFA-based solution can be significantly more time and space efficient than the Frisch-Cardelli algorithm due to its sharing of DFA- nodes, but that the latter may still perform better on regular expressions that are “more deterministic” from the right than the left. (Backtracking is, unsurprisingly, quite hopeless.)
U2 - 10.1007/978-3-642-21254-3_32
DO - 10.1007/978-3-642-21254-3_32
M3 - Article in proceedings
SN - 978-3-642-21253-6
T3 - Lecture notes in computer science
SP - 402
EP - 413
BT - Language and Automata Theory and Applications
A2 - Dediu, Adrian-Horia
A2 - Inenaga, Shunsuke
A2 - Martín-Vide, Carlos
PB - Springer
T2 - 5th International Conference on Language and Automata Theory and Applications
Y2 - 26 May 2011 through 31 May 2011
ER -
ID: 50858641