Overview of the Compiler Project

Major Milestones of the Compiler Project

PhaseDescriptionAssignmentDue DateSubmitCreate
Lexical AnalysisAnalyze the characters of the source program and break them into tokens #3 phase02.jar scan.jar
ParsingAnalyze the phrase structure of the source program and ensure it is legal #4 phase03.jar parse.jar
Syntax TreeConvert the source program into an abstract syntax tree #5 phase05.jar check.jar
Semantic AnalysisAnalyze the abstract syntax tree, relate variables to the declarations, check types of expressions
Frame LayoutPrepare machine-dependent activation record #6 phase07.jar translate.jar
IR TranslationTranslation to intermediate-representation trees
CanonicalizeHoist side effects out of expressions, organize basic blocks #7 phase09.jar select.jar
Instruction SelectionGroup the IR-tree nodes so that each corresponds to actual machine instructions
Register AllocationChoose a register to hold each of the variables and temporary values used by the program #8 phase12.jar compile.jar
Emit CodeFinish details concerning procedure entry/exit, insert choosen register into instructions, and write instructions

Compiler Project As Relates to the Textbook

ChapterProjectAssignmentDue DateSubmitCreate
Chapter 2
Lexical Analysis
Lexical Analysis, page 33. #3 phase02.jar scan.jar
Chapter 3
Parsing
Parsing, page 81. #4 phase03.jar parse.jar
Chapter 4
Abstract Syntax
Abstract Syntax, page 101. #5 phase05.jar check.jar
Chapter 5
Semantic Analysis
Type Checking, page 114.
Chapter 6
Activation Records
Frames, page 132. #6 phase07.jar translate.jar
Chapter 7
Translation to Intermediate Code
Translation to Trees, page 159.
Chapter 8
Basic Blocks and Traces
Basic Blocks and Traces. #7 phase09.jar select.jar
Chapter 9
Instruction Selection
Instruction Selection, page 197.
Chapter 10
Liveness Analysis
Constructing Flow Graphs, page 217.  
Liveness, page 217.
Chapter 11
Register Allocation
Graph Coloring, page 244. #8 phase12.jar compile.jar
Chapter 12
Putting It All Together
Procedure Entry/Exit, page 270.
Making It Work, page 252.

Compiler Output

The file, e.g., some/dir/Factorial.java, is the one and only argument to the compiler.
java -jar compile.jar some/dir/Factorial.java
Without an argument the compiler should print an error message to the standard error stream. In all cases, the standard input stream is ignored by the compiler. All input to the compiler comes from the one file (and the one command line argument).

Every phase of the compiler should always print a message of the following form to the standard output stream:

filename=some/dir/Factorial.java, errors=0
If there are no errors, then there should be no output on the standard error stream. If there is output on the standard error stream, then errors should be greater than zero.

Compiler errors and warnings (if any) should appear only on the standard error stream, and have the following form:

Factorial.java:014.037:  Unary 'not' operator not applied to an expression of type boolean.
The filename, line number, and character number of the line appear at the beginning of every error message. Error messages can be more than one line long.

If there are no errors, the compiler should produce a file suitable as input to the assembler. This file has the same name as the input file, but with the extension .s. So, in the case of the input file Factorial.java, the output file will have the name Factorial.s. In the case of the input file some/dir/Factorial.java, the output file will have the name some/dir/Factorial.s. It would be convenient if this file had your name in comment as the first line.

The compiler can be invoked with the verbose option:

java -Dverbose -jar compile.jar Factorial.java

In this case a phase-specific file may also be written. The table below is a brief overview of the verbose output for the source program Factorial.java from Appel's testcases. Beginning with phase 9 the .s output file needs to be written.

Chapter-D FilenameVerbose OutputFactorial.s
Chapter 2
Lexical Analysis
Factorial-02.txt List of recognized tokens (not yet)
Chapter 3
Parsing
Factorial-03.txt Parsing trace (not yet)
Chapter 4
Abstract Syntax
Factorial-04.txt Pretty print AST (not yet)
Chapter 5
Semantic Analysis
Factorial-05.txt Symbol table (not yet)
Chapter 6
Activation Records
  (nothing) (not yet)
Chapter 7
Translation to Intermediate Code
Factorial-07.txt Pretty print IR tree (not yet)
Chapter 8
Basic Blocks and Traces
Factorial-08.txt Pretty print IR tree (after linearization) (not yet)
Chapter 9
Instruction Selection
  (nothing) Psuedo assembly code
Chapter 10
Liveness Analysis
Factorial-10.txt Interference graph Same psuedo assembly code
Chapter 11
Register Allocation
Factorial-11.txt Map of temporaries Same psuedo assembly code
Chapter 12
Putting It All Together
  (nothing) Final assembly code