4. (20pt) Consider the C-style switch statement.

(1) (15pt) Write an S-attributed LL(1) grammar that generates C-style switch statements and check that all labels of the arms of the switch instructions are distinct. In order to do that, the starting nonterminal, S, will have an attribute dup that will store all the duplicate values. There are no duplicate values on the arms of the switch statement if and only if S.dup = . Therefore, your grammar is required to eventually compute the attribute dup of S. For simplicity, assume that the conditional expression of the statement and the constant ex- pressions labelling the arms are expr tokens and that each arm has a statement that is a stmt token; the break and default parts are omitted as their role is irrelevant for our problem. Each expr has an attribute val provided by the scanner that gives the value of the expression. Explain why your grammar works as required. For LL(1), you can use jflap to compute the parse table and show there is no conflict; include the jflap answer (whole window) in your answer.

(2) (5pt) Using this attributed grammar, draw a decorated parse tree for the following switch instruction:

switch ( expr ) {

case 1 :

case 2 :

case 3 : stmt

case 2 : stmt

case 2 :

case 3 : stmt }

Show all attributes and arrows indicated what attributes are used to compute each value.