MODULE - 4
Chapter 5
Syntax-Directed
Translation
This chapter develops the theme of Section 2.3: the translation of languages
guided by context-free grammars. The translation techniques in this chapter
will be applied in Chapter 6 to type checking and intermediate-code generation.
The techniques are also useful for implementing little languages for specialized
tasks; this chapter includes an example from typesetting.
We associate information with a language construct by attaching attributes
to the grammar symbol(s) representing the construct, as discussed in Sec-
tion 2.3.2. A syntax-directed de nition speci es the values of attributes by
associating semantic rules with the grammar productions. For example, an
in x-to-post x translator might have a production and rule
PRODUCTION SEMANTIC RULE (5.1)
E ! E1 + T E:code = E1 :code k T:code k 0 +0
This production has two nonterminals, E and T ; the subscript in E1 distin-
guishes the occurrence of E in the production body from the occurrence of E
as the head. Both E and T have a string-valued attribute code. The semantic
rule speci es that the string E:code is formed by concatenating E1 :code, T:code,
and the character 0 +0 . While the rule makes it explicit that the translation of
E is built up from the translations of E1 , T , and 0 +0 , it may be inecient to
implement the translation directly by manipulating strings.
From Section 2.3.5, a syntax-directed translation scheme embeds program
fragments called semantic actions within production bodies, as in
E ! E1 + T f print 0 +0 g (5.2)
By convention, semantic actions are enclosed within curly braces. (If curly
braces occur as grammar symbols, we enclose them within single quotes, as in
303
, 304 CHAPTER 5. SYNTAX-DIRECTED TRANSLATION
0 f0 and 0 g0.) The position of a semantic action in a production body determines
the order in which the action is executed. In production (5.2), the action
occurs at the end, after all the grammar symbols; in general, semantic actions
may occur at any position in a production body.
Between the two notations, syntax-directed de nitions can be more readable,
and hence more useful for speci cations. However, translation schemes can be
more ecient, and hence more useful for implementations.
The most general approach to syntax-directed translation is to construct a
parse tree or a syntax tree, and then to compute the values of attributes at the
nodes of the tree by visiting the nodes of the tree. In many cases, translation
can be done during parsing, without building an explicit tree. We shall therefore
study a class of syntax-directed translations called \L-attributed translations"
(L for left-to-right), which encompass virtually all translations that can be
performed during parsing. We also study a smaller class, called \S-attributed
translations" (S for synthesized), which can be performed easily in connection
with a bottom-up parse.
5.1 Syntax-Directed De nitions
A syntax-directed de nition (SDD) is a context-free grammar together with
attributes and rules. Attributes are associated with grammar symbols and rules
are associated with productions. If X is a symbol and a is one of its attributes,
then we write X:a to denote the value of a at a particular parse-tree node
labeled X . If we implement the nodes of the parse tree by records or objects,
then the attributes of X can be implemented by data elds in the records that
represent the nodes for X . Attributes may be of any kind: numbers, types, table
references, or strings, for instance. The strings may even be long sequences of
code, say code in the intermediate language used by a compiler.
5.1.1 Inherited and Synthesized Attributes
We shall deal with two kinds of attributes for nonterminals:
1. A synthesized attribute for a nonterminal A at a parse-tree node N is
de ned by a semantic rule associated with the production at N . Note
that the production must have A as its head. A synthesized attribute at
node N is de ned only in terms of attribute values at the children of N
and at N itself.
2. An inherited attribute for a nonterminal B at a parse-tree node N is
de ned by a semantic rule associated with the production at the parent
of N . Note that the production must have B as a symbol in its body. An
inherited attribute at node N is de ned only in terms of attribute values
at N 's parent, N itself, and N 's siblings.
Chapter 5
Syntax-Directed
Translation
This chapter develops the theme of Section 2.3: the translation of languages
guided by context-free grammars. The translation techniques in this chapter
will be applied in Chapter 6 to type checking and intermediate-code generation.
The techniques are also useful for implementing little languages for specialized
tasks; this chapter includes an example from typesetting.
We associate information with a language construct by attaching attributes
to the grammar symbol(s) representing the construct, as discussed in Sec-
tion 2.3.2. A syntax-directed de nition speci es the values of attributes by
associating semantic rules with the grammar productions. For example, an
in x-to-post x translator might have a production and rule
PRODUCTION SEMANTIC RULE (5.1)
E ! E1 + T E:code = E1 :code k T:code k 0 +0
This production has two nonterminals, E and T ; the subscript in E1 distin-
guishes the occurrence of E in the production body from the occurrence of E
as the head. Both E and T have a string-valued attribute code. The semantic
rule speci es that the string E:code is formed by concatenating E1 :code, T:code,
and the character 0 +0 . While the rule makes it explicit that the translation of
E is built up from the translations of E1 , T , and 0 +0 , it may be inecient to
implement the translation directly by manipulating strings.
From Section 2.3.5, a syntax-directed translation scheme embeds program
fragments called semantic actions within production bodies, as in
E ! E1 + T f print 0 +0 g (5.2)
By convention, semantic actions are enclosed within curly braces. (If curly
braces occur as grammar symbols, we enclose them within single quotes, as in
303
, 304 CHAPTER 5. SYNTAX-DIRECTED TRANSLATION
0 f0 and 0 g0.) The position of a semantic action in a production body determines
the order in which the action is executed. In production (5.2), the action
occurs at the end, after all the grammar symbols; in general, semantic actions
may occur at any position in a production body.
Between the two notations, syntax-directed de nitions can be more readable,
and hence more useful for speci cations. However, translation schemes can be
more ecient, and hence more useful for implementations.
The most general approach to syntax-directed translation is to construct a
parse tree or a syntax tree, and then to compute the values of attributes at the
nodes of the tree by visiting the nodes of the tree. In many cases, translation
can be done during parsing, without building an explicit tree. We shall therefore
study a class of syntax-directed translations called \L-attributed translations"
(L for left-to-right), which encompass virtually all translations that can be
performed during parsing. We also study a smaller class, called \S-attributed
translations" (S for synthesized), which can be performed easily in connection
with a bottom-up parse.
5.1 Syntax-Directed De nitions
A syntax-directed de nition (SDD) is a context-free grammar together with
attributes and rules. Attributes are associated with grammar symbols and rules
are associated with productions. If X is a symbol and a is one of its attributes,
then we write X:a to denote the value of a at a particular parse-tree node
labeled X . If we implement the nodes of the parse tree by records or objects,
then the attributes of X can be implemented by data elds in the records that
represent the nodes for X . Attributes may be of any kind: numbers, types, table
references, or strings, for instance. The strings may even be long sequences of
code, say code in the intermediate language used by a compiler.
5.1.1 Inherited and Synthesized Attributes
We shall deal with two kinds of attributes for nonterminals:
1. A synthesized attribute for a nonterminal A at a parse-tree node N is
de ned by a semantic rule associated with the production at N . Note
that the production must have A as its head. A synthesized attribute at
node N is de ned only in terms of attribute values at the children of N
and at N itself.
2. An inherited attribute for a nonterminal B at a parse-tree node N is
de ned by a semantic rule associated with the production at the parent
of N . Note that the production must have B as a symbol in its body. An
inherited attribute at node N is de ned only in terms of attribute values
at N 's parent, N itself, and N 's siblings.
