Synthesized attribute can be easily simulated by a
2009
Synthesized attribute can be easily simulated by a
Answer: C. LR grammar — Concept: In syntax-directed translation, a synthesized attribute at a grammar-tree node is computed only from the attribute values already present at that…
- A.
LL grammar
- B.
Ambiguous grammar
- C.
LR grammar
- D.
None of the above
Attempted by 51 students.
Show answer & explanation
Correct answer: C
Concept: In syntax-directed translation, a synthesized attribute at a grammar-tree node is computed only from the attribute values already present at that node's children (plus the node's own local information); an SDT that uses only synthesized attributes is called S-attributed. The defining property of an S-attributed definition is that it can be evaluated in a single bottom-up sweep of the parse tree, exactly in step with the reductions a bottom-up (LR / shift-reduce) parser performs.
Identify the direction of attribute flow the stem is asking about: a synthesized attribute is computed strictly from values already available at a node's children, i.e. a child-to-parent flow.
Recall how an LR (bottom-up, shift-reduce) parser processes input: it shifts symbols onto a stack and reduces a production A -> X1 X2 ... Xn to A only after every Xi is already fully parsed and sitting on the stack with its attribute values computed.
At exactly that reduction step, every value a synthesized attribute of A needs (the attributes of X1 ... Xn) is already available on the stack, so the parser can compute A's synthesized attribute in the very same action that performs the reduction, with no separate tree-building pass required.
Contrast this with an LL (top-down, recursive-descent) parser: it expands A into X1 X2 ... Xn before any Xi has itself been parsed, so a value meant to flow child-to-parent is not yet available at expansion time; reproducing a synthesized attribute this way needs extra bookkeeping (deferred evaluation once the whole subtree finishes), not a direct one-pass fit.
Ambiguity is an unrelated grammar property: a grammar is ambiguous when some string it generates has more than one distinct parse tree. This says nothing about the order in which a parser visits a node relative to its children, so it has no bearing on how synthesized attributes are evaluated.
Cross-check: this matches the standard classification of syntax-directed definitions -- an S-attributed definition (synthesized attributes only) pairs naturally with bottom-up (LR) parsing, while an L-attributed definition (which can add left-to-right inherited attributes) is the one that pairs with top-down (LL) parsing. Since the stem is exclusively about synthesized attributes, the bottom-up pairing applies, confirming LR grammar as the correct choice among the given options.