Compiler Design

Syntax Directed Translation (SDT) / SDT Trace: Infix to Postfix

PreviousNext

SDT Trace: Infix to Postfix

Let us trace how an infix expression is converted into postfix notation during syntax analysis using embedded actions.

SDT Rules for Postfix Translation

ProductionEmbedded Action
E → E_1 + T{ print('+') }
E → Tno action
T → T_1 * F{ print('*') }
T → Fno action
F → ( E )no action
F → id{ print(id.name) }
F → num{ print(num.val) }

Step-by-Step Execution for: a + b * c

Below is the step-by-step reduction trace demonstrating when each print statement is executed:

  1. First reduction: F → id(a).
    Action executed: print(a).
    Output so far: a.
  2. Promote to term: T → F (No action).
  3. Promote to expression: E → T (No action).
  4. Second reduction: F → id(b).
    Action executed: print(b).
    Output so far: a b.
  5. Promote to left factor: T_1 → F (No action).
  6. Third reduction: F → id(c).
    Action executed: print(c).
    Output so far: a b c.
  7. Product reduction: T → T_1 * F.
    Action executed: print(*).
    Output so far: a b c *.
  8. Sum reduction: E → E_1 + T.
    Action executed: print(+).
    Final Output: a b c * +.

The numbered circles indicate the order in which nodes are reduced and their semantic actions are triggered:

              E [8: print('+')]
             / | \
            E  +  T [7: print('*')]
            |    / | \
            T   T  *  F [6: print('c')]
            |   |     |
            F   F     id(c)
            |   |
          id(a) id(b)
          [1:a] [4:b]
          
Reductions occur in this order:
1. F -> id(a)       [Prints 'a']
2. T -> F
3. E -> T
4. F -> id(b)       [Prints 'b']
5. T -> F
6. F -> id(c)       [Prints 'c']
7. T -> T * F       [Prints '*']
8. E -> E + T       [Prints '+']
Back to Syntax Directed Translation (SDT)S-Attributed & L-Attributed Definitions