Slide 8.8: Reduction rules for integer arithmetic expressions (cont.)

Reduction Rules for Integer Expressions (Cont.)

Let us see how these reduction rules can be applied to a complicated expression to derive its value. Take, for example, the expression 2 * (3 + 4) – 5. To show each reduction step clearly, we surround each character with quotes within the reduction steps. We first reduce the expression 3 + 4 as follows:

     '3' '+' '4'
   ⇒ 3 '+' '4'                      (Rules 1 and 7)
   ⇒ 3 '+' 4                        (Rules 1 and 10)
   ⇒ 3 + 4 = 7                      (Rule 3)

Hence by Rule 14, we have '3' '+' '4' ⇒ 7. Continuing,

     '(' '3' '+' '4' ')'
   ⇒ '(' 7 ')'                      (Rule 13)
   ⇒ 7                              (Rule 6)

Now we can reduce the expression 2 * (3 + 4) as follows:

     '2' '*' '(' '3' '+' '4' ')'
   ⇒ 2 '*' '(' '3' '+' '4' ')'      (Rules 1 and 9)
   ⇒ 2 '*' 7                        (Rule 12)
   ⇒ 2 * 7 = 14                     (Rule 5)

And, finally,

     '2' '*' '(' '3' '+' '4' ')' '–' '5'
   ⇒ 14 '–' '5'                     (Rule 8)
   ⇒ 14 '–' 5                       (Rules 1 and 11)
   ⇒ 14 – 5 = 9                     (Rule 4)

We have shown that the reduction machine can reduce the expression 2 * (3 + 4) – 5 to 9, which is the value of the expression.