Command parsing and rewrite system

• US 6,138,098 A
• Filed: 06/30/1997
• Issued: 10/24/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Lernout & Hauspie Speech Products NV (Intel Corporation)
• Inventors: Armstrong, John, Shieber, Stuart M., Bentz, Bryan A., Baptista, Rafael Jose, Ganong, William F. III, Selesky, Donald Bryant
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Lerner, Martin
• Application Number:
  US08/885,631
• Time in Patent Office: 1,212 Days
• Field of Search: 704/8, 704/9, 704/257, 704/270, 704/275, 395/703, 395/705, 395/707, 395/709, 395/708
• US Class Current: 704/257
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A system and method of allowing a user to control a computer application with spoken commands, include the steps of processing the spoken commands with a Speech Recognition application into candidate word phrases, and parsing at least one candidate word phrase with a Context Free Grammar (CFG) parser, into a parse tree. A plurality of predefined rewrite rules grouped into a plurality of phases applied are to the parse tree, for rewriting the parse tree. Each of the plurality of rewrite rules includes a pattern matching portion, for matching at least a part of the parse tree, and a rewrite component, for rewriting the matched part. A command string is produced by traversing each terminal node of the modified parse tree. The command string is sent to an interpreter application or directly to the computer application. Possible applications include word processing and other voice-entry systems.

Claims

1. An enhanced speech recognition system having dictation capability and the capability of converting an unprompted user-generated word phrase into a command string for causing a computer application to perform actions as directed by said word phrase comprising:

a speech recognition engine providing a dictation output and candidate word phrases to a second output;

a command interpreter, coupled to the second output, the command interpreter having;

(i) a parser for completely parsing a candidate word phrase into a parse tree;

(ii) a plurality of predefined rewrite rules divided and grouped into a plurality of phases; and

(iii) a rewriting component, for applying at least one of said predefined rewrite rules to said parse tree, for rewriting said parse tree according to said at least one predefined rewrite rule so as to produce said command string, wherein all predefined rewrite rules grouped into one of said plurality of phases are applied to said parse tree before applying predefined rewrite rules grouped into another of said plurality of phases to said parse tree.

2. The system of claim 1, wherein said plurality of predefined rewrite rule grouped into each of said phases are applied in a predefined sequence to said parse tree.

3. The system of claim 1 wherein each of said predefined rewrite rules includes a pattern matching portion and a rewriting portion.

4. The system of claim 3 wherein said rewriting component applies at least one predefined rewrite rule to said parse tree by comparing said predefined rewrite rule pattern matching portion to at least a part of said parse tree.

5. The system of claim 4 wherein if said predefined rewrite rule pattern matching portion matches at least a part of said parse tree, said matched part of said parse tree is rewritten according to said predefined rewrite rule rewriting portion.

6. If The system of claim 1 wherein said parser includes a predefined CFG (Context Free Grammar) comprising a plurality of rules, and said CFG parser applies at least one of said rules to said word phrase, to produce said parse tree.

7. The system of claim 6, wherein said CFG parser includes a predefined CFG (Context Free Grammar) comprising a plurality of rules, and said CFG parser applies at least one of said rules to said word phrase to produce said parse tree.

8. The system of claim 1 wherein said command string includes programming language instructions.

9. The system of claim 8 wherein said programming language instructions are interpreted by an interpreting application which causes said computer application to perform actions as directed by said word phrase.

10. The system of claim 8 wherein said programming language instructions are interpreted by computer application to cause said computer application to perform actions as directed by said word phrase.

11. The system of claim 1 wherein said computer application is a word processing application.

12. A method of an enhanced speech recognition system for interpreting an unprompted user-generated word phrase and directing a computer application to perform actions according to said word phrase, comprising the steps of:

providing a first output having recognized dictated text, and a separate second output having a plurality of candidate word phrases, the first and second outputs being mutually exclusive;

parsing said word phrase from the candidate word phrase output into a complete parse tree representing said candidate word phrase;

applying a plurality of predefined rewrite rules to said parse tree, for rewriting said parse tree into at least one modified parse tree, the plurality of predefined rewrite rules being divided and grouped into a plurality of phases each of said plurality of predefined rewrite rules including a pattern matching portion, for comparison to and matching at least a part of said parse tree, and also including a rewriting portion, for rewriting a matched part of said parse tree, each of the predefined rewrite rules grouped in one of the plurality of phases being applied before applying predefined rewrite rules grouped into another of the plurality of phases;

producing a command string by traversing nodes of said at least one modified parse tree; and

providing said command string to said computer application.

13. The method of claim 12, wherein said step of applying a plurality of predefined rewrite rules to said parse tree includes:

comparing said predefined rewrite rule pattern matching portion to at least a part of said parse tree.

14. The method of claim 13 wherein said step of comparing said predefined rewrite rule pattern matching portion to at least a part of said parse tree further includes the step of:

if said predefined rewrite rule pattern matching portion matches said at least a part of said parse tree, rewriting said matched part of said parse tree according to said predefined rewrite rule rewriting portion.

15. The method of claim 14 further including the step of:

if said matched part of said parse tree includes subnodes not matched by said predefined rewrite rule pattern matching portion, sequentially applying said predefined rewrite rules grouped in one of said plurality of phases to said unmatched subnodes of said parse tree.

16. The method of claim 14 wherein each of said phases includes an implicit predefined rewrite rule which matches and rewrites one node of said parse tree, said implicit predefined rewrite rule being applied to said parse tree if no other predefined rewrite rules grouped in each of said phases match said parse tree.

17. The method of claim 12 wherein said step of providing said command string to said computer application includes the step of:

providing said command string to an interpreting application, said interpreting application executing said command string and causing said computer application to perform actions.

18. The method of claim 12 wherein said command string is a set of instructions for causing said computer application to perform actions.

19. The method of claim 12 wherein said command string is a compiled program for causing said computer application to perform actions.

20. The method of claim 12, wherein said applying a plurality of predefined rewrite rules to said parse tree representing a candidate word phrase includes rejecting said parse tree, and proceeding to a next parse tree representing a next candidate word phrase.

21. The method of claim 12 wherein said parsing said word phrase into a parse tree representing said word phrase includes:

parsing said word phrase with a Context Free Grammar (CFG) parser applying a plurality of CFG parsing rules to said word phrase.

22. The method of claim 12 wherein said computer application is a word processing application.

23. A method of an enhanced speech recognition system for allowing a user to control a computer application with spoken commands, comprising the steps of:

converting an unprompted user-generated word phrase into electrical signals representing said word phrase;

processing said electrical signals, with a Speech Recognition application that produces a first output having recognized dictated text, and a separate second output having a plurality of candidate word phrases, the first and second outputs being mutually exclusive;

parsing at least one candidate word phrase with a Context Free Grammar (CFG) parser, into a complete parse tree;

applying a plurality of predefined rewrite rules grouped into a plurality of phases to said parse tree, for rewriting said parse tree into at least one modified parse tree, each of said plurality of predefined rewrite rules including a pattern matching portion, for matching at least a part of said parse tree, and also including a rewriting portion, for rewriting said matched part of said parse tree, the predefined rewrite rules grouped in one of the plurality of phases being applied before applying predefined rewrite rules in another of the plurality of phases;

producing a command string by traversing nodes of said at least one modified parse tree;

providing said command string to an interpreter application; and

directing said interpreter application to execute said command string, for causing said interpreter application to instruct said computer application to perform actions appropriate for said spoken command.