Syntax Directed Translation Questions and Answers

Answer: C

Attributes are chosen by the designer and can hold anything. Their design is the real work; the mechanism of evaluation is mechanical once the flows have been settled. Choosing the wrong attributes is far harder to recover from than a coding error.

Answer: D

The restriction buys a guarantee of cheap evaluation. It is a limitation in principle, but in practice almost every translation a compiler needs can be written within it. The exceptions are unusual enough to be worth restructuring the grammar for.

Answer: C

The output is 2 3 1.

The input aab is derived as \(S \Rightarrow aA \Rightarrow aSb \Rightarrow aab\). A bottom-up parser performs the reductions in the reverse of this rightmost derivation, printing as each rule is reduced:

1. Shift a, shift a; reduce the second a to \(S\) by \(S \rightarrow a\): print 2.
2. Shift b; reduce \(Sb\) to \(A\) by \(A \rightarrow Sb\): print 3.
3. Reduce \(aA\) to \(S\) by \(S \rightarrow aA\): print 1.

1 3 2 is the top-down (preorder) order of the same rules, and 2 2 3 would need two reductions by \(S \rightarrow a\), but the first a is never reduced on its own. The input is in the language, so there is no syntax error.

Answer: A

The value computed is 45.

Parse 'MMLK' as \(S \to DHTU\) with D = MM, H = L, T = \(\epsilon\) and U = K, then evaluate bottom-up:

\[ \begin{aligned} D &= 5 + (5 + (-5)) = 5 \\ H &= 5 \times 10 + (-10) = 40 \\ T &= -5,\quad U = 5 \\ S &= 5 + 40 - 5 + 5 = 45 \end{aligned} \]

The \(\epsilon\) productions contribute negative values that are easy to forget: dropping the −5 for the empty T gives 50, and dropping the −5 at the end of D's chain as well gives 55.

Answer: C

Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed.

An S-attributed definition uses only synthesized attributes. An L-attributed one may also use inherited attributes, but each child's inherited attribute may depend only on the parent's inherited attributes and on its left siblings.

• Rule 1: A.i = B.i makes A depend on B, its right sibling. That breaks the L-attributed condition, and B.i = R.i - 1 is inherited, so the rule is not S-attributed either.
• Rule 2: D.i = C.i + 2 is inherited from D's left sibling C, which is allowed in an L-attributed definition, and P.i is synthesized. Inherited attributes mean it is not S-attributed.
• Rule 3: Q.i = E.i + F.i is a synthesized attribute only, so it is S-attributed, and every S-attributed rule is also L-attributed.