Fall 2023

CSC 416/565: Design and Construction of Compilers

https://cs.wcupa.edu/rburns/Compilers

Take me to the course schedule

Course Description

Design and construction of compilers including lexical analysis; parsing techniques such as LL(1), LR, and LALR(1) code generation techniques. Error analysis and simple code optimizations will be introduced. A large-scale project consisting of developing a lexical analyzer, parser, abstract syntax tree, symbol table, activation code, and intermediate code generation, and finally generating assembly code will be implemented.

Students will design and implement a compiler using standard UNIX-based compiler tools for a small but representative language.

  • Fulfills Undergraduate CSC Large-Scale Complex Course Requirement
  • CSC 416 Prerequisites: CSC 220, 240, 241, {CSC231 or CSC242}
    CSC 565 Prerequisites: CSC 520, CSC530


By the end of the course, students will attain the following:

  1. understand the phases of a compiler.
  2. utilize modern tools to perform the lexing and parsing phases of a compiler’s front-end.
  3. understand the theoretical concepts of LL(1) and LR(1) parsing.
  4. understand the back-end phases of a compiler, including: intermediate representations, runtime organization, optimization, and code generation.
  5. implement a compiler that spans from the lexical front-end to code generation in the back-end.

Instructor and Office Hours

I am Dr. Richard Burns, Professor in the Computer Science Department. My research interests include artificial intelligence and machine learning. I started teaching this course around 10 years ago. It's fun and interesting to teach, and still very relevant in modern day computing.

Office Hours

  • Mondays: 2p-3p (virtual only)
  • Tuesdays: 4p-5p (in-person or virtual)
  • Wednesdays: 12p-1p (in-person or virtual)
  • Thursdays: 1p-2p (in-person or virtual)
  • Must schedule appointment at least 12 hours in advance via Microsoft Bookings. Virtual meeting Room instructions will be provided in confirmation email.

Email, Office, Phone

  • E-mail: rburns@wcupa.edu
  • Office: (25 University Ave.) UNA 150D
  • Phone: 610-436-2690

Meeting Information

This course will engage in-person for all classes, unless otherwise indicated on the course schedule. Zoom information for any remote synchronous meetings can be found at: D2L Course Page > Zoom.

  • Section 01: Tuesdays: 7:15p-10p, UNA 166

Resources

  1. (Required) Textbook: [Thain] Introduction to Compilers and Language Design, Douglas Thain, Second edition, 2021.
  2. CSC345 discord server (invitation link posted on D2L: D2L > Content > Overview): We will use discord for additional remote communication and collaboration (e.g. sharing work, posting conceptual questions, posting programming questions, potentially breaking out into groups for the team projects). Please post and answer your peers' questions. There is no stupid question.
  3. Textbook (Optional): [Appel] Modern Compiler Implementation in Java. Andrew W. Appel. 2nd Edition.
  4. Textbook (Optional): [Dragon] Compilers: Principles, Techniques, and Tools. Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman. Second Edition. Addison-Wesley.
  5. Textbook (Optional): [CaC] Crafting a Compiler, 1st Edition. Fisher, Cytron, Leblanc. Addison-Wesley. ISBN-13: 9780136067054
  6. Textbook (Optional): [Cooper] Engineering a Compiler. Keith Cooper and Linda Torczon. Second Edition. Morgan Kaufman.
  7. Textbook (Optional, free e-textbook): [Torben] Basics of Compiler Design. Torben Mogensen. 2010 Edition.
  8. D2L

Evaluation

  • 30% - Programming Assignments
  • 20% - Written Homeworks
  • 20% - Midterm Exam
  • 30% - Final Exam

Grade Scheme

This is the "minimum" grade scale. Usually overall course grades end up being curved higher, based on the mean and standard deviation of scores. Please see me to discuss grades rather than speculating.

CSC416 (undergraduate)

GradePercentage Equivalents
A93-100
A-90-92
B+87-89
B83-86
B-80-82
C+77-79
C73-76
C-70-72
D+67-69
D63-66
D-60-62
F0-59

CSC565 (graduate)

GradePercentage Equivalents
A93-100
A-90-92
B+87-89
B83-86
B-80-82
C+77-79
C73-76
C-70-72
F0-69

Other Course Policies

Other course policies (e.g. attendance, lateness, academic integrity, ... ) can be found on the syllabus, which will never change.

Course Schedule

The course schedule is tentative and is subject to change. Updates to the schedule will be posted here.
Class 1 Tues, Aug 29 In-Person

Course Introduction

Syllabus

Structure of a Compiler SLIDES

[Thain] Chs. 1, 2

Class Discord invitation Link Posted on D2L: D2L > Content > Overview

Programming Assignment 0 Out (1% of overall course grade) GitHub Classroom Assignment Invitation SLIDES

Class 2 Tues, Sept 5 In-Person

Role of the Scanner

Lexical Analysis: Lexical Tokens, Regular Languages, Lexical Specifications SLIDES

[Thain] Ch. 3.1-3.3

Data Structures for Tree Languages

[Appel] Ch. 1 (link)

Programming Assignment 1 Out (data structures for tree languages)

CSC416 and CSC565:GitHub Classroom Assignment Invitation
CSC565 complete this as well:GitHub Classroom Assignment Invitation
SLIDES

Class 3 Tues, Sept 12 In-Person

Regular Expressions into NFAs, NFAs to DFAs

Scanner Generators (JavaCC) SLIDES

[Thain] Ch. 3.4-3.8

Written Homework 1 Out HW1

Programming Assignment 0 Due (1% of overall course grade)
Class 4 Tues, Sept 19 In-Person

Role of the Parser

Context Free Grammars, Derivations, Parse Trees

Ambiguity, Top-Down Parsing, Recursive Descent SLIDES

[Thain] Ch. 4.1-4.2, 4.3.4

Programming Assignment 2 Out (the scanner)

CSC416 and CSC565:GitHub Classroom Assignment Invitation
SLIDES

Class 5 Tues, Sept 26 In-Person

Eliminating Left Recursion, Left Factoring

Predictive Parsing

LL(1) Grammars, LL(1) Parsing Tables

Parsing Table Construction for LL(1) grammars: FIRST and FOLLOW sets SLIDES

[Thain] Chs. 4.3-4.6

Programming Assignment 1 Due (data structures for tree languages)

Written Homework 2 Out HW2
Class 6 Tues, Oct 3 In-Person

Bottom-Up Parsing

SLR Parsing

Parsing Tools

Error Recovery SLIDES

[Thain] Ch. 4.4.1, 4.4.3

Written Homework 1 Due

Programming Assignment 3 Out (the parser)

CSC416 and CSC565:GitHub Classroom Assignment Invitation
Class 7 Tues, Oct 10 In-Person

Abstract Syntax Trees (AST)

Semantic Actions

Disambiguating Grammars for Operator Precedence

Visitor Design Pattern SLIDES

[Thain] Ch. 5.3, 6.1

Programming Assignment 2 Due (the scanner)
Tues, Oct 17

Fall Break - No class!
Class 8 Tues, Oct 24 In-Person

Semantic Analysis: Symbol Tables

Semantic Analysis: Type Checking SLIDES

[Thain] Ch. 7.1-7.2, 7.4-7.7

Midterm Review, HW #1 Solutions, HW #2 Solutions

Written Homework 2 Due
Class 9 Tues, Oct 31 In-Person

Midterm Exam

Programming Assignment 3 Due (the parser) extended one week
Class 10 Tues, Nov 7 In-Person

Runtime Memory Organization

Activation Frames SLIDES

[Thain] Ch. 9.1, 9.2, 9.4

Programming Assignment 3 Due (the parser)

Programming Assignment 4 Out (the semantic analyzer)

CSC416 and CSC565:GitHub Classroom Assignment Invitation
SLIDES

Class 11 Tues, Nov 14 In-Person

Assembly Language SLIDES

Appendix A (A.1 - A.6, Byte Order and System Calls in A.9, most useful instructions in A.10, A.11) from Hennessy and Patterson's Computer Organization and Design: The Hardware/Software Interface

MIPS Simulator: MARS (MIPS Assembler and Runtime Simulator)

Examples: [add.asm] [swap.asm]

[Thain] Chs. 10.1, 10.2, 10.4

Written Homework 3 OutHW3
Class 12 Tues, Nov 21 Remote Asynchronous (RA)

Programming Assignment 5 Introduction

Programming Assignment 4 Due (the semantic analyzer) extended one week

Programming Assignment 5 Out (code generation)

CSC416 and CSC565:GitHub Classroom Assignment Invitation
SLIDES

Class 13 Tues, Nov 28 In-Person

Local Optimization

Global Optimization SLIDES

[Thain] Ch. 12.1 - 12.3

Programming Assignment 4 Due (the semantic analyzer)

Written Homework 3 Due (optional)

Written Homework 4 Out HW4
Class 14 Tues, Dec 5 In-Person

Register Allocation SLIDES

[Thain] Ch. 12.4 - 12.5

Final Exam Review

Written Homework 4 Due (optional)
Finals Tues, Dec 12 (8:15p-10:15p ☕, in regular classroom) In-Person

Final Exam

Programming Assignment 5 Due (code generation, due Mon Dec 11)