CCG Parsing Algorithm with Incremental Tree Rotation

Proceedings of NAACL-HLT 2019, pages 228–239 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 228 CCG Parsing Algorithm with Incremental Tree Rotation Miloˇs Stanojevi´c School of Informatics University of Edinburgh m.stanojevic@ed.ac.uk Mark Steedman School of Informatics University of Edinburgh steedman@inf.ed.ac.uk Abstract The main obstacle to incremental sentence processing arises from right-branching con- stituent structures, which are present in the majority of English sentences, as well as from optional constituents that adjoin on the right, such as right adjuncts and right conjuncts. In CCG, many right-branching derivations can be replaced by semantically equivalent left- branching incremental derivations. The problem of right-adjunction is more resis- tant to solution, and has been tackled in the past using revealing-based approaches that of- ten rely either on the higher-order unification over lambda terms (Pareschi and Steedman, 1987) or heuristics over dependency represen- tations that do not cover the whole CCGbank (Ambati et al., 2015). We propose a new incremental parsing algo- rithm for CCG following the same revealing tradition of work but having a purely syntactic approach that does not depend on access to a distinct level of semantic representation. This algorithm can cover the whole CCGbank, with greater incrementality and accuracy than pre- vious proposals. 1 Introduction Combinatory Categorial Grammar (CCG) (Ades and Steedman, 1982; Steedman, 2000) is a mildly context sensitive grammar formalism that is at- tractive both from a cognitive and an engineer- ing perspective. Compared to other grammar for- malisms, the aspect in which CCG excels is incre- mental sentence processing. CCG has a very flex- ible notion of constituent structure which allows (mostly) left-branching derivation trees that are easier to process incrementally. Take for instance the derivation tree in Figure 1a. If we use a non- incremental shift-reduce parser (as done in the ma- jority of transition-based parsers for CCG (Zhang and Clark, 2011; Xu et al., 2014; Xu, 2016)) we will be able to establish the semantic connection between the subject “Nada” and the verb “eats” only when we reach the end of the sentence. This is undesirable for several reasons. First, human sentence processing is much more incremental, so that the meaning of the prefix “Nada eats” is avail- able as soon as it is read (Marslen-Wilson, 1973). Second, if we want a predictive model—either for better parsing or language modelling—it is crucial to establish relations between the words in the pre- fix as early as possible. To address this problem, a syntactic theory needs to be able to represent partial constituents like “Nada eats” and have mechanisms to build them just by observing the prefix. In CCG solu- tions for these problems come out of the theory naturally. CCG categories can represent partial structures and these partial structures can combine into bigger (partial) structures using CCG com- binators recursively. Figure 1b shows how CCG can incrementally process the example sentence via a different derivation tree that generates the same semantics more incrementally by being left- branching. This way of doing incremental processing …

Content truncated to 500 words