LARA

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.

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.

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)
}

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;
}

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?

Solution:

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).