Compilers (coursera)

From https://class.coursera.org/compilers/lecture/preview (now https://www.youtube.com/watch?v=cfsN0r-DOWo&index=28&list=PLFB9EC7B8FE963EB8)

Seriously, fuck coursera: http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=Compilers

http://prog21.dadgum.com/30.html

http://squanch.org/writing-a-compiler-in-go/

https://www.youtube.com/watch?v=-E2tu3MqR24

https://www.youtube.com/watch?v=G78cTmgeUxI

https://github.com/DoctorWkt/acwj

https://www.cs.cornell.edu/courses/cs6120/2020fa/self-guided/

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.

For example, to enforce * over +:

 E → E' + E | E'
 E' → id * E' | id | (E) * E' | (E)

The associative example used nested if...then...else. The else should always associate to the closest if

 E → if E then E
 E → if E then E else E

Above is ambiguous. Below is not

 E → MIF
 E → UIF
 MIF → if E then MIF else MIF
 UIF → if E then E
 UIF → if E then MIF else UIF

but I'm not clear on how to get E back into MIF

I think you can use the order to define the 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, Prefix_k+1...Prefix_n 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.

05

SLR Parsing. Looking at reduce/reduce and shift/reduce conflicts. Add heuristics and precedence. Though really, they are conflict resolutions not precedence.

06

SLR Parsing example. SLR parsing is k=1. I think we reduce whenever possible. But it is not possible is the next symbol is NOT in the follow. The next symbol not being in the follow means it must be in the current symbol. I'm a bit confused, it looks like after replacing part of the stack with a reduction, we reparse the whole stack. By having a single start symbol, if we reach it with no more input, we can accept.

07

Ah, they're addressing my repeated-work concern. Store the DFA state associated with each symbol on the stack. Also the start now needs to be <any, start>

The algorithm for running the SLR parser is very concise, but building the parse table is a bit tricky.

Interesting note, the parser never actually uses the lexemes. We could get rid of them, but we'll need them later for semantic analysis.

08

Show that

 S' → S
 S → SaS
 S → b

Is not SL(1), it produces an unresolvable shift-reduce conflict.

Semantic Analysis and Type Checking

01

Semantic analysis handle some error that the parser cannot. It is the last filter step. After this, we can successfully compile.

02

Scope.

03

Symbol tables. We use a stack. Or, start scope, check, add and find, then exit scope.

For classes, we need two passes. One to find all classes, then another to check class usage. Semantic analysis requires multiple passes, sometime, many passes.

04

Types. Types are a set of values and a set of operations on those values.

Static and dynamic typing.

05

Type checking. The formalism for type checking is logical rules of inference. Symbols used:

 ⇒ if-then
 ^ and
 x:T x has type T

So

 e1:int ^ e2:int ⇒ e1 + e2:int

06

Type Environments.

07

Subtyping. lub(x,y) is the least-upper-bound of x and y, the first shared super-class of x and y. If nothing else, it will be 'object'

08

Typing methods.

09

Implementing Type Checking.

Type Checking

01

Some correct programs will be disallowed by the type checker. Dynamic type checking is more accepting.

Methods can be redefined, but must have the same type.

02

SELF_TYPE and inheritance.

03

More Self_type...

This is getting super boring, skipping to...

Runtime Organization

01

• Static: compile time
• Dynamic: runtime

How memory is used to store the execution of the program. OS loads program into memory and jumps to 'main'.

02

Activations.

To overall goals: correctness and efficiency. Either is easy, both is hard.

Two assumptions:

• Execution is sequential
• When a procedure is call, control always returns to the point immediately after the call

Lifetime is a dynamic concept, scope is a static concept.

If P call Q, Q will return before P.

03

more activations

04

Globals can't be stored in an activation record.

Heap and stack work from opposite ends of memory, growing towards the center.

05

Alignment. 8bits in a byte, 4 or 8 bytes in a word(32/64 bit architecture). Machines are either byte or word addressable. Data is word aligned if it begins at a word boundary.

06

Stack Machine. Operates on the top of a stack. More compact than register machines. But a register machine is (generally) faster.

Opposed to a register machine, which names it's registers.

A 1-register stack machine is called an accumulator.

Code Generation

01

x

02

Code generation follows templates, doing + in example.

03

Code can be generated recursively.