Chart parsing using compacted grammar representations

#This invention relates to techniques and apparatus for carrying out chart parsing making direct use of compactly encoded grammars. The invention has application to automatic speech recognition with natural language input.

#Natural language interfaces play an increasingly important role in the use of small handheld devices, such as cell phones and personal digital assistants (PDAs). Natural language interfaces are also becoming important in a range of other applications, including automotive accessory control and home-appliance control. In all of the applications, there are benefits in having the natural language interface be as efficient as possible so as to minimize cost, size and power consumption.

#Natural language processing systems that make use of context free grammars must load these grammars from a textual format into internal memory. The grammars may be written in a compact format, such as the Backus-Naur Form (BNF) described in “The Syntax And Semantics Of The Proposed International Algebraic Language Of The Zuerich Acm-Gamm Conference”, by J. Backus, published in Information Processing: Proceedings of the International Conference on Information Processing, Paris, pp 125-132, UNESCO, 1959. If such a compact form is used, the rules of the grammar must typically first be expanded in order for a chart parser to make use of them. Many algorithms exist for parsing natural language using context free grammars. These algorithms use numerous techniques to improve performance, the most important being the use of a chart to avoid re-computation of previous results and the incorporation of filtering techniques to avoid computation of irrelevant results.

#The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself however, both as to organization and method of operation, together with objects and advantages thereof, may be best understood by reference to the following detailed description of the invention, which describes certain exemplary embodiments of the invention, taken in conjunction with the accompanying drawings in which:

#FIG. 1 is a diagrammatic representation of the internal representation of exemplary abbreviated grammar rules in accordance with the present invention.

#FIG. 2 is an exemplary parse chart in accordance with the present invention.

#While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail specific embodiments, with the understanding that the present disclosure is to be considered as an example of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described. In the description below, like reference numerals are used to describe the same, similar or corresponding parts in the several views of the drawings.

#The present invention relates to a bottom-up parsing technique that directly processes natural language expressions using grammars that consist of rules specifying the possible alternative expansions of a non-terminal symbol in the form of a regular expression, i.e. the Backus-Naur form (BNF) grammars. The present invention is applicable to all context-free grammar formalisms that use abbreviatory notation to express optionality, disjunction and repetition. Here, a terminal symbol is taken to be any symbol that can occur in the natural language expression itself. For example, in spoken language, the terminal symbols may be actual words and numbers. Non-terminal symbols are generic terms for sequences of one or more terminal symbols or other non-terminal symbols. For example, <noun>, <verb> and <sentence> are non-terminal symbols. The parse tree analysis of an expression is determined by finding instances of the relevant regular expressions through matching them against the words in the expressions and the intermediate parsing results in the chart. The intermediate results in the chart directly refer to the compacted grammar rules in the BNF grammar. This in turn necessitates an adaptation of the standard chart-parsing operations for creating intermediate results.

#Context-free grammars (CFGs) are a device for modeling natural languages; see for example, “Three Models For The Description Of Language”, N, Chomsky, IRI Transactions on Information Theory, 2(3), 113-124, 1956. CFGs consist of a set of nonterminal and terminal symbols in conjunction with a set of rewrite rules for rewriting expression using these symbols. Each rewrite rule consists of a left-hand side and a right-hand-side, where the left-hand side consists of a single non-terminal and the right-hand side consists of a sequence of terminal and non-terminal symbols. An example of a CFG with 28 rewrite rules is listed below.