tailieunhanh - Báo cáo khoa học: "Shift-Reduce CCG Parsing"

CCG s are directly compatible with binarybranching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accuracies compared to C&C. . | Shift-Reduce CCG Parsing Yue Zhang University of Cambridge Computer Laboratory Stephen Clark University of Cambridge Computer Laboratory Abstract CCGS are directly compatible with binarybranching bottom-up parsing algorithms in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG the shift-reduce method has been little explored. In this paper we develop a shift-reduce CCG parser using a discriminative model and beam search and compare its strengths and weaknesses with the chart-based C C parser. We study different errors made by the two parsers and show that the shift-reduce parser gives competitive accuracies compared to C C. Considering our use of a small beam and given the high ambiguity levels in an automatically-extracted grammar and the amount of information in the CCG lexical categories which form the shift actions this is a surprising result. 1 Introduction Combinatory Categorial Grammar ccg Steedman 2000 is a lexicalised theory of grammar which has been successfully applied to a range of problems in NLP including treebank creation Hockenmaier and Steedman 2007 syntactic parsing Hockenmaier 2003 Clark and Curran 2007 logical form construction Bos et al. 2004 and surface realization White and Rajkumar 2009 . From a parsing perspective the C C parser Clark and Curran 2007 has been shown to be competitive with state-of-the-art statistical parsers on a variety of test suites including those consisting of grammatical relations Clark and Curran 2007 Penn Treebank phrase-683 structure trees Clark and Curran 2009 and unbounded dependencies Rimell et al. 2009 . The binary branching nature of CCG means that it is naturally compatible with bottom-up parsing algorithms such as shift-reduce and CKY Ades and Steedman 1982 Steedman 2000 . However the parsing work by Clark and Curran 2007 and also Hockenmaier 2003 and Fowler and Penn 2010 has only considered .