San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Department of Computer Science
Department of Applied Data Science
Spring Semester 2020

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

CMPE 152: Compiler Design

Section 1:  TuTh  3:00 - 4:15 PM  room ENG 337

Lab Assignments

# Date Due Assignment
1 Jan 28 Feb 4 Write Simple Pascal Programs

Assignment input file: presidents.txt
Solutions: HelloWorld.pas   ListMerge.pas   Presidents.pas

Sample Pascal program: EmployeeListing.pas
Sample program input file: employees.txt
Sample program output: output.txt
2 Feb 4 Feb 14 New Pascal Tokens

Input: LoopTest.pas

Extra-credit input: arrow.txt
Extra-credit output: arrow.out.txt
3 Feb 11 Feb 21 LOOP AGAIN statement

Input: LoopTest.txt    LoopErrors.txt
4 Feb 20 Mar 2 Execute the LOOP AGAIN statement

Input: LoopTest2.txt
Sample output: LoopTest2.out.txt
5 Mar 3 Mar 16 New built-in complex type

Input: ComplexAssignments.txt
Sample output: complex.out.txt
6 Mar 24 Apr 10 ANTLR 4 Grammar

Sample grammar file: Pcl1.g4
Sample main program: Pcl1.cpp
Sample source file: sample1.pas
Sample main output: Pcl1.output.txt
7 Apr 16 Apr 27 Code generation

Runtime library: PascalRTL.jar


Week Date Content
1 Jan 23 Slides: Goals; course learning outcomes; project teams; grading; postmortem assessment report; overview of the compilation process; compiler as translator; Pascal tutorials
2 Jan 28 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

Lab: Assignment #1
Jan 30 Slides: Initial Pascal-specific parser and scanner; token class; factory classes; initial back end classes; first end-to-end test

Lab: Assignment #1, cont'd
3 Feb 4 Slides: Basic scanning algorithm; Pascal scanner; Pascal token classes: word, string, number; syntax error handling; Pascal tokenizer

Lab: Assignment #2
Feb 6 Slides: Symbol table conceptual design; symbol table interfaces; symbol table factory class; symbol table and symbol table stack implementation; Symbol table entries; cross-reference listing

Lab: Assignment #2, cont'd
4 Feb 11 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; printing parse trees; Pascal Syntax Checker I

Lab: Assignment #3
Feb 13 Slides: Parsing REPEAT statements; error synchronization and recovery; Pascal Syntax Checker II; parsing FOR and IF statements

Lab: Assignment #3, cont'd
5 Feb 18 Slides: Top-down recursive descent parsing; temporary hacks; statement and expression executor classes; executing compound statements, assignment statements, and expressions; runtime error handling; Simple Interpreter I

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.

Lab: Assignment #3, cont'd
Feb 20 Slides: syntax and semantics; control statement executors; executing loops Executing if and CASE statements; parsing declarations; syntax diagrams for Pascal declarations; constant definitions; simple type definitions

Lab: Assignment #4
6 Feb 25 Slides: Pascal array and record type definitions; 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

Lab: Assignment #4, cont'd
Feb 27 Slides: BlockParser; DeclarationsParser; ConstantDefinitionsParser; type definition structures; TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser
7 Mar 3 Slides: RecordTypeParser; Pascal multidimensional arrays; variable declarations; 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; Assignment #5
Mar 5 Slides: Type checking the IF statement; parsing variables; program header; procedure and function 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 10 Video recording
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 17 Video recording
Slides: Midterm solutions; minimum acceptable compiler project; deterministic finite automata (DFA); state transition matrix; DFA for Pascal identifiers and numbers; a simple DFA scanner; tips on Assignment #5

DFA scanner: SimpleDFAScanner.h    SimpleDFAScanner.cpp    SimpleDFAInput.txt
Mar 19 Video recording
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; postmortem report

ANTLR example: Expr.g4    ExprMain.cpp    input.txt
10 Mar 24 Video recording
Slides: ANTLR workflow; syntax error handling; resolving ambiguities; ANTLR parse trees; Pcl1; Assignment #6

Pcl compiler with grammar:
Syntax diagrams
Mar 26 Video recording
Slides: Parse tree listener interface; visitor interface; visitor interface example; grammar requirements for Assignment #6

ANTLR visitor example: LabeledExpr.g4    input.txt    EvalVisitor.h    EvalVisitor.cpp    Calc.cpp
11 Apr 7 Video recording
Slides: Pcl2; Pcl2.g4; Pcl2 syntax diagrams; Pcl2 compiler Java code; Pcl2 compiler C++ code; interpreter vs. compiler; target machines; Java Virtual Machine (JVM) architecture; JVM runtime stack and stack frame; JVM instructions; Jasmin assembly instructions

Pcl compiler with symbol table:
Jasmin program example: hello.j
Apr 9 Video recording
Slides: Jasmin assembly instructions: shortcuts, local variables, load and store, arithmetic, other instructiions; code templates; compilation strategy; Jasmin type descriptors; Pascal program; program fields; main program; loading and storing program variables; dode for procedures and functions; local variables; code for expressions
12 Apr 14 Video recording Password E9#j5?$I
Slides: javap disassembler; Jasmin instructions for comparisons; code templates for relational expressions, assignment statements, if statements; Pcl3; current status

Pcl compiler with code generation:
Aor 16 Video recording Password R4$7F#80
Slides: Pcl3; pass 1 symbol table and data types; pass2 code generation; code for IF statement and REPEAT statement; Newton's Square Root example; SELECT statemen; procedures and functions; main program; function call; call System.out.print() and System.out.printf(); Assignment #7

Pcl compiler with print statements:
13 Apr 21 Video recording Password 9i+*VP78
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 23 Video recording Password 3P*0@3=$
Slides: 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   hilbert2.j
14 Apr 28 Video recording Password 5n+@M35*
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; extra credit presentations
Apr 30 Video recording Password 4W?*6M0@
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; project demo
15 May 5 Video recording Password 6Y%f4B8G
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 7 Team presentations

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.

Course Learning Outcomes (CLO)


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

Source codes

Source codes from the Writing Compilers and Interpreters textbook, in both the original Java and ported to C++, are available for download at .

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

You can edit, compile, and run Pascal programs online.