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.

06

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.

DID NOT FINISH, STOPPED AFTER FIRST QUESTION (7:37)