Compiler Design

Attribute Grammars / Worked Example: Expression Evaluation

PreviousNext

Worked Example: Expression Evaluation

Let us trace how an expression is parsed and evaluated using only synthesized attributes. We will use a standard arithmetic grammar with a synthesized attribute .val.

Grammar & Semantic Rules

Production RuleSemantic Rule (Synthesized .val)
L → E \nL.val = E.val; print(L.val)
E → E_1 + TE.val = E_1.val + T.val
E → TE.val = T.val
T → T_1 * FT.val = T_1.val * F.val
T → FT.val = F.val
F → ( E )F.val = E.val
F → digitF.val = digit.lexval

Step-by-Step Trace of: 3 + 5 * 2

Here is how the compiler evaluates 3 + 5 * 2 during a bottom-up (postorder) traversal of the parse tree:

  1. Lexical Scan: Lexer yields the tokens:digit(3),+,digit(5),*,digit(2).
  2. First leaf reduction: F → digit(3).
    Calculation: F.val = digit.lexval = 3.
  3. Promote term: T → F.
    Calculation: T.val = F.val = 3.
  4. Initialize expression: E → T.
    Calculation: E.val = T.val = 3 (Left subtree completed).
  5. Second leaf reduction: F → digit(5).
    Calculation: F.val = 5.
  6. Promote second term: T_1 → F.
    Calculation: T_1.val = 5.
  7. Third leaf reduction: F → digit(2).
    Calculation: F.val = 2.
  8. Multiplication reduction: T → T_1 * F.
    Calculation: T.val = T_1.val * F.val = 5 * 2 = 10.
  9. Addition reduction: E → E_1 + T.
    Calculation: E.val = E_1.val + T.val = 3 + 10 = 13.
  10. Halting step: L → E \n.
    Calculation: L.val = 13, triggering the print action.

The annotated parse tree showing the values flowing upwards:

         L [val=13]
         |
      E [val=13]
     /   |   \
E [val=3] +   T [val=10]
   |         /   |   \
T [val=3] T [val=5] * F [val=2]
   |         |         |
F [val=3] F [val=5] digit [lexval=2]
   |         |
digit(3)  digit(5)
Back to Attribute GrammarsSyntax Directed Definitions (SDD)