Lambek Categorial Grammars for Practical Parsing

This dissertation investigates which grammar formalism to use for representing the structure of natural language in a practical parser, and advocates the use of Lambek Categorial Grammar (LCG) over similar formalisms such as Combinatory Categorial Grammar (CCG). Before we argue for the advantages of LCG, we first overcome two obstacles to its use in practical parsers: its NP-Complete parsing problem, and its weak equivalence to Context-Free Grammars (CFGs). We develop a parsing algorithm for LCG that is polynomial when the order of categories in the grammar is bounded by a constant. Furthermore, we show that in CCGbank, the only existing categorial grammar corpus, the order of categories is very low. Next, we analyze the Clark and Curran parser, the state of the art in categorial grammar parsing, and establish that the CCG that it uses is also weakly equivalent to CFGs. Then, we train the Petrov parser, a probabilistic CFG parser, on CCGbank and obtain the best results to date on the test set. This establishes that LCG's weak equivalence to CFGs is not a hindrance to its use in a practical parser. Having established the viability of using LCG in a parser, we then argue for its superiority over CCG as a representation for the structure of natural language sentences. We show that LCG offers a greater transparency between its syntactic structure and the categorial semantics that can be built from a parse of a categorial grammar. As part of this argument, we show that representing LCG derivations as proof nets allows for a more cohesive representation of categorial syntax, dependency structures and categorial semantics than CCG. To demonstrate this, we develop a corpus of LCG derivations by semi-automatically translating the CCG derivations of CCGbank into LCG proof nets.Ph.D