Stanford Compilers Coursework (COOL Compiler)

Table of Contents

1. Introduction
2. Project structure
3. Testing and grading
4. Sample COOL Programs
5. Setup & Reproduce

Introduction

This is a repository of coursework assignments for the Stanford Compilers MOOC course. The result of completing all coursework assignments is a fully-working compiler for the COOL Programming Language. Compiler is written in C++ and depends on several assignment supplied libraries (like symbol table, identifiers table ...). Flex and Bison are used to implement first compiler frontend phases and other compiler passes are handcoded in C++.

The compiler compiles COOL into MIPS Assembly. MIPS is a reduced instruction set architecture about which you can learn more here. Resulting programs are run using SPIM simulator.

COOL (Classroom Object Oriented Language) is a computer programming language designed by Alexander Aiken for use in a compiler course taught at Stanford. COOL resembles many modern programming languages, including features such as objects, automatic memory management, strict static typing and simple reflection. COOL constructs take a few ideas taken from functional programming languages, so that every COOL statement is an expression which must return something.

COOL is precisely defined in specification documents, the most relevant ones are:

• COOL Manual
  • describes lexical and syntactical structure of the language
  • describes type system rules (equations) and language operational semantics
• COOL Runtime System
  • describes the runtime system backing this programming language
  • describes garbage collection algorithms used and the interface between those and a correct compiler
  • describes the object layout recommended to implement this language and the interface to the garbage collection routines

Here are a few examples of simple COOL programs:

Hello world

class Main inherits IO {
  main(): SELF_TYPE {
   out_string("Hello, World.\n")
  };
};

Palindrome checking program

class Main inherits IO {
   pal(s : String) : Bool {
       if s.length() = 0 
         then true
       else if s.length() = 1 
         then true
       else if s.substr(0, 1) = s.substr(s.length() - 1, 1) 
         then pal(s.substr(1, s.length() -2))
       else false
       fi fi fi
   };

   i : Int;

   main() : Object {
     {
         i <- ~1;
         out_string("enter a string\n");
         if pal(in_string())
             then out_string("that was a palindrome\n")
             else out_string("that was not a palindrome\n")
         fi;
     }
   };
};

Project Structure

The compiler project consists of four programming assignments:

• Lexer - writing Flex specification which generates lexer
  • The input to the lexer is a string and the output is a stream of tokens
  • Here is the assignment specification
• Parser - writing Bison specification which generates LALR(1) parser
  • The input to the parser is a stream of tokens and the output is an abstract syntax tree
  • The abstract syntax tree is constructed using a simple syntax directed translation
  • Here is the assignment specification
• Semantic Analyser - writing a pass for semantical analysis, mainly type checking
  • The input to the semantic analyser is a raw abstract syntax tree and the output is the attributed abstract syntax tree
  • Here is the assignment specification
• Treewalk Code Generator - writing a pass for code generation using a naive treewalk algorithm, generating code for the 'stack machine')
  • The input to the code generator is the attributed abstract syntax tree and the output is a file consisting of MIPS instructions
  • Here is the assignment specification

Sample COOL Programs

In the examples folder, there are various example COOL programs. Some of them are very simple and illustrate only key features of the COOL language, but there a few ones which are quite advanced.

All of these programs were provided in the skeleton course project. You can find more about them here.

Setup & Reproduce

Dev Containers

This setup will use Dev Containers as development environment. All the tool, library and environment are set up for you.

1. Download and install Visual Studio Code and Docker.
2. Open Visual Studio Code.
3. Install Dev Containers pulgin.
4. Open command palette, select open folder in container command, then Visual Studio Code will build and connect to the container.

Trouble Shooting

undefined reference to 'yylex'

The reason is caused by use c++ library instead c library. See here.

Just modify Makefile to link libc static.

LDFLAGS= -static

lexer: ${OBJS}
        ${CC} ${LDFLAGS} ${CFLAGS} ${OBJS} ${LIB} -o lexer

spim cannot open file: '../lib/trap.handler'

When you work on PA5, you may encounter this error. The reason is that the spim simulator use relative path to find the trap.handler file. So you need go to the ./bin folder and run spim command there.

spim ../assignments/PA5/example.s