Paper: Efficient Parsing for Transducer Grammars

ACL ID N09-1026
Title Efficient Parsing for Transducer Grammars
Venue Human Language Technologies
Session Main Conference
Year 2009

The tree-transducer grammars that arise in current syntactic machine translation systems are large, flat, and highly lexicalized. We ad- dress the problem of parsing efficiently with such grammars in three ways. First, we present a pair of grammar transformations that admit an efficient cubic-time CKY-style parsing algorithm despite leaving most of the grammar in n-ary form. Second, we show how the number of intermediate symbols gen- erated by this transformation can be substan- tially reduced through binarization choices. Finally, we describe a two-pass coarse-to-fine parsing approach that prunes the search space using predictions from a subset of the origi- nal grammar. In all, parsing time reduces by 81%. We also describe a coarse-to-fine prun- ing scheme for forest-based language model...