US 6,223,150 B1 · Method and apparatus for parsing in a spoken language translation system

Abstract

A method and apparatus for parsing in a spoken language translation system are provided, wherein an input is received comprising at least one input sentence or expression. A parsing table is accessed and consulted for a next action, wherein the parser looks up in the next action in the parsing table. During parsing operations, the parser may perform shift actions and reduce actions. In performing a shift action, a next item of the input string is shifted onto a stack or intermediate data structure of the parser. A new parse node is generated, and a feature structure or lexical feature structure of the shifted input item is obtained from a morphological analyzer and associated with the new parse node. The new node is placed on the stack or intermediate data structure. In performing a reduce action, a grammar rule and an associated compiled feature structure manipulation are applied. When the manipulations succeed, a new parse node is generated comprising the new feature structures resulting from the successful feature structure manipulations. When the entire input is successfully parsed then an accept action is performed, a rebuilding procedure is performed, and a structural analysis of the input is provided comprising a number of parse trees and sentential feature structures.

Claims36

Dependent claims

A method for performing spoken language translation, comprising:

receiving at least one input expression;
determining at least one next action using at least one parsing table;
shifting at least one component of the at least one input expression into a data structure when the at least one next action is determined to be a shift action;
generating at least one new parse node;
associating at least one feature structure of the at least one component with the at least one new parse node;
placing the at least one new parse node on the data structure;
generating at least one packed shared parse forest comprising a plurality of parse trees and a plurality of nodes;
rebuilding at least one node of the at least one packed shared parse forest;
and
outputting at least one structural analysis of the at least one input expression.

7 more elements

An apparatus for spoken language translation comprising:

at least one processor;
an input coupled to the at least one processor, the input capable of receiving at least one input expression, the at least one processor configured to translate the received at least one input expression by,
determining at least one next action using at least one parsing table,
shifting at least one component of the at least one input expression into a data structure when the at least one next action is determined to be a shift action,
generating at least one new parse node,
associating at least one feature structure of the at least one component with the at least one new parse node,
placing the at least one new parse node on the data structure,
generating at least one packed shared parse forest comprising a plurality of parse trees and a plurality of nodes,
rebuilding at least one node of the at least one packed shared parse forest;
and
an output coupled to the at least one processor, the output capable of providing at least one structural analysis of the at least one input.

8 more elements

A computer readable medium containing executable instructions which, when executed in a processing system, causes the system to perform a method for spoken language translation, the method comprising:

receiving at least one input expression;
determining at least one next action using at least one parsing table;
shifting at least one component of the at least one input expression into a data structure when the at least one next action is determined to be a shift action;
generating at least one new parse node;
associating at least one feature structure of the at least one component with the at least one new parse node;
placing the at least one new parse node on the data structure;
generating at least one packed shared parse forest comprising a plurality of parse trees and a plurality of nodes;
rebuilding at least one node of the at least one packed shared parse forest;
and
outputting at least one structural analysis of the at least one input expression.

7 more elements

Dependencies are inferred from the claim text.

Method and apparatus for parsing in a spoken language translation system

Life of this patent

Method and apparatus for parsing in a spoken language translation system

Life of this patent

Abstract

Claims36