San Jose State University : Site Name

Navigation

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

Assignments


# 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

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

Solutions
3 Feb 21 Mar 3 LOOP AGAIN statement

Suggested solution: Assignment3LA.zip
4 Mar 7 Mar 24 New built-in complex type


Lectures


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: SimpleDFAScanner.java    SimpleDFAInput.txt
Mar 23 Slides: JavaCC parser specification; production rule methods; choice conflicts; left factoring; backtracking; lookahead; left recursion; right recursion; iteration; JJDoc

Example .jj files:
phone.jj   phone_method_param.jj   phone_choice.jj   phone_left_factored.jj   phone_lookahead.jj   expression_left_recursion.jj   expression_iteration.jj   expression_right_recursion.jj


Labs


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


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


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
Generating Parsers with JavaCC, 2nd edition
Tom Copeland
Centennial Books, 2009
http://generatingparserswithjavacc.com/
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.