San Jose State University : Site Name

Navigation

Main Content

Buddy Goals

Ronald Mak

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

Office hours: TuTh: 4:30-5:30 PM online via Zoom
Office location: ENG 250 (but working from home)
E-mail: ron.mak@sjsu.edu

CMPE 152: Compiler Design


Section 1: TuTh 3:00 - 4:15 PM online via Zoom


Lab Assignments

# Date Due Assignment
1 Jan 28 Feb 4 Write Simple Pascal Programs
Assignment input file: presidents.txt

Example Pascal program: EmployeeListing.pas
Example program input file: employees.txt
Example program output: employees.out.txt
2 Feb 4 Feb 11 Pascal Scanner

Simple Pascal (C++ version): SimpleCpp.zip
Test input files: Newton.txt    ScannerTest.txt
Example output: ScannerTest.out.txt
Example solution: Asgn02Cpp.zip
3 Feb 11 Feb 25 Simple Pascal interpreter

Test input files and expected output: TestWhile.txt    TestWhile.out.txt    TestIf.txt    TestIf.out.txt    TestFor.txt    TestFor.out.txt    TestCase.txt    TestCase.out.txt
Example solution: Asgn03Cpp.zip
4 Feb 25 Mar 9 Pcl interpreter using ANTLR

Executor skeleton: Asgn04Cpp.zip
5 Mar 19 Apr 9 Pascal to C++ Converter

Partial converter code: Asgn05Cpp.zip
6 Apr 8 Apr 23 Pascal Compiler

Partial compiler code: Asgn06Cpp.zip

Lectures

Week Date Content
1 Jan 28 Zoom recording Password: S@Nwn&1d
Slides: Goals; course learning outcomes; project teams; grading; postmortem assessment report; overview of the compilation process; compiler as translator; other forms of translation; Pascal tutorials
2 Feb 2 Zoom recording Password: nHT73T?s
Slides: It's all about translation; conceptual design; major parts of compilers, converters, and interpreters; compilers vs. interpreters; three Java packages; syntax diagrams; how to scan for tokens; basic scanning algorithm; test the scanner; current character vs. next character; consume characters and tokens; Object.h

Sample code: SimpleCpp.zip
Feb 4 Zoom recording Password: @j=&V1XV
Slides: Assignment #2; Pascal statement syntax diagrams; expressions; operator precedence; control statements; REPEAT statement syntax; parse tree design and operations; building a parse tree; test the parser; parse tree nodes;
3 Feb 9 Zoom recording Password: 3*UQz7Sb
Slides: Building the parse tree with parser member functions; the symbol table and its entries; a hack; a simple symbol table concepts and operations; who needs a symbol table? entering and searching for identifiers
Feb 11 Zoom recording Password: h+LBS9&F
Slides: Simple interpreter; "run time"; using the parse tree and symbol table at run time; another hack; visiting parse nodes during run time; REPEAT statement; Assignment #3; WHILE statement; IF statement and the dangling ELSE; FOR statement; CASE statement
4 Feb 16 Zoom recording Password: 1.Ai+.jP
Slides: Assignment #3; the dangling ELSE; maximum munch; an executor improvement; syntax and semantics; options for error recovery; top-down recursive descent parsing; accomplishments so far; temporary hacks; a DFA scanner

DFA scanner: SimpleDFAScanner.h    SimpleDFAScanner.cpp    SimpleDFAInput.txt
Feb 18 Zoom recording Password: T&p8XkE+
Slides: BNF; grammars and languages; derivations and productions; EBNF; compiler-compilers; ANTLR 4; ANTLR lexer; ANTLR grammar file; Java main programs; on the command line

ANTLR example: Expr.g4    ExprMain.cpp    input.txt
5 Feb 23 Zoom recording Password: Vu6%8^TL
Slides: What does ANTLR do for us?; ANTLR workflow; ANTLR parse trees; syntax error handling; resolving ambiguities; visitor interface; interface ExprVisitor; base visitor class ExprBaseVisitor; labeled production rules; interface ExprLabeledVisitor; base class ExprLabeledBaseVisitor; class Executor; main

ANTLR example: ExprLabeledCpp.zip
Feb 25 Zoom recording Password: 7x@Wi3.a
Slides: Pcl4 grammar; package structure; Pcl4 visitor interface; Pcl4 base visitor class; class Executor; Assignment #4; declarations; constant definitions; simple type definitions; array type definitions; record type definitions; variable declarations; declarations and the symbol table; scope and the symbol table stack
6 Mar 2 Zoom recording Password: j8sJ2p#l
Slides: Scope and the symbol table stack; nested scopes; scope of record fields; class Symtab; class SymtabStack; class SymtabEntry; Pascal declarations; grammar file Pcl5.g4; declarations and the symbol table; type specification attributes; class Typespec

ANTLR example: Pcl5Cpp.zip
Mar 4 Zoom recording Password: D.N6YxM$
Slides: Multipass compilers; type declaration structures; multidimensional array; predefined scalar types; type checking; Pass 2 visit functions; new fields for parse tree nodes; grammar Pcl4.g4
7 Mar 9 Zoom recording Password: sbNU*!31
Slides: Pcl6 main; pass2 functions for type definitions; type checking; assignment and comparison compatible; new fields for parse tree nodes; class TypeChecker; type checking expressions; cross-reference listing; Pascal.g4; pass 3 execution; runtime memory management; symbol table stack vs. runtime stack; stack frame; access to nonlocal variables

ANTLR example: Pcl6Cpp.zip
Pascal grammar: Pascal.g4
Mar 11 Zoom recording Password: AWt*dn@1
Slides: Pascal.g4; pass 3 execution; runtime memory management; symbol table stack vs. runtime stack; stack frame; access to nonlocal variables; runtime display; recursive calls; allocate a stack frame; runtime error checking; grammar for a variable; type check a variable; grammar for a procedure or function definition; symbol table entry for a procedure or function; grammar for procedure and function calls; type check a call; Pascal interpreter; interactive source-level debugger; machine-level vs. source-level debugging; simple debugger command-line language; breakpoints; watchpoints; parsing and executing the debugger commands
8 Mar 16 Zoom recording Password: d%ss=4U6
Slides: Grammar and visit functions for the debugger command language; debugger visit functions; a Pascal to C++ language converter; Assignment #5; review for the midterm
Mar 18 Midterm
9 Mar 23 Zoom recording Password: .NUi4#i1
Slides: Interpreter, converter, compiler; target machines; Java Virtual Machine (JVM) architecture; JVM runtime stack and stack frame; Jasmin assembler; Jasmin assembly instructions: shortcuts, local variables, load and store, arithmetic, other instructions; code templates; compilation strategy; Jasmin datatype descriptors

Example Jasmin program: hello.j
Mar 25 Zoom recording Password: ?963it$N
Slides: Program fields; code template for the main method; loading and storing a program variable's value; code for procedures and functions; compiling local variables; generating code for expressions; comparing integer values and other datatypes; What Would James Gosling Do?; Jasper; relational expressions; load and store tips

Example Java program: Test.java
10 Apr 6 Zoom recording Password: D8mKiH?8
Slides: Code templates: assignment statements, if statements, looping statements; Newton's square root function; FOR statement; select template; CASE statement; procedures and functions; code: main program, function, call a function
Apr 8 Zoom recording Password: VK%T1AL2
Slides: Calling methods on objects; invokestatic vs. invokevirtual; code for println() and printf(); translation recap; Assignment #6; final compiler project
11 Apr 13 Zoom recording Password: KFXJ1M*.
Slides: Pascal arrays; code generation for arrays and subscripts; allocate memory for scalar arrays; access an element of a 2-D array; subscripted variables; allocate memory for non-scalar arrays; 1-D array of strings; 2-D array of strings;
Apr 15 Zoom recording Password: !079hhV7
Slides: Code for records and fields; passing parameters; runtime libraries; passing parameters: Java and C++; pass by reference: C++, Java hack; runtime libraries; library example; project presentations schedule; example project

Pass-by-reference examples: ReferenceParm.java   ReferenceParm1.cpp   ReferenceParm2.cpp   IWrap.java   ReferenceHack1.java   ReferenceHack2.java
Runtime library example: Multiplier.java   LibraryTest.java   LibraryTest.j
12 Apr 20 Zoom recording Password: 9$ZKz9v1
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
Apr 22 Zoom recording Password: $^Nv5Ra2
Slides: Static and dynamic scoping; backend compiler architecture
13 Apr 27 Zoom recording Password: d^5$%HBf
Slides: Runtime memory management; heap management; garbage collection algorithms: reference counting, mark and sweep, stop and copy, generational; aggressive heap management; garbage collection research
Apr 29 Zoom recording Password: @B^vjR4*
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
14 May 4 Zoom recording Password: 9iM!p0rR
Slides: Compiler design theory; Noam Chomsky; formal languages; languages; rules of a language; grammars; production rules; derivations; language generation; sentential forms; equivalent grammars
May 6 Zoom recording Password: 6yvt9!%4
Project presentations: Teams CODENT, HZWZ, Programmers for Fun, The Compiler Whispers, WSRY
15 May 11 Zoom recording Password: EvQ#J6ap
Project presentations: Devs United, JTTG, Team 300, To the Moon
May 13 Zoom recording Password: fk3!*Eek
Project presentations: Elbrus-64, No Name 4, TTCP, Hakuna Matata, XXX

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 126 and CMPE 102 both with a C- or better.
Computer Engineering and Software Engineering majors only.

Required book

The Definitive ANTLR 4 Reference, 2nd edition
Terence Parr
Pragmatic Bookshelf, 2012
ISBN: 978-1934356999
http://www.antlr.org/

Recommended book

Writing Compilers and Interpreters, 3rd edition
Ronald Mak
Wiley Publishing, Inc., 2009
ISBN: 978-0-470-17707-5
Source files


Useful tutorials

Some useful tutorials for my classes where the preferred platforms for application development are MacOS X and the Ubuntu distribution of Linux. Windows 10 may present significant compatibility challenges.

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