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

  1. 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.
  2. 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.
  3. 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. 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

Semantics

The semantics of c is identical to that of C except in a number of noteworthy cases: There are eight built-in functions that c understands and you should put them all in your run-time library. 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.