Algorithms for Compiler Design: SWITCH/CASE

To capture the syntactic structure of the switch statement, we add the following productions to the grammar. Here, break is assumed to be a part of statement that is derivable from a nonterminal S.

S        → switch E { caselist}
caselist → caselist case V : S
caselist → case V: S
caselist → default: S
caselist → caselist default: S

A switch statement is comprised of two components: an expression E, which is used to select a particular case from the list of cases; and a caselist, which is a list of n number of cases, each of which corresponds to one of the possible values of the expression E, perhaps including a default case.

Note�

A case statement can be implemented in a variety of different ways. If the number of cases is not too great, then a case statement can be implemented by generating a sequence of conditional jumps, each of which tests for an individual value and transfers to the code for the corresponding statement. If the number of cases is large, then it is more efficient to construct a hash table for the case values with the labels of the various statements as entries.

A syntax-directed translation scheme that translates a case statement into a sequence of conditional jumps, each of which tests for an individual value and transfers to the code for the corresponding statement, is considered below. We begin with a typical switch statement:

switch (E)
  {
    case V1: S1
    case V2: S2
    .
    .
    .
    case Vn:Sn
  }

The generated three-address that is required for the statement is shown in Figure 1. Here, next is the label of the code for the statement that comes next in the switch statement execution order.

Figure 1: A switch/case three-address translation.

Therefore, switch statement translation involves generating an unconditional jump after the code of every S1, S2,…, Sn statement in order to transfer control to the next element of the switch statement, as well as to remember the code start of S1, S2,…, Sn, and to generate the conditional jumps. Each of these jumps tests for an individual value and transfers to the code for the corresponding statement. This requires introducing nullable nonterminals before S1, as shown in Figure 2.

Figure 2: Nullable nonterminals are introduced into a switch statement translation.

EXAMPLE 1

Consider the following switch statement:

switch (i + j )
  {
    case 1: x = y + z
    default: p = q + r
    case 2: u = v + w
  }

The above translation scheme translates into the following three-address code, which is also shown in Figure 3:

Figure 3: Contents of queue during the translation.

EXAMPLE 2

Using the above translation scheme translates the following switch statement:

switch (a+b)
  {
           case 2: { x = y; break; }
           case 5: {switch x
                   {
                           case 0: { a = b + 1; break; }
                           case 1: { a = b + 3; break; }
                           default: { a = 2; break; }
                   }
                   break;
           case 9: { x = y - 1; break; }
           default: { a = 2; break; }
  }

The three address code is:

1. t1 = a + b

2. goto(23)

3. x = y

4. goto NEXT

5. goto(14)

6. t3 = b + 1

7. a = t3

8. goto NEXT

9. t4 = b + 3

10. a = t4

11. goto NEXT

12. a = 2

13. goto NEXT

14. if x = 0 goto(6)

15. if x = 1 goto(9)

16. goto(12)

17. goto NEXT

18. t5 = y − 1

19. x = t5

20. goto NEXT

21. a = 2

22. goto NEXT

23. if t1 = 2 goto(3)

24. if t1 = 5 goto(5)

25. if t1 = 9 goto(18)

26. goto(21)