Author: Steve Lytinen and Noriko Tomuro
Journal-ref: DePaul CTI Tech Report 98-002
Many algorithms for parsing unification grammars are extensions of well-known context-free parsing techniques, such as chart parsing. An example is Shieber's abstract parsing algorithm (Shieber, 1992), which can be viewed as an extension of Earley's algorithm. In this paper, we discuss a difficulty that exists in these algorithms in general, and in Shieber's algorithm in particular. The difficulty is that these algorithms produce what we call "nonminimal derivations". Nonminimal derivations are parse trees which contain more information (i.e., features) than they absolutely have to. We show examples of nonminimal derivations produced by Shieber's algorithm, and enumerate the situations in which such derivations are produced. We then suggest several possible ways to modify to the algorithm to address this problem.
Paper: Full paper (postscript 199k)