Unrolling quantifications to control in-degree and/or out-degree of automaton
Apparatus, systems, and methods for a compiler are disclosed. One such compiler parses a human readable expression into a syntax tree and converts the syntax tree into an automaton having in-transitions and out-transitions. Converting can include unrolling the quantification as a function of in-degree limitations wherein in-degree limitations includes a limit on the number of transitions into a state of the automaton. The compiler can also convert the automaton into an image for programming a parallel machine, and publishes the image. Additional apparatus, systems, and methods are disclosed.
1. A computer-implemented method comprising:
converting a quantification into an automaton, wherein converting includes unrolling the quantification to control an in-degree of the automaton; and
converting the automaton into machine code corresponding to a target device.
2. The computer-implemented method of claim 1 , further comprising:
parsing an expression into a non-language specific representation including the quantification.
3. The computer-implemented method of claim 2 , wherein parsing an expression into a non-language specific representation comprises parsing a regular expression into a syntax tree.
4. The computer-implemented method of claim 1 , wherein converting includes, when a repeated expression for the quantification is nullable, unrolling the quantification as a quantification having a non-nullable form of the repeated expression that can be matched zero times.
5. The computer-implemented method of claim 1 , wherein converting the automaton into machine code comprises converting the automaton into an image configured to program a parallel machine.
6. The computer-implemented method of claim 5 , further comprising:
publishing the image.
7. The computer-implemented method of claim 1 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling the quantification as a function of an in-degree limitation.
8. The computer-implemented method of claim 7 , wherein the in-degree limitation includes a limit on the number of transitions into a state of the automaton.
9. The computer-implemented method of claim 1 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling based on an in-degree constraint of the target device.
10. The computer-implemented method of claim 1 , wherein the quantification is a regular expression.
11. The computer-implemented method of claim 1 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling the quantification to control an in-degree of the automaton based on a threshold.
12. The computer-implemented method of claim 11 , wherein the threshold is based on a hardware limitation of the parallel machine.
13. A computer-readable medium that is not a transitory propagating signal, the computer-readable medium including instructions, which when executed by the computer, cause the computer to perform operations comprising:
converting a quantification into an automaton, wherein converting includes unrolling the quantification to control an out-degree of the automaton; and
converting the automaton into machine code corresponding to a target device.
14. The computer-readable medium of claim 13 , wherein unrolling includes limiting the out-transitions for each state of the automaton to below a threshold number.
15. The computer-readable medium of claim 13 , wherein unrolling includes minimizing out-transitions for each state of the automaton.
16. The computer-readable medium of claim 13 , wherein converting includes, when a repeated expression for the quantification is nullable, unrolling the quantification as a quantification having a non-nullable form of the repeated expression that can be matched zero times.
17. The computer-readable medium of claim 13 , wherein converting includes:
when the quantification can be matched with a single number of loops, unrolling the quantification to form an automaton having states representing a number of expressions equal to the single number linked in series, wherein the expressions correspond to a repeated expression for the quantification.
18. The computer-readable medium of claim 13 , wherein when the quantification can be matched with a multiple number of loops, the multiple number of loops including a first number of loops, n1, and a second number of loops, n2, unrolling the quantification includes:
splitting the quantification into a first quantification that can be matched with the n1-1 number of loops and a second quantification that can be matched with from one to a n2-n1+1 number of loops.
19. The computer-readable medium of claim 13 , wherein the instructions cause the computer to perform operations comprising:
loading the image onto a parallel machine.
20. The computer-readable medium of claim 13 , wherein the instructions cause the computer to perform operations comprising:
storing the image on a computer readable medium.
21. A computer comprising:
a memory having software stored thereon; and
a processor communicatively coupled to the memory, wherein the software, when executed by the processor, causes the processor to:
convert a quantification into an automaton, wherein convert includes unroll the quantification to control an in-degree or an out-degree of the automaton; and
convert the automaton into machine code corresponding to a target device.
22. The computer of claim 21 , wherein the software causes the processor to control the in-degree and out-degree by trading off in-transitions for out-transitions in the automaton.
23. The computer of claim 22 , wherein the in-transitions for each state are limited to below a threshold number when unrolling.
24. The computer of claim 22 , wherein the in-degree is limited to a ratio of the out-degree.
25. The computer of claim 24 , wherein the in-degree is limited to the ratio of the out-degree until a threshold of in-transitions are reached for a state of the automaton.
26. A system comprising:
a computer configured to:
convert a quantification into an automaton, wherein convert includes unrolling the quantification to control an in-degree or an out-degree of the automaton; and
convert the automaton into machine code corresponding to a target device.
27. The system of claim 26 , wherein the machine code comprises an image configured to program a parallel machine, and further comprising:
a device communicatively coupled to the computer and configured to load the image onto a parallel machine.
28. The system of claim 26 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling the quantification as a function of an in-degree limitation.
29. The system of claim 28 , wherein the in-degree limitation includes a limit on the number of transitions into a state of the automaton.
30. The system of claim 26 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling based on an in-degree constraint of the target device.
31. The system of claim 26 , wherein unrolling the quantification to control an in-degree of the automaton comprises unrolling the quantification to control an in-degree of the automaton based on a threshold.
32. The system of claim 31 , wherein the threshold is based on a hardware limitation of the parallel machine.
33. A parallel machine programmed by an image produced by the process of claim 1 .
34. A computer-implemented method comprising:
converting a quantification into an automaton, wherein converting includes unrolling the quantification to control an out-degree of the automaton; and
converting the automaton into machine code corresponding to a target device.
35. The computer-implemented method of claim 34 , further comprising:
parsing a regular expression into a syntax tree.
36. The computer-implemented method of claim 34 , wherein converting the automaton into machine code comprises converting the automaton into an image configured to program a parallel machine.
37. The computer-implemented method of claim 36 , further comprising:
publishing the image.
38. The computer-implemented method of claim 34 , wherein unrolling the quantification to control an out-degree of the automaton comprises unrolling the quantification as a function of an out-degree limitation.
39. The computer-implemented method of claim 38 , wherein the out-degree limitation includes a limit on the number of transitions out of a state of the automaton.
40. The computer-implemented method of claim 34 , wherein unrolling the quantification to control an out-degree of the automaton comprises unrolling based on an out-degree constraint of the target device.
41. The computer-implemented method of claim 34 , wherein unrolling the quantification to control an out-degree of the automaton comprises unrolling the quantification to control an out-degree of the automaton based on a threshold.
42. The computer-implemented method of claim 41 , wherein the threshold is based on a hardware limitation of the parallel machine.
43. A computer-readable medium that is not a transitory propagating signal, the computer-readable medium including instructions, which when executed by the computer, cause the computer to perform operations comprising:
converting a quantification into an automaton, wherein converting includes unrolling the quantification to control an in-degree of the automaton; and
converting the automaton into machine code corresponding to a target device.
44. The computer-readable medium of claim 43 , wherein unrolling includes limiting the in-transitions for each state of the automaton to below a threshold number.
45. The computer-readable medium of claim 43 , wherein unrolling includes minimizing in-transitions for each state of the automaton.
46. The computer-readable medium of claim 43 , wherein converting includes, when a repeated expression for the quantification is nullable, unrolling the quantification as a quantification having a non-nullable form of the repeated expression that can be matched zero times.
47. The computer-readable medium of claim 43 , wherein converting includes:
when the quantification can be matched with a single number of loops, unrolling the quantification to form an automaton having states representing a number of expressions equal to the single number linked in series, wherein the expressions correspond to a repeated expression for the quantification.
48. The computer-readable medium of claim 43 , wherein when the quantification can be matched with a multiple number of loops, the multiple number of loops including a first number of loops, n1, and a second number of loops, n2, unrolling the quantification includes:
splitting the quantification into a first quantification that can be matched with the n1-1 number of loops and a second quantification that can be matched with from one to a n2-n1+1 number of loops.