Begin anchor annotation in DFAs

摘要

Disclosed is a method and system of matching a string of symbols to a ruleset. The ruleset comprise a set of rules. The method includes ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset, annotating the accepting states of the DFA with the begin anchor information, executing the DFA, and checking begin anchor annotations to determine if begin anchor requirement are satisfied if an accepting state is reached. Embodiments also include rulesets with begin anchors on matches, rulesets with early exit information on non-accepting states, and rulesets with accept begin anchors in accepting states.

主权项

1. A method of matching a string of symbols to a ruleset, said ruleset comprising a set of pattern matching rules, comprising:
at a compiler;
ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset; andannotating the accepting states of the DFA with begin anchor information; at a server,
receiving an input stream comprising said string of symbols;to match symbols in said string of symbols, executing the DFA by a descent from a DFA root state;checking the begin anchor annotations to determine whether begin anchor requirements are satisfied if an accepting state match is reached; andreporting the match if the begin anchor requirements as annotated are satisfied; and prior to descent of the DFA, building a record of which begin anchors are satisfied by a first symbol position, wherein the record is referable during each DFA descent to check begin anchor status.