Java Reference
In-Depth Information
However, not all aspects of well-formed programs can be described by context-
free syntax. For example, CFGss cannot specify type compatibility and scoping
rules. For example, a programming language may specify that a=b+c is illegal
if any of the variables are undeclared or if b or c is of type Boolean.
Because of the limitations of CFGss, the semantics of a programming
language are commonly divided into two classes:
•
Static semantics
•
Runtime semantics
The
static semantics
of a language provide a set of rules that specify which
syntactically legal programs are actually valid. Such rules typically require that
all identifiers be declared, that operators and operands be type-compatible,
and that procedures be called with the proper number of parameters. The
common thread through all of these rules is that they cannot be expressed
with a CFGs. Thus static semantics
augment
context-free specifications and
complete the definition of valid programs.
Static semantics can be specified formally or informally. The prose descrip-
tions found in most programming language specifications are informal. They
tend to be relatively compact and easy to read, but often they are imprecise.
Formal specifications can be expressed using any of a variety of notations.
For example,
attribute grammars
[Knu68] can formalize many of the semantic
checks found in compilers. The following rewriting rule, called a
production
,
specifies that an expression, denoted by E, can be rewritten into an expression
E plus a term T:
E
→
E+T
In an attribute grammar, this production might be augmented with a type
attribute for E and T and a predicate testing for type compatibility, such as
E
result
→
E
v
1
+T
v
2
if
v
1
.
type
=
numeric
and
v
2
.
type
=
numeric
then
result
.
type
←
numeric
else call
error
()
Attribute grammars are a reasonable blend of formality and readability, but
they can be rather verbose and tedious. Most compiler-writing systems do
