Using speculative parsing to process complex input data

• US 5,963,742 A
• Filed: 09/08/1997
• Issued: 10/05/1999
• Est. Priority Date: 09/08/1997
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Williams, Gerald S.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US08/925,564
• Time in Patent Office: 757 Days
• Field of Search: 395/708, 704/9, 707/1
• US Class Current: 717/143
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A parser includes a plurality of subparsers, a main parser unit, and a selector. Each of the subparsers attempts to interpret a stream of tokens corresponding to a statement in a respectively different way. In addition, each subparser returns a speculative result and a respective confidence level. The main parser unit receives the stream of tokens, identifies that the stream of tokens make up a statement and invokes at least a few of the subparsers. The selector selects one speculative result based upon the confidence level returned by the subparsers which are invoked by the main parser unit.

Claims

1. A parser comprising:

a plurality of subparsers, each for attempting to interpret a stream of tokens corresponding to a statement in a respectively different way and for returning a respective speculative result and a respective confidence level;

a main parser unit for receiving said stream of tokens, for identifying said stream of tokens as said statement and for invoking ones of said plurality of subparsers; and

a selector for selecting said respective speculative result based upon each confidence level, returned by said ones of said plurality of subparsers which are invoked, being at a predetermined level.

2. A parser according to claim 1, wherein said predetermined level is total success interpreting said stream of tokens.

3. A parser comprising:

a plurality of subparsers, each for attempting to interpret a stream of tokens corresponding to a statement in a respectively different way and for returning a respective speculative result and respective confidence level;

a main parser unit for receiving said stream of tokens, for identifying said stream of tokens as said statement and for invoking ones of said plurality of subparsers; and

a selector for selecting said respective speculative result based upon each confidence level, returned by said ones of said plurality of subparsers which are invoked, being above a predetermined level.

4. A parser comprising:

a plurality of subparsers, each for attempting to interpret a stream of tokens corresponding to a statement in a respectively different way and for returning a respective speculative result and a respective confidence level;

a main parser unit for receiving said stream of tokens, for identifying said stream of tokens as said statement and for invoking ones of said plurality of subparsers; and

a selector for selecting said respective speculative result based upon each confidence level, returned by said ones of said plurality of subparsers which are invoked, being higher than other respective confidence levels returned by other of said parsers.

5. A parser comprising:

a plurality of subparsers, each for attempting to interpret a stream of tokens corresponding to a statement in a respectively different way and for returning a respective speculative result and a respective confidence level;

a main parser unit for receiving said stream of tokens, for identifying said stream of tokens as said statement and for invoking ones of said plurality of subparsers wherein, said ones of said plurality of subparsers are invoked in a predetermined order; and

a selector for selecting said respective speculative result based upon each confidence level returned by said ones of said plurality of subparsers.

6. A parser according to claim 5, wherein said predetermined order is based upon complexity of each interpretation attempted for said stream of tokens.

7. A parser according to claim 5, wherein said predetermined order is based upon execution speed of each interpretation attempted for said stream of tokens.

8. A parser comprising:

a plurality of subparsers, each for attempting to interpret a stream of tokens corresponding to a statement in a respectively different way and for returning a respective speculative result and a respective confidence level;

a main parser unit for receiving said stream of tokens, for identifying said stream of tokens as said statement and for invoking ones of said plurality of subparsers wherein, said ones of said plurality of subparsers are invoked concurrently; and

a selector for selecting said respective speculative result based upon each confidence level returned by said ones of said plurality of subparsers which are invoked.

9. A method of parsing a stream of tokens corresponding to a statement, comprising the steps of:

receiving said stream of tokens and identifying said stream of tokens as said statement;

invoking a plurality of subparsers to attempt to interpret said stream of tokens, wherein each of said subparsers generates a respective speculative result and a respective confidence level; and

selecting one of said speculative results from said plurality of subparsers based upon said respective confidence level, generated by each of said subparsers, being at a predetermined level.

10. A method of parsing a stream of tokens according to claim 9, wherein said predetermined level is total success interpreting said stream of tokens.

11. A method of parsing a stream of tokens corresponding to a statement, comprising the steps of:

receiving said stream of tokens and identifying said stream of tokens as said statement;

invoking a plurality of subparsers to attempt to interpret said stream of tokens, wherein each of said subparsers generates a respective speculative result and a respective confidence level; and

selecting one of said speculative results from said plurality of subparsers based upon said respective confidence level, generated by each of said subparsers, being above a predetermined level.

12. A method of parsing a stream of tokens corresponding to a statement, comprising the steps of:

receiving said stream of tokens and identifying said stream of tokens as said statement;

invoking a plurality of subparsers to attempt to interpret said stream of tokens, wherein each of said subparsers generates a respective speculative result and a respective confidence level; and

selecting one of said speculative results from said plurality of subparsers based upon said respective confidence level, generated by each of said subparsers, being higher than other respective confidence levels returned by other of said parsers.

13. A method of parsing a stream of tokens corresponding to a statement, comprising the steps of:

receiving said stream of tokens and identifying said stream of tokens as said statement;

invoking a plurality of subparsers to attempt to interpret said stream of tokens wherein, said ones of said plurality of parsers are invoked in a predetermined order, wherein each of said subparsers generates a respective speculative result and a respective confidence level; and

selecting one of said speculative results from said plurality of subparsers based upon said respective confidence level, generated by each of said subparsers.

14. A method of parsing a stream of tokens according to claim 13, wherein said predetermined order is based upon complexity of each interpretation attempted for said stream of tokens.

15. A method of parsing a stream of tokens according to claim 13, wherein said predetermined order is based upon execution speed of each interpretation attempted for said stream of tokens.

16. A method of parsing a stream of tokens, comprising:

receiving said stream of tokens and identifying said stream of tokens as said statement;

invoking a plurality of subparsers to attempt to interpret said stream of tokens wherein, ones of said subparsers are invoked concurrently, wherein each of said subparsers generates a respective speculative result and a respective confidence level; and

selecting one of said speculative results from said plurality of subparsers based upon said respective confidence level, generated by each of said subparsers.