Syntax Directed Translation Questions and Answers

Answer: C

The edges record which values must be available before which others can be computed. Any topological sort of the graph is a legal evaluation order. Drawing the graph for a small tree is the quickest way to see whether a definition is workable.

Answer: D

Correct answer: the attributes cannot be evaluated in any order at all

A cycle means each attribute in it needs one of the others before it can be computed, so no ordering exists - the definition is circular and not merely slow. It is a defect in the definition rather than in the grammar, so rewriting the grammar is not the remedy.

Answer: A

Correct answer: False

Testing an arbitrary definition for circularity is exponential in the worst case, which is why compilers do not attempt it. They restrict themselves to the S-attributed and L-attributed classes instead, both of which are non-circular by construction and evaluable in a known order.

Answer: B

Correct answer: a parse tree in which every node carries its attribute values

The annotated tree is the parse tree with the attribute values filled in, and it is the conceptual result of applying a syntax directed definition. It need not be built in practice - for S- and L-attributed definitions the values can be computed during the parse - but it is the object the definition describes.

Answer: C

Correct answer: places the semantic actions at explicit positions in the right side

A definition says what the relationships are; a scheme says when the code runs, by writing the actions between the grammar symbols. That commitment to an order is what makes a scheme directly implementable, and what makes it possible to write one that a given parser cannot execute.

Answer: D

By the time the action runs, every symbol on the right has been processed and its attributes are available. This is precisely the placement an S-attributed definition uses throughout. Nothing else is permitted if the definition is to remain S-attributed.

Answer: A

The value must exist when the parser begins that symbol. Placing the action after it would compute a value nobody could have used, which is why the L-attributed restriction matters here. The restriction is exactly what makes valid placement always possible.

Answer: B

Deciding the information comes first, its direction of flow second, and the rules third. Action placement is the final step and is constrained by the classification already made. Getting the classification wrong is discovered at this point, uncomfortably late.

Answer: C

Each grammar symbol pushed has a corresponding value. A reduction pops the values of the right side, computes the value of the left side and pushes it, which realises the definition directly. The two stacks move in step, which keeps the implementation straightforward.

Answer: D

A tree can be walked in whatever order the dependencies demand, so the mixture presents no difficulty at all. A strictly one pass translator has to force the definition into one of the restricted classes or resort to markers and backpatching, which is why compilers that optimise almost always build the tree.