Incremental Constraint-based Parsing: An Efficient Approach for Head-final Languages

Abstract

In this dissertation, I provide a left-to-right incremental parsing approach for Headdriven Phrase Structure Grammar (HPSG; Pollard and Sag (1987, 1994)). HPSG is a lexicalized, constraint-based theory of grammar, which has also been widely exploited in computational linguistics in recent years. Head-final languages are known to pose problems for the incrementality of head-driven parsing models, proposed for parsing with constraint-based grammar formalisms, in both psycholinguistics and computational linguistics. Therefore, here I further focusmy attention on processing a head-final language, specifically Turkish, to highlight any challenges that may arise in the case of such a language. The dissertation makes two principal contributions, the first part mainly providing the theoretical treatment required for the computational approach presented in the second part. The first part of the dissertation is concerned with the analysis of certain phenomena in Turkish grammar within the framework of HPSG. The phenomena explored in this part include word order variation and relativization in Turkish. Turkish is a head-final language that exhibits a considerable degree of word order freedom, with both local and long-distance scrambling. I focus on the syntactic aspects of this freedomin simple and complex Turkish sentences, detailing the assumptions Imake both to dealwith the variation in the word order, and also to capture certain restrictions on that variation, within the HPSG framework. The second phenomenon, relativization in Turkish, has drawn considerable attention in the literature, all accounts so far being within the tradition of transformational grammar. Here I propose a purely lexical account of the phenomenon within the framework of HPSG, which I claim is empirically more adequate than previous accounts, as well as being computationally more attractive. The motivation behind the work presented in the second part of the dissertation mainly stems from psycholinguistic considerations. Experimental evidence (e.g. Marslen- Wilson (1973)) has shown that human language processing is highly incremental, meaning that humans construct aword-by-word partial representation of an utterance as they hear each word. Here I explore the computational effectiveness of an incremental processing mechanism for HPSG grammars. I argue that any such processing mechanism has to employ some sort of nonmonotonicity in order to guarantee both completeness and termination, and propose a way of doing that without violating the soundness of the overall approach. I present a parsing approach for HPSG grammars that parses a string of words fromleft to right, attaching every word of the input to a global structure as soon as it is encountered, thereby dynamically changing the structure as the parse progresses. I further focus on certain issues that arise in incremental processing of a “free”word order, head-final language like Turkish. First, I investigate howthe parser can benefit from the case values in Turkish in foreseeing the existence of an embedded phrase/clause before encountering its head, thereby improving the incrementality of structuring. Second, I propose a strategy for the incremental recovery of filler-gap relations in certain kinds of unbounded dependency constructions in Turkish, which further enables one to capture a number of (strong) preferences that humans exhibit in processing certain examples with potentially ambiguous long-distance dependency relations.