Parsing with controlled tokenization

• US 6,990,442 B1
• Filed: 09/21/2001
• Issued: 01/24/2006
• Est. Priority Date: 07/27/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Davis, James F.
• Primary Examiner(s): Smits, Talivaldis Ivars
• Assistant Examiner(s): Serrou, Abdelali
• Application Number:
  US09/960,775
• Time in Patent Office: 1,586 Days
• Field of Search: 717/143, 704/9, 704/256, 704/257
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

The present invention provides a parsing technique wherein a parsing process provides feedback to a tokenizer to select an appropriate sub-tokenizer process corresponding to a grammar rule being implemented by the current parsing state. Each parsing state will select a corresponding sub-tokenizer process to tokenize a corresponding portion of an input stream for a message to be parsed. Each sub-tokenizer process is preferably unique and configured to provide only tokens capable of being processed by the grammar rule being implemented in the corresponding parser state. If the input string cannot be tokenized as required by the corresponding grammar rule implemented by the parser state, an error message is delivered. The parser process will move from one state to another, based on processing the respective tokens, until the input stream for the message is completely parsed.

Claims

1. A computer readable medium comprising software for instructing a computer to:

a) provide a parser process having a plurality of states, each state implementing a rule in a defined grammar; and

b) provide a tokenizer process having a plurality of sub-tokenizer processes corresponding to the plurality of states in the parser process, each sub-tokenizer process adapted to tokenize a portion of an input string to generate a token corresponding to the rule implemented by one of the plurality of states in the parser process, wherein the parser process selects one of the plurality of sub-tokenizer processes to tokenize the portion of the input string based on a current one of the plurality of states.

2. The computer readable medium of claim 1 wherein the parser process is adapted to move from one of the plurality of states to another based on the token received from a corresponding one of the sub-tokenizer processes.

3. The computer readable medium of claim 2 wherein the parser process is adapted to generate an action for at least one of the plurality of states based on the token received from the corresponding one of the sub-tokenizer process.

4. The computer readable medium of claim 1 wherein the tokenizer process receives the input string, which is broken into subparts and tokenized by respective ones of the sub-tokenizer processes.

5. The computer readable medium of claim 1 wherein the plurality of sub-tokenizer processes are adapted to return an error to the parser process when the portion of the input string cannot generate a token corresponding to the rule implemented by the corresponding one of the plurality of states.

6. The computer readable medium of claim 1 wherein the input string is a text based protocol.

7. A system for parsing comprising:

a) an interface for receiving an input string; and

b) a control system associated with the interface and adapted to provide;

i) a parser process having a plurality of states, each state implementing a rule in a defined grammar; and

ii) a tokenizer process having a plurality of sub-tokenizer processes corresponding to the plurality of states in the parser process, each sub-tokenizer process adapted to tokenize the portion of the input string to generate a token corresponding to the rule implemented by one of the plurality of states in the parser process, wherein the parser process selects one of the plurality of sub-tokenizer processes to tokenize a portion of the input string based on a current one of the plurality of the states.

8. The system of claim 7 wherein the parser process is adapted to move from one of the plurality of states to another based on the token received from a corresponding one of the sub-tokenizer processes.

9. The system of claim 8 wherein the parser process is adapted to generate an action for at least one of the plurality of the states based on the token received from the corresponding one of the sub-tokenizer process.

10. The system of claim 7 wherein the tokenizer process receives the input string, which is broken into subparts and tokenized by respective ones of the sub-tokenizer processes.

11. The system of claim 7 wherein the plurality of sub-tokenizer processes are adapted to return an error to the parser process when the portion of the input string cannot generate a token corresponding to the rule implemented by the corresponding one of the plurality of the states.

12. The system of claim 7, wherein the input string is a text based protocol.

13. A method for parsing comprising:

a) providing a parser process having a plurality of states, each state implementing a rule in a defined grammar;

b) providing a tokenizer process having a plurality of sub-tokenizer processes corresponding to the plurality of states in the parser process, each sub-tokenizer process adapted to tokenize a portion of an input string to generate a token corresponding to the rule implemented by one of the plurality of states in the parser process, wherein the parser process selects one of the plurality of sub-tokenizer processes to tokenize a portion of the input string based on a current one of the plurality of states.

14. The computer method of claim 13 wherein the parser process is adapted to move from one of the plurality of states to another based on the token received from a corresponding one of the sub-tokenizer processes.

15. The method of claim 14 wherein the parser process is adapted to generate an action for at least one of the plurality of states based on the token received from a corresponding one of the sub-tokenizer process.

16. The method of claim 13 wherein the tokenizer process receives the input string, which is broken into subparts and tokenized by respective ones of the sub-tokenizer processes.

17. The method of claim 13 wherein the plurality of sub-tokenizer processes are adapted to return an error to the parser process when the portion of the input string cannot generate a token corresponding to the rule implemented by the corresponding one of the plurality of states.

18. The method of claim 13 wherein the input string is a text based protocol.

19. A method for parsing comprising:

a) selecting one of a plurality of sub-tokenizing processes to tokenize a portion of an input string based on a current parsing state;

b) tokenizing the portion of the input string to generate a token corresponding to a grammar rule implemented by the current parsing state;

c) processing the token according to the grammar rule of the current parsing state with the selected sub-tokenizing process;

d) moving to a subsequent parsing state based on processing the token according to the grammar rule of the current parsing state; and

e) repeating steps a through d until the input string is parsed.

20. The method of claim 19 further comprising generating an action based on processing the token according to the grammar rule of the current parsing state.

21. The method of claim 19 wherein the selecting step further comprises selecting a portion of a remainder of the input string corresponding to the grammar rule implemented by the current parsing state.

22. The method of claim 19 further comprising generating an error message when the portion of the input string cannot generate a token corresponding to the grammar rule of the current parsing state.

23. The method of claim 19 wherein the input string is a text based protocol.