The Semantics of Grammar Formalisms Seen as Computer Languages

The Semantics of Grammar Formalisms Seen as Computer Languages Fernando C. N. Pereira and Stuart M. Shieber Artificial Intelligence Center SRI International and Center for the Study of Language and Information Stanford University Abstract The design, implementation, and use of grammar for- ma]isms for natural language have constituted a major branch of coml)utational linguistics throughout its devel- opment. By viewing grammar formalisms as just a spe- cial ease of computer languages, we can take advantage of the machinery of denotational semantics to provide a pre- cise specification of their meaning. Using Dana Scott's do- main theory, we elucidate the nature of the feature systems used in augmented phrase-structure grammar formalisms, in particular those of recent versions of generalized phrase structure grammar, lexical functional grammar and PATR- I1, and provide a (lcnotational semantics for a simple gram- mar formalism. We find that the mathematical structures developed for this purpose contain an operation of feature generalization, not available in those grammar formalisms, that can be used to give a partial account of the effect of coordination on syntactic features. 1. Introduction I The design, implementation, and use of grammar for- malisms for natural lang,age have constituted a major branch of computational linguistics throughout its devel- opment. Itowever, notwithstanding the obvious superfi- cial similarily between designing a grammar formalism and designing a programming language, the design techniques used for grammar formalisms have almost always fallen short with respect to those now available for programming language design. Formal and computational linguists most often explain the effect of a grammar formalism construct either by ex- ample or through its actual operation in a particular im- plementation. Such practices are frowned upon by most programming-language designers; they become even more dubious if one considers that most grammar formalisms in use are based either on a context-free skeleton with augmentations or on some closely related device (such as ATNs), consequently making them obvious candidates for IThe research reported in this paper has been made possible by a gift from the System Development Foundation. a declarative semantics z extended in the natural way from the declarative semantics of context-free grammars. The last point deserves amplification. Context-free grammars possess an obvious declarative semantics in which nonterminals represent sets of strings and rules rep- resent n-ary relations over strings. This is brought out by the reinterpretation familiar from formal language theory of context-free grammars as polynomials over concatena- tion and set union. The grammar formalisms developed from the definite-clause subset of first order logic are the only others used in natural-language analysis that have been accorded a rigorous declarative semantics--in this case derived from the declarative semantics of logic pro- grams [3,12,1 I]. Much confusion, wasted effort, and dissension have re- sulted from this state of affairs. In the absence of a rigorous semantics for a given grammar formalism, the user, critic, or implementer of the formalism risks misunderstanding the intended interpretation of a construct, and is in a poor posi- tion to compare it to alternatives. Likewise, the inventor …

Content truncated to 500 words