15-411 Compiler Design
[ Home | Members
| Schedule | Overview
| Discussions | Assignments
]
15-411 Assignment #3
Part One Due: 12:01am, Tuesday, February 17, 1998
Part Two Due: 12:01am, Thursday, March 5, 1998
Goal
The goal of this assignment is to create a compiler for the c (pronounced
"little-C") language. This language, the syntax and semantics of
which are described below, implements integer, boolean, and character types;
C-style conditional statements, for-loops, while-loops, and control blocks;
and a significant number of C's primitive operations. It will also
require you to add several functions to the runtime library, all of which
are described at the end of the "semantics" section below. The assignment
is divided into two parts. Although they will not be graded separately,
you must show that you have completed the first part by handing it in on
February 17 as you would any other assignment. If you do not hand
it in on time, three points out of 25 will be deducted from your grade
for the whole assignment. If you do not hand it in within the usual
one-day extension, ten points will be deducted. As usual, you are
free to choose any real, widely-available target machine. You are
also free to use either your code for the Simple compiler or one of the
sample solutions provided for Assignment #2 as a starting point for your
c compiler. Note that this assignment is worth 25% of your
final grade, so, although you will have some time to work on it, please
start right away.
Instructions
-
For Part One, write the lexer and parser of your c compiler.
The code you hand in should take a valid c program as input and
convert it into an abstract syntax tree. The lexer and parser may
not seem like much work, especially considering that the lexical classes
and syntax of c are quite well specified below, but turning the
syntax into an LALR(1) grammar, which is what Yacc requires, can be tricky.
So get them done ASAP and start thinking about how to write the elaborator,
which will be much larger than the Simple elaborator as c actually
has types.
-
For Part Two, write the rest of your c compiler. The code
you hand in should take a valid c program as input and compile it
to (commented) assembly language for the target machine of your choice.
Feel free to modify the code from Part One as you see fit. Note also
that it is still perfectly acceptable if your register allocator gives
up after all the registers have been used. We will not be covering
register allocation for this assignment -- that will be for Assignment
#4. You are encouraged, however, if your Assignment #2 register allocator
was particularly poor, to use a better one from the sample solutions for
Assignment #2, so that you can test your compiler on non-trivial programs.
-
For both parts, hand in your compiler by following the standard hand-in
procedure described in Derek's post to the class bboard. For Part
One, it is not necessary to provide any sample test runs since the output
is just an abstract syntax tree at that stage and we won't be grading it.
Remember, the goal of Part One is just to ensure that you aren't falling
behind. You should tar your main directory and place the tar file,
called c.tar, in /afs/andrew/scs/cs/15-411/studentdir/your-login-id/ass3/.
When I run "tar xvf" on this file, it should create your main directory
with all your files in it, so that I can go into the directory, run CM.make()
from SML, and test your compiler. Lastly, please remember to put
your name and login-id at the top of every source file.
Extra Credit (for Part Two)
A machine-level multiplication or division instruction can be very expensive,
taking up tens of clock cycles. However, multiplication and division
by a constant can be reduced to a sequence of shift and add (or shift-and-add,
if your target machine allows) instructions. Implement multiplication
and division as efficiently as possible, using shifts and adds when it
is profitable to do so. Partial extra credit may be given even if
your compiler only optimizes these instructions some of the time.
In any case, be sure to document your optimizations thoroughly.
The c Language
In this section we will give definitions of the lexical classes, syntax,
and semantics of the c language, sometimes formally, sometimes informally.
Lexical Classes
The c lexemes are divided into numbers, characters, identifiers,
keywords, and symbols.
-
For our purposes, the only kind of numbers that our c language
will admit are integers written in the usual decimal notation (no scientific
notation). In fact, numbers should be dealt with just as in the Simple
compiler we gave you.
-
Characters should always be enclosed in single quotes. Your
lexer should be able to recognize and interpret the following set of standard
escape sequences as well: '\n',
'\t', '\v',
'\b', '\r',
'\f', '\a',
'\\', '\'',
'\"', and
'\ddd'.
For the last one, this should represent the character with decimal ASCII
code ddd in the range 0-255 where the d's are digits.
-
An identifier is any combination of letters, digits, and underscores
that begins with a letter and is not a keyword. Note that, like C,
c is case-sensitive, which just means that your compiler has to
do less work.
-
The sets of keywords and symbols comprise all the red lexemes
surrounded by single quotes appearing in the BNF syntax below.
Comments begin with the sequence '/*'
and end with a matching '*/'.
Comments may span multiple lines and may be nested within other comments.
Lastly, note that a number of situations may arise where there is the possibility
of choosing between two tokens because one is a prefix of the other.
In such cases, the longest match should always be taken. For instance,
if the source input is 'x+++y', this should be parsed into the
sequence of tokens: ID,
'++', '+',
ID.
BNF (Backus-Naur Form) Syntax
<program> ::= <block>
<block> ::= '{' '}' | '{' <stmts> '}'
<stmts> ::= <stmt> | <stmts> <stmt>
<stmt> ::= <simp> ';' | <control>
<simp> ::= <decl> | <assign> | <exp> | <skip>
<decl> ::= <type> <var> '=' <exp> | <type> <var>
<type> ::= ID
<var> ::= ID
<exp> ::= NUM | CHAR | 'true' | 'false' | <var> | <exp> '+' <exp>
| <exp> '-' <exp> | <exp> '*' <exp> | <exp> '/' <exp>
| <exp> '%' <exp> | <exp> '==' <exp> | <exp> '!=' <exp>
| <exp> '<' <exp> | <exp> '<=' <exp> | <exp> '>' <exp>
| <exp> '>=' <exp> | <exp> '&&' <exp> | <exp> '||' <exp>
| '!' <exp> | '-' <exp> | <exp> '?' <exp> ':' <exp>
| '(' <exp> ')' | <fcall> | <var> '++' | '++' <var>
| <var> '--' | '--' <var>
<fcall> ::= ID '(' ')' | ID '(' <exp> ')'
<assign> ::= <var> '=' <exp> | <var> '+=' <exp> | <var> '-=' <exp>
| <var> '*=' <exp> | <var> '/=' <exp> | <var> '%=' <exp>
<skip> ::= .
<control> ::= <cond> | <while> | <for> | <block>
<cond> ::= 'if' '(' <exp> ')' <stmt>
| 'if' '(' <exp> ')' <stmt> 'else' <stmt>
<while> ::= 'while' '(' <exp> ')' <stmt>
<for> ::= 'for' '(' <simps> ';' <exp> ';' <simps> ')' <stmt>
<simps> ::= <simp> | <simps> ',' <simp>
Notes on the Syntax
The precedence of operators is given in the following table.
| operator |
precedence
level |
associativity |
| '!', '-'
(unary) |
7 |
none |
| '*', '/',
'%' |
6 |
left |
| '+', '-' |
5 |
left |
'<', '<=',
'>', '>=' |
4 |
left |
| '==', '!=' |
3 |
left |
| '&&' |
2 |
left |
| '||' |
1 |
left |
| '?:' |
0 |
none |
Other than the order of operations, the only important thing to note is
that for 'if'
statements, each 'else' clause is
matched with the nearest enclosing 'if'.
Semantics
The semantics of c is identical to that of C except in a number
of noteworthy cases:
-
There are three types: int, bool, and char.
-
true and false are values of type bool, not int.
-
Variables can be declared anywhere in the code, as in C++ and Java.
-
If a variable is not initialized upon its declaration, it is initialized
by default to 0 if it is of type int, false if it is of type bool, and
the null character ('\000') if it is of type char.
-
Variables may be redeclared (to be of any type), but the new declaration
will shadow the old one.
-
Control structures (<control>) follow fairly typical scoping
rules -- they can manipulate the variables defined outside them, but any
variables declared inside are not accessible outside. Note that these
scoping rules apply even when a control structure acts as the body of another
control structure.
-
If the evaluation of an expression requires the evaluation of more than
one subexpression, the subexpressions are evaluated left-to-right.
-
The arithmetic operators (+,-,*,/,%,unary -,++,--) take expressions
of type int and compute a value of type int. The relational operators
(==,!=,<,<=,>,>=) either take two expressions of type int,
two expressions of type char, or two expressions of type bool, and compute
a value of type bool. The logical operators (&&,||,!,==,!=)
take expressions of type bool and compute a value of type bool. The
== and != operators are both relational and logical.
Note that ++ and -- only operate on variables but return
expressions.
-
The dynamic semantics of && is the obvious: if its left
expression evaluates to false, then it returns false, otherwise it returns
whatever its right expression evaluates to. The dynamic semantics
of || is equally obvious: if its left expression evalutes to true,
then it returns true, otherwise it returns whatever its right expression
evaluates to.
-
As for the ?: operator, its first expression must be of type bool,
its second and third can be anything, but must have the same type.
Essentially, this C-style conditional expression has the same static semantics
as if-then-else in ML. As for its dynamic semantics, the test-condition
is evaluated, then either the second or third is evaluated depending on
its truth or falsity, but not both.
-
The test-expressions in the parentheses of conditionals, for-loops, and
while-loops must be of type bool.
There are eight built-in functions that c understands and you should
put them all in your run-time library.
-
printi (n) -- takes a parameter n of type int and prints n to the
screen along with a newline. Returns nothing.
-
printc (c) -- takes a parameter c of type char and prints c to the
screen along with a newline. Returns nothing.
-
printb (b) -- takes a parameter b of type bool and prints b ("true"
if b is true and "false" if b is false) to the screen along with a newline.
Returns nothing.
-
geti () -- takes no parameters, but reads in an integer followed
by a newline from the keyboard and returns the integer.
-
getc () -- takes no parameters, but reads in a character followed
by a newline from the keyboard and returns the character.
-
getb () -- takes no parameters, but reads in either the string "true"
or the string "false" followed by a newline from the keyboard and returns
the appropriate boolean value.
-
chr (n) -- takes a parameter n of type int and returns the character
with ASCII code n.
-
ord (c) -- takes a parameter c of type char and returns the integer
ASCII code of c.
If you have any confusion whatsoever regarding the rather informal description
of c's semantics we have given here or about the c language
in general, do not hesitate to ask us. It is critical that all the
students compile the same source language.
For problems or questions regarding this web contact [petel@cs.cmu,edu].
Last updated: February 3, 1998.