Phrase Structure Grammars and Natural Languages

ABSTRACT

During most of the last two decades, computational linguists and AI researchers working on natural language have assumed that phrase structure grammars, despite their computational tractability, were unsatisfactory devices for expressing the syntax of natural languages. However, during the same period, they have come to realize that transformational grammars, whatever their linguistic merits, are computationally intractable as they stand . The assumption, unchallenged for many years, that PSG 's were inadequate for natural languages is based on arguments originally advanced by transformational linguists in the late 1950's and early 1960's. But recent work has shown that none of those arguments were valid. The present paper draws on that work to argue that (i) there is no reason, at the present time, to think that natural languages are not context-free languages, ( ii) there are good reasons to think that the notations needed to capture significant syntactic generalizations will characterize phrase structure grammars or some minor generalization of them, and (iii) there are good reasons for believing that such grammars, and the monostratal representations they induce, provide the necessary basis for the semantic interpretation of natural languages . If these arguments are valid, then the prospects for a fruitful interaction between theoretical linguistics and AI are much brighter than they would otherwise be.

I INTRODUCTION

Consider the following quotations:

As already mentioned, a context - free phrase structure grammar is not sufficient to describe or analyze the whole range of syntactic constructions which occur in natural language texts (cf. Chomsky 1957) . Even if one disregards the theoretical linguist's demand for satisfactory descriptions of the syntactic structure of sentences, there are strong reasons to design a more powerful parser than the one described above. Cases in point are the phenomenon of agreement within noun phrases, the correspondence in the verb phrase between the form of the main verb and the type of the auxiliary, and subject verb agreement. The argument structure of predicates, that is, their various types of objects and complements, represents another

PHRASE STRUCTURE GRAMMARS AND NATURAL LANGUAGES

Gerald Gazdar

Cognitive Studies Programme University of Sussex

Brighton BN1 9QN

kind of context-sensitivity in natural language . The best strategy seems to be to take care of the particular types of context-sensitivity recognized by linguistic theory by means of special procedures which act as a superstructure of the algorithm for context-free analysis . .. . In addition to the above -mentioned drawbacks a context-free phrase structure grammar has difficulty handling word order ·variation in a natural way.

(~elin 1979 : 62- 63)

One significant use of the general context­ free methods is as part of a system of processing natural languages such as English. we are not suggesting that there is a context - free grammar for English. It is probably more appropriate to view the grammar/parser as a convenient control structure for directing the analysis of the input string. The overall analysis is motivated by a linguistic model which is not context free, but which can frequently make use of structures determined by the context­ free grammar .

(Graham, Harrison & Ruzzo 1980 : 415- 416)

These two passages have a number of things in common, of which three are relevant here. Firstly, the issue of whether natural languages (NL 's) are context-free languages (CFL's) and are susceptible to analysis by context-free phrase structure grammars (CF- PSG 's) is one the authors take to be relevant to parsing. Secondly, both passages assume that this issue has already been resolved, and resolved in the negative. Thirdly, I did not have to look for them, I merely bumped into them, as it were, in the course of recent reading . However, I am sure that if I had been in the business of finding passages with this kind of flavour in the parsing literature of the past 20 years, then I could have found dozens, probably hundreds.

The purpose of the present paper is simply to draw the attention of computational linguists to the fact that the issue of the status of NL's with respects to the CFL 's and CF-PSG 's is not resolved, and to the fact that all the published arguments seeking to establish that NL's are not CFL's, or that CF- PSG's are not adequate for the analysis of NL's, ar e completely without force. Of course, this does not entail that NL's are

CFL's or that CF-PSG's constitute the appropriate formal theory of NL grammars. But it does have as a consequence that computational linguists should not just give up on CF-PSG's on the grounds that theoretical linguistics has demonstrated their inadequacy. No such demonstration exists.

In assessing whether some formal theory of grammar is an adequate theory for NL's, at least the following three criteria are relevant, and have been historically. (i) Does it permit NL's qua sets of strings to be generated? (ii) Does it permit significant generalizations to be expressed? (iii) Does it support a semantics, that is, does it provide a basis on which meanings can be assigned to NL expressions in a satisfactory manner?

In the remainder of this paper, I shall consider these three criteria in turn with reference to the adequacy of CF-PSG 's as grammars for NL's. The issues are large, and space is limited, so my discussion will take the form, for the most part, of annotated references to the literature where the various issues are properly dealt with.

II GENERATING NATURAL LANGUAGE STRING SETS

The belief that CF-PSG's cannot cope with syntactic concord and long-distance dependencies, and hence that NL's are not CFL's, but, say, properly context-sensitive languages, is well entrenched. One textbook goes so far as to assert that 'the grammatical phenomenon of Subject Predicate Agreement is sufficient to guarantee the accuracy of [the statement that] English is not a CF-PSG language' (Grinder & Elgin 1973: 59). The phenomenon guarantees no such thing, of course. Nor is the character of th~ problem changed when agreement is manifested across unbounded distances in strings .(pace Bach · 1974: 77, Bresnan 1978: 38). Indeed, finite state languages can exhibit such dependencies (see Pullum & Gazdar, 1982).

The introductory texts and similar expository works in the field of generative grammar offer nothing that could be taken seriously as an argument that NL's are not CFL's. However, five putatively non-specious arguments to this effect are to be found in the more technical literature. These are based on the following phenomena:

• (a) English comparative clauses (Chomsky 1963: 378-9),
• (b) the decimal expansion of pi (Elster 1978: 43-44),
• (c) 'respectively' (Bar-Hillel & Shamir 1960: 96, Langendoen 1977: 4-5),
• (d) Dutch subordinate clauses (Huybregts 1976),
• (e) Mohawk noun incorporation (Postal 1964).

Pullum & Gazdar (1982) show that (a) is based on a false empirical claim and a false claim about formal languages, (b) has no bearing on English or any other natural language since it depends on a confusion between grammar and arithmetic, (c) is based on a false empirical claim, and the facts, such as they are, are relevant to semantics rather than syntax in any case, (d) provides no basis for any string set argument [1], and (e) Postal crucially failed to take account of one class of permissible incorporations once these are recognized, the formal basis of his argument collapses.

Thus, Pullum & Gazdar (1982) demonstrate that every published argument purporting to show that one or another NL is not a CFL is invalid, either formally, or empirically, or both. whether any NL, construed as a string set, falls outside the class of CFLs remains an open question, just as it was twenty five years ago.

III CAPTURING SIGNIFICANT GENERALIZATIONS

Argumentation purporting to show that CF-PSG's will miss significant generalizations about some NL phenomenon has been woefully inadequate. Typically it consists simply of providing or alluding to some CF-PSG which obviously misses the generalization in question. But, clearly, nothing whatever follows from such an exhibition. Any framework capable of handling some phenomenon at all will typically make available indefinitely many ugly analyses of the phenomenon. But this fact is neither surprising nor interesting. what is surpr~s~ng, and rather disturbing, is that arguments of this kind (beginning, classically, in chapter 5 of Chomsky 1957) have been taken so seriously for so long.

Capturing significant generalizations is largely a matter of notation. But CF-PSG's, taken as a class of mathematical objects, have properties which are theirs independently of the notations that might be used to define them. Thus they determine a certain set of string sets, they determine a certain set of tree sets, they stand in particular equivalence relations, and so on. An analogy from logic is pertinent here: the truth function material implication just is material implication whether you notate it with an arrow, or a hook, or the third letter of the alphabet, and whether you use prefix, infix, or postfix positioning of the symbol.

Over its 25 year history, transformational grammar developed a whole armoury of linguistically useful notations, and many of these can just as well be used in characterizing CF-PSG's. Three such notational devices merit individual mention: (a) complex symbols, (b) rule schemata, and (c) mappings from one set of rules into another (metarules).

Harman (1963) deserves the credit for first seeing the potential of PSG's incorporating complex symbols. The use of a finite set of complex symbols, in place of the traditional finite set of monadic symbols, leaves the mathematical properties of CF-PSG's unchanged. Every CF-PSG employing complex symbols generates a tree set that is isomorphic to the tree set generated by some CF-PSG not employing complex symbols. However, complex symbol systems including features, "X-bar conventions", and "slash categories", etc., allow syntactic generalizations to straightforwardly. many significant be captured rather For example, Gazdar & Pullum (1981) show how the use of complex symbols for subcategorization in a CF-PSG can capture generalizations that had had to be stipulated in the standard transformational account employing context-sensitive lexical insertion. And in Gazdar (1981a, 1981b) and Sag ( 1982a, 1982b) complex symbols called "slash categories" are shown to be able to capture the generalizations underlying the class of unbounded dependency constructions in English (e .g. relative clauses, wh-questions, topicalization, etc.). Figure 1 illustrates with a topicalization example:

Interestingly, such an analysis of unbounded dependencies is able to capture a generalization about their interaction with coordination that was never satisfactorily captured in transformational grammar (see Gazdar, Pullum, Sag & Wasow 1982).

Rule schemata allow generalizations to be ca~tured by collapsing sets of rules with some common property into a single statement. In a CF-PSG, one can cap ture the familiar generalization that only like- constituents conjoin with a schema along the following lines:

The generalization that this captures was not captured in classical TG: part of it was expressed in the base rules, and the rest was intendedly expressed in the formulation of a transformation called "Coordination Reduction" .

Another example of the power of rule schemata (applied to complex symbols) involves agreement phenomena:

S -> NP["6) VP[iJ

where ~ ranges over permissible

combinations of agreement features.

This schema, taken together with a widely assumed, and putatively univeral, convention of feature transfer (the Head Feature 1982) suffices to capture facts about subject verb Figure 2 illustrates: Convention, see Gazdar all the straightforward agreement in English.

Indeed, as Borsley (1983) and Stucky (1983, appendix) demonstrate, far more subtle and complex agreement phenomena succumb to analysis by phrase structure grammars equipped with features and rule schemata.

Like a rule schema, a metarule characterization device (i.e. a definition of the grammar). But is a clause unlike grammar in the a rule schema , it is one which enables one to define one set of rules in terms of another set, antecedently given. Generalizations which would be lost if the two sets of rules were merely listed are captured by the metarule [2].

For example, suppose that our grammar contains, inter alia, the following set of rules expanding VP:

VP -> V[ 1] NP VP -> V[2] NP NP VP -> V[3] NP pp VP -> V[4] NP VP VP -> V[5) NP s

VP -> V[6] NP NP s

Then we can augment the grammar by means of the following metarule:

This says that for every rule in the grammar whi ch expands VP as a verb followed by an NP possibly followed by other stuff (we don't care what), there is also to be a rule expanding a passive VP as the verb followed by the other stuff (if there was any) followed optionally by an agentive PP. This metarule will thus adg the following rules to our grammar:

VP[PAS] -> v [ 1] ( PP[ by]) VP[PAS] -> V[2] NP ( pp [by]) VP[PAS] -> V[3) pp (PP[by]) VP[PAS] -> V[4] VP (PP[by]) VP[PAS] -> V[5) s (PP[by]) VP[PAS] -> V[6] NP s (PP[by])

These rules will now allow the grammar to generate passive sentences directly.

Note that transformations were mappings from sets of structures to sets of structures, whereas metarules are mappings from sets of rules to sets of rules. Gazdar & Sag (1981) and Gunji (1983) show how metarules can capture reflexive pronoun generalizations in the definitions of PSG's for English and Japanese, respectively, and Gazdar, Pullum & Sag (1982) use metarules to provide accurate and nonredundant analyses for "Subject­ auxiliary inversion", adverb placement, and VP ellipsis in a grammar of the English auxiliary system.

So-called "free word order" languages have sometimes been alleged to pose a problem in principle for the generalization-capturing powers of CF-PSG's. That they do not is amply demonstrated in Horrocks (1983), Pullum (1982) and Stucky (1983) [3].

There is, thus, at the present time, no reason whatsoever to think that the goal of capturing linguistically significant generalizations is in any way inconsistent with the use of CF-PSG's.

IV SUPPORT OF A SEMANTICS

In asking whether some theory of syntax "supports a semant ics", we are asking whether there exists some semantic theory which will interpret the structures provided by the syntax in a manner consistent with our judgments concerning ambiguity, synonymy, entailment, etc. Within linguistics, the key semantic development of the 1970's was the appearance of a model theory for natural languages originating in the work of ~ontague (see Montague 1974; Dowty et al. 1981). Before Montague, linguists had been disposed either to do their semantics in the syntax, a the Generative Semanticists, or not at all, as in Chomsky's oeuvres. But the sophisticated and extension operators, etc.) which Montague had

practice that reached its apogee in the work of machinery (including lambda abstraction, meaning postulates, higher order quantification, intension made available meant that semantics could now be done as such. This had all kinds of implications for syntax.

Here are some examples. (i) Heny (1970) and Cooper (1975) showed that quantifier scope ambiguities could be handled entirely in the semantics, without the need for quantifier movement in the syntax. More recently, Cooper (1983) has provided a general semantic treatment of pronouns and quantifier binding which directly interprets a phrase structure syntax. (ii) Dowty (1978) showed that the semantic properties of dative, passive, unspecified object, "Raising", and "Equi" constructions could all be provided for directly, without corresponding syntactic operations that moved or deleted NP's. (iii) Also in 1978, three sets of authors independently proposed closely related cross-categorial semantic theories for Faltz 1978). This work, which is further advanced in Partee & Rooth (1983), completely undercuts all semantic motivation for "Coordination Reduction"

coordination (Cooper 1979; Gazdar 1980a; Keenan & transformations or equivalent operations in the syntax. that (iv) McCloskey (1979) was able to show the deep structure/surface structure distinction was irrelevant to giving a semantics for relative clauses and wh-questions: structures of either kind provide a suitable locus for semantic interpretation. (v) Klein (1980, 1981a, 1981b, 1982) has demonstrated that the meaning of all the various comparative constructions found in English can be derived directl y from their surface syntactic forms as given by a CF-PSG along the lines of Gazdar (198Gb). (vi) Was ow, Sag, & Nunberg (1982) argue that the proper treatment of idioms is one which semantically interprets them compositionally. Their analysis vitiates all the arguments for syntactic movement rules that depend on the claim that sentences like tabs were kept on every suspect cannot be --compositionally interpreted. In a similar vein, Sag (1982c) and Sag & Klein (1982) have shown that the syntactic distribution of the English "dummy subjects" it and there (as in such sentences as it appears to be ObVIOus that we lost, and there-seems to have been a lion--rrl -thepark) folloWfrom ---ail appropriare--semantrc- theory of such expressions, without any need for ra~s~ng operations in the syntax. (vii) And, in related work, Klein & Sag (1982) develop a semantic theory for phrase structure grarr~ars for natural languages which largely eliminates the need to stipulate semantic translation rules. Instead, these rules follow from a function which takes as arguments (1) the semantic type of a lexical item, and (2) the phrase structure rule responsible for introducing the lexical item.

Thus there is every reason to believe that CF­ PSG's can support appropriate semantic theories for NL's at least as well as multilevel syntactic frameworks [4, 5]. Indeed, there is an ad hominem argument which suggests that they may be preferable. It is noteworthy that almost all the linguists currently working out the implications of Montague's semantic legacy (e.g. Bach, Cooper, Dahl, Dowty, Karttunen, Keenan, Klein, Partee, Peters, and Sag, to name but ten) have gravitated towards essentially monostratal syntactic theories although this concreteness is not obviously presaged in Montague's own, rather abstract, approach to syntax.

V CONCLUSIONS

In brief, I have tried to make plausible the following three claims. ( i) There is no reason, at the present time, to think that NL's are not CFL's. (ii) There are good reasons for thinking that the notations that we need to capture significant syntactic generalizations will characterize CF-PSG's, or some minor generalization of them, such as indexed grammars. (iii) There are very good reasons for believing that such grammars, and the monostratal representations they induce, provide the necessary basis for the semantic interpretation of NL's. And that, concomitantly, there is no semantic motivation for syntactic operations that move, delete, permute, copy or substitute constituents.

The relevance of these claims, which emerge from current theoretical linguistics, to the computational modelling of natural language processing is something which is argued for or assumed in an increasing body of recent work [6].

ACKNOwLEDGEHENTS

This research was supported by grant HR 7829/1 from the SSRC (UK ) . I am grateful to Aravind Joshi, Ewan Klein, Geoff Pullum, Ivan Sag , Henry Thompson, and two anonymous referees for some helpful suggestions . An ancestor of this paper was presented at an SERC workshop on natural language parsing organized by Karen Sparck-Jones and Yorick Wilks and held at the University of Essex in April

1982.

FOOTNOTES

1. whether or not a CF-PSG can generate the correct structural descriptions for the relevant set of Dutch sentences is an intriguing open question. If the grammatical set of trees is exactly the set that Bresnan, Kaplan, Peters & Zaenen (1982) assume it to be, then, as they show, the answer is no. But see, now, Pullum ( 1983) and Thompson (1983).
2. The idea of using one grammar to generate another originates in computer science with the work of van Wijngaarden (1969) who used the technique to give a perspicuous syntax for ALGOL68. A good introduction to his work can be found in Cleaveland & Uzgalis (1975). Janssen (1980) employs a van Wijngaarden-style two-level grammar to define a generalization of Montague's PTQ syntax. Recent work in computational linguistics that employs metarules includes Gawron et al. (1982), Kay (1983), Konolige (1980), Robinson ( 1980), Schubert and Pelletier ( 1982), Shieber, Stucky , Uszkoreit and Robinson (1983), and Thompson ( 1982).
3. The interesting parsing issues that "free word order" languages give rise to are addressed
4. in Shieber (1983) and Uszkoreit (1983).
5. This is not to suggest , of course, that all significant semantic problems are solved by the shift to surface structure syntax. One currently interesting puzzle concerns how one binds pronouns that appear in "dislocated" constituents (Cooper 1983; Dahl 1981, 1982; Engdahl 1982a, 1982b). Another concerns the possibility of multiple wh-type dependencies in Scandinavian languages, and the variable-binding issue that this gives rise to (see Engdahl 1980; Maling & Zaenen 1982) . One promising strategy for getting a solution to both these problems entails grounding the semantics on an indexed grammar (Aho 1968; Hopcroft & Ullman 1979, pp. 389- 390) rather than on a CF-PSG. Indexed grammars are similar to CF-PSG's which employ complex symbols, except that there is no finite limit on the number of distinct complex symbols that can be used. This generalization of CF-PSG is potentially relevant to the issue mentioned in footnote 1, above, and to the nesting of equative and comparative clauses (see Klein 1981b). Cf., also, the tree adjunction
6. defined MCSL's of Joshi (1982) (the MCSL's properly include the CFL's but are properly included by the indexed languages).
7. I assume that this conclusion would carry over to non-Montague approaches to semantics. However, I have restricted myself here to the 1'1ontague paradigm since it is by far and away the most detailed and extensive framework for NL semantics available at the present time. That Montague's ideas are compatible with a computational orientation to language is evidenced or argued in a large body of recent work: e.g., Bronnenberg et al. (1980), Friedman (1978, 1981), Friedman, Moran & Warren (1978), Friedman & Warren (1978), Fuchi (1981), Gunji & Sondheimer ( 1980), Hobbs & Rosenschein (1978), Indurkhya ( 1981), Ishimoto ( 1982) , Janssen ( 1976, 1977, 198 3) , Landsbergen (1981, 1982), l>Iatsumoto (1981, 1982), Moran (1980), Nishida et al. (1981), Nishida & Doshita (1982, 1983), Root (1981), Saheki (1982), Sawamura ( 1981), Sondheimer & Gunj i ( 1978), and warren (1979). See also Gunji (1981) for a description of the programming language ElL - Extended Intensional Lisp.
8. E.g., Bear & Karttunen (1979), Ejerhed ( 1980) , Fodor ( 1982a, 1982b) , Gawron et al. (1982), Joshi (1983), Joshi & Levy (1982), Kay ( 1983) , Konolige ( 1980), Pullum ( 1983), Pulman ( 1983) , Robinson ( 1980, 1982), Rosenschein & Shieber ( 1982), Ross ( 1981, 1982) , Schubert ( 1982), Schubert & Pelletier ( 1982), Shieber ( 1983a, 19b3b) , Thompson ( 1981, 1982, 1983) , and Uszkoreit (1983). And see Berwick & Weinberg (1982) for a rather extended metatheoretical disquisition.