System and method for analyzing data

• US 20030187633A1
• Filed: 02/03/2003
• Published: 10/02/2003
• Est. Priority Date: 02/01/2002
• Status: Active Grant

• Current Assignee: John Fairweather
• Original Assignee: John Fairweather
• Inventors: Fairweather, John
• Granted Patent: US 7,328,430 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 9/4493 Object persistence
• CPC Class Codes: G06K 13/0825 the ejection arrangement being of the push-push kind
• CPC Class Codes: Y10S 707/913 Multimedia
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method provide the ability to construct lexical analyzers on the fly in an efficient and pervasive manner. The system and method split the table describing the automata into two distinct tables and splits the lexical analyzer into two phases, one for each table. The two phases consist of a single transition algorithm and a range transition algorithm, both of which are table driven and permit the dynamic modification of those tables during operation. A third ‘entry point’ table may also be used to speed up the process of finding the first table element from state 0 for any given input character.

Claims

1. ) A method for performing lexical analysis, comprising the steps of:

creating a first table, wherein the first table describes one or more single character transitions using records of type ET_onecat;

creating a second table, wherein the second table is an ordered series of records of type ET_catrange;

responsive to text input, searching through the records of the first table searching for each text input character;

if a matching record is identified in the first table, providing the token associated with the matching record as output;

responsive to a failure to locate a matching record in the first table, searching the records of the second table from the beginning for each input character, wherein a match is found when the current analyzer state lies between the upper state and lower state bounds and the input character lies between the upper character and lower character bounds, in each case as specified in the record being searched;

if a matching record in the second table is found, assigning the current analyzer state the value of the ‘

estat’

field in the matching record;

if an exit condition is reached, terminating the loop.

2. ) The method of claim 1, wherein the method further includes the step of creating a third table, wherein the third table stores the first table element from State 0 for any given input character.

3. ) The method of claim 1, wherein the method further includes the step of reserving one or more lower state values as accepting values.

4. ) The method of claim 3, wherein the method further includes the step of storing highest the state value associated with an accepting state.

5. ) The method of claim 1, wherein the method further includes the step of creating one or more additional records in the first table.

6. ) The method of claim 5, wherein the step of creating one or more additional records includes adding one or more symbols to the first table.

7. ) The method of claim 6, wherein the step of adding one or more symbols includes the step of creating a token number to refer back to whatever was registered with the symbol.

8. ) The method of claim 1, wherein the method further includes the step of creating a array of delimiters.

9. ) The method of claim 8, wherein the step of creating an array of delimiters includes modifying the array by adding delimiters associated with the language of the text input.

10. ) The method of claim 8, wherein the step of creating an array of delimiters includes modifying the array by removing delimiters not associated with the language of the text input.

11. ) The method of claim 1, wherein the method further includes the step of creating an array of whitespace characters.

12. ) The method of claim 11, wherein the step of creating an array of whitespace characters includes modifying the array by adding whitespace characters associated with the language of the text input.

13. ) The method of claim 11, wherein the step of creating an array of whitespace characters includes modifying the array by removing whitespace characters associated with the language of the text input.

14. ) The method of claim 1, wherein the steps of searching through the records of the first and second table to determine whether there is a match with the input text includes searching for records having a value that is in the same case as the input text.

15. ) The method of claim 1, wherein the steps of searching through the records of the first and second table to determine whether there is a match does not include matching the case of the input text.

16. ) A parsing system, comprising:

a programmable gate array, wherein such gate array contains one or more LAM modules which can operate on the incoming text stream in parallel;

logically connected to the gate array, a first table, wherein the first table describes one or more single character transitions using records of type ET_onecat;

logically connected to the gate array, a second table, wherein the second table is an ordered series of records of type ET_catrange; and

logically connected thereto, a function, wherein such function loads each memory table on to the gate array and associates it with one or more LAM(s).

17. ) The system of claim 16, wherein the system comprises one or more programmable gate arrays.

18. ) The system of claim 17, wherein the system comprises a circuit card which combines each of the programmable gate arrays.

19. ) The system of claim 18, wherein the circuit card includes logic for permitting each gate array to process an incoming text stream in parallel.

20. ) The system of claim 16, further comprising a third table, wherein the third table stores the first table element from State 0 for any given input character.