ECE251: Programming Languages and Translators (Fall 2010)

Patrick Lam

You may use these lecture notes however you like. I am placing no restrictions on their use. As far as I'm concerned, feel free to remix and share. I'll make the git repository available shortly.

• Lecture 1: Introduction. Bootstrapping. Parts of a compiler.
• Lecture 2: (version 2) Scanners: learning objectives. Regular expressions: Motivating applications, scanner example, what versus how, finite automata.
• Lecture 3: (version 2) Regular expressions: Syntax and semantics. Deterministic Finite Automata. Nondeterministic Finite Automata. Executing NFAs and DFAs. Expressive power. Efficiency.
• Lecture 4: Executing regular expressions (compilation to NFAs). Summary of regular expressions, NFAs and DFAs.
• Lecture 5: String-processing applications of regular expressions. Using the string matching API. Operational vs. declarative semantics in language design. Regular expressions vs. regexps.
• Lecture 6: Interlude on (writing) Interpreters and Domain-Specific Languages (internal and external).
• Lecture 7: Parsers: learning objectives. Parsing example.
• Lecture 8: Context-free grammars. Backus-Naur form (and EBNF, railroad syntax diagrams). More parsing examples. Regexps vs CFGs.
• Lecture 9: Crash course on object-oriented programming. Types, inheritance, polymorphism, and type casting. Back to parsing: ambiguity, parse trees example. Recursive descent parser example.
• Lecture 10: Parsing an expression. Building recursive-descent top-down parsers: basic scheme; FIRST and FOLLOW set examples.
• Lecture 11: General algorithm for computing FIRST sets. Where to use them.
• Lecture 12: Fixing grammars to work with top-down parsing: eliminating ambiguity and left-recursion. About common prefixes.
• Lecture 13: Recap of parser generators. Bottom-up parsing and common ailments with it. Four examples.
• Lecture 14: Interlude: Abstract Syntax Trees, Visitor Pattern.
• Lecture 15: Scoping. Static versus Dynamic. Issues in static scoping.
• Lecture 16: How to build a symbol table with a list of tables. Symbol table operations and their uses.
• Lecture 17: Execution: interpreters, virtual machines, native code. Big picture (what you can do with what). Interpreting ASTs.
• Lecture 18: (version 2) Interpreting bytecodes. Three-address code and virtual machine implementation. Quadratic formula example.
• Lecture 19: Other uses of ASTs: source-to-source transformations, generating three-address code.
• Lecture 20: Code optimization, register allocation, object headers. Native code generation intro.
• Lecture 21: Recap of the course so far. JIT compilation and dynamic binary translation.
• Lecture 22: Type checking. Definitions. Type checking examples. Type coercion.
• Lecture 23: Coercion example. Type equivalence. Formalism for type checking (type rules, environments). Implementation issues.
• Lecture 24: Intro to programming paradigms: functional, logic, scripting.
• Lecture 25: (version 2) Scala quicksort example: imperative and functional styles. Higher-order functions: map, filter.
• Lecture 26: More higher-order functions: fixing a parameter; currying and uncurrying; fold and reduce.
• Lecture 27: MapReduce. Introduction to logic programming.
• Lecture 28: Prolog (a superficial view).
• Lecture 29: Overview of scripting languages: use cases, common characteristics, application domains.
• Lecture 30: Domain-specific languages for the Web. How the Web works. Apache server-side includes as a DSL. CGIs. Languages for dynamic webpages.
• Lecture 31: PHP and compiler techniques. Client-side Web programming.
• Lecture 32: Other domain-specific languages: protein structures, drawing languages, XML, Java extensions.
• Lecture 33: Course summary: relating the parts of the course to the course goals.