Syntactic Constraints and Efficient Parsability

SYN'I'ACI IC CONSTI~,,\INTS AND F~FI:ICIFNI' I~AI(SAI~,II.I'I'Y Robert C. Berwick Room 820, MIT Artificial Intelligence l,aboratory 545 Technology Square, Cambridge, MA 02139 Amy S. Weinberg Deparuncnt of Linguistics, MIT Cambridge, MA 02139 ABSTRACT A central goal of linguistic theory is to explain why natural languages are the way they are. It has often been supposed that com0utational considerations ought to play a role in this characterization, but rigorous arguments along these lines have been difficult to come by. In this paper we show how a key "axiom" of certain theories of grammar, Subjacency, can be explained by appealing to general restrictions on on-line parsing plus natural constraints on the rule-writing vocabulary of grammars. The explanation avoids the problems with Marcus' [1980] attempt to account for the same constraint. The argument is robust with respect to machine implementauon, and thus avoids the problems that often arise wilen making detailed claims about parsing efficiency. It has the added virtue of unifying in the functional domain of parsing certain grammatically disparate phenomena, as well as making a strong claim about the way in which the grammar is actually embedded into an on-line sentence processor. I INTRODUCTION In its short history, computational linguistics has bccn driven by two distinct but interrelated goals. On the one hand, it has aimed at computational explanations of distinctively human linguistic behavior -- that is, accounts of why natural languages are the way they are viewed from the perspective of computation. On the other hand, it has accumulated a stock of engineenng methods for building machines to deal with natural (and artificial) languages. Sometimes a single body of research has combined both goals. This was true of the work of Marcus [1980]. for example. But all too often the goals have remained opposed -- even to the extent that current transformational theory has been disparaged as hopelessly "intractable" and no help at all in constructing working parsers. This paper shows that modern transformational grammar (the "Government-Binding" or "GB" theory as described in Chomsky [1981]) can contribute to both aims of computational linguistics. We show that by combining simple assumptions about efficient parsability along with some assumpti(ms about just how grammatical theory is to be "embedded" in a model of language processing, one can actually explain some key constraints of natural languages, such as Suhjacency. (The a)gumcnt is differmlt frt)m that used in Marcus 119801.) In fact, almost the entire pattern of cunstraints taken as "axioms" by the GB thct)ry can be accutmtcd tbr. Second, contrary to what has sometimes been supposed, by exph)iting these constraints wc can ~how that a Gll-based theory is particularly compatil)le v~idl efficient parsing designs, in particdlar, with extended I I~,(k,t) parsers (uf the sort described by Marcus [1980 D. Wc can extcnd thc I,R(k.t) design to accommodate such phenomena as antecedent-PRO and pronominal binding. Jightward movement, gappiug, aml VP tlcletion. A, Functional Explanations o__f I,ocality Principles Let us consider how to explain locality constraints in natural languages. First of all, what exactly do we mean …

Content truncated to 500 words