The State of the Art in Intrusion Prevention and Detection

248 The State of the Art in Intrusion Prevention and Detection

10.4.2 froM regular expreSSion to nfa

10.4.2.1 Parsing PCRE

Conventionally, the compilation of a regular expression (regex) starts from parsing the regex into

a right-leaned (or left-leaned) parse tree representing the right-linear (or left-linear) production

for the regular language [44]. When used for NIDS regular expressions in the Perl-compatible

regular expression (PCRE) format, however, this approach is not concise for constrained rep-

etitions. A repetition of {n} will be parsed as n identical concatenation nodes. A repetition of

{m, n} will be converted to an (n – m)–level nested union node in the parse tree. It creates an

unnecessarily deep tree, which, in turn, results ...