Switch-Statements

Switch-Statements

1 Translation of Switch-Statements

 2 Syntax-Directed Translation of Switch-Statements

 3 Exercises for Section 6.8

The "switch" or "case" statement is available in a variety of languages. Our switch-statement syntax is shown in Fig. 6.48. There is a selector expression E, which is to be evaluated, followed by n constant values Vi, V₂, • • • ,V_n that the expression might take, perhaps including a default "value," which always matches the expression if no other value does.

1. Translation of Switch-Statements

The intended translation of a switch is code to:

   Evaluate the expression E.

Find the value V} in the list of cases that is the same as the value of the expression. Recall that the default value matches the expression if none of the values explicitly mentioned in cases does.

3. Execute the statement Sj associated with the value found.

Step (2) is an n-way branch, which can be implemented in one of several ways. If the number of cases is small, say 10 at most, then it is reasonable to use a sequence of conditional jumps, each of which tests for an individual value and transfers to the code for the corresponding statement.

A compact way to implement this sequence of conditional jumps is to create a table of pairs, each pair consisting of a value and a label for the corresponding statement's code. The value of the expression itself, paired with the label for the default statement is placed at the end of the table at run time. A simple loop generated by the compiler compares the value of the expression with each value in the table, being assured that if no other match is found, the last (default) entry is sure to match.

If the number of values exceeds 10 or so, it is more efficient to construct a hash table for the values, with the labels of the various statements as entries. If no entry for the value possessed by the switch expression is found, a jump to the default statement is generated.

There is a common special case that can be implemented even more effi-ciently than by an n-way branch. If the values all lie in some small range, say min to max, and the number of different values is a reasonable fraction of max — min, then we can construct an array of max — min "buckets," where bucket j — min contains the label of the statement with value j; any bucket that would otherwise remain unfilled contains the default label.

To perform the switch, evaluate the expression to obtain the value j; check that it is in the range min to max and transfer indirectly to the table entry at offset j — min. For example, if the expression is of type character, a table of, say, 128 entries (depending on the character set) may be created and transferred through with no range testing.

2. Syntax-Directed Translation of Switch-Statements

The intermediate code in Fig. 6.49 is a convenient translation of the switch-statement in Fig. 6.48. The tests all appear at the end so that a simple code generator can recognize the multiway branch and generate efficient code for it, using the most appropriate implementation suggested at the beginning of this section.

The more straightforward sequence shown in Fig. 6.50 would require the compiler to do extensive analysis to find the most efficient implementation. Note that it is inconvenient in a one-pass compiler to place the branching statements at the beginning, because the compiler could not then emit code for each of the statements Si as it saw them.

To translate into the form of Fig. 6.49, when we see the keyword switch, we generate two new labels test and next, and a new temporary t. Then, as we parse the expression E, we generate code to evaluate E into t. After processing E, we generate the jump goto test.

Then, as we see each case keyword, we create a new label Li and enter it into the symbol table. We place in a queue, used only to store cases, a value-label pair consisting of the value Vi of the case constant and Li (or a pointer to the symbol-table entry for Li). We process each statement case Vi: Si by emitting the label Li attached to the code for Si, followed by the jump goto next.

When the end of the switch is found, we are ready to generate the code for the n-way branch. Reading the queue of value-label pairs, we can generate a sequence of three-address statements of the form shown in Fig. 6.51. There, t is the temporary holding the value of the selector expression E, and h_n is the label for the default statement.

The case t Vi Li instruction is a synonym for if t = Vi goto Li in Fig. 6.49, but the case instruction is easier for the final code generator to detect as a candidate for special treatment. At the code-generation phase, these sequences of case statements can be translated into an n-way branch of the most efficient type, depending on how many there are and whether the values fall into a small range.

3. Exercises for Section 6.8

Exercise 6.8.1 :  In order to translate a switch-statement into a sequence of case-statements as in Fig. 6.51, the translator needs to create the list of value label pairs, as it processes the source code for the switch. We can do so, using an additional translation that accumulates just the pairs. Sketch a syntax-direction definition that produces the list of pairs, while also emitting code for the statements Si that are the actions for each case.