Frontier Pruning for Shift-Reduce CCG Parsing
Stephen Merity, James Curran · 2011
We apply the graph-structured stack (GSS) to shift-reduce parsing in a Combinatory Categorial Grammar (CCG) parser. This allows the shift-reduce parser to explore all possible parses in polynomial time without resorting to heuristics, such as beam search. The GSSbased shift-reduce parser is 34 % slower than CKY in the finely-tuned C&C parser. We perform frontier pruning on the GSS, increasing the parsing speed to be competitive with the C&C parser with a small accuracy penalty. 1