This is the substantially revised and almost completely re-written (paper and implementation) version of our earlier draft.
Friday, 8 June 2012
Regular Expression Sub-Matching using Partial Derivatives
Regular expression sub-matching is the problem of finding for each sub-part of a regular expression a matching sub-string. Prior work applies Thompson and Glushkov NFA methods for the construction of the matching automata. We propose the novel use of derivatives and partial derivatives for regular expression sub-matching. Our benchmarking results show that the run-time performance is promising and that our approach can be applied in practice.