Compulsory Exercises in I125

The compulsory exercises in I125 form a large project with a complete compiler for C- as the final goal. Each individual exercise is one step towards the final goal.

Newsgroup

The course has its own newsgroup: news:uib.kurs.i125 You may discuss the exercises and the project as you please.

Overview

Part 1 is to be solved and handed in individually. Part 2,3 and 4 are highly recommended to be done by groups of two students

Scanning. A scanner should be implemented using jlex. Deadline October 4th.
Syntax Tree. A syntax tree structure for C- should be designed and implemented in Java. Deadline October 18th.
Parser. A recursive-descent parser should be implemented in Java using an abstract syntax tree. Deadline November 8th.
Code Generation. Translation of two sample C- programs into executable code for BVM. Deadline November 22nd.

The language

You are going to write a compiler for C- which is described in the text book, with a few changes:

Nested comments should be allowed.
White space before and after identifiers and numbers is not required. Special symbols work as separators as well.

We also make a couple of specifications:

Local variables shadowing formal parameters are allowed, i.e. you may declare a function with a formal parameter and a local variable of the same name, with the result that the formal parameter is of no use whatsoever. In such a case gcc(1) would issue a warning, but you don't have to check for this.
Void variables, void arrays, and void parameters are not allowed. (A void parameter list is of course allowed.)
Identifiers may not be overloaded within the same scope, i.e., the same identifier cannot be used both for a function and for a global variable. (You may of course declare local variables with the same identifier as a variable or function in an outer scope.)

Software

JLex

JLex is a tool for generating lexical parsers or scanners. JLex reads source files in its own format and outputs java code which may be used in larger programs like your compiler. (There is also Lex which generates C code from a format similar to that of JLex.)

We have made a local version of JLex, which you can download and run as a jar file. The changes we have made are

Package names are written in lowercase which is common practice.
The source file should have suffix .lex, while the resulting java file gets suffix .java instead.

To run JLex from the jar file, you write

  java -cp i125.jar jlex.Main Scanner.lex

User manual and other information may be found on the homepage of JLex:

JLex: A Lexical Analyzer Generator for Java(TM)

Jar

Jar (java archive) is a program to pack a bunch of class files into a single file. To make a jar file of all classes in the current directory you can run

  jar cf scanner.jar *.class

and to run the Scanner class from this file, you type

  java -cp scanner.jar Scanner

Jar can do several other things as well, see the man page jar(1).

Other programs

The programs below may be useful, but they are not absolutely necessary for the project.