Compositional Semantics for Linguistic Formalisms

Compositional Semantics for Linguistic Formalisms Shuly Wintner* Institute for Research in Cognitive Science University of Pennsylvania 3401 Walnut St., Suite 400A Philadelphia, PA 19018 shuly@:t±nc, cis. upenn, edu Abstract In what sense is a grammar the union of its rules? This paper adapts the notion of com- position, well developed in the context of pro- gramming languages, to the domain of linguis- tic formalisms. We study alternative definitions for the semantics of such formalisms, suggest- ing a denotational semantics that we show to be compositional and fully-abstract. This fa- cilitates a clear, mathematically sound way for defining grammar modularity. 1 Introduction Developing large scale grammars for natural languages is a complicated task, and the prob- lems grammar engineers face when designing broad-coverage grammars are reminiscent of those tackled by software engineering (Erbach and Uszkoreit, 1990). Viewing contemporary linguistic formalisms as very high level declara- tive programming languages, a grammar for a natural language can be viewed as a program. It is therefore possible to adapt methods and techniques of software engineering to the do- main of natural language formalisms. We be- lieve that any advances in grammar engineering must be preceded by a more theoretical work, concentrating on the semantics of grammars. This view reflects the situation in logic program- ming, where developments in alternative defini- tions for predicate logic semantics led to im- plementations of various program composition operators (Bugliesi et al., 1994). This paper suggests a denotational seman- tics tbr unification-based linguistic formalisms and shows that it is compositional and fully- *I am grateful to Nissim Francez for commenting on an em'lier version of this paper. This work was supported by an IRCS Fellowship and NSF grant SBR 8920230. abstract. This facilitates a clear, mathemati- cally sound way for defining grammar modu- larity. While most of the results we report on are probably not surprising, we believe that it is important to derive them directly for linguis- tic formalisms for two reasons. First, practi- tioners of linguistic formMisms usually do not view them as instances of a general logic pro- gramming framework, but rather as first-class programming environments which deserve in- dependent study. Second, there are some cru- cial differences between contemporary linguis- tic formalisms and, say, Prolog: the basic ele- ments -- typed feature-structures -- are more general than first-order terms, the notion of uni- fication is different, and computations amount to parsing, rather than SLD-resolution. The fact that we can derive similar results in this new domain is encouraging, and should not be considered trivial. Analogously to logic programming languages, the denotation of grammars can be defined us- ing various techniques. We review alternative approaches, operational and denotational, to the semantics of linguistic formalisms in sec- tion 2 and show that they are "too crude" to support grammar composition. Section 3 presents an alternative semantics, shown to be compositional (with respect to grammar union, a simple syntactic combination operation on grammars). However, this definition is "too fine": in section 4 we present an adequate, compositional and …

Content truncated to 500 words