# Theory of computation

The theory of computation is mathematically model a machine (for example a computer) and study the theory about it which means what are the problems which would be solved by this machine, what are the limitations of the machine etc.

## Compiler basics

• Compilers vs interperters

• Structure of a compiler
The structure of a compiler consists of 5 major fases:

1. Lexical analysis
Lexical analysis divides program text into words also known as lexemes by reading the text from left to right.

The output of the lexical analysis is a series of tokens where the token class for each lexeme is identified. A token consists of: <token class, lexeme>

Lookahead is always needed to decide where one token ends and the next token begins.
Minimize the amount of lookaheads to simplify the implementation of the lexical analyzer.

2. Parsing
Parsing is diagramming sentences to understand sentence structure.

3. Semantic Analysis
Understand meaning to sentences to catch inconsistencies.

4. Optimization
Automatically modify program so that they run faster, use less memory, reduce power usage, use less database/network connection etc.
Modern compilers spend large amount of time in optimization compare to other fases.

5. Code generation
Produces usually assembly code (translate into another language).

• Regular languages
Regular languages are used to determine which set of strings is in a token class.

To define regular languages, regular expressions are used. Each regular expression (=syntax) denotes a set of strings (=regular languages).
There are two basic regular expressions:

• A single character

A single character 'c' is an expression which denotes a language containing a string with a single character:
'c' = {"c"}

• Epsilon

ε is an expression which denotes a language containing an empty string:
ε = {""}

There are three compound regular expressions:

• Union (∪)

A + B is an expression which denotes a language containing a string:
A + B = {a | a∈A} ∪ {b | b∈B}

• Concatenation (∧)

AB is an expression which denotes a language containing a string:
AB = {ab | a∈A ∧ b | b∈B}

• Iteration (*)

A* is an expression which denotes a language containing a string:
A* = ∪i>=0Ai
Ai = A0, A1, A2, A3,...
A0 = ε
Note: The empty string (ε) is always a elements of A*.

Definition: The regular expression over Σ (=alphabet) are the smallest set of expressions including:
R = ε | 'c' | R+R | RR | R*
Note: 'c' ∈ Σ

If we want to know the regular language we need to know what the alphabet (Σ) is.

Σ = {0,1}

Question: The expression 1* what language does it denotes?
Answer: ε + 1 + 11 + 111 + 1111 + ...
All strings of 1's.

Question: The expression (1+0)1 what language does it denotes?

Question: The expression 0* + 1* what language does it denotes?
Answer: {0i | i>=0} ∪ {1i | i>=0}

Question: The expression (0 + 1)* what language does it denotes?
Answer: {"",(0 + 1),(0 + 1)(0 + 1),(0 + 1)(0 + 1)(0 + 1),...}
This means ALL strings of 0's and 1's. Can also be indicated by Σ*

• Formal languages

A language over Σ is a set of strings of characters drawn from Σ.
Formal language examples:

Alphabet = English characters
Language = English sentences

Alphabet = ASCII
Language = C programs

• Meaning function (L)

Meaning function L maps syntax to semantics. A meaning function is used:
• It makes clear what is syntax and what is semantics.
• Allow us to consider notation as a separate issue.
• Because expressions and meanings are not 1-1. There are more expressions than meanings. Meaning is many to one and never one to many.

L(e) = M
e = regular expression
M = set of strings

Example:
L(ε) = {""}
L('c') = {"c"}
L(A+B) = L(A) ∪ L(B)
L(AB) = {ab | a∈L(A) ∧ b | b∈L(B)}
L(A*) = ∪i>=0 L(Ai)

• Regular expression shorthand notation
• At least one: A+ ≡ AA*
• Union: A | B ≡ A + B
• Option: A? ≡ A + ε
• Range: [a-z] ≡ 'a' + 'b' + 'c' + 'd' + ...
• Excluded Range: [^a-z] ≡ complement of [a-z]

• Lexical specifications

Regular expression describe many useful languages.
Regular languages are a language specification.
Regular expressions is used as the specification language for lexical analysis.

• Keywords
"if" + "then" + "else"

• Integer: a non-empty string of digits
digit = '0' + '1' + '2' + '3' + '4' + '5' + '6' + '7' + '8'+ '9'
Integer = digit digit* = digit+

Note:
* = 0 or more
+ = 1 or more

• Identifier: string of letters or digits, starting with a letter
letter = 'a' + 'b' + 'c' + 'd' + ... + 'A' + 'B' + 'C' + 'D' + ...
letter = [a-zA-Z]
Identifier = letter(letter+digit)*

• Whitespace: a non-empty sequence of blanks, newlines and tabs.
Whitespace = (' ' + '\t' + '\n')+

Examples:

Email address = letter+ '@' letter+ '.' letter+

number = 12 or 12.34 or 12E+8
digit = '0' + '1' + '2' + '3' + '4' + '5' + '6' + '7' + '8'+ '9'
digits = digit+
opt_fraction = ('.'digits) + ε = ('.'digits)?
opt_exponent = ('E'('+' + '-' + ε) digits) + ε = ('E'('+' + '-')? digits)?
number = digits opt_fraction opt_exponent

To design the lexical specification of the language the following procedure must be followed:

1. Create regular expression for the lexemes of each token class
• Number = digit+
• Keyword = 'if' + 'else' + ...
• Identifier = letter(letter+digit)*
• OpenPar = '('
• :

2. Construct a gigantic regular expression R, matching all lexemes for all tokens

R = Keyword + Identifier + Number + ...
R = R1 + R2 + R3 + ...

3. Loop thru the input and check it against the meaning function L(R)

Let input be x1...2
For 1 <= i <= n check
x1...i ∈ L(R)

Note:
• Always choose the longest input ("maximal munch").
• If there is more than one token class which the input might belong choose the one listed first. In the lexical specification, keywords are given a higher priority than identifiers.

4. If success then we know that:
x1...i ∈ L(Rj) for some j

If no rule matches, create error strings for all strings not in the lexical specifications.
Put these error strings last in the priority list.

5. Remove x1...i from input and go to step 3

• Finite Automata

Finite automata is used as an implementation model for regular expressions. Regular expressions and finite automaton are very close related. They can specify exactly the same languages called the regular languages.

A finite automaton consists of:

• An input alphabet: Σ
• A finite set of states: S
• A start state: n
• A set of accepting states: F ⊆ S
• A set of transistion states: state ->input state

The language of a finite automaton ≡ set of strings that the automaton accepts.

• Deterministic Finite Automata (DFA)

• One transistion per input state
• No ε-moves

A DFA takes only one path through the state graph per input.
DFAs are faster to execute than NFAs because there are no choices to consider.
DFAs and NFAs recognize the same set of regular languages.

• Nondeterministic Finite Automata (NFA)

• Can have multiple transistions in a given state
• Can have ε-moves

An NFA accepts if some choices lead to an accepting state.
NFAs are, in general, smaller compared to DFAs.

• Regular expressions into NFAs

Lexical specification we want to implement -> write a set of regular expressions -> translate regex to NFAs -> translate NFAs to DFAs -> implement DFAs as a set of Lookup tables and code for traversing thos tables.

For each kind of regex define an equivalant NFA
Notation: NFA for regexp M