## Lexical analysis

Describe a lexical analyzer that recognizes a sequence of the following tokens using the longest
match rule: , , , , , .

It should also skip whitespace characters between the tokens. (Denote the whitespace characters by the _ (underscore) symbol.)

As an example, consider the string . It should give the token stream ,,,,

- Draw an automaton which accepts the tokens above, optionally followed by white spaces. Use one different accepting state for each token.

## Parsing

Let's consider a grammar for expressions where we want to make the multiplication sign optional.

ex ::= ex + ex | ex * ex | ex _ ex | ex / ex | ( ex ) | ID | INTLITERAL

The underscore denotes whitespace.

- Find a LL(1) grammar recognizing the same language.
- Using your grammar, draw the parse tree for the following expression: 3 * x - z _ 2
- Create the LL(1) parsing table.

## Type checking

If the following programs type-check according to the rules given in the course, give the corresponding type derivation tree, otherwise give a partial tree that shows where it doesn't work

class A {} class B extends A {} class Test { val array: Array[A] = new Array[B](2) array(0) = new A array(0) = new B }

class Test { class A {} class B extends A {} class C extends B {} def func(x: B=>B): A val y: A=>C val z = func(y) }

## Code generation

Translate the following code into bytecode using the techniques seen in class:

boolean b; int f(int x, int y, int z) { while ((!b && (x > 2*(y+z))) || (x < 2*y +z)) { x = x +3; } return x; }

## Data-flow analysis

Draw the control-flow graph for the following program.

var x = 2 var y = input() if (x == y) { do { y = y + 1 x = x + y + 3 } while (y < 4) } else if (y <= -1 && y >= -7) { y = y * y } else { y = x - 3 } val z = x/y

Assume that the ranges that the integers can take are [-128, 127] for simplicity, i.e. all intervals within this range are allowed, for instance [-1, 3]. The function input() every time returns a possibly different integer in [-128, 127], and this integer is not known at compile time.

Run range analysis that maintains an interval for x and y at each program point in the control flow graph. Give the intervals for each node in the control-flow graph obtained after the analysis.

What are the values of all variables at the last assignment?

and the final ranges are:

x y 1: bottom bottom 2: [2, 2] [-128, 127] 3: [2, 2] [-128, 127] 4: [2, 127] [2, 3] 5: [2, 127] [3, 4] 6: [8, 127] [3, 4] 7: [2, 2] [-128, 127] 8: [2, 2] [-128, -1] 9: [2, 2] [-7, -1] 10: [2, 2] [-128, 127] 11: [2, 127] [-1, 49] 12: [2, 127] [-1, 49] z: T

Thus, in the final assignment, y can have value 0 and a division by zero is possible (according to the analysis).