GATE CS 2003 Q18 — Syntax-directed Translation

In bottom-up parsing (such as LR parsing), the parse tree is constructed from the leaves up to the root. This makes the evaluation of synthesized attributes straightforward because the attributes of the children are already computed and available on the parser stack when a reduction occurs.

However, inherited attributes depend on parent or left-sibling attributes. Since parent nodes do not exist yet on the stack during bottom-up traversal, evaluating arbitrary inherited attributes is generally not possible.

To evaluate inherited attributes during bottom-up parsing, the Syntax-Directed Definition (SDD) must be restricted:

• An SDD is L-attributed if every inherited attribute of a symbol $X_j$ on the right-hand side of a production $A \to X_1 X_2 \dots X_n$ depends only on:
  1. The inherited attributes of the head $A$.
  2. The attributes (either synthesized or inherited) of the symbols $X_1, X_2, \dots, X_{j-1}$ to the left of $X_j$.
• If the SDD is L-attributed, we can systematically convert the grammar by inserting marker non-terminals (dummy actions) to compute these inherited attributes and place them on the stack just before the symbol is processed.

Thus, inherited attributes can be evaluated in a bottom-up parser only if the definition is L-attributed.