Chart parsing using compacted grammar representations

Details Chart parsing using compacted grammar representations Chart parsing using compacted grammar representations

2001-10-15

2004-08-31

Edouard, Patrick N. (Department: 2644)

Data processing: speech signal processing, linguistics, language

Linguistics

Natural language

C704S257000

Reexamination Certificate

active

06785643

ABSTRACT:

TECHNICAL FIELD
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.
BACKGROUND OF THE INVENTION
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.
Until recently, relatively little attention has been given to direct parsing with context free grammars written in a compact form, such as BNF. Mostly for theoretical reasons, some approaches deal with particular types of compacted grammar notations. For example, “An efficient context-free parsing algorithm”, J. Earley, Communications of the ACM, 6(8), 451-455, 1970, shows how a chart parser can be extended to deal with express repetition. “Direct Parsing of ID/LP Grammars”, S. Shieber, Linguistics and Philosophy, 7:135-154, 1984, discusses the extension of a chart parser for direct processing of Immediate Dominance/Linear Precedence. The abbreviated notation in ID/LP grammars is designed especially for abbreviating grammars of natural languages that exhibit relatively free word order. However, none of these approaches take advantage of the compact BNF representation for context-free grammars that is often used by the author of a grammar during development.
A related chart parsing algorithm is proposed in “SOUP: A Parser For Real-World Spontaneous Speech”, M. Gavalda, International Workshop on Parsing Technologies, 2000. This algorithm processes expressions in a top-down fashion, using recursive transition networks automatically derived from a grammar in the Java Speech Grammar format. A top-down parsing approach is conjectured to be less efficient than a bottom-up approach as it comes to processing fragmentary input resulting from speech recognition errors and/or ungrammatical utterances.
Existing parsers are unable to make direct use of a grammar represented in an abbreviated or compact form, such as the Backus-Naur form. Consequently, significant memory and processing resources are required to expand and store the rules of an abbreviated grammar. There is an unmet need for a parser that can make direct use of a grammar represented in an abbreviated or compact form.


REFERENCES:
patent: 5625554 (1997-04-01), Cutting et al.
patent: 5642519 (1997-06-01), Martin
patent: 5960384 (1999-09-01), Brash
patent: 5963742 (1999-10-01), Williams
patent: 6128596 (2000-10-01), Mackie
Marsal Gavalda; “Soup: A Parser for Real-World Spontaneous Speech”; Interactive Systems, Inc.; Pittsburgh, PA.
Jay Earley; “An Efficient Context-Free Parsing Algorithm”; University of Californai, Berkeley, CA.; pp. 25-33.
“Direct Parsing of ID/LP Grammars” by Stuart M. Shieber.Liguistics and Philosophy7; D. Reidel Publishing Company, 1984, pp. 135-154.

Affiliated with

Also associated with

Rating

Chart parsing using compacted grammar representations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Chart parsing using compacted grammar representations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chart parsing using compacted grammar representations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3362173