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.

Answer: D

Type checking is normally done during Syntax Directed Translation.

Type checking is part of semantic analysis. In the Aho, Lam, Sethi and Ullman treatment, it is implemented as a syntax-directed translation: semantic rules attached to the grammar productions compute the types of expressions from the types of their parts and report mismatches as the parse tree is built.

Lexical analysis only groups characters into tokens and knows nothing about types. Syntax analysis checks that the token sequence fits the grammar, which says nothing about whether the operand types agree. Code generation comes after the checks and uses type information that is already established.

Answer: A

A type checker may prevent (i) and (ii) only.

Depending on the language, the static checker can reject an expression that uses a variable which has not been declared (i), since such a name has no type, and a function declared to return a value whose body can end without returning one (ii), as Java's compiler does.

Statement (iii), variables declared before they are used, describes correct programs, which the checker requires rather than prevents. Every option including (iii) is therefore wrong.

Answer: A

The process is called Binding of the attribute.

A binding is the association of an attribute, such as a type, value or storage location, with a programming language construct. Computing the attribute's value and attaching it to the construct is binding, and when it happens (language design, compile time, load time, run time) is its binding time.

A collision is a hashing term, chaining is a way of resolving collisions, and synthesising refers to how an attribute's value is derived in an attribute grammar, not to the act of associating it with the construct.

Answer: B

The answer is (i) and (iii) only.

A synthesized attribute is one computed by the semantic rules (attribute evaluation rules) of a production (i), and its value at a parse tree node is determined from the attribute values of that node's children (iii). Information flows upward, as in computing the value of an expression from its operands.

Statement (ii) describes an inherited attribute, whose value at a node depends on its parent and siblings. So options including (ii) are wrong.

Answer: D

This is Static type checking.

When a meaningless operation, such as adding a string to an array, is detected while the program is being compiled and the compiler rejects it, the type checking is done statically, before the program runs. C, Java and Pascal check types this way.

Dynamic type checking catches such errors only at run time. Strong typing means all type errors are caught, whether at compile time or run time, and weak typing means some are allowed through; neither term specifies detection by the compiler.