Exercise 1 - First Sets
Given the following grammar, construct the first set for each symbol:

P -> ES
ES -> E; ES | E;
E -> T D | D := v | epsilon
T -> int | bool
D -> x | y

Example of a program:
int x;
bool y;
x := 4;
y := false

First(int):
First(bool):
First(id):
First(:):
First(=):
First(v):
First(E):
First(ES):
First(D):
First(T):
First(P):

S -> aA
A -> BCB
B -> b
C -> cC | epsilon

First(S):
First(A):
First(B):
First(C):

Exercise 2 - Parsing
Given the following grammar, fill in the following skeleton code for a recursive descent parser:

S -> baS | pSq | q

parse_P
   if (lookahead == ) {
   
   }
   Else if (lookahead == ) {
   
   }
   Else if (lookahead == ) {
   
   }
   Else error();
}

Exercise 3 - Operational Semantics

Given the rules:

---------------
n < n -> n < n  // Remember, left of the -> is lexical tokens, right is mathematical operations.
                // That is to say, we evaluate < when it appears in the language :)
------
n -> n

   n1 < n2 -> true e1 -> v1
---------------------------------
if n1 < n2 then e1 else e2 -> v1 

   n1 < n2 -> false e2 -> v2
---------------------------------
if n1 < n2 then e1 else e2 -> v2

Deduce the following expressions by explicitly writing out the natural deductions:

if 2 < 4 then 3 else 5 -> 3
if 4 < 2 then 3 else 5 -> 5