ONE PASS SUBMATCH EXTRACTION

摘要

A method for one pass submatch extraction may include receiving an input string, receiving a regular expression with capturing groups, and converting the regular expression with capturing groups into a finite automaton M to extract submatches. The finite automaton M may be evaluated to determine whether the regular expression belongs to a set of regular expressions for which submatch extraction is implemented by using one pass by determining whether an automaton M′=rev(close(M)) is deterministic. The input string may be matched to the regular expression if the regular expression belongs to the set of regular expressions for which submatch extraction is implemented by using one pass.

主权项

1. A method for one pass submatch extraction, the method comprising:
receiving an input string; receiving a regular expression with capturing groups; converting, by a processor, the regular expression with capturing groups into a finite automaton M to extract submatches; evaluating the finite automaton M to determine whether the regular expression belongs to a set of regular expressions for which submatch extraction is implemented by using one pass by determining whether an automaton M′=rev(close(M)) is deterministic; and matching the input string to the regular expression if the regular expression belongs to the set of regular expressions for which submatch extraction is implemented by using one pass.