You do not need to submit anything for this homework. The homework is
designed for self-evaluation on the reading material. It is assumed that you know this material as you construct
your compiler and before your take-home final exam.
// Section 5.1 "Syntax-Directed Definitions" *
-----------------------
Grammar I. Figure 5.1
-----------------------
Production Rule Semantic Rule
=================== ======================
1. L -> E \n L.val = E.val // final result of the calc
2. E -> E_1 + T E.val = E_1.val + T.val
3. E -> T E.val = T.val
4. T -> T_1 * F T.val = T_1.val * F.val
5. T -> F T.val = F.val
6. F -> ( E ) F.val = E.val
7. F -> digit F.val = digit.lexval // returned by the lexer
// \n is the ENDLINE marker
01. For each attribute in Grammar I, state whether it is inherited or
synthesized. Is Grammar I L-attributed or S-attributed?
02. Using the SDD for Grammar I above, draw the annotated parse tree for
9 + 3 * (5 + 4) \n.
03. In what type of traversal is the parse tree for an expression in Grammar I
annotated? Note that the leaves of the tree are terminals and the internal
nodes are nonterminals. The root of the tree is the starting symbol.
04. Is Grammar I left or right associative for + op? To confirm your answer
draw a parse tree for input
9 + 3 + 5 \n
------------------------
Grammar II. Figure 5.4
------------------------
PRODUCTION SEMANTIC RULE
================= =================
1. T -> F T' T'.inh = F.val // inherited
T.val = T'.syn // synthesized
2. T' -> * F T'_1 T'_1.inh = T'.inh * F.val // inherited
T'.syn = T'_1.syn // synthesized
3. T' -> epsilon T'.syn = T'.inh // synthesized
4. F -> digit F.val = digit.lexval // intrinsic
05. Give the annotated Parse Tree for 3 * 5 using Grammar II.
Grammar II an L-attributed grammar. The * operation is right associative. One
possible decoration order for this parse tree is shown below. Assuming that the
intrinsic attribute digit.lexval is assigned by the lexical scanner, there are
seven attributes that need to be assigned. This is one possible order:
(7) T.val = T'.syn=15
/ \
(1) F.val=lexval=3 (2) T'.inh=F.val = 3
| (6) T'.syn=T'_1.syn=15
digit.lexval=3 / | \
* (3)F.val=lexval=5 (4)T'_1.inh=T'.inh*F.val=3*5
| (5)T'_1.syn = T'.inh = 15
digit.lexval=5 |
e
Think of the parse tree as a DAG (directed acyclic graph) with 9 vertices,
each vertex representing an attribute and each directed edge denoting the
"happens-before" quality. A correct decoration order such as 1,2,3,4,5,6,7
is then a topological sort of the DAG. Here are the constraints:
1 -> 2 # attribute 1 must be assigned before attribute 2
2 -> 4 # attribute 2 must be assigned before attribute 4
3 -> 4 # attribute 3 . . . before attribute 4
4 -> 5 # attribute 4 . . . before attribute 5
5 -> 6 # attribute 5 . . . before attribute 6
6 -> 7 # attribute 6 . . . before attribute 7
Here is the DAG based on the constraints:
3
|
v
1 -> 2 -> 4 -> 5 -> 6 -> 7
06. To generate a second acceptable ordering, apply a DFS to the above DAG. The
reverse pop order of the DFS is a possible topological sort. What is it?
07. Extend Grammar II to include the addition operator +, where + has lower
precedence than *, and parentheses (e.g. follow the syntax of Grammar I
but use inherited as well as synthesized attributes). Try to add as few
new rules as possible.
Original Grammar II:
PRODUCTION SEMANTIC RULE
=============== =================
T -> F T' T'.inh = F.val
T.val = T'.syn
T' -> * F T'_1 T'_1.inh = T'.inh * F.val
T'.syn = T'_1.syn
T' -> epsilon T'.syn = T'.inh
F -> digit F.val = digit.lexval
What is the new grammar?
08. For your new SDD from question 4, give an annoted parse tree for
9+3*5+4 (note that + associates to the right)
********************************************
* Section 5.2 "Evaluation Orders for SDDs" *
********************************************
----------------------
Grammar 3. Figure 5.8
----------------------
PRODUCTION SEMANTIC RULES
1) D -> TL L.inh = T.type
2) T -> int T.type = integer
3) T -> float T.type = float
4) L -> L_1,id L_1.inh = L.inh
addType(id.entry,L.inh)
5) L -> id addType(id.entry,L.inh)
The above attribute grammar is an SDD for simple type declarations.
09. Following the SDD of Grammar 3, give an annotated parse tree for
int a, b, c
10. Following the SDD of Grammar 3, provide a dependency graph based on the
parse tree for
int a, b,c
First arbitrarily label each attribute with a unique vertex letter. Since
T.type at vertex A is an intrinsic attribute assigned by the scanner before
parsing begins you can omit it from the DAG without a problem.
11. Next, construct a DAG where each labeled node is a vertex and the edges
denote the happens-before relationship.
12. Give all possible topological sorts for the dependency graph in question 7.
13. Assume some attribute grammar with production A -> BCD, where each
nonterminal has a synthesized attribute s and an inherited attribute i.
For each of the rules below, state whether the rule is consistent with an
S-attributed definition, an L-attributed definition, or neither.
a) A.s = B.s + C.s
b) D.i = C.s + B.s
c) D.i = A.s
d) C.i = D.s
To answer this question it helps to see the AG visually as shown here:
A.i
A.s
/ | \
B.i C.i D.i
B.s C.s D.s