Method and apparatus for compiling regular expressions
AssigneeMicron Technology, Inc.
InventorsPaul Glendenning, Junjuan Xu
Life of this patent
Estimating the term…
Abstract
Apparatus, systems, and methods for a compiler are described. One such compiler converts source code into an automaton comprising states and transitions between the states, wherein the states in the automaton include a special purpose state that corresponds to a special purpose hardware element. The compiler converts the automaton into a netlist, and places and routes the netlist to provide machine code for configuring a target device.
Claims15
A machine-readable medium that is not a transitory propagating signal, the machine-readable medium including instructions that, when executed by a machine, cause the machine to perform operations comprising:
- optimizing an automaton created from source code elements including combining redundant states;
- mapping states of the automaton to hardware elements of a target device;
- identifying at least one of a conflict or further optimization between the automaton and the hardware elements of the target device during the mapping;
- modifying the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton, the modified automaton including at least one of a state unrolled into multiple states or multiple states collapsed to a special purpose state corresponding to special purpose hardware element to resolve the optimization or conflict;
- and
- mapping the modified automaton to the target device.
A machine-implemented method comprising:
- optimizing an automaton created from source code elements including combining redundant states;
- mapping states of the automaton to hardware elements of a target device;
- identifying at least one of a conflict or a further optimization between the automaton and the hardware elements of the target device during the mapping;
- modifying the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton, the modified automaton including at least one of a state unrolled into multiple states or multiple states collapsed to a special purpose state corresponding to special purpose hardware element to resolve the optimization or conflict;
- and
- mapping the modified automaton to the target device.
A system comprising:
- a memory including instructions stored thereon;
- and
- a processor communicatively coupled to the memory when the computer is in operation, wherein the instructions, when executed by the processor, cause the processor to:
- optimize an automaton created from source code elements including combining redundant states;
- map states of the automaton to hardware elements of a target device;
- identify at least one of a conflict or a further optimization between the automaton and the hardware elements of the target device during the mapping;
- modify the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton, the modified automaton including at least one of a state unrolled into multiple states or multiple states collapsed to a special purpose state corresponding to special purpose hardware element to resolve the optimization or conflict;
- and
- map the modified automaton to the target device.
Dependencies are inferred from the claim text.