San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Spring Semester 2019

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 1 (class):  TuTh  4:30 - 5:20 PM  room BBC 320
Section 2 (lab):  Tu 6:00 - 8:45 PM  room ENG 206
Section 3 (lab):  Th 6:00 - 8:45 PM  room ENG 206


# Date Due Assignment
1 Jan 25 Feb 1 Write Pascal Programs

Sample Pascal program: EmployeeListing.pas
Input file: employees.txt
Output: output.txt
2 Feb 5 Feb 15 C++ Scanner

3 Feb 14 Mar 4 WHEN statement

Input: when.txt    whenerrors.txt
4 Feb 28 Mar 13 New built-in complex type

Input: ComplexAssignments.txt
5 Mar 26 Apr 17 ANTLR 4 Grammar

Sample grammar file: Pcl.g4
Sample main program: Pcl.cpp
Sample source file: sample.pas
Sample main output: Pcl.output.txt
6 Apr 18 May 1 Code generation

Runtime library: PascalRTL.jar


Week Date Content
1 Jan 24 Slides: Goals; course learning outcomes; project teams; grading; postmortem assessment report; overview of the compilation process; compiler as translator; Assignment #1
2 Jan 29 Slides: Interpreters; compiler vs. interpreter; key steps for success; Java packages; class relationships; abstract parser and scanner classes; token and source classes; currentChar() vs. nextChar(); messages;
Jan 31 Slides: Initial Pascal-specific parser and scanner; token class; factory classes; initial back end classes; first end-to-end test; Pascal token classes
3 Feb 5 Slides: Basic scanning algorithm; Pascal scanner; Pascal token classes: word, string, number; syntax error handling
Feb 7 Slides: Pascal tokenizer; Assignment #2; symbol table conceptual design; symbol table interfaces; symbol table factory class; symbol table and symbol table stack implementation; Symbol table entries; cross-reference listing; statement syntax diagrams
4 Feb 12 Slides: statement syntax diagrams; parse tree conceptual design; syntax diagrams: Pascal statements and expressions; parse tree: conceptual design, basic operations, implementation, buildingPascal expression syntax; precedence rules; example expression decomposition; parsing expressions; Parsing expressions; printing parse trees; Pascal Syntax Checker I
Feb 14 Slides: Parsing REPEAT and WHILE statements; error synchronization and recovery; Pascal Syntax Checker II; parsing FOR and IF statements; Assignment #3
5 Feb 19 Slides: Temporary hacks; statement and expression executor classes; executing compound statements, assignment statements, and expressions; runtime error handling; Simple Interpreter I; parsing CASE statements; top-down recursive descent parsing; syntax and semantics; control statement executors; executing loops

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 21 Slides: Executing if and CASE statements; parsing declarations; syntax diagrams for Pascal declarations; constant definitions; type definitions: simple, array, and record; variable declarations
6 Feb 26 Slides: Variable declarations; declarations and the symbol table; scope and the symbol table stack; type specification interfaces and attributes; string types; type factory; how identifiers are defined; predefined identifiers and types; BlockParser; DeclarationsParser; ConstantDefinitionsParser
Feb 28 Slides: Type definition structures; TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser; RecordTypeParser; Assignment #4; Pascal multidimensional arrays; variable declarations
7 Mar 5 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
Mar 7 Slides: Program header; procedure and function declarations; forward declarations; 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
8 Mar 12 Slides: The interpreter; runtime memory management; symbol table stack vs. runtime stack; activation records; access to nonlocal variables; recursive calls; allocating and initializing activation records; passing parameters during a call; procedure and function call classes; runtime error checking; execute entire Pascal programs; review for the midterm
9 Mar 19 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
Mar 21 Slides: BNF; grammars and languages; derivations and productions; EBNF; 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    input.txt
10 Mar 26 Slides: ANTLR workflow; syntax error handling; resolving ambiguities; ANTLR parse trees; Pcl; Assignment #5; listener interface

Pcl compiler: Pcl.g4    Pcl.cpp    Pcl.cpp    sample.pas

ANTLR listener example: Java.g4    ExtractInterfaceListener.h    ExtractInterfaceListener.cpp    ExtractInterfaceTool.cpp
Mar 28 Slides: Parse tree listener interface; visitor interface; visitor interface example; grammar requirements for Assignment #5

ANTLR visitor example: LabeledExpr.g4    t.expr    EvalVisitor.h    EvalVisitor.cpp    Calc.cpp
11 Apr 9 Slides: Pcl; Pcl.g4; Pcl syntax diagrams; Pcl compiler Java code; Pcl compiler C++ code; interpreter vs. compiler; target machines; Java Virtual Machine (JVM) architecture; JVM runtime stack and stack frame

Pcl compiler: Pcl.g4    sample.pas
Apr 11 Slides: JVM instructions; 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

Jasmin program example: hello.j
Jasmin multiply engine: MultiplyEngine.j
12 Apr 16 Slides: Code for procedures and functions; local variables; code for expressions; javap disassembler; Jasmin instructions for comparisons; code templates for relational expressions, assignment statements, if statements; current status
Apr 18 Slides: Newton's Square Root example; Pcl2; code generation in two tree vists; Assignment #6; Jasmin code for looping statements, select statements, and procedures and functions; call System.out.print() and System.out.printf()

Pcl2 compiler: Pcl2Cpp.g4    sample.pas    sample.j
13 Apr 23 Slides: invokestatic vs. invokevirtual; Code for System.out.println(), String.format(), scalar arrays, and subscripted variables; code for non-scalar arrays; code for records and fields
Apr 25 Slides: Code for records and fields; 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

Free compiler book: Understanding and Writing Compilers
Parameter passing: parmswrap.pas   parmsclone.pas   parmsbad.pas
Performance tester: hilbert2.pas
14 Apr 30 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; debugging and optimizing compilers; compiling object-oriented languages
May 2 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
15 May 7 Slides: Context-free and context-sensitive grammars; top-down and bottom-up parsers; shift-reduce parsing; yacc and lex

Example grammar: calc.l   calc.y
May 9 Slides: Team presentations


Dates Activities
Jan 24, 29 Slides: Assignment #1: Write simple Pascal programs
Jan 31, Feb 5 Slides: Install development environment; compile and run Chapter2cpp sources
Feb 7, 12 Slides: Work on Assignment #2: C++ Scanner
Feb 14, 19 Slides: Complete Assignment #2; start Assignment #3: WHEN Statement
Feb 21, 26 Slides: Complete Assignment #3: WHEN Statement
Feb 28, Mar 5 Slides: Work on Assignment #4: New Built-in Complex Type
Mar 7, 12 Slides: Complete Assignment #4: New Built-in Complex Type
Mar 26 - Apr 16 Slides: Assignment #5: ANTLR 4 Grammar
Apr 23 - 30 Slides: Assignment #6: Code Generation

Goals of the course

This course will concentrate on practical aspects of compiler construction, programming language design, and engineering a large, complex software application.

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
Source files

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

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.

Online Pascal development sites