Method for analyzing data and performing lexical analysis

• US 8,099,722 B2
• Filed: 07/11/2007
• Issued: 01/17/2012
• Est. Priority Date: 02/01/2002
• Status: Active Grant

• Current Assignee: John Fairweather
• Original Assignee: John Fairweather
• Inventors: Fairweather, John
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US11/776,299
• Publication Number:
  US 20080016503A1
• Time in Patent Office: 1,651 Days
• Field of Search: 717140-146, 711/103, 711/114
• US Class Current: 717/143
• 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 programmable gate array comprising:

a hardware implementation in the programmable gate array of a two-phase lexical analyzer module “

LAM”

, the two-phase LAM comprising;

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

a range transition module having a second table, wherein the second table is an ordered series of records of type ET_catrange; and

a combination logic for combining the output of the single transition module and the range transition module, wherein when either the range transition module or the single transition module completes its processing and the other module is still processing characters from the incoming text stream, the combination logic allows the other module to complete its processing;

wherein one or more LAMs implemented into the programmable gate array operate on an incoming text stream in parallel to output a series of language tokens for use by external hardware or external software applications.

2. The programmable gate array according to claim 1 wherein each LAM further comprises:

a recognizer memory for the single transition module; and

a range table memory for the range transition module.

3. The programmable gate array according to claim 1 further comprising:

a table memory for the one or more LAMs.

4. The programmable gate array according to claim 1 further comprising:

a software function logically connected to the programmable gate array, wherein the software function loads the table memory for the one or more LAMs and dynamically ties each of the one or more LAMs to a particular block of the table memory.

5. The programmable gate array according to claim 1 wherein the combination logic synchronizes the clocking of successive characters from the incoming text stream so that either the single transition module or the range transition module wait for the other before proceeding to process a next text character of the incoming text stream.

6. The programmable gate array according to claim 1 wherein when the single transition module fails to recognize a language token and the range transition module is still processing characters from the incoming text stream, the combination logic allows the range transition module to complete its processing.

7. The programmable gate array according to claim 1 wherein the combination logic allows the software function to determine which of the single transition module or the range transition module recognized the outputted language token.

8. The programmable gate array according to claim 1 wherein the external hardware or software applications further comprise at least a one of text searching, pattern matching, language translation, sorting, content addressable memory and lookup, and software parser.

9. The programmable gate array according to claim 1 wherein an additional memory block associated with the one or more LAMs, and addressed using the current character value, can be loaded by the external software applications in order to implement and support additional features such as configurable delimiter characters, whitespace determination, and case insensitivity.