Formal Constraints on Metarules

Formal Constraints on Metarules* Stuart M. Shieber, Susan U. Stucky, Hans Uszkoreit, and Jane J. Robinson SRI International 333 Ravenswood Avenue Menlo Park, California Abstract Metagrammaticai formalisms that combine context-free phrase structure rules and metarules (MPS grammars) allow con- cise statement of generalizations about the syntax of natural lan- guages. Unconstrained MPS grammars, tmfortunately, are not cornputationally "safe." We evaluate several proposals for con- straining them, basing our amae~ment on computational trac- tability and explanatory adequacy. We show that none of them satisfies both criteria, and suggest new directions for research on alternative metagrammatical formalisms. 1. Introduction The computational-linguistics community has recently shown interest in a variety of metagrammatical formalisms for encoding grammars of natural language. A common technique found in these formalisms involves the notion of a metarule, which, in its most common conception, is a device used to generate grammar rules from other given grammar rules. 1 A metarule is essentially a statement declaring that, if a grammar contains rules that match one specified pattern, it also contains rules that match some other specified pattern. For example, the following metarule (1) VP -..V VP ~ VP-*Y ADVP VP [+/;-I [+o.~i states that, if there is a rule that expands a finite VP into a finite auxiliary and a nonfinite VP, there will also be a rule that expands the VP as before except for an additional adverb between the auxiliary and the nnnfinite VP. 2 The patterns may contain variables, in which case they characterize "families ~ of related rules rather than individual pairs. *This reeearch was supported by the National Science Foundation grant No. IST-8103550. The views and conclusions expressed in this document are those of the authors and should not be interpreted as represent,.tive of the views of the National Science Foundation or the United States government. We are indebted to Fernando Pereira, Stanley Peters, and Stanley Roscnscheln for many helpful discun~ons leading to the writing of this paper. IMetarules were first utilized for natural-language research and are most extensively developed within the theory of Generalized Phrase Structure Grammar (GPSG) [Ga2dar end Pullum, 1082; Gawron et ~., 1982; Thompson. 1082 I. 2A metarule similar to our example was proposed by Gazdar, Pullum, and sag [10s2, p. oorl. The metarule notion is a seductive one, intuitively allowing generalizations about the grammar of a language to be stated concisely. However, unconstrained metarule formalisms may possess more expressive power than is apparently needed, and, moreover, they are not always compatationally "safe." For ex- ample, they may generate infinite sew of rules and describe ar- bitrary languages, lu this paper we examine both the formal and linguistic implications of various constraints on metagram- matical formalisms consisting of a combination of context-free phrase structure rules and metarules, which we will call metarule phrase.structure (MPS] grammars. The term "MPS grammar" is used in two ways in this paper. An MPS grammar can be viewed as a grammar in its own right that characterizes a language directly. Alternatively, it can be viewed as …

Content truncated to 500 words