Parsing and Derivational Equivalence

PARSING AND DERIVATIONAL EQUIVALENCE* Mark Hepple and Glyn Morrill Centre for Cognitive Science, University of Edinburgh 2 Buccleuch Place, Edinburgh EH8 9LW Scotland Abstract It is a tacit assumption of much linguistic inquiry that all distinct derivations of a string should assign distinct meanings. But despite the tidiness of such derivational uniqueness, there seems to be no a pri- ori reason to assume that a gramma r must have this property. If a grammar exhibits derivational equiv- alence, whereby distinct derivations of a string as- sign the same meanings, naive exhaustive search for all derivations will be redundant, and quite possibly intractable. In this paper we show how notions of derivation-reduction and normal form can be used to avoid unnecessary work while pars- ing with grammars exhibiting derivational equiv- alence. With grammar regarded as analogous to logic, derivations are proofs; what we are advocat- ing is proof-reduction, and normal form proof; the invocation of these logical techniques adds a further paragraph to the story of parsing-as-deduction. Introduction The phenomenon of derivational equivalence is most evident in work on generalised categorial grammars, where it has been referred to as ~spu- rious ambiguity'. It has been argued that the ca- pacity to assign left-branching, and therefore incre- mentally interpretable, analyses makes these gram- mars of particular psychological interest. We will illustrate our methodology by reference to gener- alised categorial grammars using a combinatory logic (as opposed to say, lambda-calculus) seman- tics. In particular we consider combinatory (cate- gorial) grammars with rules and generalised rules *We thank Mike Reape for criticism and suggestions in relation to this material, and Inge Bethke and Henk Zee- vat for reading a late draft. All errors are our own. The work was carried out by the alphabetically first author under ESRC Postgraduate Award C00428722003 and by the sec- ond under ESRC Postgraduate Award C00428522008 and an SERC Postdoctoral Fellowship in IT. of the kind of Steedman (1987), and with metarules (Morri~ 19ss). Although the problem of derivational equiva- lence is most apparent in generalised categorial grammars, the problem is likely to recur in many grammars characterising a full complement of con- structions. For example, suppose that a grammar is capable of characterising right extraposition of an object's adjunct to clause-final position. Then sentences such as Joha met a man yesterday who swims will be generated. But it is probable that the same grammar will assign Joha met a maa who swims a right extraposition derivation in which the relative clause happens to occupy its normal posi- tion in the string; the normal and right extrapo- sition derivations generate the same strings with the same meanings, so there is derivational equiva- lence. Note that a single equivalence of this kind in a grammar undermines a methodological assump- tion of derivational uniqueness. Combinatory Logic and Combina- tory Grammar Combinatory logic (CL; Curry and Feys, 1958; Curry, Hindley and Seldin, 1972; Hindley and Seldin, 1986) refers to systems which are ap- plicative, like the lambda-calculi, but which for- malise functional …

Content truncated to 500 words