Blended match mode DFA scanning
View Patent ↗Disclosed is a method for simultaneously finding matches for rules that require greedy matching and comprehensive matching by executing a single Deterministic Finite Automaton (DFA). DFAs annotations are used to enable a single DFA to represent rules that require greedy and comprehensive matching. DFA descents are performed from various positions in an input stream, match information is recorded and match results are selectively generated (filtered) to achieve the greedy or comprehensive match behavior required by individual rules.
1. A method for matching rules to an input stream by executing a single DFA having a plurality of states, wherein said rules require greedy matching and comprehensive matching, comprising:
in a scanner:
executing the DFA in a single scan descent;
reporting comprehensive match tokens;
reporting greedy match tokens; and
if it is known that a given start position in the input stream cannot be the beginning of a comprehensive match, and the start position overlaps a committed greedy match, skipping to the next viable position in the input stream.
2. The method of claim 1 , wherein the step of reporting greedy matches comprises:
recording non-terminal matches as greedy-last accept information;
updating the greedy-last accept information as the descent continues; and
reporting the last updated greedy-last accept information when the descent ends.
3. The method of claim 1 , said method further comprising selectively filtering greedy matches by iteratively inspecting match tokens in the increasing order of the start position.
4. The method of claim 1 , wherein the step of reporting greedy matches comprises:
recording non-terminal matches as greedy-last accept information;
updating the greedy-last accept information as the descent continues;
reporting the last updated greedy-last accept information when the descent ends; and
wherein said method further comprises selectively filtering greedy matches by iteratively inspecting match tokens in the increasing order of the start position.
5. The method of claim 1 , wherein the steps of reporting comprehensive match tokens and reporting greedy match tokens do not affect each other.
6. The method of claim 1 , said method further comprising:
sorting any reported tokens.
7. The method of claim 1 , said method further comprising:
annotating sections of branches in the DFA that lead only to greedy matches, wherein a scanner is enabled to abandon DFA descents that overlap committed greedy matches.
8. The method of claim 1 , wherein each of said plurality of states is associated with a state instruction block:
wherein an accepting state instruction block contains at least one comprehensive match token and at least one greedy match token; and
the at least one comprehensive match token is at a nonnegative offset from the base address in the state instruction block and the at least one greedy match token is at a negative offset from the base address in the state instruction.