Administrative Details
The project will be graded on a
scale of 100, scaled to 5% of your final grade, allocated as follows:
————————————————————————————
10%
Parser (CParser.hs) — This will take a String representing a Mini-C
program and produce an AST expression for the program. You must also implement a prettyShow function
in Ast.hs whos output must always parse.
# input一个mini-c 的string 并对它做 AST expression 的
parse 操作，在Ast.hs中必须包含一个prettyshow
function。 out put 必须被parse过
10%
Interpreter (ASTInterpreter.hs) — This will take an AST expression
output by the parser, evaluate it,
#input 一个parser
return的 Ast expression
and return a list of Strings
(produced by print statements in the program).
# 通过print 来return 一个strings 的list
60%
Compiler (CCompiler.hs) — This
will take an AST expression and convert it into an Intermediate Code program (a
list of IC statements). This IC program can then be executed by the IC
interpreter provided to generate output from the print statements in the
program.
#input 一个AST
expression 然后这个文件会把它转化成intermediate code program（是一个ic statement 组成的list）， 这个ic
program 然后会被IC interpreter 运行并产生program中的print statement 作为output
20%
Additional features (FeaturesTests.hs))
— For the final 20% of the grade, you must implement at least two
refinements to the project. Some possibilities for this are as follows, but you
ma也consult with us about your own ideas. Each of these is
worth 10%, so you can do any two (no extra credit if you do more, though we’ll
be impressed and I’ll be sure to mention it if you ask me for a recommendation
down the road!).
#从以下的几个选项中选择两个做，多做没有加分，每个%10
o Code optimizer — Use a stack-based
allocation scheme for temporaries to reuse them intelligently, and eliminate
redundant jumps.
o Add additional language features to Mini-C:
comments, for loop, do-while loop.
o Modify the grammar (and hence the entire project)
to allow any number of arguments to a function and allow procedures (functions
that do not return arguments).
o Add a list data type and built in functions
(cons, nill, head, tail, indexing) to manipulate lists. Type errors (e.g., trying
to add a list and an int) can be ignored (just let the program crash!)
o Add floats to the language and write a
simple static type checker which will flag errors before execution. Or you
could do this for lists (combining with the previous item).
o Add nested function definitions to the
language (functions defined inside other functions).
Provide a file FeaturesTests.hs
with tests that prove your additional features work as required. We may
test your code on our own tests as
well.
Make sure that your implementation
works on the basic tests, as well as any additional features tests
you may write. If you want to add
required type declarations this would be a problem, so talk to us
before you go down this road.
Please talk to us if you have any
other ideas. There are many possibilities!
We will test your code on the test cases provided and
also write some of our own tests. Testing your code with your own tests is part
of the project!
Some Advice on How to Proceed
There are several
linked phases:
The first task is to decide on the AST which can represent the source language;
this
should be fairly easy, since we have been doing this kind of thing all
semester.
One thing you should think about is whether you want to have an explicit
“separator” to create lists of statements, or whether you just want
to
have Haskell lists of statements. In lecture I tended to write ASTs on
the board using the former, but you may find (as I did) that using
explicit lists is easier: for for example, in my AST I had programs defined
as:
type Program = [Func] —
a program is a list of function definitions
and then later I had:
data Stmt = Block [Stmt]
| etc.
Once you have decided on the AST, then you can break the basic work into
separate
pieces. Some of the additional features can not be separated out (e.g.,
reworking
the grammar), so maybe you want to put them in the plan from the beginning.
The parser, the AST Interpreter, and the optimizer are the least amount of
work,
and the compiler is probably as much work as all these combined, so plan
accordingly.
Some parts of the compiler are busywork, since after you have figured out how
to,
say compile one kind of expression, the rest are exactly the same and you end
up
cutting and pasting.
You can begin to test your implementations using the examples below and
in the ICInterpreter.hs file (e.g., optimization). Additional
test cases may be provided, but we will also use our own test cases, so
testing and making sure everything works as it should is part of the project!
One nice way to check your work is to verify that the AST interpreter and
the IC Interpreter (after compilation) produce the same results.
The Source Language: Mini-C
The grammar for the source language has been provided in the lecture slides for
lecture 24, but here it is
again for your convenience (there have been some changes made relative to what
was actually presented in
the lecture, but the PDF of the lecture slides has been updated — mostly I
changed the language so
that only function definitions may be given at the top level, and there is no
global memory).
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. Translations of these
are provided as examples in the file ICInterpreter.hs, with the same numbers.
Some of these may be provided as test cases in github.
—————————————————————–
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
The result of running this example in the ICInterpreter would be a list
containing
the result of the print statement in line 19, showing that GCD(2868,264) is 12:
ICInterpreter> execute icTest11
Just [“res = 12”]
ICInterpreter>
Further examples of IC Programs are found in the test cases in the
file ICInterpreter.hs. Use showICProgram
to see readable versions
of these programs.
Hint:如果思路不同可以不用的
Input code ^ 经过compiler以后的code