Paper: Efficient CCG Parsing: A* versus Adaptive Supertagging

ACL ID P11-1158
Title Efficient CCG Parsing: A* versus Adaptive Supertagging
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2011

We present a systematic comparison and com- bination of two orthogonal techniques for efficient parsing of Combinatory Categorial Grammar (CCG). First we consider adap- tive supertagging, a widely used approximate search technique that prunes most lexical cat- egories from the parser’s search space using a separate sequence model. Next we con- sider several variants on A*, a classic exact search technique which to our knowledge has not been applied to more expressive grammar formalisms like CCG. In addition to standard hardware-independent measures of parser ef- fort we also present what we believe is the first evaluation of A* parsing on the more realistic but more stringent metric of CPU time. By it- self, A* substantially reduces parser effort as measured by the number of edges consid...