A survey of adaptable grammars

Henning Christiansen
Department of Computer Science
Roskilde University, P.O.Box 260, DK-4000 Roskilde, Denmark

This paper is a comment on two recent contributions to Sigplan Notices. In his paper, "The static semantics file", no. 25/4, Brian Meek discusses the relevance of the notion of "static semantics". The relation between a variable's declaration and the restrictions on its use, for example, is usually classified as static semantics. Meek finds the designation rather misleading since it is applied for concepts concerned with context-dependent syntax. The term "semantics" should properly only be used for aspects that have to do with real meaning, e.g., the association between program statements and their intended computation. Here I will show that this distinction between syntax and semantics can be made clearer using grammars which adapt themselves to the current program contexts. For example, declarations of new items can be described by adding new rules to the grammar and thus, within a given scope of a program, the set of valid phrases can be derived freely by means of the current set of grammar rules. This way, we get rid of some of those - often quite complicated - context constraints that are called static semantics. In no. 25/5, Boris Buhrsteyn presents an article, "On the modification of the formal grammar at parse time". The author suggests an approach to language recognition in which declarations of, say, variables result in an adaptation of the grammar as outlined above and in turn in an adjustment of the parsing tables. The idea can be traced back to the early sixties, and over the years several proposals for adaptable grammar formalisms have been suggested. In the following, I complement Buhrsteyn's article giving an overview of the area and describe the advantages and disadvantages of describing programming language syntax this way. Section 1 below describes the principle of adaptable grammars and how it can be used to characterize various context-dependent, syntactic aspects. The notation used will be my own generative clause grammars which are adaptable versions of Prolog's definite clause grammars. The formal definition is given in appendix A, appendix B shows some examples. Section 2 provides a short historic survey of approaches to extensible or adaptable grammar formalisms. The more problematic issues of the approach and how they have been solved or not solved in various formalisms are discussed in section 3. Visibility rules and recursive declarations represent syntactic aspects that are difficult to handle this way. Chapter 4 provides for a summary and a discussion of the distinction between syntax and semantics.

SIGPLAN Notices, 25/11, pp. 35-44, 1990.
See pdf, dvi, postscript.