The Fitted Parse: 100% Parsing Capability in a Syntactic Grammar of English

The Fitted Parse: 100% Parsing CapabiliW in a Syntactic Grammar of English Karen Jensen and George E. Heidorn Computer Sciences Department IBM Thomas J. Watson Research Center Yorktown Heights, Hew York 10598 Abstract A technique is described for performing fitted parsing. After the rules of a more conventional syntactic grammar are unable to produce a parse for an input string, this technique can be used to produce a reasonable approximate parse that can serve as input to the remaining stages of processing. The paper describes how fitted parsing is done in the EP[STLE system and discusses how it can help in dealing with many difficult problems of natural language analysis. Introduction The EPISTLE project has as its long-range goal the ma- chine processing of natural language text in an office environ- ment. Ultimately we intend to have software that will be able to parse and understand ordinary prose documents (such as those that an office principal might expect his secretary to cope with), and will be able to generate at least a first draft of a business letter or memo. Our current goal is a system for critiquing written material on points of grammar and style. Our grammar is written in NLP (Heidorn 1972). an aug- mented phrase structure language which is implemented in LISP/370. The EPISTLE grammar currently uses syntactic, but not semantic, information. Access to an on-line standard dictionary with about 130.000 entries, including part-of-speech and some other syntactic information (such as transitivity of verbs), makes the system's vocabulary essentially unlimited. We test and improve the grammar by regularly running it on a data base of 2254 sentences from 411 actual business letters. Most of these sentences are rather complicated; the longest contains 63 words, and the average length is 19.2 words. Since the subset of English which is represented in busi- ness documents ,s very large, we need a very comprehensive grammar and robust parser. In the course of this work we have developed some new techniques to help deal with the refractory nature of natural language syntax. In this paper we discuss one such technique: the fitted parse, which guarantees the production of a reasonable parse tree for any string, no matter how unorthodox that string may be. The parse which is produced by fimng might not be perfect; but it will always be reasonable and useful, and will allow for later refinement by semantic processing. There is a certain perception of parsing that leads to the development of techniques like this one: namely, that trying to write a grammar to describe explicitly all and only the sen- fences of a natural language is about as practical as trying to find the Holy Grail. Hot only will the effort expended be Herculean, it will be doomed to failure. Instead we take a heuristic approach and consider that a natural language parser can be divided into three parts: (a) a set of rules, called the core grammor, that precisely define the central, agreed-upon grammatical structures of a …

Content truncated to 500 words