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?