Language: this time, we just extend Tool.

We add the operators ⇒ (implication) and ⇔ (boolean equivalence, like !(x ^^ y)).

Draw a deterministic automaton that accepts ⇐, =, ==, >=, ⇒, ⇔, using longest-match rule. Mark different accepting states.

We want to make “*” optional in multiplication expressions (like in math).

Transform the following rule for (a subset of) expressions:

e ::= e * e

  | e e
  | e + e
  | e - e
  | e / e
  | -e
  | ( e )
  | ID
  | INTLITERAL

Make it LL(1), and encode the priorities as usual. Make sure that x -y parses as x - y, NOT as x * (-y).

What now if we want to add the rule e ::= e ( e (, e)* ). Explain the problem, and suggest a solution.

Consider Tool without arrays but with covariant everything (like Eiffel)

This is not a sound type system, there are programs that type check but crash with 'method not found' exception.

Show one such example.

Propose a correction to the covariance rules that still accepts the following program:

has both co and contra

...

Compile a tiny while loop where “!(x ⇒ y)” is used with short-circuit.

Here is a small program with nested loop and only + as arithmetic operator

Assume all integers are implemented as unbounded BigInt-s.

a) Convert it to CFG.

b) Run the following analysis until fixpoint from range_analysis_example.

• here is the transfer function for +

c) Write the transfer function for

x = y * z

Apply it to the following two examples.

• one easy
• one illustrating the general case