Must be viewed in IE 4.0 or later for greek symbols

Chapter 5 - Syntax-Directed Translation

Now that the syntactic structure of the program is known, we need to attach attributes to grammar symbols based on semantic rules associated with productions in the grammar. Further, syntax-directed translation is a means of translating the source code into the target code by inserting semantic actions into the grammar, thus, the grammar directs the translation.

We briefly discussed in chapter 2 the concept of syntax-directed definitions where each grammar symbol (node) has attribute values which can be things such as: value, address, type, ...

How do we associate the value of an attribute at a parse tree node? Answer: By the semantic rule associated with the production used at that node. Associated with each production is: (a) semantic rules for evaluating attributes (b) semantic rules for producing side-effects (e.g. updating a global variable).

We have discussed the concept of an annotated parse tree, where the process of computing the attribute values at each node is called "annotating" or "decorating" the parse tree.

Defn [Aho]: "In a syntax-directed definition, each grammar production A -> α has associated with it a set of semantic rules of the form b:= f(c1, c2, ..., ck) where f is a function and either: (a) b is a synthesized attribute of A and c1, c2, ...ck are attributes belonging to the grammar symbols of the production OR (b) b is an inherited attribute of one of the grammar symbols on the right side of the production and c1, c2, ... ck are attributes belonging to the grammar symbols of the production."

Note: An attribute grammar cannot have side-effects.

Problem: Construct a simple grammar that can represent unsigned numbers.

Answer: 

num -> num dig | dig
dig -> 0 | 1 | ... | 9
For now, we associate an attribute called val with each of the nonterminals which leaves us with the following attribute grammar: 
Production          Semantic Rules
num -> num1 dig     num.val = num1.val * 10 + dig.val
num -> dig          num.val = dig.val
dig -> 0            dig.val = 0
dig -> 1            dig.val = 1
...
dig -> 9            dig.val = 9

P#1: Draw the annotated parse tree for the number 345.

Q#1: Is val an inherited or synthesized attribute? Why?

Consider the following productions and semantic rules:
Production Semantic Rules
decl -> datatype list list.att = datatype.type
datatype -> int datatype.type := integer
datatype -> float datatype.type := real
list -> list1, id

list1.att := list.att

addST (id, list.att)

list -> id addST (id, list.att)

Q#2: What is L(decl)?

Q#3: Show the annotated parse tree for float a,b

Q#4: What are the attributes? For each attribute, state whether it is inherited or synthesized and why.

Douglas J. Ryan / ryandj@pacificu.edu