San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Fall Semester 2017

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 403
Section 5 (lab):  Tu 6:00 - 8:45 PM  room ENG 206


# Date Due Assignment
1 Aug 24 Sep 1 Write a Pascal Program

Input: widgets.csv
Output: widgets.out

Sample Pascal program: EmployeeListing.pas
Input file: employees.txt
Output: output.txt
2 Sep 5 Sep 15 Java Scanner

Output: output.txt
3 Sep 19 Oct 2 WHEN statement

Input: when.txt    whenerrors.txt
Some files to change: FilesToChange.pdf
4 Oct 5 Oct 23 New complex type

Standard Pascal program: Complex.pas
Pascal program to compile and run: ComplexBuiltIn.pas
5 Oct 24 Nov 3 ANTLR 4 Grammar
6 Nov 9 Nov 27 Code generation


Date Content
Aug 24 Slides: Goals; compiler as translator; Assignment #1
Aug 29 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
Aug 29 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
Aug 31 Slides: Initial back end classes; first end-to-end test; listening to messages; Pascal token classes
Sep 5 Slides: Basic scanning algorithm; Pascal scanner; Pascal token classes: word, string, number; syntax error handling; Pascal tokenizer; symbol table conceptual design
Sep 5 Lab Slides: 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; Assignment #2
Sep 7 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
Sep 12 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
Sep 12 Lab Slides: Parsing REPEAT and WHILE statements; error synchronization and recovery; Pascal Syntax Checker II; parsing FOR, IF, CASE statements
Sep 14 Slides: Top-down recursive descent parsing; syntax and semantics; control statement executors; executing loops; executing if; Assignment #3
Sep 19 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.
Sep 19 Lab Slides: Constant definitions; type definitions: simple, array, and record; variable declarations; declarations and the symbol table; scope and the symbol table stack; work on Assignment #3
Sep 21 Slides: Type specification interfaces and attributes; string types; type factory; how identifiers are defined; predefined identifiers and types; BlockParser; DeclarationsParser; ConstantDefinitionsParser; type definition structures
Sep 26 Slides: TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser; RecordTypeParser; Pascal multidimensional arrays
Sep 26 Lab 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; work on Assignment #3
Sep 28 Slides: Parsing variables; program header; procedure and function declarations; forward declarations; nested scopes and the symbol stack
Oct 3 Slides: 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
Oct 3 Lab Slides: Runtime memory management; symbol table stack vs. runtime stack; activation records; access to nonlocal variables; runtime display; recursive calls; Assignment #4
Oct 5 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
Oct 10 Slides: Review for the midterm
Oct 10 Lab Work on Assignment #4
Oct 17 Slides: Midterm solutions; minimum acceptable compiler project; deterministic finite automata (DFA); state transition matrix; DFA for Pascal identifiers and numbers; a simple DFA scanner

DFA scanner: SimpleDFAScanner.h    SimpleDFAScanner.cpp    SimpleDFAInput.txt
Oct 17 Lab Slides: BNF; grammars and languages; derivations and productions; EBNF; work on Assignment #4
Oct 19 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
Oct 24 Slides: ANTLR workflow; syntax error handling; resolving ambiguities; ANTLR parse trees; listener interface; Assignment #5

ANTLR listener example: Java.g4    ExtractInterfaceListener.h    ExtractInterfaceListener.cpp    ExtractInterfaceTool.cpp
Oct 26 Slides: Parse tree visitor interface; visitor interface example

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

Pcl compiler: Pcl.g4    sample.pas    CompilerVisitor.h    CompilerVisitor.cpp    Pcl.cpp
Oct 31 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 #5

Jasmin program example: hello.j
Nov 2 Slides: Jasmin assembly 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
Nov 7 Slides: Local variables; code for expressions; javap disassembler; Jasmin instructions for comparisons;
Nov 7 Lab Slides: Code templates for relational expressions, assignment statements, if statements, looping statements, and select statements; work on code generation
Nov 9 Slides: Current status; Pcl2; Jasmin code for select statements; code for procedures and functions

Sample Pcl2 program: sample.pas
Generated Jasmin code: sample.j

Pcl2 compiler, Java version: Pcl2.g4

Pcl2 compiler, C++ version: Pcl2.g4    Pcl2.cpp    Pass1Visitor.h    Pass1Visitor.cpp    Pass2Visitor.h    Pass2Visitor.cpp
Nov 14 Slides: Code for System.out.println(), String.format(), scalar arrays, and subscripted variables; code for non-scalar arrays; code for records and fields
Nov 14 Lab Slides: Code for records and fields; work on code generation
Nov 16 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
Nov 21 Slides: Code generation; instruction selection; register allocation; data flow analysis; instruction scheduling; code optimization: safety, profitability, constant folding, constant propagation
Nov 21 Lab Slides: Strength reduction, dead code elimination, loop unrolling, common subexpression elimination; debugging and optimizing compilers; compiling object-oriented languages
Nov 28 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
Nov 30 Slides: Source-level debugger; machine-level debugger; debugger architecture; back end messages; interprocess communication; integrated development environment (IDE)
Dec 5 Slides: Presentation: Team Mak & Cheese; yacc and lex; course review
Dec 5 Lab Slides: Top-down and bottom-up parsers; shift-reduce parsing

Goals of the course

  1. Compiler construction. Design and build a working compiler for a programming language that you invented. Write sample programs in your language, compile your programs into byte code for the Java Virtual Machine to produce .class files, and then successfully run your programs on the JVM.
  2. Software engineering. Employ the best practices of object-oriented design and team-based software engineering. A compiler is a large, complex program! Managing the development of such a program requires learning skills that are highly desired by employers.

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.