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.
05
FAs can be stored as tables, in practice, arrays.
Parsing
01
Lexers (regular languages) can't count. Parsers can.
02
A CFG consists of
- A set of terminals
- Set of non-terminals
- Start symbol
- Set of productions (S → (S))
This still seems reversed to me. How to go from string back to grammar?
03
Derivations, seems obvious, but not useful.
04
Ambiguity. Use different symbols to force unabiguity.
It is not possible to automatically convert an ambiguous grammar to an unambiguous.
In practice this is done with associtivity and precedence.
Top Down Parsing
01
Panic Mode: Continue consuming tokens until we find a token we know what to do with then resume parsing.
Error Productions: specify common mistakes in the grammar. (promotes common mistakes to alternative syntax)
Error Correction: try to find a "correct nearby" program. But this is hard, slows down parsing and can produce incorrect (unintended) output.
Historically, these techniques used to be more important. Compile times could be upwards of a day and it was valuable to find as many errors as possible, and even try to produce working code despite those errors.
02
Abstract syntax trees. Parse trees are inconvenient for compilers.
03
Recursive decent parsing. Actually, fairly straight forward. Start with the first production rule, and continue to follow the highest production rule until a terminal symbol is reached. If that terminal symbol matches the current symbol, keep going. If not, back up a level and move the next production rule. If that level has no more rules, back up another production level.
Seems slow, but it would work.
04
Good lecture, shows the mechanisms of implementing recursive decent.
05
Left recursion; this happens if you get infinite left recursion. Can be re-written as two rules. Left recursion can be automatically removed, does not require manual correction.
Predictive Parsing
01
Predictive Parsing. No backtracting. Looks ahead to the next few tokens. Only works for a restricted set of grammars, the LL(k) grammars. That's left-to-right left-most-derivation k-token-look-ahead. In practice, k is always 1.
Each production rule for a given token must start with a symbol unique to that symbol. To do this we factor out common prefixes using left factorization.
The stack is the fronteir of the parse tree.
This is pretty cool!!!
02
First Sets.
If a terminal doesn't match, that not necessarily a reject state, if the current branch can reach ε the next branch may accept the terminal. We say t ∈ Follow(A). (t is a terminal and A is non-terminal).
The first set of every terminal is just that terminal. For non-terminals, trace down through all possible branches until terminals are reached and record the first terminal. Any time an ε is encountered, we need to look at the next symbol as well.
03
The follow symbols are everything that can follow a given symbol.
Start with
$ ∈ Follow(S) // S: start, $: end
For each
A → α X Β
Define
First(Β) - {ε} ⊆ Follow(x)
And if
ε ∈ First(Β)
Then
Follow(A) ⊆ Follow(X)
It looks like loops can arise, need to catch that. Don't include ε in follow sets.
04
Filling in the table is pretty straight forward (table is non-terminals x terminals). Then adding ε requires looking up follows. If a rule contains an ε we add it for each of the follow symbols for that rule.
Some grammars are not LL(1), it will produce multiple entries in the parse table.
05
Bottom-up parsing. More general than top-down parsing. Generally, the preferred method. Don't require left-factored grammars.
Reduces a string by inverting productions, known as reductions. When the productions are read backwards, they trace a rightmost derivation.
06
Shift-reduce parsing.
Let
αXω → αΒω
Assume the reduction is by
X → Β
Then there are no terminals to the right of X because ω is a terminal.
To do bottom up parsing we only need Shift and Reduce. Reduce is explained above, shift just shifts the marker in the string.
So, given
Cbxyijk
Split as
Cbxy | ijk
We perform a Reduce on the rightmost section of
Cbxy
The split point starts all the way to the left and moves right with each shift. The left portion can be implemented as a stack.
Bottom-up Parsing 2
01
Handles. We don't always want to reduce even if we can, this can lead to error states when a correct was possible.
Given
S →* αXω → αΒω
Then αΒ is a handle of αΒω
We only want to reduce on handles.
02
Recognizing handles. There is no known efficient algorithm to recognize handles.
For any grammar, the set of viable prefixes is a regular languages. The stack is always a stack of prefixes. Eventually, Prefixk+1...Prefixn will reduce to αk.
03
Recognizing viable prefixes.
We're going to build an NFA that will run against the stack determine if it is a viable prefix. If it is not, we have a parse error. The NFAs get *very* complex.
04
Valid Items
Item
X → Β.γ
is valid for viable prefix
αΒ
if
S' →* αXω → αΒγω
After parsing αΒ, the valid items are the possible tops of the stack of items.