San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Spring Semester 2018

Office hours: TuTh: 3:00-4:00 PM
Office location: ENG 250
Mission Control, Jet Propulsion Laboratory (JPL)
NASA Mars Exploration Rover Mission

CMPE 152: Compiler Design

Section 4 (seminar):  TuTh  4:30 - 5:20 PM  room ENG 325
Section 5 (lab):  Tu 6:00 - 8:45 PM  room ENG 206


# Date Due Assignment
1 Jan 25 Feb 2 Write a Pascal Program


Sample Pascal program: EmployeeListing.pas
Input file: employees.txt
Output: output.txt
2 Feb 6 Feb 19 Java Scanner

Output: output.txt
3 Feb 13 Feb 28 WHEN statement

Input: when.txt    whenerrors.txt
4 Feb 27 Mar 7 New complex type

Test input file: ComplexAssignments.txt
5 Mar 5 Mar 23 Execute complex arithmetic

Standard Pascal program: Complex.pas
Pascal program with built-in complex type to compile and run: ComplexBuiltIn.pas
6 Apr 3 Apr 16 ANTLR 4 Grammar
7 Apr 19 May 4 Code generation

Runtime library: PascalRTL.jar


Date Content
Jan 25 Slides: Goals; course learning outcomes; project teams; grading; postmortem assessment report; overview of the compilation process; compiler as translator; Assignment #1
Jan 30 Slides: Definitions; conceptual designs; parser; scanner; token; front end; intermediate tier; backend; intermediate code; symbol table; code generator; interpreters; compiler vs. interpreter; key steps for success
Jan 30 Lab Slides: C++ namespaces; class relationships; abstract parser and scanner classes; token and source classes; current_char() vs. next_char(); messages; initial Pascal-specific parser and scanner; token class; factory classes; Pascal programming workshop
Feb 1 Slides: Initial back end classes; first end-to-end test; listening to messages; Pascal token classes
Feb 6 Slides: Symbol table conceptual design; symbol table interfaces; symbol table factory class; symbol table and symbol table stack implementation; symbol table entries; what to store in each entry; cross-reference listing;
Feb 6 Lab Slides: Basic scanning algorithm; Pascal scanner; Pascal token classes: word, string, number; syntax error handling; Pascal tokenizer; Assignment #2
Feb 8 Slides: Statement syntax diagrams; parse tree conceptual design; syntax diagrams: Pascal statements and expressions; parse tree: conceptual design, basic operations, implementation, building; Pascal precedence rules; example expression decomposition; parsing expressions
Feb 13 Slides: Parsing expressions; printing parse trees; Pascal Syntax Checker I; temporary hacks; statement and expression executor classes; executing compound statements, assignment statements, and expressions; runtime error handling; Simple Interpreter I; parsing REPEAT and WHILE statements; error synchronization and recovery; Pascal Syntax Checker II
Feb 13 Lab Slides: Parsing REPEAT and WHILE statements; error synchronization and recovery; Pascal Syntax Checker II; parsing FOR, IF, CASE statements
Feb 15 Slides: Top-down recursive descent parsing; syntax and semantics; control statement executors; executing loops; executing if; Assignment #3
Feb 20 Slides: Executing CASE statements; multipass compilers; parsing declarations; syntax diagrams for Pascal declarations; constant definitions; type definitions: simple, array, and record; variable declarations

An article about the FORTRAN compiler for the IBM 1401 computer system. The compiler made 63 passes and ran in 8K of memory; each pass had at most 300 instructions! Assembly language source code of the compiler. Just read the comments for enlightenment.
Feb 20 Lab Slides: Work on Assignment #3
Feb 22 Slides: Declarations and the symbol table; scope and the symbol table stack; type specification interfaces and attributes; string types; type factory; how identifiers are defined; Type specification interfaces and attributes; string types; type factory; how identifiers are defined; predefined identifiers and types; BlockParser;
Feb 27 Slides: DeclarationsParser; ConstantDefinitionsParser; type definition structures TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser
Feb 27 Lab Slides: Parsing Pascal arrays; parsing Pascal records; Assignment #4
Mar 1 Slides: Parsing variables with subscripts and fields; type checking; adding type information to parse tree nodes; assignment and comparison compatible; type checking expressions and control statements; parsing variables; program header; procedure and function declarations; forward declarations
Mar 6 Slides: Nested scopes and the symbol stack; parsing programs, procedures, and functions; parsing calls to procedures and functions; class Predefined; formal and actual parameters; parsing calls to the standard routines; parse entire Pascal programs; the interpreter; compile time vs. run time; runtime memory management; symbol table stack vs. runtime stack; activation records; access to nonlocal variables
Mar 6 Lab Slides: The interpreter; compile time vs. run time; runtime memory management; symbol table stack vs. runtime stack; activation records; access to nonlocal variables; runtime display; recursive calls; Assignment #5
Mar 8 Slides: Allocating and initializing activation records; passing parameters during a call; memory management classes; procedure and function call classes; runtime error checking; execute entire Pascal programs; tips for Assignment #5
Mar 13 Slides: Review for the midterm
Mar 13 Lab Work on Assignment #5
Mar 20 Slides: Midterm solutions; minimum acceptable compiler project; deterministic finite automata (DFA); state transition matrix; DFA for Pascal identifiers and numbers; a simple DFA scanner

Midterm solution
DFA scanner: SimpleDFAScanner.h    SimpleDFAScanner.cpp    SimpleDFAInput.txt
Mar 20 Lab Slides: BNF; grammars and languages; derivations and productions; EBNF; work on Assignment #5
Mar 22 Slides: Compiler-compilers; ANTLR 4; ANTLR lexer; ANTLR grammar file; Java and C++ main programs; Java and C++ command lines; compiler team project; project deliverables; post mortem report

ANTLR example: Expr.g4    ExprMain.cpp    t.expr
Apr 3 Slides: ANTLR workflow; syntax error handling; resolving ambiguities; ANTLR parse trees; listener interface; Assignment #6

ANTLR listener example: Java.g4    ExtractInterfaceListener.h    ExtractInterfaceListener.cpp    ExtractInterfaceTool.cpp
Apr 3 Lab Slides: Complete Assignment #5; download and install ANTR 4 and its Eclipse plugin; work on Assignment #6
Apr 5 Slides: Parse tree visitor interface; visitor interface example

ANTLR 4 and C++
ANTLR visitor example: LabeledExpr.g4    t.expr    EvalVisitor.h    EvalVisitor.cpp    Calc.cpp
Apr 10 Slides: Pcl; Pcl.g4; Pcl syntax diagrams; Pcl compiler Java code; Pcl compiler C++ code; interpreter vs. compiler; target machines;

Pcl compiler:
Apr 10 Lab Slides: Java Virtual Machine (JVM) architecture; JVM runtime stack and stack frame; JVM instructions; Jasmin assembler; Jasmin assembly instructions; loading constants; local variables; load and store instructions; work on Assignment #6

Jasmin program example: hello.j
Apr 12 Slides: Jasmin arithmetic and other instructions; using Java to test Jasmin code; code templates; compilation strategy; Jasmin type descriptors; Pascal program, program fields, main program; loading and storing program variables; code for procedures and functions

Jasmin multiply engine: MultiplyEngine.j
Apr 17 Slides: Local variables; code for expressions; javap disassembler; Jasmin instructions for comparisons
Apr 17 Lab Slides: Code templates for relational expressions, assignment statements, if statements, looping statements, and select statements; work on code generation; fix remaining ANTLR Windows problems
Apr 19 Slides: Current status; Pcl2; Assignment #7; Jasmin code for procedures and functions

Pcl2 compiler, Java version: Pcl2.g4
Pcl2 compiler, C++ version:
Generated Jasmin code: sample.j
Sample Pcl2 program: sample.pas
Apr 24 Slides: Code for System.out.println(), System.out.printf(); Jasper disassembler; code for scalar arrays, subscripted variables; code for non-scalar arrays

Jasper disassembler: jasper.jar
Apr 24 Lab Slides: Code for records and fields; work on Assignment #7
Apr 26 Slides: JavaCC error handling with synchronization; Pascal runtime library; passing parameters by value and by reference; wrapping scalars; cloning arrays; compiling Wolf Island and Hilbert; compiled code vs. interpreted code speed comparison

Parameter passing: parmswrap.pas   parmsclone.pas   parmsbad.pas
Performance tester: hilbert2.pas

Free compiler book: Understanding and Writing Compilers
May 1 Slides: Code generation; instruction selection; register allocation; data flow analysis; instruction scheduling; code optimization: safety, profitability, constant folding, constant propagation, strength reduction, dead code elimination, loop unrolling, common subexpression elimination
May 1 Lab Slides: debugging and optimizing compilers; compiling object-oriented languages; work on Assignmenht #7
May 3 Slides: Static and dynamic scoping; runtime memory management; Java command-line arguments; heap management; garbage collection algorithms: reference counting, mark and sweep, stop and copy, generational; aggressive heap management; garbage collection research
May 8 Slides: Source-level debugger; machine-level debugger; debugger architecture; back end messages; interprocess communication; integrated development environment (IDE); top-down and bottom-up parsers; shift-reduce parsing; yacc and lex
May 8 Lab Slides: Course review; work on compilers

Goals of the course

You will have the unique opportunity to invent a programming language, define its grammar, create a compiler for it, and then successfully compile and run programs written in your new language.

This is a challenging course that will demand much of your time
and effort throughout the semester


Department policy is to enforce
all course prerequisites strictly

CMPE 102 Assembly language programming grade C- or better
CMPE 126 Algorithms and data structure design grade C- or better

Required books

Writing Compilers and Interpreters, 3rd edition
Ronald Mak
Wiley Publishing, Inc., 2009
ISBN: 978-0-470-17707-5
Source files
The Definitive ANTLR 4 Reference, 2nd edition
Terence Parr
Pragmatic Bookshelf, 2012
ISBN: 978-1934356999

ANTLR 4 C++ .h files and runtime libraries for Windows 10:

Online Pascal tutorials

Pascal Tutorial  looks very good. It has an online Pascal compiler.
Learn Pascal  also looks good, although it doesn't appear to cover set types.