Incremental DFA compilation with single rule granularity

A method of constructing a composite DFA (deterministic finite automaton) using subset construction, said method comprising:

• compiling a plurality single-rule DFAs;
• performing a first subset construction on said plurality single-rule DFAs to generate a first composite DFA, retaining subset for said first composite DFA;
• searching said subset information for subsets containing single-rule DFA states corresponding to a rule to be deleted;
• deleting all single-rule DFA state references found during said search from said subset information;
• and
• deleting any composite DFA state whose subset becomes empty after said step of deleting all single-rule DFA state references.

A computer system comprising a non-transitory computer readable medium including programmed instructions, a compiler and a first set of rules for constructing a composite DFA (deterministic finite automaton) using subset construction, wherein the instructions, when executed by a computer, cause the computer system to:

• compile a first set of single-rule DFAs from said first set of rules;
• subset construct said single-rule DFAs into a first composite DFA, retaining subset information for said first composite DFA;
• compile at least one new rule into at least one corresponding additional single-rule DFA;
• subset construct a second composite DFA using said first composite DFA as a first NFA (non-deterministic finite automaton) input for subset construction and said at least one corresponding additional single-rule DFA as at least one additional NFA input for subset construction, retaining subset information;
• delete at least one rule from said set of rules by use of a search of said subset information for subsets containing single-rule DFA states corresponding to a rule to be deleted;
• delete all single rule DFA state references found during said search from said subset information;
• and
• delete any composite DFA state whose subset becomes empty.