Synthesized Attributes for Evaluating Arithmetic Expressions (E→E+T|T, T→T*F|F)

We are given the expression grammar:

A standard attribute-grammar solution is to attach a synthesized numeric attribute to each nonterminal—typically $E.val$, $T.val$, and $F.val$—so the value of an expression is computed bottom-up in the parse tree. Synthesized attributes are computed from children and flow upward. 2

Key idea: represent the usual operator precedence/associativity:

• $*$ binds tighter than $+$ because it is defined at the $T$ level, not at $E$.
• Left recursion ($E\to E+T$, $T\to T*F$) corresponds to left-associative chaining in the parse tree.

Attribute grammar (S-attributed)

Use a single synthesized attribute:

• val on each nonterminal $E, T$.
• lexval on terminal digit.

Semantic rules for each production:

For $E$

1. $E \to E + T$
   • $E.val := E_1.val + T.val$
2. $E \to T$
   • $E.val := T.val$

For $T$

1. $T \to T * F$
   • $T.val := T_1.val * F.val$
2. $T \to F$
   • $T.val := F.val$

For $F$

1. $F \to digit$
   • $F.val := digit.lexval$

This is an S-attributed translation scheme: every attribute on the LHS depends only on RHS children attributes, so it can be evaluated bottom-up. 2

Annotated syntax tree / parse tree (with computed attributes)

One syntax-tree shape that matches the grammar’s precedence is:

• Root: $E$
• Root production: $E \to E + T$
• Left child: $E \to T \to F \to digit(3)$
• Right child: $T \to T * F$
  • left of $*$: $T \to F \to digit(5)$
  • right of $*$: $F \to digit(2)$

Bottom-up attribute computation corresponds exactly to:

• $F.val(3)=3,\;F.val(5)=5,\;F.val(2)=2$
• $T.val(5*2)=5*2=10$
• $E.val(3+(5*2))=3+10=13$

Synthesized attributes flow upward from $F$ to $T$ to $E$. 2