Epsilon - a very small language

The project is to write a compiler for the Epsilon programming language. Epsilon is a relatively simple, imperative language. It is almost a subset of Pascal, but with some constructs and semantics from C. A grammar for Epsilon can be found in Homework 1.

Epsilon has two control structures: while...do and if...then...else. There are constructs for assignment, reading/printing, and for returning a value (from functions). The language allows code blocks, delineated by begin and end.

Epsilon has procedures and functions, as well as a statement and an expression for calling them. Procedures and functions cannot be nested, i.e., local procedures/functions are not allowed. Each procedure or function has its own namespace. Thus, there are two levels of namespaces for variables and parameters: one level for global names and one level for local names. A local name can shadow a global name. Because all procedure and function names are in the global namespace, all procedures/functions can call each other.

The parameters for functions and procedures are passed according to the copy-in/copy-out principle (also known as call-by-value-result). A function returns a value by the return expression statement, where expression must evaluate to an integer. Recursion is allowed.

There are two types: Integers and one-dimensional arrays of integers. Operations (such as assignment, +, and -) cannot be performed on entire arrays, only on individual elements. Entire arrays can be passed as parameters, but not returned from functions. Arrays are indexed by 0. There are no out of bounds checks for arrays, so referencing an element beyond the first or last element of the array has undefined consequences.

Example programs

simple.epsilon

procedure proc (p1);
var l1;
begin
   l1 := 123;
   p1 := l1
end;

var m1;
begin
   proc (m1);
   write m1
end.

fac.epsilon (computes n!)

function fac(n);
var k;
begin
  if n = 0 then
     return 1;
  if n >= 1 then
  begin
    k := n - 1;
    k := n * fac(k);
    return k
  end
end;

var x;
begin
  read x;
  x := fac(x);
  write x
end.

count.epsilon

procedure count (start, stop, step);
var i;
begin
   i := start;

   while i <= stop do
   begin
      write i;
      i := i + 1
   end
end;

var n1, n2, n3;
begin
   n1 := 0;
   n2 := 100;
   n3 := 10;
   count (n1, n2, n3)
end.

swap.epsilon

var x[10], y[10];

procedure swap(x, y);
var z;
begin
   z := x;
   x := y;
   y := z
end;

procedure swap_array(x[10], y[10]);
var i;
begin
   i := 0;
   while i < 10 do
   begin
      swap(x[i], y[9 - i]);
      i := i + 1
   end
end;

var i;
function max(x[10]);
var i, m;
begin
   m := 0;
   i := 0;
   while i < 10 do
   begin
      if m < x[i] then
         m := x[i];
      i := i + 1
   end;
   return m
end;

var a,b;

begin
   i := 0;
   while i < 10 do
   begin
      read x[i];
      i := i + 1
   end;
   swap_array(x, y);
   i := 0;
   while i < 10 do
   begin
      write y[i];
      i := i + 1
   end;
   write max(y)
end.