Hardware accelerator personality compiler

• US 20040172234A1
• Filed: 10/03/2003
• Published: 09/02/2004
• Est. Priority Date: 02/28/2003
• Status: Abandoned Application

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Dapp, Michael C., Ng, Sai Lun
• Application Number:
  US10/677,744
• Publication Number:
  US 20040172234A1
• Time in Patent Office: Days
• US Class Current: 704/1
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Error-free state tables are automatically generated from a specification of a group of desired performable functions, such as are provided in a programming language in a formal notation such as Backus-Naur form or a derivative thereof by discriminating tokens corresponding to respective performable functions, identifications, arguments, syntax, grammar rules, special symbols and the like. The tokens may be recursive (e.g. infinite), in which case they are transformed into a finite automata which may be deterministic or non-deterministic. Non-deterministic finite automata are transformed into deterministic finite automata and then into state transitions which are used to build a state table which can then be stored or, preferably, loaded into a finite state machine of a hardware parser accelerator to define its personality.

Claims

1. A method of providing state tables in a self-describing format, said method comprising steps of

providing a specification of performable functions,

discriminating tokens corresponding to respective ones of said performable functions,

transforming tokens into deterministic finite automata, and

transforming said deterministic finite automata into state table entries.

2. The method as recited in claim 1, wherein said step of transforming said deterministic finite automata includes forming a character string.

3. The method as recited in claim 1, including a further step of

detecting grammar entities in said specification of performable functions which express special rules.

4. The method as recited in claim 3, wherein said special rules include exclusion.

5. The method as recited in claim 3, wherein a detected grammar entity is recursive.

6. The method as recited in claim 5, including further step of

generating a set of finite automata corresponding to a recursive grammar entity.

7. The method as recited in claim 5, including the further step of storing a recursive symbol in a recursive symbol table.

8. The method as recited in claim 5, wherein a recursive grammar entity is a delimiter symbol.

9. The method as recited in claim 1, wherein said step of transforming tokens includes a further step of

detecting non-deterministic finite automata corresponding to respective ones of said tokens.

10. The method as recited in claim 9, wherein said step of transforming tokens includes a further step of

transforming non-deterministic finite automata into deterministic finite automata.

11. The method as recited in claim 10, wherein said step of transforming non-deterministic finite automata includes a further step of

forming a closure set from states of said non-deterministic finite automata.

12. The method as recited in claim 5, wherein said step of transforming tokens includes a further step of

detecting non-deterministic finite automata corresponding to respective ones of said tokens.

13. The method as recited in claim 12, wherein said step of transforming tokens includes a further step of

transforming non-deterministic finite automata into deterministic finite automata.

14. The method as recited in claim 13, wherein said step of transforming non-deterministic finite automata includes a further step of

generating a closure set from states of said non-deterministic finite automata.

15. The method as recited in claim 1, including a further step of optimizing deterministic finite automata.

16. The method as recited in claim 6, including a further step of optimizing deterministic finite automata.

17. The method as recited in claim 10, including a further step of optimizing deterministic finite automata.

18. The method as recited in claim 1, wherein said steps of transforming tokens and transforming deterministic finite automata are performed as a single non-branching sequence.

19. A personality compiler comprising

means for inputting a specification of functions performable by a data processor, said specification including grammar entities,

means for generating finite automata from tokens in said specification, including means for generating a set of finite automata for recursive grammar entities,

means for generating a closure set from states of non-deterministic finite automata to form deterministic finite automata, and

means for transforming said deterministic finite automata into state table entries to define a finite state machine.

20. The personality compiler as recited in claim 19, further including

a loader for loading said state table entries into said finite state machine, said loader including a stack for storing and outputting said sets of finite automata corresponding to said recursive grammar entities.

21. A hardware parser accelerator including

a finite state machine,

a loader for loading state table data into said finite state machine, and

a personality compiler comprising

means for inputting a specification of functions performable by a data processor, said specification including grammar entities,

means for generating finite automata from tokens in said specification, including means for generating a set of finite automata for recursive grammar entities,

means for generating a closure set from states of non-deterministic finite automata to form deterministic finite automata, and

means for transforming said deterministic finite automata into state table entries to define a finite state machine.

22. A hardware parser accelerator as recited in claim 21, wherein said loader includes

a stack for storing and outputting said sets of finite automata corresponding to said recursive grammar entities.

23. A hardware parser accelerator as recited in claim 21, wherein the personality compiler and loader operate in substantially real time to alter state tables of said finite state machine.

24. A hardware parser accelerator as recited in claim 23, wherein loading of said finite state machine adapts said parser accelerator and said personality compiler over time responsive to conditions observed in an input data stream.

25. A hardware parser accelerator as recited in claim 21, wherein a portion of said personalty compiler is operated when said hardware parser accelerator is off-line and provides storage for results in the form of either finite automata or state tables and said loader is operated on an on-demand basis.