Parsing Incomplete Sentences

Parsing Incomplete Sentences Bernard LANG INRIA B.P. 105, 78153 Le Chesnay, France lang@inria.inria, fr Abstract An efficient context-free parsing algorithm is presented that can parse sentences with unknown parts of unknown length. It pa'oduees in finite form all possible parses (of- ten infinite in number) that could account for the missing parts. The algorithm is a variation oa the construction due to Earley. ltowever, its presentation is such that it can readily be adapted to any chart parsing schema (top- down, bottom-up, etc...). 1 Introduction It is often necessary in practical situations to attempt parsing an incorrect or incomplete input. This may take many forms: e.g. missing or spurious words, misspelled or misunderstood or oth- erwise unknown words [28], missing or unidentified word bound- aries [22,27]. Specific techniques may be developed to deal with these situations according to the requirements of the application arcs (e.g. n~tural language processing, progrmrmfing language parsing, tea:i-time or off-line processing). The con~lext-fi.ee (CF) parsing of a sentence with unknown words hss been considered by other authors [28]. Very simply, an unknown word may be considered as a "special multi-part-of- speech word whose pa'ct of speech can be anything". This multi- psi't-of-speech word need not be introduced in the CF grammar of the lang0age, but only implicitly in the construction of its parser. Thi;~ works very well with Earley-like (chart) parsers that can simulate all possible parsing paths that could lead to a correct parse. In this paper, we deal with the more complex problem of parsing a ser*.tence for wtfich one or several subparts of unknown length are roissing. Again we can use a chart parser to try all possible parses on all possible inputs. However the fact that the length of th~ 1*fissing subsequence is unknown raises an addi- tional difficulty. Many published chart parsers [24,28,23,21] are constructed ~,ith the assumption that tim CF grammar of the language ho~', no cyclic rules. Tlfis hypothesis is reasonable for the syntax ol natural (or programming) languages. However the resulting simplification of the pm'ser construction does not allow its extension to parsing sentences with unknown subsequenees of words. If the length (in words) of the missing subsequence were known, we could simply replace it with as many unknown words, a problem we know how to handle. When this length is not known, the tdgorithm has to simulate the parsing of an arbi- trary numbe~: of words, and thus may have to go several tim~ tht'ough reduction by the same rules of the grammar 1 without ever' touchinl; the stack present before scanning the unknown t~equenee, aml without reading the input beyond that sequence. If we consider the unknown sequence as a special input word, wc are in a situation that is analogous to that created by cyclic grammars, i.~. g~amrnars where a nonterminal may derive onto IThis grammar oriented view of the computation of the autonmton is only meant as a support for intuition. itself without producing any terminal. This explains why tech- niques limited to non-cyclic …

Content truncated to 500 words