Java Reference
In-Depth Information
Languages that support dynamic binding (such as some versions of LISP and some
functional programming languages) require us to keep the symbol table around at run-
time; here, eciency becomes even more important; hash tables are the usual solution. A
radical solution to dealing with the run-time name environments of function programming
languages is to do away the names altogether! David Turner [Turner, 1979] proposed a
practical scheme where all functional programs might be translated to constant combinators.
4.8 Attribute Grammars
Notice that as we recursively traverse our abstract syntax tree, we are making additional
passes over the syntax for enforcing type rules, which are not expressible using the context
free syntax. It would be nice if we could somehow attach type rules to our (BNF) grammar
rules. An attempt at this takes the form of attribute grammars.
Attribute grammars, first developed by Donald Knuth [Knuth, 1968] as a means of
formalizing the semantics of a context-free language, are useful in specifying the syntax and
semantics of a programming language. An attribute grammar can be used to specify the
context-sensitive aspects of a language, such as checking that a variable has been declared
before use and that the use of the variable is consistent with its declaration. Attribute
grammars can also be used to specify the operational semantics of a language by defining a
translation into machine-specific lower-level code.
In this section, we will first introduce attribute grammars through examples, then pro-
vide a formal definition for an attribute grammar, and finally present attribute grammars
for a couple of constructs in j--.
4.8.1 Examples
An attribute grammar may be informally defined as a context-free grammar that has been
extended to provide context sensitivity using a set of attributes, assignment of attribute
values, evaluation rules, and conditions. In a parse tree representing the input sentence
(source program), attribute grammars can pass values from a node to its parent, using a
synthesized attribute, or from a node to its child, using an inherited attribute. In addition
to passing values up or down the tree, the attribute values may be assigned, modified, and
checked at any node in the tree. We clarify these ideas using the following examples.
Let us try and write a grammar to recognize sentences of the form
a
n
b
n
c
n
. The sentences
aabbcc
and
abc
belong to this grammar, but the sentences
abbcc
and
aac
do not. Consider
the following context-free grammar (from [Slonneger and Kurtz, 1995]:)
letterSequence ::= aSequence bSequence cSequence
aSequence ::=
a
j aSequence
a
bSequence ::=
b
j aSequence
b
cSequence ::=
c
j aSequence
c
It is easily seen that the above grammar, in addition to generating the acceptable strings
such as
aabbcc
, also generates the unacceptable strings such as
abbcc
. It is impossible to
Search WWH ::
Custom Search