Paper: A Structure-Sharing Representation For Unification-Based Grammar Formalisms

ACL ID P85-1017
Title A Structure-Sharing Representation For Unification-Based Grammar Formalisms
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1985
Authors
  • Fernando Pereira (SRI International, Menlo Park CA; Stanford University, Stanford CA)

This paper describes a structure-sharing method for the rep- resentation of complex phrase types in a parser for PATR-[I, a unification-based grammar formalism. In parsers for unification-based grammar formalisms, complex phrase types are derived by incremental refinement of rite phrase types defined in grammar rules and lexical entries. In a naive implementation, a new phrase type is built by copying older ones and then combining the copies according to the constraints stated in a grammar rule. The structure-sharing method was designed to eliminate most such copying; indeed, practical tests suggest that the use of this technique reduces parsing time by as much as 60%. The present work is inspired by the structure-sharing method for theorem proving introduced by Boyer and Moore and on the ...