Compiler

Call by value

Actual parameters are evaluated and their r-values are passed to the called procedure. Operations on the formal parameters do not affect values in the caller.

Call by reference

The caller passes to the called procedure a pointer to the storage address of each actual parameter. A reference to a formal parameter in the called procedure becomes an indirect reference through the pointer passed to the called procedure. Change of values in the called procedure will affect the values in the calling procedure.

Basic block

A logical grouping of consecutive statements, with the property that jumps from other basic block into a block can only happen by entering the block start (leader), and jumps into another block can only happen at the block end.

Flow graph

A directed graph that represents the execution flow of a program. The nodes are the basic blocks and there is a directed edge from block A to block B if B can immediately follow A either because of the program order or because of a jump.

Optimization using flow graph

In a process called control flow analysis, the optimizer can identify loops from the flow graph of the program. Using this information, various optimization can be performed.

Dominator

a dominates b in a flow graph if every path from the initial node to b goes through a.

First set

A → a | ε

C → c | ε

B → Ab

D → AC

FIRST(A) = {a, ε}

FIRST(C) = {c, ε}

FIRST(B) = {a, b} (note that ε is not in FIRST(B))

FIRST(D) = {a, c, ε} (ε is in FIRST(D) because if A → ε and C→ ε, then nothing will be generated)

Follow set

$ is in FOLLOW(START_SYMBOL) ε cannot be in FOLLOW

Recursion elimination

Move from rules for nonterminal 1 to n

If it refers to a nonterminal before it, replace with the actual values
eliminate recursion to oneself

LL(1)

Grammar LL(1) cannot be ambiguous or left-recursive

LR(1)

First construct the canonical item set with their goto relation.

If A → α・aβ is in I_i and goto(I_i, a) = I_j, then action[i, a] = shift j (a is a terminal)

If A → α・ (other than S' → S・) is in I_i and a is in FOLLOW(A), action[i, a] = reduce with rule A → α

If S' → S・ is in I_i, action[i, $] = accept

If A → α・Bβ with B a nonterminal is in Ii and goto(I_i, B) = I_j, then goto[i, B] = j

Canonical LR

The first item is [S' → ・S, $]

The thing to note is when doing closure. [A → α・Bβ, a] yield [B → ・γ, FIRST(βa)]

Making table:

For terminal, goto maps to shift
[A → α・, a] (A not S') maps to reduce (no need to find FOLLOW(A))
[S' → S・, $] maps to accept

LALR

Just join sets having the same core

Common subexpression elimination

a = b + c;
d = b + c;

becomes

a = b + c;
d = a;

API

Interface implemented by a software program which enables it to interact with other software. An API is implemented by applications, libraries, and operating systems to determine their vocabularies and calling conventions, and is used to access their services. It may include specifications for routines, data structures, object classes, and protocols used to communicate between the consumer and the implementer of the API.

module strength/cohesion

A measure of its modularity. A strong module is the one that performs a single logical task, for example the function sin(x). A weak module is a jumble of many tasks.

def 1: The degree that actions within a single program module are related to one another

オートマトン

from regular language to DFA

Suppose M is an automata, with F the set of final states.

R(i, j, k) means all strings in Σ^* that drives M from q_i to q_j without passing through state k or greater (but state k can be the endpoints). Starting state is q₁, the number of states is n, i and j runs from 1 to n, and k runs from 1 to n + 1.

L(M) = ∪{R(1, j, n+1): q_j ∈ F}

R(i, j, k + 1) = R(i, j, k) ∪ R(i, k, k)R(k, k, k)*R(k, j, k)

the basic sets are a ∪ b ∪ ... ∪ n

and ε ∪ a ∪ b ... ∪ n

正規言語に対する反復補題

Lを正規言語とする．定数nで，Lに属し，かつ，|w|≥nを満たす任意の文字列wに対し，wを次の条件を満たす3個の部分列の連接w = xyzに分解できるようなものが存在する．

y ≠ ε．
|xy| ≤ n．
すべてのk ≥ 0に対し，文字列xy^kzもまたLに属する．

正規表現の演算子の結合の強さ

閉方 > 連接 > 和

εを削除する

n/a

準同型写像

文字列に対する準同型写像(homomorphism)とは、文字列上で定義される関数（写像）であり、文字列の中の各文字を特定の文字列で置き換えるものである。

定理 4.14

LがアルファベットΣ上の正規言語であり，hがΣ上の準同型写像であるとき，h(L)も正規言語である．

逆準同型写像

hをあるアルファベットΣから別のアルファベットT上の文字列への準同型写像とする．LをアルファベットT上の言語とする。このとき，h^-1(L)は、Σ^*に属す文字列wで，h(w)がLに属すようなものの全体から成る集合である．

定理 4.16

アルファベットΣからアルファベットTへの準同型写像をhとする．LがT上の正規言語であるならば，h^-1(L)もΣ上の正規言語である．

{ Lのオートマトンから、L'を作る．L'の遷移関数γは、Lの遷移関数δをもとに作る．

\gamma (q,a)={\overline {\delta }}(q,h(a))

}

Pushdown automaton

A pushdown automaton is a tuple M = (K, Σ, Γ, Δ, s, F), where

K is a finite set of states,
Σ is an alphabet (the input symbols),
Γ is an alphabet (the stack symbols),
s ∈ K is the inital state,
F ⊆ K is the set of final states, and
Δ, the transition relation, is a finite subset of (K × Σ* × Γ*) × (K × Γ*)

push a: ((p, u, e), (q, a))

pop a: ((p, u, a), (q, e))

{この括弧のある文章は自作}