Compilers (coursera)
From https://class.coursera.org/compilers/lecture/preview
Video Lectures
Intro
01
Compiler and interpreter.
The interpreter takes the program and some data produces output. This would be scripting.
A compiler takes the program and produces and executable. This executable can be run on the data.
- lexical analysis
- parsing
- semantic analysis
- optimization
- code generation
02
Lexing breaks input into tokens. Parsing produces a tree. Semantic analysis checks that the program is correct. Optimization makes it run faster and use less memory, or any number of resource balancing. Code generation produces code, generally machine code.
03
Why are there so many programming languages? Application domains.
Programmer training is the dominant cost for a programming language.
Cool
01
Classroom object orient language.
Writes, compiles and runs a cool program.
02
Factorial example
03
List flattening example.
Lexical Analysis
01
Lexer breaks the code into tokens; string (or lexeme) + class.
Painfully slow example of manual tokenization.
02
Looked at bad classic examples. Lookaheads are sometimes required.
03
Regular languages. Union, concatenation, iteration.
04
Let a set of characters = Σ A language over Σ is a set of strings drawn from Σ
05
Details of regular expressions.
06
Deduceit demo...meh.
Finite Automata
01
R is the set of all regular expressions used in a language. How to make choices in ambiguity during lexing (identifier vs keyword). Should write an error class and put it last. Can be done with a single pass and very few character operations.
02
Finite Automata, state machines. Determinist (DFA) and Non-deterministic (NFA). An NFA accepts as long as one set of choices leads to an accepting state.
03
Convert regex to NFA.
Lex Spec → Regex → NFA → DFA → Tabled DFA
Building generic NFA segments from the 5 fundamental components of regex.
04
The ε closure for a state is all states that can be reached with only ε moves.
Begin with start, find all ε closures. Then find all possible inputs, then ε closures and so forth. Note that for an input, you have to group it with the &epsilon closures for that state.