Interleaving Syntax and Semantics in an Efficient Bottom-Up Parser

INTERLEAVING SYNTAX AND SEMANTICS IN AN EFFICIENT BOTTOM-UP PARSER* John Dowding, Robert Moore, Franqois Andry~ and Douglas Moran SRI International 333 Ravenswood Avenue Menlo Park, CA 94025 {dowding,bmoore,andry, moran)@ai.sri.com Abstract We describe an efficient bottom-up parser that in- terleaves syntactic and semantic structure build- ing. Two techniques are presented for reducing search by reducing local ambiguity: Limited left- context constraints are used to reduce local syn- tactic ambiguity, and deferred sortal-constraint application is used to reduce local semantic am- biguity. We experimentally evaluate these tech- niques, and show dramatic reductions in both number of chart edges and total parsing time. The robust processing capabilities of the parser are demonstrated in its use in improving the ac- curacy of a speech recognizer. INTRODUCTION The parsing problem is typically framed as a recognition problem: Given a grammar and a word string, determine if the word string is a member of the language described by the grammar. For some applications, notably robust natural-language pro- cessing and spoken-language understanding, this is insufficient, since many utterances will not be accepted by the grammar, because of nonstandard language, inadequate grammatical coverage, or er- rors made in speech recognition. In these cases, it is still desirable to determine what well-formed phrases occurred {n the word string, even when the entire string is not recognized. The goal of the parser described here is to construct a chart, as ef- ficiently as possible, that contains all the syntacti- cally well-formed semantically meaningful phrases *This research was supported by the Advanced Re- search Projects Agency under Contract ONR N00014- 90-C-0085 with the Office of Naval Research. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either ex- pressed or implied, of the Advanced Research Projects Agency of the U.S. Government. tCurrent address: CAP GEMINI Innovation, 86- 90 Rue Thiers, 92513-Boulogne Billancourt, France, andry@capsoget i. fr. that occur in the word string. The most efficient practical context-free parsers (Earley, 1970; Graham, Harrison, and Ruzzo, 1980) are left-corner parsers, which gain efficiency by their ability to constrain the search to find only phrases that might contribute to a sentence that starts at the left edge of the string being parsed. These strong left-context syntac- tic constraints can prevent the parser from finding some phrases that are well-formed, however. This is a problem for us that is avoided by bottom- up parsers (Kasami, 1965;Younger, 1967), but at the expense of creating many more edges, which can lead to dramatic increases in parse time. Since our goal is to find only the phrases that are semantically meaningful as well as syntacti- cally well-formed, we also need to compute se- mantic constraints for every syntactic phrase we construct. This requires making finer distinctions than syntax-only parsing, which can introduce ad- ditional ambiguity, multiplying the number of dis- tinct phrases found and increasing parse time. We describe two special techniques for speed- ing up bottom-up parsing by reducing local am- biguity …

Content truncated to 500 words