Benchmarking Regular Expression Matching
摘要
In this paper we benchmark the matching time of regular expression matching engines when they use either the Thompson or Glushkov regular expressions to state machine conversion algorithms, with or without using memoisation while matching, and doing matching either by using a lockstep or a Spencer type scheduler. We conduct our empirical investigation by expanding on the virtual machine for regular expressions matching approach, introduced by Russ Cox.