San Jose State University : Site Name

Navigation

Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Fall Semester 2018

Office hours: TuTh: 3:00-4:00 PM
Office location: ENG 250
E-mail: ron.mak@sjsu.edu
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 ENG 343
Section 2 (lab):  Tu 6:00 - 8:45 PM  room ENG 206
Section 3 (lab):  Th 6:00 - 8:45 PM  room ENG 206


Assignments

# Date Due Assignment
1 Aug 21 Aug 29 Write Pascal Programs

Sample Pascal program: EmployeeListing.pas
Input file: employees.txt
Output: output.txt

Sample solution #1: HelloWorld.pas
Sample solution #2: SortArray.pas    SortArray.out.txt
Sample solution #3: Presidents.pas    Presidents.out.txt
2 Aug 30 Sep 12 C++ Scanner

Input: cpptest.in
3 Sep 11 Sep 28 WHEN statement

Input: when.txt    whenerrors.txt
4 Sep 27 Oct 8 New complex type

Input: ComplexAssignments.txt
5 Oct 23 Nov 2 ANTLR 4 Grammar

Sample grammar file: Pcl.g4
Sample source file: sample.pas
Sample main output: Pcl.output.txt
6 Nov 8 Nov 28 Code generation

Runtime library: PascalRTL.jar

Lectures

Week Date Content
1 Aug 21 Slides: Goals; course learning outcomes; project teams; grading; postmortem assessment report; overview of the compilation process; compiler as translator; Assignment #1
Aug 23 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 Slides: Pascal programming workshop
2 Aug 28 Slides: Initial Pascal-specific parser and scanner; token class; factory classes; initial back end classes; first end-to-end test; Pascal token classes
Aug 30 Slides: Basic scanning algorithm; Pascal scanner; Pascal token classes: word, string, number; syntax error handling; Pascal tokenizer; Assignment #2; symbol table conceptual design; symbol table interfaces; symbol table factory class; symbol table and symbol table stack implementation
Lab Slides: Install development environment; compile and run Chapter2cpp sources
3 Sep 4 Slides: Symbol table entries; what to store in each entry; cross-reference listing; statement syntax diagrams; parse tree conceptual design; syntax diagrams: Pascal statements and expressions; parse tree: conceptual design, basic operations, implementation, building
Sep 6 Slides: Pascal expression syntax; precedence rules; example expression decomposition; parsing expressions; 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
Lab Slides: Work on Assignment #2
4 Sep 11 Slides: Parsing REPEAT and WHILE statements; error synchronization and recovery; Pascal Syntax Checker II; parsing FOR and IF statements; Assignment #3
Sep 13 Slides: Parsing CASE statements; top-down recursive descent parsing; syntax and semantics; control statement executors; executing loops; executing if and CASE statements

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 Slides: Work on Assignment #3
5 Sep 18 Slides: Multipass compilers; parsing declarations; syntax diagrams for Pascal declarations; constant definitions; type definitions: simple, array, and record; variable declarations; declarations and the symbol table; scope and the symbol table stack;
Sep 20 Slides: type specification interfaces and attributes; string types; type factory; how identifiers are defined; predefined identifiers and types; BlockParser; DeclarationsParser; ConstantDefinitionsParser
Lab Slides: Work on Assignment #3
6 Sep 25 Slides: Type definition structures; TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser; RecordTypeParser; Pascal multidimensional arrays
Sep 27 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; Assignment #4
Lab Slides: Finish Assignment #3
7 Oct 2 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
Oct 4 Slides: The interpreter; compile time vs. run time; 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; memory management classes
Lab Slides: Assignment #4
8 Oct 9 Slides: Procedure and function call classes; runtime error checking; execute entire Pascal programs; review for the midterm
9 Oct 16 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 18 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    t.expr
Lab Slides: Install ANTLR 4
10 Oct 23 Slides: ANTLR workflow; syntax error handling; resolving ambiguities; ANTLR parse trees; listener interface; Assignment #5

ANTLR listener example: Java.g4    Demo.java    ExtractInterfaceListener.h    ExtractInterfaceListener.cpp    ExtractInterfaceTool.cpp
Oct 25 Slides: Some useful scripts; parse tree visitor interface; visitor interface example; grammar requirements for Assignment #5

ANTLR visitor example: LabeledExpr.g4    t.expr    EvalVisitor.h    EvalVisitor.cpp    Calc.cpp
Lab Slides: Work on Assignment #5
11 Oct 30 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    PclCpp.zip
Nov 1 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    MultiplyTester.java
Lab Slides: Work on Assignment #5
12 Nov 6 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
Nov 8 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    Pcl2Cpp.zip
Lab Slides: Work on ANTLR 4 grammar
13 Nov 13 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
Nov 15 Smoked out. No class.
Lab Slides: Work on Assignment #6
14 Nov 20 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

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

Free compiler book: Understanding and Writing Compilers
Lab Slides: Work on Assignment #6
15 Nov 27 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
Nov 29 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
Lab Slides: Work on Assignment #6
16 Dec 4 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
Dec 6 Slides: Review for the final exam

Presentations: Pepe, Pied Piper, SSD, The Kool Krab
Lab Slides: Complete the compiler project

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.

Prerequisites

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
http://www.antlr.org/

ANTLR 4 C++ .h files and runtime libraries for Windows 10:
antlr4-cpp-runtime-4.7-Windows10.zip

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

http://rextester.com/l/pascal_online_compiler
https://www.tutorialspoint.com/compile_pascal_online.php
https://www.jdoodle.com/execute-pascal-online