Hardware accelerator personality compiler
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
25 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.
-
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.
-
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.
Specification