The Structure of Shared Forests in Ambiguous Parsing Sylvie Billot† ∗ Bernard Lang∗

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(n3) 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