Lecture Notes

These are the links to CB's lecture notes. All notes are in pdf. I suggest you use 4-page psnup (psnup -4) to print them. For that, convert the pdf files to ps with pdf2ps first. The fonts are large enough to be legible in 4-column format.

Linux example (for "other" systems, type the print command (lpr) separately, and eliminate the pipe '|'):

pdf2ps notes1.pdf
psnup -4 notes1.ps | lpr

These are not meant to be substitutes for coming to class or taking your own notes. My goal is to have less writing and more discussion in class.

Nobody learns anything by staring at it on a screen or printed paper (so much for on-line 'education' on my part). You have to come to class and study interactively with someone to turn these short notes into your personal experience.

1. Introduction: A walk through the stages of language processing
2. Lexical Analysis (reading: antLR lexical analysis)
3. Lexical analysis is linear, syntactic analysis is cubic. (CKY algorithm)
4. Syntactic Analysis
   1. Lookaheads and deterministic parsing
   2. LL(k) parsing
   3. Simple LR(k) parsing
   4. Canonical (general) LR and LALR (slides that are not provided are pages from the textbook)
5. Syntax-directed Translation
   1. Attribute grammars
   2. Parser generators: yacc/antLR
   3. Syntax-directed definition
   4. Abstract syntax trees and attribute evaluation (Updated!)
   5. Tree parsing
6. Semantic Analysis and Generation (for imperative languages, e.g. C, Java, Python etc.)
   1. Type systems and type checking
   2. Intermediate Code: IL instruction set; SL expressions
   3. Intermediate Code: IC templates and SL instructions
   4. Internal representation of IC
7. Run-time issues
   1. Run-time organisation
   2. Parameter passing and access to names
8. Optimisation and the target code
9. Compiling Functional Languages (Haskell, ML, Miranda etc.)
   1. Functions and lambda calculus
   2. Graph reduction as program evaluation
   3. Combinators and Supercombinators
   4. SK-machine as a Virtual Machine (aka. "the mother of all combinators")
   5. Some optimisation: BSC-machine versus the SK-machine
10. Compiling Logic Languages (Prolog)
    1. Definite Clauses as Programmes
    2. Quantifier elimination: Skolemisation
    3. SLD Resolution
    4. The Warren Abstract Machine (WAM)