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