CMSC 445: Compiler design

Spring 2012

Prof. Blaheta

Unless you go to work for a compiler company or do research in debugging or optimisation, it's relatively unlikely that you will be called upon to implement a traditional compiler. However, the main compiler components---lexing, parsing, and code generation---crop up separately in a much wider variety of applications; and a better understanding of the compilation process will make you a better programmer overall (and much better at deciphering some of the more cryptic error messages that compilers give from time to time).

Plus, there's a special thrill in running a compiler that you wrote yourself, and then running the executable it produces!

This class meets 2:00pm on MWF.

Textbooks

The main textbook is intended to be Aho et al, Compilers, 2e. ISBN 978-0-321-48681-1. The bookstore appears to be somewhat short of copies; contact me if this is a problem.

Also recommended are two references that will be really handy when we dive into the main compiler project: Prinz and Prinz, C pocket reference, ISBN 978-0-596-00436-1; and Levine et al, flex & bison (or the older lex & yacc). For the C reference, I particularly recommend the print copy as opposed to e-book.

Course materials

• Syllabus
• Collaboration policy
• FA videos:
  • RE to NFA
  • NFA to DFA
• x64 calling conventions

Labs, homeworks, projects

• Due 27 Jan: Homework 1
• Due 3 Feb: Project 1
• Due 10 Feb: Homework 2
• Due 15 Feb: Project 2
• Due 29 Feb: Project 3a
• Due 22 Feb: Homework 3: see Project 3a handout.
• Due 23 Mar: Homework 3 (4)
• Due 9 Apr?: Project 4
• Due 9 Apr: Homework 5
• Due TBA: Project 5

Board photos

• 20 Jan: left (paradigm, scope); right (environment, parameters)
• 23 Jan: left (grammar basics); right (parse example)
• 25 Jan: left (grammar issues); right (concrete vs abstract syntax tree)
• 27 Jan: left (syntax trees); right (parse tree)
• 30 Jan: board (generation, lexing)
• 1 Feb: left (symbol table); right (lexemes etc)
• 3 Feb: left (regular expressions); right (transition diagrams)
• 6 Feb: left (trees); right (NFAs)
• 8 Feb: left (RE->NFA->DFA); right (NFA simulation)
• 10 Feb: board (Roman numerals)
• 13 Feb: left (Parse errors); right (Ambiguity, factoring)
• 15 Feb: left (flex issues); right (Recursive descent)
• 17 Feb: left (LL(1) issues); right (FIRST/FOLLOW sets)
• 20 Feb: left (parser design); right (LL(1) revision)
• 22 Feb: board (bottom-up parsing)
• 24 Feb: orig-left (LL(1) expr); left (LR(0) automaton); right (bottom-up parse)
• 27 Feb: board (project 3 notes)
• 29 Feb: board (LR(0) trace (Nick, Zach))
• 5 Mar: board (project 3 notes)
• 7 Mar: board (LR(1) trace)
• 9 Mar: left (grammar ambiguity); right (else if, yacc)
• 19 Mar: left (lvalues, 3-addr code); right (got it/not)
• 21 Mar: board (yacc, ambiguity)
• 23 Mar: left (semantic analysis); right (converting parser)
• 26 Mar: left (converting parser); right (semantic analysis)
• 28 Mar: left (code generation---branching); right (branching in asm)
• 30 Mar: left (Proj 4 data); right (Proj 4 funcs/methods)
• 2 Apr: board (compiler chain, convert nodes)
• 4 Apr: left (Assembly); right (data layout)
• 9 Apr: left (code generation); right (addressing modes)
• 11 Apr: board (conversion nodes)
• 13 Apr: board (stack allocation)
• 16 Apr: board (register management)
• 20 Apr: board (putchar etc)
• 23 Apr: board (code gen example)
• 25 Apr: board (Project 5 phases)
• 27 Apr: board (assembly, reg mgmt)