Computer Science 411
- This is an individual project. What you submit must be your own
work, although you may discuss the problem in general terms
with other people. You should definitely not be showing other people
your code, and generally speaking, it is not a good idea to talk about
the project when you're sitting in front of the computer.
- Sources of algorithms and code, if any, must be properly cited.
Remember that plagiarism regulations apply to code too.
You can put citations into comments in your code.
- If you have any questions about what you can and can't safely do,
feel free to email me.
- Per course policy, late projects are not accepted.
Generate ARM assembly code for
J-- files. The generated assembly code
should be assembled and linked with the supplied tools in
~aycock/411/bin and run under the supplied version of
qemu. (You have been given, via your TA, a Makefile to
automate this as well as sample ARM programs that exercise the system
calls your run-time system needs to perform.)
Test files may be found in the usual location.
You can use the code in
~aycock/411/TEST/planb if you don't
want (or are unable) to use your code from past milestones. This is
your decision, but note that there is a penalty for doing so in terms of
marks - see Evaluation below.
The C code for a
J-- file can be produced using
astdumpmain in the
reference compiler directory. The code output should be compiled
gcc -Wall -shared output.c -o output.so
in order to work with the driver supplied in
You may email me and ask for my RTS code if you don't want to write
your own. However, note that by doing so, there is a penalty in terms
of marks - see Evaluation below.
Some marks are allocated for performing some optimizations to the
code you generate - see Evaluation below.
You will need to supply appropriate testing to
demonstrate to the TA that your optimizations work.
If you want more options, come see me.
- Peephole optimization. You may write a separate script (e.g., Python, Perl)
to do this post-compilation
if you want. A good reference for ideas on how to go about
this is Davidson and Whalley's paper.
- Constant folding, i.e., evaluating constant expressions at compile
- Unreachable code elimination. This would include whole functions
as well as unreachable code within a function. Note that this
is different from dead code elimination.
- Optimal evaluation of arithmetic expressions. The canonical starting
point for this is this paper; often compiler books (e.g., the Dragon Book) will cover this algorithm too.
- Graph-coloring register allocation with spilling. Not for the
faint of heart. See me for references.
And the fine print:
- Your code must be written in C, C++, or Java (with the one exception
for peephole optimization).
- You parser may use any of Yacc, Bison, CUP, or Bisonc++ if you choose,
as before, but
does not have to. Your scanner may still use lex, flex, or JFlex
- If you are using C or C++, you may ignore dynamic memory deallocation
if you want.
- Your program must accept exactly one command-line argument: the
pathname of an input file.
- The standard input should be ignored.
- Normal (non-error) output must go to the standard output.
- Error and warning messages must go to standard error. You may
exit after an error message. Any errors and warnings, at a
minimum, must identify the input file name, the line number (or
as close to it as may be ascertained), and a human-readable
diagnostic message that's as specific as possible.
- Your program must return an appropriate return value: zero on success,
nonzero on failure or error.
- Under no circumstances can your program exit in an uncontrolled
fashion, like a segmentation fault, bus error, or exception.
- Your code should be documented in a professional manner, and
should mention any limitations that your program has.
- You should observe good coding practices; also, any compiled
code of yours must compile cleanly with no warnings. (C/C++: compile
Idioms must be appropriate to
the language, e.g., calling
system as opposed to coding
something directly in the language you've chosen will result in you
losing marks. Be sure to check for error conditions and handle
- There are two exceptions to the ``no warnings'' rule above. First,
if the warning is due to tool-generated code that you can't do
anything about, you don't need to worry about it. Second, if
the parser generator complains about a shift/reduce conflict
on the dangling else, you may leave it as is. In both cases,
you should be verifying that the cause of the warning is
what you think it is!
- Your project submission must be compiled and tested on the CPSC machines.
On the project due date, email your TA an archive file
containing all your source code along with your test
Please send it to the email address
You don't need to include automatically-generated
code from compiler tools.
Include your name and student ID number in your email.
In your archive file, also include the output from the
script program, in which you:
- Show a full build of your compiler from scratch, on the CPSC
machines. (You may substitute a screenshot of the build from
your IDE if you're unable to build it from the command line
- Show your compiler's output when run with your test files.
The TA will be using this
to verify what your compiler's doing, so ensure everything
pertinent is actually printed in a readable fashion.
- 6/35 marks. Run-time system, one mark per functional routine.
If you can't compile enough test files to demonstrate your
run-time system's functionality, then you should be sure to
demonstrate a hand-written assembly file that shows your
RTS working. If you request my RTS to use, that's fine, but
that means that you will lose all these marks even if you
submit your own later.
- 5/35 marks. Using your own code from milestones 1-3. The
``Plan B'' code is available for your use if you choose
not to continue using your compiler code from before.
If you use the Plan B code, you will get no marks for this
part. To keep things sane for your TA to mark, you're either
using your own code or you're not - no mixing and matching.
- 4/35 marks. Optimizations, each worth two marks; you can't
get more than four marks on this, sorry.
- 20/35 marks. ARM assembly output generated and runs to produce
correct result for supplied test files, one mark per file.
(Note this does not mean that your generated assembly
matches that of the reference compiler.)
A nonfunctional submission, an incomplete submission,
or one that deviates radically from the
above specifications, cannot be given a grade above 25%
and will be referred to me to mark. You don't want that,
because if you deviate from the spec, I get to deviate from
the marking guide!