San Jose State University : Site Name

Navigation

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
E-mail: ron.mak@sjsu.edu
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

Lectures

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; Pcl; Assignment #6

Pcl compiler: Pcl.g4    sample1.pas    Pcl1.cpp
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 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: Pcl2Cpp.zip
Jasmin program example: hello.j

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)

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/

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 http://www.cs.sjsu.edu/~mak/CMPE152/sources .

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.
http://rextester.com/l/pascal_online_compiler
https://www.tutorialspoint.com/compile_pascal_online.php
https://www.jdoodle.com/execute-pascal-online