Structure Sharing and Parallelization in a GB Parser
Marwan Shaban · 1994
By utilizing structure sharing among its parse trees, a GB parser can increase its efficiency dramatically. Using a GB parser which has as its phrase structure recovery component an implementation of Tomita's algorithm (as described in [Tom86]), weinvestigate how a GB parser can preserve the structure sharing output byTomita's algorithm. In this report, we discuss the implications of using Tomita's algorithm in GB parsing, and wegive some details of the structuresharing parser currently under construction. We also discuss a method of parallelizing a GB parser, and relate it to the existing literature on parallel GB parsing. Our approach to preserving sharing within a shared-packed forest is applicable not only to GB parsing, but anytime wewant to preserve structure sharing in a parse forest in the presence of features.