The Structure of Shared Forests in Ambiguous Parsing

The Structure of Shared Forests in Ambiguous Parsing Sylvie Billot t" Bernard Lang* INRIA rand Universit~ d'Orl~ans billotGinria.inria.fr langGinria.inria.fr Abstract The Context-Free backbone of some natural language ana- lyzers produces all possible CF parses as some kind of shared forest, from which a single tree is to be chosen by a disam- biguation process that may be based on the finer features of the language. We study the structure of these forests with respect to optimality of sharing, and in relation with the parsing schema used to produce them. In addition to a theo- retical and experimental framework for studying these issues, the main results presented are: - sophistication in chart parsing schemata (e.g. use of look-ahead) may reduce time and space efficiency instead of improving it, - there is a shared forest structure with at most cubic size for any CF grammar, - when O(n 3) complexity is required, the shape of a shared forest is dependent on the parsing schema used. Though analyzed on CF grammars for simplicity, these re- sults extend to more complex formalisms such as unification based grammars. Key words: Context-Free Parsing, Ambiguity, Dynamic Programming, Earley Parsing, Chart Parsing, Parsing Strategies, Parsing Schemata, Parse Tree, Parse Forest. 1 Introduction Several natural language parser start with & pure Conte~zt. Free (CF) backbone that makes a first sketch of the struc- ture of the analyzed sentence, before it is handed to a more elaborate analyzer (possibly a coroutine), that takes into ac- count the finer grammatical structure to filter out undesir- able parses (see for example [24,28]). In [28], Shieber sur- veys existing variants to this approach before giving his own tunable approach based on restrictions that ~ split up the infinite nonterminal domain into a finite set of equivalence classes that can be used for parsing". The basic motivation for this approach is to benefit from the CF parsing technol- ogy whose development over 30 years has lead to powerful and ei~cient parsers [I,7]. A parser that takes into account only an approximation of the grammatical features will often find ambiguities it can- not resolve in the analyzed sentences I. A natural solution *Address: INRIA, B.P. 105, 78153 Le Chesn~y, France. The work reported here was partially supported by the Eureka Software Factory project. 1 Ambiguity may also have a semantical origin." is then to produce all possible parses, according to the CF backbone, and then select among them on the basis of the complete features information. One hitch is that the num- ber of parses may be exponential in the size of the input sentence, or even infuite for cyclic grammars or incomplete sentences [16]. However chart parsing techniques have been developed that produce an encoding of all possible parses as a data structure with a size polynomial in the length of the input sentence. These techniques are all based on a dynamic programming paradigm. The kind of structure they produce to represent all parses of the analyzed sentence is an essential characteristic of these …

Content truncated to 500 words