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.