Paper: The Structure Of Shared Forests In Ambiguous Parsing

ACL ID P89-1018
Title The Structure Of Shared Forests In Ambiguous Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1989

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 depende...