Exercise 1.

Next: Exercise 2. Up: Quiz2 Previous: Guidelines.

Exercise 1.

We consider the following syntax-directed definition with nonterminals B and D, terminals 0 and 1 and attributes B.pos, B.val, D.pow and D.val.

Production	Semantic Rule
B $\longmapsto$ DB₁	B.pos := B₁.pos + 1
	B.val := B₁.val + D.val
	D.pow := B₁.pos
B $\longmapsto$ D	B.pos := 1
	B.val := D.val
	D.pow := 0
D $\longmapsto$ 0	D.val := 0
D $\longmapsto$ 1	D.val := 2^D.pow

Is the above syntax-directed definition L-attributed? Give a parse tree for w = 10. Then compute the attributes at each node.

Answer 1

**Figure 1:** The decorated parse tree for w = 10.
$\begin{figure}\centering\includegraphics[scale=.2]{binaryExpansionSDT.eps} \end{figure}$

$% latex2html id marker 781 \fbox{ \begin{minipage}{13 cm} No this is not an $L$-... ...for the attributes at each node of the parse tree for $w = 10$. \end{minipage}}$

Next: Exercise 2. Up: Quiz2 Previous: Guidelines.

Marc Moreno Maza
2004-12-02