Haskell Implementation of Pure Compiler Using Monadic Sequencing.

  Parser  -> AST  ->  AST Interpreter ----------------------------------------------> Output (list of Strings)
              |                                                                       ^
	  |---->  Compiler  ---> IC Program -------->  IC Interpreter (provided) -|
	                               |                ^
		                       | --> Optimizer -|

The Source Language: Mini-C

0: Program := Funcs
1: Funcs := Func Funcs
2: Funcs := Func
3: Func := def identifier ( ) { Stmts }
4: Func := def identifier ( identifier ) { Stmts }
5: Stmts := Stmt ; Stmts
6: Stmts := Stmt ;
7: Stmts := Block Stmts
8: Stmts := Block
9: Block := { Stmts }
10: Block := while ( BExpr ) Block
11: Block := if ( BExpr ) Block
12: Block := if ( BExpr ) Block else Block
13: Stmt := id = Expr
14: Stmt := return Expr
15: Stmt := print identifier
16: Stmt := break
17: Stmt := continue
18: BExpr := BTerm || BExpr
19: BExpr := BTerm
20: BTerm := BFactor && BTerm
21: BTerm := BFactor
22: BFactor := ! Bfactor
23: BFactor := Cond
24: Bfactor := ( Bexpr )
25: Cond := Expr == Expr
26: Cond := Expr != Expr
27: Cond := Expr < Expr
28: Cond := Expr <= Expr
29: Cond := Expr > Expr
30: Cond := Expr >= Expr
31: Expr := Expr + Term
32: Expr := Expr - Term
33: Expr := Term
34: Term := Term \* Factor
35: Term := Term / Factor
36: Term := Term % Factor
37: Term := Factor
38: Factor := - Factor
39: Factor := identifier ( )
40: Factor := identifier ( Expr )
41: Factor := identifier
42: Factor := integer
43: Factor := ( Expr )

Here are some examples of the Mini-C language

---

Test 1: Just a simple example of expression evaluation

def main() {
    x = 6;
    y = 8;
    z = x _ y / 3 + -x + 2 _ y;
    w = z - x % (x - 2);
    print w;
    return 0;
}

---

Test 2: Conditionals

def main() {
    x = 4;
    y = 2;
    z = -1;
    if(x > 2) {
    print x;
    }
    if(y < 2) {
    print y;
    }
    if(z != 2) {
    print z;
    } else {
    print y;
    }
    print(z);
    if(z <= y) {
    print x;
    if(x + y > z) {
    print y;
    }
    else {
    print z;
    }
    } else {
    print z;
    }
    return 0;
}

---

Test 3: While loops -- sum the numbers from 1 to 10

def main() {
    k = 1;
    sum = 0;

    while ( k <= 10 ) {
    sum = sum + k;
    k = k + 1;
    }

    print sum;
    return 0;
}

---

Test 4: nested while loops -- for (n,m) with 1 <= n <= 3 and 1 <= m <= 4,

count for how many pairs n evenly divides m.

def main() {
    n = 1;

    count = 0;

    while ( n <= 3 ) {
    m = 1;
    while ( m <= 4 ) {
    if ( m % n == 0 ) {
    count = count + 1;
    }
    m = m + 1;
    }
    n = n + 1;
    }

    print count;
    return 0;

}

---

Test 5: Nested While and If statements: output the first 10 primes

def main() {
count = 0;
limit = 10;
n = 2;

while (count <= limit) {
isPrime = 1;
k = 2;
while ( k < n ) {
if (n % k == 0) {
isPrime = 0;
}
k = k + 1;
}
if (isPrime==1) {
print n;
count = count + 1;
}
n = n + 1;
}
return 0;
}

---

Test 6: Basic Boolean expressions -- short-circuit evaluation

def main() {

    x = 3;
    y = 5;
    z = 1;

    if( x > 2 && y < 5) {
        print x;
    }

    if( x > 2 || y < 5) {
        print x;
    }

    if( x > 2 && y < 5 || !(z == 2)) {
        print x;
    }

    if(z != 2 || x > 2 && y < 5) {
        print x;
    }
    return 0;

}

---

Test 7: Basic function call

def f(x) {
    n = x + 1;
    n = n \* 2;
    return n;
    }

    def main() {
    y = 2;
    n = 3;
    z = f(y+n);
    print z;
    return 0;
}

---

Test 8: multiple function calls

def succ(x) {
    return x + 1;
}

def main() {
    a = 1;
    z = succ(a) + succ(a+1) * succ(a*2);
    print z;
    return 0;
}

---

Test 9: multiple nested function calls

def succ(x) {
    return x + 1;
}

def main() {
    a = 5;
    z = succ(succ(succ(a)));
    print z;
    return 0;
}

---

Test 10: multiple functions calling each other

def succ(x) {
return x + 1;
}

def times2(x) {
return x \* 2;
}

def f(y) {
z = succ(y);
y = times2(z);
return y;
}

def main() {
z = f(10);
print z;
return 0;
}

---

Test 11: Recursion: This calculates the GCD of two numbers; because we only have one parameter for a function, I put the second number inside the function!

def gcd( b) {
a = 2854;
while( b != 0 ) {
t = b;
b = a % b;
a = t;
}
return a;
}

def main() {
m = 264;
res = gcd(m);
print res;
return 0;
}

---

Test 12: Produces the first 20 members of the Hofstader Q sequence in a sequence of print statements

def Q(n) {
if(n <= 2) {
return 1;
}
else {
return Q(n - Q(n-1)) + Q(n - Q(n-2));
}
}

def main() {
k = 1;
while(k<20) {
q = Q(k);
print q ;
k = k + 1;
}
return 0;
}

---

Target Language: Intermediate Code

The target language for the project is an abstract assembly language for a simple machine with a stack. It is specified by the following, which is also in the file ICInterpreter.hs:

data Op = Var' String | Val' Int

data IC_Instruction
= Plus' Op Op Op -- primes are added so that you can use these opcodes in
| Minus' Op Op Op -- your compiler without name clashes
| Times' Op Op Op
| Div' Op Op Op
| Mod' Op Op Op
| Equal' Op Op Op
| NotEq' Op Op Op
| Lt' Op Op Op
| Gt' Op Op Op
| Le' Op Op Op
| Ge' Op Op Op
| And' Op Op Op
 | Or' Op Op Op
| Uminus' Op Op
| Not' Op Op
| Assign' Op Op
| Bzero' Op Int
| Jump' Int
| Call' Int
| Push'
| Return' Op
| Print' String Op
| Halt'

Here is a pretty-printed version of Test 11, which calculates the GCD of 2868 and 264:

0: push
1: call 13
2: halt
3: a = 2868
4: \_t1 = b != 0
5: bzero \_t1 12
6: jump 7
7: t = b
8: \_t2 = a % b
9: b = \_t2
10: a = t
11: jump 4
12: return a
13: m = 264
14: push
15: b = m
16: call 3
17: \_t2 = \_ret_val
18: res = \_t2
19: print "res = " res
20: return 0