Chart parsing using compacted grammar representations

• US 6,785,643 B2
• Filed: 10/15/2001
• Issued: 08/31/2004
• Est. Priority Date: 10/15/2001
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Thompson, William, Hayosh, Thomas E., Minnen, Guido A., Bliss, Harry Martin
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/977,624
• Publication Number:
  US 20030074184A1
• Time in Patent Office: 1,051 Days
• Field of Search: 704/9, 704/10, 704/257, 704/256, 704/259
• 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/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A chart parser and a method for generating a parse chart for a sequence of input symbols in accordance with an abbreviated representation of a grammar. According to the method, an abbreviated representation of a grammar is stored as a set of finite-state automata, each finite-state automaton corresponding to a rule of the grammar. Chart edges are derived chart edges from the sequence of input symbols in accordance with the set of finite-state automata and are stored in the parse chart. Each chart edge spans a portion of the sequence of input symbols and may include a left input vertex index corresponding to the start of the span of the chart edge, a right input vertex index corresponding to the end of the span of the chart edge, a rule number, indicating which finite-state automaton of the plurality of finite-state automata has been used to generate the chart edge, a left state index, indicating the left most state of the finite-state automaton that has been matched and a right state index, indicating the right most state of the finite-state automaton that has been matched, the left-hand side of the rule and a path through the finite state comprising the right-hand side of the rule or so-called backpointers to the edges used to derive the current edge. The chart parser includes a chart controller and an agenda controller, together with associated memory.

Claims

1. A method for generating a parse chart for a sequence of input symbols in accordance with an abbreviated representation of a grammar comprising a set of rules formed using operaters for optionality, disjunctivity, and repetition, said method comprising:

storing the abbreviated representation of the grammar as a set of finite-state automata, each finite-state automaton of the set of finite-state automata corresponding to a rule of the set of rules;

receiving the sequence of input symbols;

deriving chart edges from the sequence of input symbols in accordance with said abbreviated representation of the grammar each such chart edge identified by one automaton of said set of finite-state automata; and

storing said chart edges in the parse chart.

2. A method in accordance with claim 1, wherein said sequence of input symbols is indexed by a plurality of input vertex indices.

3. A method in accordance with claim 1, wherein said abbreviated representation of a grammar is a Extended Backus-Naur Form (EBNF).

4. A method in accordance with claim 1, further comprising:

initializing an agenda of items with a passive chart edge for each symbol of the sequence of input symbols;

for each item of said agenda of items, comprising;

if any new chart edges can be derived from said item in accordance with said abbreviated representation of the grammar;

deriving said new chart edges; and

adding the new chart edges to the agenda of items;

storing said item in said parse chart.

5. A method in accordance with claim 1, further comprising

indicating failure if the parse chart contains no passive edge that spans the sequence of input symbols;

and

indicating success if the parse chart contains a passive edge that spans the sequence of input symbols.

6. A method in accordance with claim 1, wherein each rule of the set of rules has a left-hand side and a right-hand side, further comprising:

initializing an agenda of items with a passive edge for the first symbol of the sequence of input symbols;

until no more symbols in the sequence of input symbols, repeating the process of;

if the agenda of items is empty, adding a passive edge for the next symbol of the sequence of input symbols;

retrieving an item from said agenda of items;

deriving one or more new edges from said item in accordance with said abbreviated representation of the grammar and a plurality of edges stored in said parse chart;

storing said one or more new edges in said agenda of items; and

storing the item in said parse chart.

7. A method for generating a parse chart for a sequence of input symbols in accordance with an abbreviated representation of a grammar, said method comprising:

storing the abbreviated representation of the grammar as a plurality of finite-state automata, each finite-state automaton of the plurality of finite-state automata corresponding to a rule of the grammar;

receiving the sequence of input symbols;

deriving chart edges from the sequence of input symbols in accordance with said abbreviated representation of the grammar in accordance with said plurality of finite-state automata; and

storing said chart edges in the parse chart

wherein each chart edge spans a portion of the sequence of input symbols and wherein each rule of the grammar has a left-hand side and a right-hand side, each said chart edge comprising;

a left input vertex index corresponding to a start of a span of the chart edge;

a right input vertex index corresponding to an end of the span of the chart edge;

a rule number, indicating a finite-state automaton of the plurality of finite-state automata that has been matched to generate the chart edge;

a left state index, indicating the left-most state of the finite-state automaton that has been matched; and

a right state index, indicating the right-most state of the finite-state automaton that has been matched.

8. A method in accordance with claim 7, wherein said chart edge further comprises a left-hand side of a rule from the grammar.

9. A method in accordance with claim 8, wherein said chart edge further comprises a path entry representative of a path through the finite-state automaton that has been matched.

10. A method in accordance with claim 8, wherein said chart edge further comprises a list of pointers to the chart edges from which said chart edge was derived.

11. A chart parser, comprising:

an input for receiving input symbols;

a chart memory for storing chart edges;

a grammar memory for storing a set of finite state automata that have a one-to-one correspondence with a set of abbreviated grammar rules formed using operators for optionality, disjunctivity, and repetition;

an agenda memory for storing agenda items;

a program memory for storing a program of processor instructions;

a processor, operably coupled to said program memory, said processor comprising;

an agenda controller, operably coupled to said agenda memory and to said input; and

a chart controller, operably coupled to said chart memory and said grammar memory; and

an output coupled to said chart memory via said chart controller,

wherein said chart controller is operable to update the chart memory directly using one rule of the set of abbreviated grammar rules for each edge.

12. A chart parser in accordance with claim 11, wherein said input is operable to be coupled to an automatic speech recognizer and said input symbols correspond to words in a natural language utterance.

13. A chart parser in accordance with claim 11, wherein processor further comprises an automatic speech recognizer and said input symbols correspond to words in a natural language utterance.

14. A chart parser in accordance with claim 11, wherein said output is operable to be coupled to a semantic interpreter.

15. A chart parser in accordance with claim 11, wherein said processor further comprises a semantic interpreter operably coupled to said chart memory.