Tutorial Announcement      

Coling 2000 Tutorial Announcement

S. Wintner: Grammar Semantics


What do grammars mean? When are two grammars equivalent? When is it safe to replace one grammar by another? How can two grammars be combined to form a larger one? And why should I care, if all I want is to develop a broad-coverage grammar of some natural language?

This tutorial discusses some of the mathematical and computational properties of formal grammars by applying well-established results from the semantics of programming languages to linguistic formalisms. A well-founded semantics for formal grammars is a prerequisite for providing good solutions for practical problems of grammar engineering such as grammar composition, modular design, separate and incremental compilation etc. We will focus on the simplest linguistic formalism, context-free grammars, but will show that many of the results hold for unification-based grammars as well.

We will start with mostly theoretical infrastructure. Two major ways of defining grammar semantics will be presented: operational and denotational. We will discuss certain mathematical properties of the semantic definitions, their advantages and drawbacks. Then, we will define compositionality and full abstraction, two desirable properties for any semantic definition. We will show a semantics that has these two properties: this will set the stage for a discussion of grammar composition and grammar modules. The tutorial will end with a survey of practical applications of grammar semantics in grammar engineering, although fewer results and more open questions will be presented.


  1. Van Emden, M. H. and Kowalski, Robert A., 1976 The semantics of predicate logic as a programming language Journal of the Association for Computing Machinery 23(4)
  2. Apt, Krzysztof R. and Van Emden, M. H., 1982 Contributions to the theory of logic programming Journal of the Association for Computing Machinery 29(3)
  3. Pereira, Fernando C. N. and Warren, David H. D., 1983 Parsing as Deduction ACL-21
  4. Shieber, Stuart and Schabes, Yves and Fernando Pereira, 1995 Principles and Implementation of Deductive Parsing Journal of Logic Programming 24(1-2)
  5. Pereira, Fernando C. N. and Shieber, Stuart M., 1984 The semantics of grammar formalisms seen as computer languages COLING/ACL-22
  6. Gaifman, Haim and Shapiro, Ehud, 1989 Fully abstract compositional semantics for logic programming 16th Annual ACM Symposium on Principles of Logic Programming
  7. Lassez, J.-L. and Maher, M. J., 1984 Closures and fairness in the semantics of programming logic Theoretical computer science 29
  8. Shuly Wintner, 1999 Modularized Context-Free Grammars MOL6 -- Sixth Meeting on Mathematics of Language
  9. Shuly Wintner, 1999 Compositional Semantics for Linguistic Formalisms Proceedings of ACL'99, the 37th Annual Meeting of the ACL


  • Acquaintance with linguistic formalisms
  • Mathematical maturity

back to top

instructions for authors
related events
  DFKI Language Technology Lab
German Research Center
for Artificial Intelligence
Language Technology Lab