CMPE152-170502Lab.pptx Prof. Mak: CMPE 152 Compiler Design

San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Spring Semester 2017

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

CMPE 152 Compiler Design

Section 4 (seminar):  TuTh  10:30 - 11:20 AM  room ENG 303
Section 5 (lab):  Tu 1:30 -   4:20 PM  room ENG 405


# Date Due Assignment
1 Jan 31 Feb 7 Write a Pascal Program

Input: widgets.csv
Output: widgets.out
2a Feb 7 Feb 14 Java Scanner

Output: output.txt
2b Feb 7 Feb 24 Deterministic Finite Acceptors (DFAs)

3 Feb 21 Mar 3 LOOP AGAIN statement

Suggested solution:
4 Mar 7 Apr 7 New built-in complex type

Suggested solution:
6 Apr 4 Apr 14 JavaCC Parser
7 Apr 13 Apr 25 JJTree parse trees


Date Content
Jan 26 Slides: Goals; compiler as translator; definitions; overview; conceptual designs; parser; scanner; token; front end; intermediate tier; backend; intermediate code; symbol table; code generator; compiler project; grading
Jan 31 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;

Sample Pascal program:
factorial.pas  factorial.j (Jasmin assembly language object program)
Feb 2 Slides: Initial Pascal-specific parser and scanner; token class; factory classes; initial back end classes; first end-to-end test Pascal tokens; Pascal token classes; syntax diagrams; how to scan for tokens; basic scanning algorithm
Feb 7 Slides: Syntax error handling; Pascal tokenizer; symbol table conceptual design; symbol table interfaces; symbol table factory class; symbol table and symbol table stack implementation
Feb 9 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; Pascal precedence rules; example expression decomposition; parsing expressions
Feb 14 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
Feb 16 Slides: Parsing FOR, IF, and CASE statements; top-down recursive descent parsing; syntax and semantics;
Feb 21 Slides: Executing IF 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.
Feb 23 Slides: 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; type definition structures
Feb 28 Slides: TypeDefinitionsParser; TypeSpecificationParser; SimpleTypeParser; SubrangeTypeParser; EnumerationTypeParser; RecordTypeParser; Pascal multidimensional arrays
Mar 2 Slides: Parsing variables with subscripts and fields; adding type information to parse tree nodes; program header; procedure and function declarations
Mar 7 Slides: Nested scopes and the symbol table stack; 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
Mar 9 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
Mar 14 Slides: Review for the midterm
Mar 21 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:    SimpleDFAInput.txt
Mar 23 Slides: JavaCC parser specification; production rule methods; choice conflicts; left factoring;

Example .jj files:
phone.jj   phone_method_param.jj   phone_choice.jj   phone_left_factored.jj  
Apr 4 Slides: Backtracking; lookahead; left recursion; iteration; right recursion; JJDoc; JJTree; calculator example

Example .jj and .jjt files:
phone_lookahead.jj   expression_left_recursion.jj   expression_iteration.jj   expression_right_recursion.jj calculator_simple.jj   calculator_tree.jjt   calculator_tree_image.jjt   calculator_calculating.jjt  
Apr 6 Slides: Syntax error handling with JavaCC; token errors; synchronize the parser; repair the parse tree; target machines; JVM architecture; runtime stack and stack frame

Sample .jj and .jjt files:
logo_tokenizer.jj   logo_skip_chars.jj   logo_synchronize.jj   logo_tree_recover.jjt
Apr 11 Slides: JVM instructions; Jasmin assembler; example Jasmin program

Sample .j file: hello.j
Apr 13 Slides: Local variables; expressions; javap disassembler; Jasmin instructions for comparisons; code templates for relational expressions, assignment statements, if statements
Apr 18 Slides: Assignment #4 solution; looping statements, and select statements; Jasmin code for procedures and functions
Apr 20 Slides: Code for non-scalar arrays; code for records and fields
Apr 25 Slides: JavaCC error handling with synchronization; Pascal runtime library

Free compiler book: Understanding and Writing Compilers
Apr 27 Slides: Code generation; instruction selection; register allocation; data flow analysis; instruction scheduling; code optimization: safety, profitability
May 2 Slides: Introduction to code optimization: better code, safety, profitability; constant folding; constant propagation; strength reduction; dead code elimination, loop unrolling; common subexpression elimination; debugging and optimizing compilers; compiling object-oriented languages; static and dynamic scoping; Java command-line arguments; runtime heap management
May 4 Slides: garbage collection algorithms: reference counting, mark and sweep, stop and copy, generational; aggressive heap management; garbage collection research; compiler projects
May 9 Slides: Context-free and context-sensitive grammars; top-down parsers; bottom-up parsers
May 11 Slides: Shift-reduce parsing example; why bottom-up?; yacc and lex; simple interpretive calculator; LL and LR parsers

Example yacc and lex files (simple calculator): calc.y   calc.l
May 16 Slides: Command-line debugger; GUI-based IDE; review for the final examination


Date Content
Jan 31 Slides: Pascal language; Lazarus; Hello World program;

Sample Pascal programs:
HelloOnce.pas  HelloMany.pas concordance.pas
Feb 7 Slides: How to scan for tokens; basic scanning algorithm; Pascal scanner and token classes: word, string, and number; Assignment #2a; Noam Chomsky; language game; basic terms; string examples; example languages; string concatenation; languages are sets; rules of a language; automata; control unit; transition function; configuration; acceptors and transducers; deterministic vs. nondeterministic; deterministic acceptors; DFA examples; JFLAP demo; Assignment #2b
Feb 14 Slides: Simple Interpreter I; Pascal control statements; statement parser classes; parsing REPEAT and WHILE statements; synchronization and error recovery; Pascal Syntax Checker II
Feb 21 Slides: Assignment #2.a output; executing CASE statements; jump tables and jump caches; executing REPEAT, WHILE, and FOR IF statements;Assignment #3: LOOP AGAIN statement
Feb 28 Slides: ArrayTypeParser; VariableDeclarationsParser; type checking; assignment compatible; comparison compatible; type checking expressions and control statements
Mar 7 Slides: Assignment #3 sample solution; compile time vs. run time; runtime memory management; symbol table stack vs. runtime stack; runtime activation records; runtime access to nonlocal variables; the runtime display; recursive calls; Assignment #4: Complex Type
Mar 14 More review for the midterm: symbol table stack and runtime stack; tips on how to do Assignment #4
Mar 21 Slides: BNF; Extended BNF (EBNF); grammars and languages; derivations and productions; compiler-compilers; JavaCC; JavaCC regular expressions; "hello world" examples of .jj files; JavaCC Eclipse plug-in

Example .jj files:
helloworld1.jj   helloworld2.jj   helloworld3.jj   helloworld4.jj   helloworld5.jj
Apr 4 Slides: JJTree node names; node descriptors; tree shaping; Pcl; Assignment #6

Example .jjt files:
node_name_change.jjt   node_void.jjt   calculator_tree_shape_1.jjt   calculator_tree_shape_2.jjt

Apr 11 Slides: Jasmin assembly instructions; use Java to test Jasmin code; code templates; compilation strategy; Jasmin type descriptors; Pascal program, program fields, main program; loading and storing program variables; visitor design pattern; Pcl2 code generation; code for procedures and functions

Jasmin multiply engine: MultiplyEngine.j
Apr 18 Slides: Code for System.out.println(), String.format(), scalar arrays, and subscripted variables
Apr 25 Slides: 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
Pcl with error handling:

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
Generating Parsers with JavaCC, 2nd edition
Tom Copeland
Centennial Books, 2009
ISBN: 0-9762214-3-8 (book or PDF)

Recommended books

Programming for the Java Virtual Machine
Joshua Engel
Addison-Wesley Professional
ISBN: 0201309726
Understanding and Writing Compilers
Richard Bornat

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.