Paper: Guided Parsing Of Range Concatenation Languages

ACL ID P01-1007
Title Guided Parsing Of Range Concatenation Languages
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2001
Authors

The theoretical study of the range concatenation grammar [RCG] formal- ism has revealed many attractive prop- erties which may be used in NLP. In particular, range concatenation lan- guages [RCL] can be parsed in poly- nomial time and many classical gram- matical formalisms can be translated into equivalent RCGs without increas- ing their worst-case parsing time com- plexity. For example, after transla- tion into an equivalent RCG, any tree adjoining grammar can be parsed in a2a4a3a6a5a8a7a10a9 time. In this paper, we study a parsing technique whose purpose is to improve the practical efficiency of RCL parsers. The non-deterministic parsing choices of the main parser for a lan- guagea11 are directed by a guide which uses the shared derivation forest output by a prior RCL parser for a suita...