Syntax Directed Translation Questions and Answers

Answer: A

Until a reduction occurs the parser has committed to nothing, so there is no moment at which it could know that this particular action applies. Inserting an empty nonterminal manufactures a reduction at the wanted point, which is how generators implement such actions and also why they sometimes introduce conflicts.

Answer: B

Both are true and the reason gives the mechanism, and it is a common surprise in practice. A grammar that generated cleanly may report a conflict as soon as a mid-rule action is added, because the action silently introduces such a marker.

Answer: C

Correct answer: passing inherited attributes as parameters and returning synthesised ones

In recursive descent each nonterminal is a procedure, so the natural mechanism is already present: inherited attributes go in as parameters and synthesised ones come back as results. This is why recursive descent handles L-attributed definitions so comfortably, and it is the argument most often made for writing the parser by hand.

Answer: D

The L condition was chosen precisely so that this one traversal always works. Inherited attributes are ready when a subtree is entered and synthesised ones when it is left. Recursive descent performs exactly this traversal without being asked to.

Answer: A

Correct answer: restructuring the grammar so the information flows upward instead

Where a bottom up parser must evaluate a definition that uses inherited attributes, one remedy is to rewrite the grammar so the information is available from below - splitting a production so that the inherited value is synthesised by a marker nonterminal, for instance. The alternative is a marker with a mid-rule action, which amounts to the same thing.

Answer: B

Correct answer: an inherited attribute on L set from the synthesised type of T

The type is determined by T and needed by every name in L, so it must travel downward - an inherited attribute. Note that both directions appear in one rule: the type is first synthesised up from T, then inherited down into L. This is the standard example of an L-attributed definition.

Answer: C

Installing an entry is a side effect. Such rules are permitted in a translation scheme, but their order of execution then matters, which is why action placement must be specified precisely. A definition without placement leaves the behaviour of side effects undefined.

Answer: D

Correct answer: True

Rules may print output, enter names in the symbol table, emit code or report errors, and most practical translations depend on their doing so. The price is that the order of evaluation now matters in a way it does not for pure attribute computation, which is why the restricted classes are used.

Answer: A

Synthesised attributes depend only on children, so every edge points upward. A graph whose edges all point one way through a tree can never contain a cycle. This is why the S-attributed class needs no circularity test at all.

Answer: B

One edge runs from each right side attribute to the single left side attribute, giving three edges. The count would rise if the left side carried more than one attribute of its own. Counting edges is a useful check when a definition is first written down.