CS 375: Compilers: Online

CS 375 Class Web Page

Note: Links will be filled in after the lectures occur.

Lectures from Spring 2021

• January 19, 2021:
  • C vs. Pascal
  • Cost of Programmer
  • Double Buffering
  • Intro to Number Conversion

• January 21, 2021:
  • C strings
  • Integer Number Conversion
  • Floating Point
  • Floating Point Conversion

• January 26, 2021:
  • Facts re Floating Point
  • Floating Point; Grammar
  • Ambiguity; Nested Grammars
  • Grammar Hierarchy; Lex Implementation

• January 28, 2021:
  • Grammars and lex
  • lex
  • Context-Free Grammars and Languages

• February 2, 2021:
  • Derivation; Top-down Parsing; Deep Structure
  • Augmented Transition Net; Expression Parsing
  • Associativity; First-Child/Next-Sibling Tree
  • Operator Precedence Example

• February 4, 2021:
  • Parsing Methods; Shift, Reduce, Tree
  • Operator Precedence Examples
  • Operator Precedence Examples
  • Stack Handling in C
  • Parsing Function Calls and Arrays

• February 9, 2021:
  • Recursive Descent
  • Shift-Reduce Parser: yacc
  • begin statement

• February 11, 2021:
  • Intermediate Code; Trace Bit Vector
  • Edit Distance for Error Correction
  • Intermediate Code for Loops

• February 25, 2021:
  • Notes on trivb.pas Assignment
  • Hashing for Symbol Table
  • Symbol Table Levels; Constants

• March 2, 2021:
  • const declaration
  • program declaration, blocks
  • variable allocation in memory
  • variable lookup in symbol table

Lectures from Fall 2020

• August 28, 2020:
  • Pascal; Assembly Language; Economics of Programming
  • Double Buffering; Lexical Ambiguity
  • Character Codes; Table Lookup

• September 1, 2020:
  • Strings in C
  • Integer Conversion
  • Basic Float Conversion
  • Floating Point Representation

• September 3, 2020:
  • Associativity and Floating Point
  • Chomsky Language Hierarchy
  • Ambiguity
  • Eliminating Ambiguity

• September 8, 2020:
  • lex
  • lex; language hierarchy
  • context free languages; derivation
  • examples of ambiguity in programming languages

• September 10, 2020:
  • Top-Down Parsing
  • Ambiguity and Parsing
  • Shift-Reduce Parsing, First-Child/Next-Sibling Tree
  • Shift-Reduce Examples
  • Shift-Reduce Examples

• September 15, 2020:
  • Operator Precedence Examples
  • Parsing Function Call
  • Operator Precedence + Recursive Descent
  • Stack in C
  • Yacc: default action, begin-end

• September 17, 2020:
  • Intermediate Code for Begin-End
  • Building in Observability
  • Yacc vs. Hand-written Parser

• September 22, 2020:
  • For Loop; Hashing
  • Hash with Buckets; Symbol Table Levels
  • Symbolic Constants; Subrange

• September 24, 2020:
  • var Declaration and Block Structure
  • Relative Addressing
  • Data Alignment and Padding
  • Runtime Stack, Record

• September 29, 2020:
  • Record and Array Declarations
  • Type Coercion and Type Lattice
  • Structure References
  • Array References

• October 1, 2020:
  • Structure References
  • Row-Major Order
  • Combined AREFs; Circular Structures
  • Traversal of Type Structure
  • Dynamic Type Checking

• October 6, 2020:
  • Function signature; sound, complete
  • Type Equivalence
  • Polymorphic method; Quadruples
  • Reverse Polish

• October 8, 2020: and second part:
  • Loader; Banked Memory
  • Backpatching; Link Editing
  • Relocation Cases

• October 13, 2020:
  • DLL; I/O Statement Expansion
  • Keeping a Free Storage List
  • Garbage Collection Methods
  • Number Conversion for Output

• October 15, 2020: Review for Midterm
  • array and record calculations
  • operator precedence parsing
  • regular expressions and languages
  • Chomsky hierarchy, grammars, languages

• October 20, 2020: Midterm Exam

• October 22, 2020:
  • Notes on graph1 assignment
  • Type Coercion in binop(), funcall
  • Newton-Raphson Iteration for sqrt()
  • Easy sqrt(), preamble, stack frame
  • Function calls and stack; virtual machine code
  • Code generation for progn

• October 27, 2020:
  • Code Generation for Expressions
  • Immediate Instruction; Registers
  • Simple Register Allocation

• October 29, 2020:
  • x86 Addressing, Arithmetic
  • Condition Code Register and Jump
  • Code Generation for If
  • Addressing for Array Reference

• November 3, 2020:
  • Record Declarations
  • Record Reference
  • Call by Reference and Value
  • Creation of Alias by Call
  • Call by Reference vs. Value

• November 5, 2020:
  • Processing Array Declarations
  • Simple Array References
  • Compound Array References
  • Open (Inline) vs. Closed Subroutine
  • Pareto Distribution; what to Optimize

• November 10, 2020:
  • Array Declaration and Reference
  • Pointers
  • Multiple aref's; padding
  • Peephole optimization; Partial Evaluation
  • Partial Evaluation Example

• November 12, 2020:
  • Stack Machine
  • Bit Vector; Flow Graph
  • Available and Busy

• November 17, 2020:
  • Array References
  • Two-dimensional Array References
  • Definition-Use Chains
  • Graph Coloring
  • Strip Mining

• November 19, 2020:
  • Memoization, Advanced Hardware
  • PowerPC Features
  • Register Windows; Discrete Event Simulation

• November 24, 2020:
  • genarith(): Literals
  • genarith(): Binary Ops
  • genarith(): Unary Ops
  • Object Storage; Java Integer
  • Extending Objects
  • Inheritance and Shadowing

• December 1, 2020:
  • Object, Method Inheritance
  • Multiple Inheritance
  • Just In Time Compilation

• December 3, 2020: Review
  • Review A
  • Review B
  • Review C
  • Review D
  • Review E
  • Review F

-->

Lectures from Summer 2020

• July 13, 2020:
  • Pascal vs. C; kinds of code; cost of errors grows
  • Disk and input buffer; Lexical ambiguity
  • Character codes; starting assignment
  • Strings in C

• July 14, 2020:
  • Double Buffering; Assignment 1
  • Lexer; tokens
  • Integer Conversion
  • Integer Overflow
  • Floating Point Representation

• July 15, 2020:
  • Floating Point Conversion
  • Floating Point Values
  • Significant Digits; Ambiguity
  • Ambiguity; Language Classes

• July 16, 2020:
  • lex: table; special variables
  • lex: making output tokens
  • lex comments; language hierarchy
  • recursion; agreement; derivations
  • Left Recursion

• July 17, 2020:
  • Top-Down vs. Bottom-Up; Ambiguity; Deep Struture
  • Stack; Ambiguous vs Unambiguous Expression Grammar
  • Expression Trees; Associativity
  • First-Child/Next-Sibling Tree; Operator Precedence
  • Operator Precedence Parsing Example

• July 20, 2020:
  • Operator Precedence Examples
  • Operator Precedence; Stack in C
  • Parser Options
  • Parsing Function Call and Subscripts
  • Writing Recursive Descent Code

• July 21, 2020:
  • begin intermediate code
  • binop(); Building In Observability
  • Tree for IF Example

• July 22, 2020:
  • Edit Distance; For Loop Flowchart
  • For Loop Tree
  • Hashing variants
  • Lexical Scoping

• July 23, 2020:
  • Symbol Table: Constants
  • Declaration Statements
  • Addressing and Alignment
  • Notes on trivb.pas Assignment

• July 24, 2020:
  • Symbol Table Entry for Record
  • Array Size; Type Coercion
  • Type Lattice
  • Walk through Type Tree
  • Record and Array References

• July 27, 2020:
  • Array Reference Code
  • Row Major Order
  • Combined References; Circular Type References
  • Circular Function Calls; Pointer Dereference
  • Dynamic Typing and == in Java

• July 28, 2020:
  • Dynamic Typing
  • Type Equivalence
  • Polymorphic Method
  • Quadruples and Polish

• July 29, 2020: Review for Midterm
  • Record and Array Size
  • Operator Precedence Parsing
  • Hashing; Regular Expressions
  • Context Free and Regular Grammars
  • Converting Tree to Reverse Polish

• July 30, 2020: No Lecture; Midterm Exam

• July 31, 2020:
  • Installing Record Declaration
  • Executable File and Loader
  • Backpatching process

• August 3, 2020:
  • Array References
  • Pointers; Linker
  • Relocation options
  • Dynamically Linked Library; Number Conversion for Output

• August 4, 2020:
  • Math Library
  • Compound I/O Statements
  • Free List and Garbage Collection
  • Garbage Collection, Roll-your-own Free List
  • Subroutine Call Overhead

• August 5, 2020:
  • Runtime Stack; Interpreted Code
  • Code Generation
  • Expression Generation
  • Expression Generation; Memory Hierarchy

• August 6, 2020:
  • Register Allocation
  • x86 Addressing
  • x86 Arithmetic Instructions

• August 7, 2020:
  • Op Code Table; Condition Code Register
  • Conditional Jump
  • Saving Registers across Subroutine Call
  • If Statement Generation
  • Call by Reference

• August 10, 2020:
  • Call by Reference vs. Call by Value
  • Call by Value in Java; C Macros
  • Open or Inline Subroutine
  • Optimization: Pareto Distribution

• August 11, 2020:
  • Partial Evaluation
  • Common Subexpressions
  • Matrix Representation of Graph
  • Bit Vector; Control Flow
  • Data Flow

• August 12, 2020:
  • Saving Register Across Funcall
  • Data Flow, Def-Use Chain
  • Graph Coloring for Register Assignment
  • Strip Mining
  • Advancced Hardware Features

• August 13, 2020:
  • Array Reference Addressing; Object Representation
  • Class Hierarchy; Multiple Inheritance
  • Mixin Methods

• August 14, 2020: Review
  • Array size and reference
  • Grammar example
  • OOP; flow graph
  • Optimization; advanced CPU features
  • Row-major Order; Substitution, def-use chaain

Lectures from Spring 2020

• March 31, 2020:
  • Record Declarations
  • Link Editor
  • DLL
  • Math Library
  • Number Conversion for Output
  • Writeln

• April 2, 2020:
  • Free List of Released Memory
  • Identifying Type of Dynamic Storage
  • Following Pointers for Garbage Collection
  • Copying Garbage Collection
  • Private Free List in Java
  • Reference Counting
  • Call Graph and Runtime Stack

• April 7, 2020:
  • Generation of progn
  • genarith
  • Register Allocation
  • Register Reuse

• April 9, 2020:
  • Array Addressing
  • AREF Canonical Form
  • Multi-Dimensional Array Addressing
  • x86 Registers and Addressing
  • x86 Arithmetic Instructions
  • x86 Compare and Jump
  • Identity Functions

• April 14, 2020:
  • Compare/Jump Example
  • Code for genarith()
  • Flowchart for IF Statement
  • IF Statement Optimization
  • Addressing for AREF
  • Record Addressing

• April 16, 2020:
  • Call by Reference
  • Call by Value
  • Call by Value in Java
  • Call by Name
  • Closed vs. Open (inline) Subroutine
  • Pareto Distribution
  • repeat statement tree; pointer; record reference (office hours)

• April 21, 2020:
  • Pointer and Record References
  • Partial Evaluation
  • Common Subexpressions

• April 23, 2020:
  • Set as Bit Vector
  • Common Subexpressions
  • Def-Use Chain
  • Graph Coloring
  • Strip Mining

• April 28, 2020:
  • Finite Differencing, Memoization
  • Advanced CPU Features
  • Speculative Execution
  • Register Stack

• April 30, 2020:
  • Integer vs. int in Java
  • Integer cache and == : Potential Bug
  • Inheritance in Java: Fields, Methods
  • Method Inheritance and Shadowing
  • C++ Methods; Multiple Inheritance
  • Multiple Inheritance: Mixin Conflicts

• May 5, 2020:
  • Dynamic Method Dispatch
  • OOP Overhead
  • THINGLAB; Lisp REPL

• May 7, 2020:
  • Review A
  • Review B
  • Review C
  • Review D
  • Review E
  • Review F
  • Review G