Compilers

Spring 2024

Documents

• Syllabus and Schedule - revised January 15, 2024
• History and Advice
• About Laptops and Phones in Class
• Course Policies
• General Academic Calendar
• Academic Honesty
• School of Computer Science and Mathematics Department of Computing Technology Goals
• Writing Center
• Counseling Services
• Title IX at Marist
• Title IX Student Bill of Rights and IX Reporting Options
• Academic Learning Center for tutoring and more

Books

• Crafting a Compiler (required)
• The Famous Dragon Book (required)
  Two of the authors are ACM Turing Award winners.
• Compiler Construction by Niklaus Wirth
• Language Implementation Patterns by Terence Parr
• The Definitive ANTLR4 Reference by Terence Parr
• Basics of Compiler Design by Torben Mogensen
• Introduction to Compilers and Language Design by Douglas Thain
• GNU Compiler Collection Internals

Projects and Labs

• Embrace scholarship and write your labs using LaTeX. OverLeaf is probably the easiest way to do this. I've written a lab example you can use as a template. There are more LaTeX resources below.
• Most of the labs feed into the projects. Get started by looking at Our Language Grammar. Also have a look at the resources below to help get you started.
  • Lab 0: Development Tooling and Build Documentation (and getting started with LaTeX). See build environment notes.

• Project One - Build an interesting lexer.
  • Lab 1: Making tokens with your Lexer
  • Lab 2: More token making, now with Finite Automata
• Project Two - Build an interesting parser and CST.
  • Lab 3: Turning tokens into sentences with your Parser
  • Lab 4: Analyzing Grammars
  • Lab 5: Building Syntax Trees both Concrete and Abstract
• Project Three - Adding an AST and Semantic Analysis.
  • Lab 5: Building Syntax Trees both Concrete and Abstract
  • Lab 6: Symbol tables and you (and your compiler)
  • Lab 7: Semantic Analysis: Checking scope and type
• Project Four - A full compiler, with 6502a code generation.
  • Lab 8: Generating Code
  • Lab 9: Manipulating Grammars
  • Here are some Operating Systems on which to test your generated code:
    • CyberCore by Kevin Mirsky
    • SvegOS by Justin Svegliato.
    • MysteriOS Bloop by Rebecca Murphy
    • ctOS by Anthony Barranco
    • ChronOS.LL in OmniChron by Chris Cordisco
  • Here is the 6502a Instruction Set for your final project.

Examples

• Try Template Project 0 in JavaScript And here it is on GitHub.
• Template Project 0 in TypeScript on GitHub - for early versions of TypeScript
• AlanC, a simple lexer via JavaCC (ZIP file)
• A simple example in modern TypeScript (ZIP file) - for recent (as of 2023) versions of TypeScript
• A simple example in C++ (ZIP file)

Notes

• Introduction to Compilers and Before and After Compilation
• Lexical Analysis and Lex without spaces
• Parsing
• Semantic Analysis
• Type Systems
• Code Generation
  • Simple code generation example one
  • Simple code generation example two
• Ambiguous Grammars
• More Grammar Stuff
• Shift-Reduce Parse examples from MIT

Resources

• LaTeX
• Comprehensive TEX Archive Network
• Overleaf (formerly ShareLaTeX)
• LaTeX Tutorial from Overleaf
• TeX Stack Exchange
• TikZ package tutorial (for drawing DFAs and NFAs)
• Apple's Swift compiler
• Swift Source Code
• See the AST with -dump-ast option
• TypeScript
• Welcome to TypeScript
• The TypeScript Handbook
• Typescript in 5 Minutes
• The TypeScript tag at Stack Overflow
• Static code analyzer for TypeScript from SonarSource
• Videos of Anders Hejlsberg on TypeScript:
  • at BUILD 2014
  • Inside TypeScript from BUILD 2012
  • The Typescript Compiler Explained
• JavaScript
• JavaScript is Good, Actually - Well... modern JavaScript is.
• A Re-introduction to JavaScript
• JavaScript Style Guides
• The jQuery JavaScript Style Guide
• Some JavaScript code conventions - from Doug Crockford
• More JavaScript code conventions - from many people, managed via Git
• JavaScript: The Good Parts - by Doug Crockford
• The JavaScript tag at Stack Overflow
• The JavaScript tag at Pro Webmasters Stack Exchange
• JavaScript Keyboard Events Madness
• Treant.js - a JavaScipt library for tree diagram visualizations
• Write Tetris in JavaScript
• Git
• GitHub Desktop
• A Gentle Introduction to Git and GitHub from Alan
• Git from the Bottom up by John Wiegley
• Git Basics
• Try Github
• GitHub Guides
• Advanced: Git From the Inside Out
• Visualizing Git Concepts
• How to Write a Git Commit Message - pretty good advice
• The Issues Feature on GitHub
• Dangers of GitHub and Amazon
• Java
• IntelliJ IDEA
• Virual Studio Code
• NetBeans
• Eclipse
• Debugging Java in IntelliJ IDEA
• Debugging Java in Visual Studio Code
• Sun's Oracle's Java Documentation
• Oracle's "New to Java Programming" Center
• Java tutorials
• Java Coffee Break - Getting started
• The Java tag at Stack Overflow
• Memory usage in Java
• JVM Anatomy Quarks
• JVM Internals
• A JVM Does That? by Cliff Click
• Jasmin, Jasper, and JavaCC
• Jasmin at SourceForge
• Jasper
• JavaCC
• LLVM
• LLVM - Compiler Infrastructure
• LLVM for Students
• Mapping High-Level Constructs to LLVM IR
• LLVM Code Generation in HHVM
• A Tourist's Guide to the LLVM Source Code
• The C# Burst Compiler using LLVM
• Compiler Performance and LLVM
• C++
• C++ PLDB Entry
• GCC
• CLion
• Qt
• g++ cheatsheet from USC
• makefile cheatsheet from USC
• Boost Libraries
• Abseil - C++ docs and libraries from Google
• Super helpful resource on Templates in C++
• 6502 Assembly Language
• Instruction Set for Our Projects
• How To Write 6502 Assembly Language from Easy 6502
• Why the 6502? Because The 6502 CPU Powered a Whole Generation! from The 8-Bit Guy
• Visual 6502
• Virtual 6502 assembler and disassembler
• In-depth 6502 Op Code Analysis (With "illegal" op codes too.)
• 6502 / 6510 / 8502 Opcode List, with details - from Nybbles and Bytes
• 6502 Circuit Diagram
• Commodore History Part One - The PET - video from from The 8-Bit Guy
• From BitSavers' Software Archive:
  • MOS 6500 Data Sheets from 1976
  • MOS 6500 Op Codes
  • MOS 6500 Architecture
• From AtariArchives:
  • Machine Language For Beginners
  • The Second Book Of Machine Language
  • Assembly Language Programming for the Atari Computers
• T-800 Heads-up Display from The Terminator, 1984
• Learn 6502 Assembly Language by hacking Mario World
• Software Development
• Software Engineering at Google a book by Abseil
• Ideas about Software Development - 6 years later
• Software Development Developments at Microsoft
• Exploding Software Engineering Myths - more from Microsoft Research
• A Microsoft Code Review - with Marist alum Jon Miller
• A big list of naughty strings - Great for testing
• Comments on Comments
• Great books about writing software
  • Code Complete by Steve McConnell
  • Beautiful Code by Andy Oram & Greg Wilson
  • Coders at Work by Peter Seibel
• Algorithms
• Algorithm Visualizations - VisuAlgo, from Dr. Steven Halim and some of his students from the National University of Singapore
• Visualizing Algorithms by Mike Bostock, creator of d3
• Sorting Algorithm Animations - Visual demos by David R. Martin
• The Sound of Sorting - Sorting Algorithm Audibilization and Visualization, by Timo Bingmann
• Data Structure Visualization Tool from David Galles
• Alan's Algorithms Course
• Others
• DebugEx - a Regular Expression tester
• Anders Hejlsberg on Modern Compiler Construction - January 2017
• Compiler Jobs
• Compiler writing resources on Stack Overflow
• Resources for Amateur Compiler Writers
• Emscripten - an LLVM-to-JavaScript compiler
• Grammatica - a C# Compiler Compiler
• ANTLR
• ANTLR Mega-Tutorial by Federico Tomassetti
• Graal Multi-Language VM
• Ragel a state machine compiler
• Compiler Explorer - Type source code and see the machine language
• Command Line Interface Guidelines

Articles

• A simple Garbage Collector - by Bob Nystrom
• Visualizing Garbage Collection algorithms
• A peak into the Erlang compiler and BEAM bytecode
• Dijkstra on Recursive Programming from 1960
• A walk through building an interpreter
• OMeta attribute grammar example
• Inside the JVM Interactive Illustrations
• Build a compiler ("How about Minsk?") in C# by Immo Landwerth
• How Tail Call Optimization Works by Evan Klitzke
• A podcast episode about writing BNF
• A Peek Inside the Erlang Compiler from 2012
• A Timeline of Parsing
• On Language and Humanity: In Conversation With Noam Chomsky
• The EDSAC turned 70 in 2019 - Early computing from Cambridge and here's an even earlier (1951) film about it
• A Primer on Type Systems by Glenn G. Chappell
• Graph of Programming Languages connected by Compilers
• Compiler Explorer from Matt Godbolt
• How Clang Compiles a Function by John Regehr
• IR and Assembly Which is better?
• Facebook Infer - a static analysis tool
• The .NET Compiler Platform
• Secrets of Swift's Speed Thoughts on Apple's Swift language and compiler optimizations
• Apple, JavaScript, and the LLVM Compiler
• So You Want To Write Your Own Language? by Walter Bright, designer of the D programming language
• JavaScript JIT Compiler Optimizations
• Why ML is good for writing compilers
• Microsoft Research Common Compiler Infrastructure
• Anders Hejlsberg on LINQ and Functional Programming
• C Recursion - by Kernighan, Ritchie, and Lovecraft
• Comments on Comments
• Old Compiler Writing Advice - Two papers: This one and that one.
• Type Checking in Groovy
• Thoughts about Type Safety from the Programming Language Enthusiast blog
• Building a modern functional compiler from first principles in Haskell
• A History of Branch Prediction

• Compiler Fuzzing
• Compiler Fuzzing, part one
• Grammarinator an ANTLRv4 grammar-based test generator
• Compiler Fuzzing through Deep Learning
• Fuzzing in general

• Software Engineering Radio
  The podcast for professional developers
  I really like these folks. Highly recommended. Here are a few episodes to get you started:
  Compiler Construction
  • Interview with Anders Hejlsberg - Turbo Pascal, Delphi, C#
  • Internals of the Gnu Compiler Collection (GCC)
  • On Parsers
  • Type Systems
  Concurrency
  • The Singularity Research OS (Software Isolated Processes)
  • Garbage Collection and Transactional Memory
  • Concurrency Part One
  • Concurrency Part Two
  • Concurrency Part Three
  • More on Concurrency
  Languages
  • Joe Armstrong on Erlang
  • Martin Odersky on Scala
  • Martin Ordersky on Scala Update
  • Dick Gabriel on the origins of LISP
  • Simon Peyton Jones on Functional Programming and Haskell
  • Dynamic Languages for Static Minds

Past Project Hall of Fame

TypeScript and JavaScript projects only. There have been some fantastic projects in Rust, Scala, C++, Java, (and even Python once, but never again), and other languages, but they (obviously) will not execute in a web browser.

• 2024
• Compilatron by Nick Fiore
• 2023
• Compiler by Max English
• 2022
• 6502 Compiler by Gabriel Arnell
• 2021
• Nightingale Compiler (with AxiOS operating system) by Alex Badia
• 2019
• Juice Compiler
• 2018
• Sonar
• Kompailer
• The Colorful Compiler
• Daniel Ahl's Compiler
• Note: Earlier compilers used slightly different grammars compared to our current grammar.
• 2017
• Tienminator
• 2016
• Although some were close, none of the JavaScript or TypeScript projects were worthy of this hall of fame. There were some excellent projects implemented in other languages.
• 2015
• Andrew B
• Bloop Compiler
• 2014
• Svegliator
• Rob W
• ChronOS.LL in OmniChron
• Note: Earlier compilers used significantly different grammars compared to our current grammar.
• 2013
• AnnaC
• ChronOS
• Max L
• Morph6502
• 2010
• harpO
• PGP
• 2009
• Gentlemen
• Team Zero+