Crafting a compiler for the Micro language
Abstract
We will implement a compiler that can translate programs written
in the Micro language to assembly code of the Tiny machine.
1 Introducing
We have discussed the Micro language and the instructions set of the Tiny
machine. The description les of the two language have been uploaded to
the FTP site. In this project, we will write a C code to implment a compiler
to translate from Micro to Tiny.
2 Task 1: writing a scanner of Micro
Design the token types of each token. Each token can be de ned as
a pair: the token type, and token string. For an id (variable) and a
number, its token string need to be recorded, but for any other type
of token, the token string can be empty.
Write a program that can read a le and return a sequence of tokens.
You can choose to obtain all of the tokens and save them in a linked
list; Or, you can implement some function such that calling it can
obtain the next token.
Test your scanner by printing all of the tokens of some Micro program
les.
3 Task 2: Writing a syntax-based code generator
of Micro
It is common to write a parser of some language to check the syntax re-
quirements (described by some grammar) of its programs. In some complex
compiler, parser, semantic analyzer, and code generator are separated pieces
of software. In this project, we will integrate them together. More specif-
ically, we will use the recursive-decendent style. to write a parser to check
the syntax, together, along the way, check the semantic requirement, and
generate the target code of Tiny.
[Syntax requirement]: The grammar (production rules) has been
discussed in classroom, and is also included in the description le of Mi-
cro. Only the production rule of the variable is missing
in the document, which describes any kind of arithmetic computation
of integer variables and constants. You should provide a complete set
of production rules of Micro, either as comments of your C code, or as
a separate text le.
[Semantic requirement]: For any variable appearing in an expres-
sion, it must have been assigned with a value, that is, in some earlier
statement, this variable must have appeared on the LHS of some as-
signment, or in some read statement.
[code generation]: Generate the target code program in Tiny. You
should run the generated code using the virtual Tiny machine, whose
source code is provided in the FTP site.
4 Suggested plan
It is better to create 4 folders for di erent stage of your program:
One folder for code of scanner only.
One folder for code for parser. It uses code of your scanner, but does
not contain code of semantic analysis nor code generation.
One folder that contains the all the code of semantic analysis.
One folder that include all of the code for code generation (together
with the previous code of scanner and parser).
The advantages of doing so is that your compiler can be tested and graded
in di erent stages.
2
5 Program submission and grading
Scanner: 100 points.
syntax-based code generation: 300 points.
Due time: Thursday 30 November 2017, 10:00pm.
Your code will be graded according to its quality.
At most 3 students can form. a group and submit the homework to-
gether in using one email account. In this case, please cc the email to
all or the members of the group, and include all the student names in
the source code le and in the email title.
Compile and debug and run your program.
Your code should be pretty, i.e, you should indent and align your lines
and code nicely and logically following some pretty-printing style.
At the top of each of your source les (.c or .h les), write your name,
student id and date as comments.
Attach all of your source les to an email. If your program has only
one .c le, that is ne. Do not attach binary les (.o, .obj, .exe or
executable) les, since doing so will make your email being considered
as virus by the Gmail system.
Send your email to
The title of your program should be like:
[name][student id][D1|D2][hmk1 micro compiler]