Efficient Combinatory Categorial Grammar Parsing
Bojan Djordjevic, James Curran · 2006
Efficient wide-coverage parsing is integral to large-scale NLP applications. Unfortunately, parsers for linguistically motivated formalisms, e.g. HPSG and TAG, are often too inefficient for these applications. This paper describes two modifications to the standard CKY chart parsing algorithm used in the Clark and Curran (2006) Combinatory Categorial Grammar (CCG) parser. The first modification extends the tight integration of the supertagger and parser, so that individual supertags can be added to the chart, which is then repaired rather than rebuilt. The second modification adds constraints to the chart that restrict which constituents can combine. Parsing speed is improved by 30–35% without a significant accuracy penalty and a small increase in coverage when both of these modifications are used.