DFA SUB-SCANS
In a DFA, a sub-scan is executed during a DFA scan. The sub-scan consumes input symbols out of sequence relative to the DFA scan, either forward or in reverse. An input symbol in the DFA scan is matched. A sub-scan command is supplied to the DFA. The sub-scan command is executed and at least one symbol is consumed in the sub-scan.
1 . A method of executing a sub-scan during a DFA scan, wherein said sub-scan consumes input symbols out of sequence relative to said DFA scan, said method comprising:
matching at least one input symbol in said DFA scan;
supplying a sub-scan command to a DFA;
processing said sub-scan command; and
consuming at least one input symbol in said sub-scan.
2 . The method of claim 1 , wherein said step of supplying a sub-scan command comprises encoding at least one instruction with a sub-scan command.
3 . The method of claim 2 , wherein said sub-scan command comprises at least one of a reference to a root state of a sub-DFA for said sub-scan, a jump distance, a location code, a flag indicating the direction of said sub-scan, a flag indicating whether a return value is expected from said sub-scan, and a flag indicating whether said sub-scan should return to said DFA scan when said resulting sub-scan is complete.
4 . The method of claim 1 , wherein the process of processing said sub-scan command comprises accessing a second sub-scan command and performing said second sub-scan.
5 . The method of claim 1 , wherein the process of processing said sub-scan command comprises saving a current scan context and returning to said DFA scan after said sub-scan completes.
6 . The method of claim 5 , wherein saving a current scan context comprises saving a current scan context recursively to a stack.
7 . The method of claim 1 , wherein the process of processing said sub-scan command comprises:
saving a current scan context;
determining a first symbol position of said sub-scan;
accessing said first symbol position of said sub-scan;
accessing a root state of said sub-scan; and
entering said root state and taking a first sub-scan transition.
8 . The method of claim 7 , wherein taking a first sub-scan transition comprises matching a symbol in said sub-scan.
9 . The method of claim 7 , wherein taking a first sub-scan transition comprises taking an implied failure transition by terminating said sub-scan if no other transition matches.
10 . The method of claim 1 , wherein said sub-scan consumes input symbols in reverse order.
11 . A method for matching rules in a DFA, said method comprising:
performing a primary DFA descent in a DFA engine, said descent comprising consuming input symbols from an input stream in sequence, matching said symbols and transitioning to a next state upon said matching;
accessing a sub-scan command to commence a sub-scan, said sub-scan command being associated with a sub-DFA wherein input symbols from said input stream will be consumed out of sequence relative to said primary DFA descent;
performing a sub-scan, wherein results of said sub-scan will return a return value to said primary descent, said return value indicating whether said sub-scan matched a corresponding portion of one of said rules; and
continuing said primary DFA descent through a transition determined by said return value.
12 . The method of claim 11 , wherein performing said sub-scan comprises accessing a second sub-scan command and performing a second sub-scan.
13 . The method of claim 11 wherein said sub-scan is used to match a look-around assertion in one of said rules.
14 . The method of claim 11 , wherein said sub-scan is used to match a weak rule beginning.
15 . The method of claim 11 , wherein said sub-scan command comprises at least one of a reference to said root state of a sub-DFA for said sub-scan, a jump distance, a location code, a flag indicating the direction of said sub-scan, a flag indicating whether a return value is expected from said sub-scan, and a flag indicating whether said sub-scan should return to said DFA scan when it completes.
16 . The method of claim 11 , wherein said sub-scan command is encoded in a DFA instruction.
17 . The method of claim 11 , wherein said sub-scan consumes input symbols in reverse order.
18 . The method of claim 11 , wherein said step of performing said sub-scan comprises:
saving a current scan context;
determining a first symbol position of said sub-scan;
accessing first symbol position of said sub-scan;
accessing a root state of said sub-scan; and
entering said root state and taking a first sub-scan transition.
19 . A system of matching rules in a DFA, said system comprising:
a DFA compiler enabled to generate a DFA from a ruleset, to encode said DFA into an instruction set, to identify sub-scan requirements, to separate automaton sub-expressions corresponding to said identified sub-scan requirements, to build sub-DFAs based on said automaton sub-expressions, to annotate a DFA portion with sub-scan commands linking to sub-DFA instructions; and
a DFA engine enabled to execute DFA descents using said DFA instructions, said execute enablement comprising a capability to save scan context in a storage system, jump to sub-scan states and symbol positions, execute a sub-scan descent, generate return values and resume a primary scan base on said return values.
20 . The system of claim 19 , wherein said sub-scan requirements comprise matching a look-around assertion.
21 . The system of claim 19 , wherein said sub-scan requirements comprise deferring matching of a weak rule beginning.
22 . The system of claim 19 , wherein said sub-scan requirements comprise splitting a portion of said DFA into a plurality of pieces.
23 . The system of claim 19 , wherein said sub-scan comprises a backward symbol consumption command.