All of the projects are based on a small Ada-like language named
Macro.
Usually, you are given a working program (scanner, parser, or whatever)
for a subset of Macro, Mini. Your job is to extend it to work
for Macro.
Assignment 1: Scanner
You will use lex/flex (see below). The lexical definition for Macro is
here(ps
version). You are supposed to read in the source file as standard input
and write the token types and values (if any, for constants and identifiers,
certainly) to the standard output. For consistency, you are required to
use the definition in "lexicon.h".
Test cases are here,
here,
here,
here,
and here.
Oh! I got an extra!
And I remember another.
But no more, I guarentee you. (Due 10/12/98)
Remember to report errors (there is a tricky thing for integers, got
it?).
Assignment 2: Parser
You will use yacc (see below). You will generate the AST (what is
this guy?) for any program written in Macro. The grammar definition
is here
(ps
version). You will start with a skeleton,
including a much shorter description of yacc. You can download it
from webpage (To deconpress the file, try 'tar xvfz <filename>'
or for those tar pointing to /usr/bin, using 'gunzip
-c <filename> | tar xvf -'). It is also available on acme
(ONLY) under ~ics4410/Assignments/parser
You have the following to do:
make and run it on the test case for Micro, study the output.
You are supposed to create the similar output for Macro source
input when using the -d flag.
Modify ast.h, ast.c (printing part) to incorperate more AST node types.
Using your previous .l file as scanner, instead of include lexicon.h, INCLUDE
y.tab.h
Main part. Write your own .y file to generate parser. Please
use the token names in my previous lexicon.h
(That's the purpose of my lexicon.h)
Modify Makefile to include your code.
Test cases are here.
Two new tests (test31
and test32)
for functions are not included in the tar file. The test cases are
also available on acme under ~ics4410/Assignments/tests
However, in this project, you don't need to do symbol table and type
checking, that's for the next project. (Due 10/26/98).
Assignment 3: Semantics
Symbol table and type checking. For this purpose, we have to change the
grammar (It's my fault not to have a correct version) as follows, modifying
your .y file might take no more than 10 minutes (so you know how easy it
is to craft a compiler, :-) ):
(or you don't treat the last three guys as reserved words)
However, we need to clarify some semantic rules:
Static scoping. For simplicity, we don't permit the same name for
a variable, a type, a procedure, a function or a package at the same level.
But we do allow duplicated name at different levels of scoping.
Inter-package accesses are enabled using the "dot" notation. However,
only those identifers in the header (i.e., not in body) part are visible
to other packages. So, some Compound-Id's above are restricted
to package access only.
Types are name-equivalent. For this reason, function definition above
should use identifer (may with package access) only as return value type,
and similar for formal parameters.
Assignment from integer to float is allowed, and mixed arithmetic operation
of integer and float given float result.
Parameter modes are treated the same as in Ada: default mode is in; r-values
of in parameters are copied into stack; out or in out parameters must be
a l-value; values in out parameters are copied back to the destination
designated by its l-value when the procedure/function completes.
We want type checking for arithmetic/relation operations, assignments,
and parameter passing.
We sometimes also need the actual definition in case of forward definition
and private types. But private types make code generation a little bit
harder.
What you need to do (UPDATED BASED ON DISCUSSION
IN CLASS ON WEDNESDAY):
You are only required to implement a symbol table and semantic processing
for the following features for the next part of the project:
variable declarations
expressions
assignment statements
control structures
You must successfully process all test programs through test11
to satisfy the requirements for this project.
Each program is syntactically a package, so you obviously need to handle
simple packages. All of these programs consist of only a single
package, so only one scope will be used. However, be sure to
make your symbol table implementation general enough to incorporate multiple
scopes, including nested scopes, in the next submission.
Due Tuesday night, 11/10/98 (not
Monday, as I said in class) .
Assignment 4: Code generation
(part 1)
You will generate MIPS assembly language as the target code. To avoid
most of the details about the format of execution files, we will use a
simulator instead. The simulator is called SPIM. Instructions
for using SPIM are listed below.
For this assignment, you must generate code for all of the features
from assignment 3. In addition, you must implement semantic processing
and code generation for parameterless procedures. Successful execution
of all test programs through test17 plus correct reporting of the errors
in test18 will satisfy the requirements of this assignment.
Due Monday night, 11/23/98. Because
we have to get in one more assignment before the end of the quarter, this
due date is firm. Be sure to work on your compiler as well
as study for the next exam between now and 11/18. On that day, I
plan to spend some time answering project questions before we begin the
exam.
Project Grading
All students are expected to produce a working compiler will all of the
features specified through Assignment 4. Your total project
grade will be computed using the following weights:
Assignment
CS 4410
CS 6415
1
10
10
2
20
18
3
20
18
4
28
24
5
see below
see below
Following this scheme, if you receive a grade of 100 on each of the first
four assignments and you do none of assignment 5, your project grade
will be 78 if you are a 4410 student or 70 if you are a 6415 student.
The points you receive for the features listed uner assignment 5 will be
added to this score.
Assignment 5: Code generation
(part 2)
For your final assignment, you may choose to implement any or all of the
features listed below in order to earn addition points toward your final
grade on the project. The possible leatures and their values, plus
related test programs are:
Feature
Points
Tests
Parameters
8
19 - 20
Records
4
21-22
Arrays
6
23-25
Packages
(including private)
6
27-28
Constant Expression
Optimization
4
to be
added
Peephole Optimization
4
to be
added
The points associated with each feature represent the (approximate) relative
difficulty of implementing the features. You have limited time, so
plan your strategy carefully.
Bonus points may be obtained for successful
execution of test programs that combine multiple features. Each of
the following is worth one additional point:
test26 (records and arrays), test29 (packages, records and arrays)
and test30 (packages, records, arrays and parameters).
Due Friday night, 12/4/98.
Useful docs:
Do you know how to use a debugger? I like gdb,
well, it's not graphic interface, :-(
yacc: this
is from Sun Solaris AnswerBooks, I think it is the same for all Sun platforms.
SPIM:
READ this before starting, you need to know the format of your output,
if nothing else.
To run on CoC boxes: add to your path ~raja/bin. However,
for some setup problems, you must run spim with -notrap flag.
On Sun4, both spim and xspim work.
On Solaris, only spim works. xspim will complain
it cannot find libXaw.so.5.0
I cannot find it, either. But I bet /lib/X11/libXaw.so.5
is what it needs. For those who only use Solaris in CoC (like me),
try the trick: make a link (or a copy) named libXaw.so.5.0 in
your directory, and add the path to your LD_LIBRARY_PATH (if you
don't have this environment before, REMEMBER also to add /lib /usr/lib
/usr/local/lib, otherwise everything dies!)
To run on Acme: add to your path ~cs2760/rbin
Everything works.
What else?
Submission guide:
You've finished preject mission? OK. Here is the
Submission guide. You are going to use the submission system on prism.
Besides, I hope you have a Makefile (or makefile) so that I can compile
your staff.
How to setup and how to use: see this
real guide. BUT REMEMBER to use ics4410 instead of cs6410.
Yeah, it is ics4410 instead of cs4410, obviously for
historical reasons. And, USE names like p1, p2 to submit.
Exam 1 -- Suggested Study Questions
The following are taken from the end of chapter exercises.
Chapter 2: exercises 2, 6, and 8.
Chapter 3: exercises 3, 4, 5, 6, 15 and 23
Chapter 4: exercises 5, 6, 8, and 14. Try 23 to test your ability to write
grammar algorithms.
Chapter 6: exercises 9, 10 and 11 will test your automaton and parse table
constriuction abilities; exercise 3 asks you to reason about how LR(0)
works.