CSE 4251/5251: Compiler Construction (Spring 2008)

General info

Instructor

Ryan Stansifer <ryan@cs.fit.edu>

Office hours

Check my WWW page for upto date information, you are welcome to send me e-mail at ryan@cs.fit.edu.

Lectures

Lectures are from 5pm to 6:15 Tuedays and Thursdays in CRF-401.

Class URL

http://www.cs.fit.edu/~ryan/cse4251/

Mailing List

The class has a mailing list on the Florida Tech new Sympa list server. Please join, read and contribute to it. Important announcements will be sent to the list. Members can receive all e-mail sent to the list; also anyone can view the lastest postings via RSS:

Catalog Description

CSE 4251 - COMPILER THEORY. COMPILER THEORY. Introduces formal languages, the construction of scanners and recursive descent, LL(1) and LR(1) parsers, intermediate forms, symbol tables, code generation and optimization of resultant code. Prerequisites: CSE 2010 and CSE 3101.

Overview

In this class we will write an entire compiler in Java for a simple, imperative language. Knowledge of basic algorithms: trees, graphs, etc, is required. CSE 2010 is a prerequisite. CSE 3101 Machine and Assembly Langauge, is also a prerequisite. CSE 4250 Programming Languages, CSE 4051 Advanced Java programming, and CSE 4083 Formal Languages and Automata Theory are all helpful, but not required.

Goals

be able to use make and make files in project development
be able to use Java jar files
be able to construct a lexical analyzer (scanner) using regular expressions and a scanner generator tool,
understand the theory of scanning so that you could implement a scanner generator
be able to construct a parser using LALR(1) grammars and a parser generator tool,
understand the theory of parsing so that you could implement a parser generator for LL(1), SLR, LR(1), and LALR(1) grammars
be able to construct abstract syntax trees
be able to implement symbol tables
understand and implement non-local variable access
understand dataflow analysis
be able to translate to intermediate code
be able to do Sethi-Ullman register allocation
be able to generate assembly code

Textbook

The textbook for this class is:

Appel

Andrew W. Appel with Jens Palsberg.
Modern Compiler Implementation in Java, second edition.
Cambridge, England: Cambridge University Press, 2002.
ISBN: 052182060-X

Get the second edition, not the first!

We will write a compiler for a subset of Java called MiniJava (see the EBNF grammar). The compiler will produce SPARC assembly code. It really requires very little understading of SPARC architecture and assembly language to write a simple compiler. But there are some details that must be understood. A thorough discussion of these topics can be found in:

Paul

Richard P. Paul.
SPARC Architecture, Assembly Language Programming, and C, second edition.
Upper Saddle River, New Jersey: Prentice-Hall, 2000.
ISBN: 0-13-025596-3

or in Sparc Architecture Standard. You are assumed to have the equivalent of CSE3101 Machine and Assembly Language.

Please get a TRACKS account, if you do not already have one. if you need access to a SPARC computer with GNU development software. It is required to use this environment (though most of the Java development can take place on any platform). You may use ssh to login in remotely to zach.fit.edu to use a SPARC computer.

Warning

This class requires considerable programming. Good time management is required. It is impossible to extend the length of the semester. The compiler must be finished by the end of the semester --- no extensions, no incompletes.

For this reason, a good grade in this class does impress recruiters.

Grades

The numeric scores for the assignments are available on the WWW.

The course grade is determined primarily by the compiler project. Any completed, reasonably functional compiler will earn an 'A' for the course. This is subject to some conditions: a reasonable grade on the midterm, the on-time completion of the milestones, the adherence to the compiler design in the textbook, and following the submission requirements. Failure to meet these conditions makes it difficult to evaluate and assign grades equitably, in such circumstances expect an 'F'.

There will be one midterm test. It will cover scanning and parsing. There will be no final test.

Formal language concepts: context-free grammar, derivations, parse trees, ambiguity. notes on syntax [4-up, pdf]
Converting a regular expression to an NFA. chapter 2 [4-up,pdf]
Converting a NFA to a DFA. chapter 2 [4-up,pdf]
Chapter 3 snapshot
Computing nullable, first and follow
LL parsing algorithm
LL parser construction
LR parsing algorithm
LR(0) parser contstuction
SLR parser contstuction
LR(1) parser contstuction
LALR(1) parser contstuction
The relationship of the grammar classes
Chapter 4 and 5 snapshot
Chapter 6 and 7 snapshot

Calendar and Important Dates

Tuesday, 8 January 2008	first lecture
Friday, 11 January 2008	assignment #1
Monday, 21 January 2008	Martin Luther King Jr. Day (no classes)
Friday, 25 January 2008	assignment #2 Canceled
Friday, 1 February 2008	Lexer, assignment #3
Friday, 8 February 2008	Parser, assignment #4
Monday, 18 February 2008	President's Day (no classes)
Tuesday, 19 February 2008	Midterm Exam
Friday, 29 February 2008	Syntax and Semantics, assignment #5
Friday, XX March 2008	Last day to withdraw
3-7 March, 2003	Spring break (no classes)
Monday, 24 March 2008	Frames and Trees, assignment #6
Friday, 11 April 2008	Instruction Section, assignment #7
Monday, 28 April 2008	Complete Compiler, assignment #8

Syllabus

Week 1

Introduction, software development, what is a compiler

Chapter 1: Introduction

Week 2 and 3

Regular expressions, FSA, NFA, DFA

Chapter 2: Lexical Analysis

Week 4 and 5

Parsing

Chapter 3: Parsing

Week 6

Constructing Syntax Trees

Chapter 4: Abstract Syntax

Week 7

Midterm exam

Week 8

Symbol tables, Type checking

Chapter 5: Semantic Analysis

Week 9

Activation records

Chapter 6: Activation Records

Week 11 and 12

Dataflow Analysis

Chapter 10: Liveness Analysis

Week 13

Chapter 11: Register Allocation