Method and apparatus for robust efficient parsing

A method of parsing text to form a tokenized representation of the text, the method comprising:

• selecting a word from the text;
• forming a partial parse of a token based on the selected word;
• identifying an item that is needed to extend the partial parse;
• and
• placing a pointer to the partial parse in a table associated with a next word in the text, the pointer being mapped from the item that is needed to extend the parse.

A method of parsing text to form a representation of the text, the representation having structures that span sub-strings of words in the text, each structure having a token at its root, the method comprising:

• identifying a first structure that spans a first sub-string of words in the text and has a first token as its root, the first sub-string having a starting position and an ending position;
• indexing the first structure by the first token and the staring position and ending position of the first sub-string;
• identifying a second structure that spans the first sub-string of words and has the first token as its root;
• using the first token and the start position and end position of the first sub-string to locate the first structure;
• and
• removing one of the first structure and second structure from further consideration in the formation of the representation of the text.

A method of parsing text to identify a parse structure containing tokens that represent non-terminals and words, the method comprising:

• converting a selected token into a token ID;
• using a first portion of the token ID to identify a table containing definitions for tokens of a same type as the selected token;
• using a second portion of the token ID to locate the definition for the selected token in the identified table;
• and
• using the definition for the selected token as part of the method of identifying the parse structure.

A computer-readable medium having a data structure used in parsing text into a logical form containing tokens, the data structure comprising:

• a collection of tables wherein each table is associated with a type of token and each table comprises a collection of definitions for tokens of the type;
• and
• a set of token IDs, each token ID representing a separate token and comprising:
• a first part that indicates a table that contains the definition for the token represented by the token ID;
• and
• a second part that indicates the location of the definition of the token represented by the token ID within the table identified by the first part.