# 編譯器設計
###### tags: `資工系課程`

## CH1

### Compiler（編譯器）
翻譯與產生執行檔

### Interpreter（直譯器）
翻譯與直接執行

### Interpreter vs. Compiler
- Interpreter通常比較慢，因為要同時做兩件事
- Interpreter可以給比較明確的錯誤訊息，因為執行有問題就停住，會知道哪裡有問題

### The Structure of a Compiler
每個部分稱為phase，需要的部分都可以存在symbol-table中，phase有需要就可以去拿。
可以把很多的phase組合起來，像是front-end中的phase組合起來變成pass，就稱為front-end pass。

#### Lexical Analysis
會做詞彙上的分析，切出每個word

**Token: <token-name, attribute-value>**

token-name：類別
attribute-value：屬性，通常會用指標指到某個symbol table

#### Syntax Analysis
進行語法檢查、並構建由輸入的單詞組成的資料結構

#### Semantic Analysis
會做語意上的分析，看是否符合程式語言的規範


#### Intermediate Code Generation
產生中間表示式，兩個重要的特性1.Easy to produce 2.Easy to translate into the target machine

#### Code Optimization
做程式碼的優化

#### Code Generation
輸出組合語言

#### summary

### Metalanguages
**a language used to describe,define, or discuss another language**
舉例來說一些compiler tool會需要有一些規範，這些規範用的語言就是metalanguages

## CH3

### Lexical Analyzer and Parser
Lexical analyzer會做出一個一個token，後一個parser(syntax analysis)會主動地要求這些token，並且這兩個偶爾會到symbol table去放資料

### Token
token是程式語言語法的最小單位
可將token分類成有限的一連串的token type。

### Pattern

描述token長什麼樣子

### Lexeme
實際上的樣子




### Problems When Recognizing Tokens

有的時候需要往後多看幾個才能決定怎麼切

### Concatenation

### Kleene Closure
從 L 中取出任意數量的字符串（可能沒有）形成的字符串集合，可能有重複並連接所有這些字符串。

### Regular Expression (RE)
- A language allows us to use a finite description to specify a (possibly infinite) set
- **RE is the metalanguage used to define the token types of a programming language.**

還有一堆例子，請參考簡報

### Regular Definition
Names for regular expressions
類似於給綽號
C identifiers are strings of letters, digits, and underscores.

### Notational Abbreviations

[^abc] 除了a或b或c之外的都可以
[a-z] 如果是連續的就用-代替

[0-9]+ 至少要有一個
[0-9]* 可能沒有

### Finite Automata

#### Nondeterministic Finite Automata (NFA)
S: a finite set of states（state是有限的）
∑: a finite set of input symbols（symbols有限）
δ: a transition function that maps (state, symbol) pairs to sets of states（當你在某個state遇到某些symbol就會跑到其他的state）

範例1：

NFA可接受

NFA不可接受

範例2：

#### Operations on NFA states

ε-closure(s):可以瞬間移動到某一個state
ε-closure(S)：可以瞬間移動到某一些state
move(s, c): set of states to which there is a
transition on input symbol c from a state s
move(S, c)：與上方同理

#### NFA pseudo code

練習：

### Deterministic Finite Automata (DFA)
S: a finite set of states
∑: a finite set of input symbols
**δ: a transition function that maps (state, symbol) pairs to a state in S**
s0: a state distinguished as start state
F: a set of states distinguished as final state

#### DFA與NFA不同
- No state has an ε-transition
- **For each state s and input symbol a, there is at most one edge labeled a leaving s**
一個label a在一個state只有一條或是0條路

#### example

#### DFA可接受

#### DFA不可接受

#### DFA pseudo code

### Combined Finite Automata
NFA只要用ε move就可以滿足三種狀況

碰到iffail+可能會有問題，所以應該要match到最長的那個

解決方法：
Ｐ是指該字元在字串中的第幾個位置

### From a RE to an NFA
i表示start state,f表示final state

最下方的路徑代表可能什麼都沒有，最上方的代表可能會繞很多次，中間兩個代表可能只有一次


### NFA to DFA
Example：



Pseudo code
Dstates為上方大寫的ABCDE

### Minimizing the Number of States
Example

拆分流程
E跟其他人不一樣是因為是final state
D跟其他的不一樣是因為只有他可以到final state
因為AC遇到ab之後的反應是一樣的所以為一組

縮減結果

### Recognize Lexemes

## CH4
### Syntax Error Handling
目標：
- It should report the presence of errors clearly and accurately.（處理語法上錯誤時應該要精確且快速）
- It should recover from each error quickly enough to be able to detect subsequent errors.（錯誤可能會有很多，發現錯誤時要很快偵測，後續的也是趕快抓出來）
- It should not significantly slow down the processing of correct programs.（抓錯不該拖慢編譯的效率）

### Error Recovery Strategies

#### Panic mode
在發現錯誤時，parser一次丟棄一個輸入符號，直到找到一個synchronizing
tokens(像是分號)，然後就重新再繼續檢查。

#### Phrase level
遇到錯誤的時候，替換一個能讓目前parser執行下去的符號，例如把逗號換成分號

#### Error production
清楚語法規則，把最有可能出錯的地方，寫成 production rules
例如知道正確的語句語法為 $<stat> → <id><=><expr><;>$
預知錯誤的形式可能是少「=」或「；」
$<stat> → <id>error<expr><;>$
$<stat> → <id><=><expr>error$

#### Global correction
- 嘗試以最低修正次數將有錯誤的輸入改成正確的
- 最接近的正確程式可能不是programmer的想法，所以還是得告訴programmer做了什麼樣的修正，並且讓programmer決定

### Context-Free Grammars (CFG)
可以用context-free grammars描述語法

#### 優點
- 能精確描述程式語言
- 已證明若某些context-free grammars符合特定限制，我們便能找到工具自動產生parser
- 用設計良好的 grammars轉譯target code/機器碼比較方便
- 新的語法很容易更新加入現有的grammars

#### 一些定義
**G = (VN, VT, P, S)**
- VN為nonterminals可用來表示a set of strings
- VT為terminals是basic symbols (token types)
- A set of productions P: rules specifying how the terminals and nonterminals can be combined to form strings
- The start symbol S: a distinguished nonterminal that denotes the whole language

舉例：

#### Derivations推導
推導基本上是一系列生產規則，以獲取輸入字符串
S => … => a
or S =>* a
S =>+ a

### Scanner and Parser

### Notational Conventions
看一下就好

### CFG v.s. RE
- CFG也可以描述RE描述的東西
- CFG雖然比較強大，但RE更簡單理解及對於lexical analyzers更有效率

### Construct the CFG from a NFA
1. 每個NFA的state i 會產生nonterminal Ai
2. If state i has a transition to state j on input a, add the production Ai → aAj（如果state i在碰到a時有transition到state j 則新增production Ai → aAj）
3. If state i goes to state j on input ε, add the　production Ai → Aj(如果i到j之間有ε，新增production Ai → Aj)
5. If i is an accepting state, add Ai → ε（如果ｉ是accepting state又可稱final state，就新增Ai → ε）
6. If i is the start state, make Ai be the start symbol of the grammar（如果ｉ是start state，則Ai就是start symbol）

### Parse Trees
- root為start symbol
- 每個最底層的葉子都由一個token標記或是ε
- 每個中間的node都是nonterminal，也就是最底層是terminal

**Example**

### Three General Types of Parsers for Grammars
都是由左而右去看input

**Universal**
- Can parse any grammar
- Too inefficient to use in production compilers

**Top-down**
- Build parse trees from the top to the bottom

**Buttom-up**
- Build parse trees from the bottom to the top

### Push Down Automata (PDA)
- We will use $ to represent the end-of-file
marker
- We will also use $ to represent the bottom of stack maker

**example**
a↓表示push到stack中 (a, $)表示遇到a且stack的top為 $則做下方的事

### Top-Down Parsing
目標是cad，要挑對的prodection rule使得變為cad
第三個還沒有錯誤，所以不用backtrack

### Predictive Parsing
是top-down的parsing並不需要backtracking
因為會偷偷看下一個token是什麼所以就會知道production要選哪個
像是知道是if就會猜到後面有then else這些

也被稱為LL(k) parsing，第一個L代表input掃描是從左到右，第二個L代表leftmost derivation(之後要修改都是選最左邊的)
K代表會提前多看K個lookahead

#### LL(1) Parsing
有兩種實作方式
- Recursive-descent parsing
- Table-driven predictive parsing

### Recursive Descent Parsing

Ｓ有三個選擇、Ｌ有兩個、Ｅ有一個選擇，一開始Ｓ先選begin那個之後L選S;L
再來S選Print、最後E就是num

FOLLOW是指看緊跟在L後面的有誰，因為看這個才知道L是不是變成ε，且因為begin L end那行，所以如果L變ε就代表可以直接看到end，因此這樣就可以知道L是不是變ε

const int IF = 1, THEN = 2, ELSE = 3,
BEGIN = 4, END =5, PRINT = 6,
SEMI = 7, NUM = 8, EQ = 9;
int token = scanner();
void match(int t) 
{ 
    if (token == t)
        token = scanner();
    else
        error(); 
}
void S() {
    switch (token) {
        case IF: match(IF); E(); match(THEN); S();
            match(ELSE); S();
            break;
        case BEGIN: match(BEGIN); L(); 
            match(END);
            break;
        case PRINT: match(PRINT); E();
            break;
        default: error();
    }
}
void L() {
    switch (token) {
        case IF:
        case BEGIN:
        case PRINT: S(); match(SEMI); L();
            break;
        case END: break;
        default: error();
    }
}
void E() { 
    switch (token) {
        case NUM: match(NUM); match(EQ);
            match(NUM); 
            break;
        default: error();
    }
}

### Computing First Sets
第三點在講如果First(x)是Yi，代表Yi之前的全部都是ε才有可能這樣，並且First(Yi)為a，所以First(x)裡面也有a；如果整個都有可能不見(Y1~Yk)則ε就會加進First(x)中

第二點是如果要看follow(B)就要看First(β)中除了ε以外的
第三點是指如果今天A可以推到αB，就代表Follow(A)也會在Follow(B)中。舉例如果今天有Aa這個東西，follow(A)就為a，且A可以替換掉，最後變成αBa，所以Follow(B)=中就有a

Follow(E)的部分是因為S可以推到Print E，因此S的follow也會在E的follow裡面；另外因為S是start symbol所以會有錢字號。

### Table-Driven Predictive Parsing
因為L->S;L所以First(L)中就有First(S)的，另外因為L->ε所以要看有沒有碰到Follow(L)也就是end的部分

就是看stack中的top對應到input第一個詞之後再參考上面的表格對應的句子，之後替換掉stack中的top，如果stack(top)==input(top)則pop出變成matched中的詞

**講義後還有一個例子可以參考練習(推薦要看，因為好難)**

### LL(1) Grammars
A grammar is LL(1) iff its predictive parsing table has no multiply-defined entries（不能有多個rule）

第一點是若兩個有重複的為{y} 則今天A遇到y時，要把A->α跟A->β都填進去
範例：

Ambiguous Grammars 範例：

Solution:

### Left Recursive Grammars
可以改寫成
範例：


### Left factoring
有common的部分可以等到之後再決定不一樣的地方是誰

範例：

### Error Handling in Predictive Parsing
自行看講義p95

## CH5

### Definition
syntax-directed definition是指context-free grammar加上semantic attributes及semantic rules

semantic rules:是用來計算attributes的規則

Each grammar symbol is associated with a set of semantic attributes


#### Semantic Attributes
attribute如果是synthesized表示他從children拿值來計算得到的
如果是inherited則從parent and siblings拿值來計算得到的

Terminals can have synthesized attributes, **but not inherited attributes.**

#### Attribute Grammar
An SDD (syntax-directed definition) without side effects is sometimes called an attribute grammar（沒有做其他額外的事：add an entry into symbol table, generate intermediate code,...)

### Annotated Parse Trees
A parse tree, **showing the value(s) of its
attribute(s)** is called an annotated parse tree


值都是從children過來

### Inherited Attributes
Example1:



Example2:


### Semantic Rules

### Dependency Graphs


### S-Attributed Attribute Grammars
grammar is S-attributed if it uses **synthesized attributes exclusively**


### L-Attributed Attribute Grammars
grammar is L-attributed if each attribute computed in each semantic rule for each production is a **synthesized attribute, or an inherited attribute**

舉例：A → X~1~ X~2~ … X~n~
1. the attributes of X~1~, X~2~, …, X~j-1~, 1<=j<=n
2. the inherited attributes of A


### Translation Schemes
Syntax-directed translation scheme (SDT):
A translation scheme is a context-free grammar in which program fragments called **semantic actions**（有包含動作，用大括號刮起來） are embedded within the right sides of productions

ＳＤＴ會很清楚告訴你什麼時候要做這些動作以及順序關係

下面的為SDT，上面是SDD

### An Example - Translation
因為T()有回傳值，所以透過tnptr去接；ri=tnptr為大括號的動作
rs為R()的回傳值，ri為R()需要的傳入參數

syntax_tree_node * R(syntax_tree_node * i) 會有括號中的東西是因為會有傳入參數


### Syntax Tree
Use a data structure AST (abstract syntax tree)to **serve as the central data structure** for all post parsing activities

In a syntax tree, operators and keywords do not appear as leaves

### An Example: Syntax tree for “a-4+b”

### Type Declarations

statement 幾乎都有先檢查，再指派S的type

## CH6

### Three-Address Code(Pseudo Assembly Code)

==There is at most one operator on the right side of an instruction==


#### Types of Three-Address Code



### Implementation of Three-Address Code
優化很容易，因為資訊都存起來很清楚，但有點浪費空間

這個的result被移除，但會用index描述一些argument像是1的arg2
節省空間

方便後續compiler在優化的時候調整用，直接調整instruction的資料結構就好，不用動到其他地方

每個變數只會被define一次，執行效能會比較好，以及可以得知某個變數在哪裡被define的訊息，對compiler優化分析很重要

#### Example
要將t2移動到t3跟t4之間，但不能直接交換表格中的東西，因為可能會影響到index

需要scan一遍受到影響到index 1跟index 2並修改

但如果是inderect只要改instruction的表格就好

### Three-Address Code for Expression
a = b + -c;的範例
被遮住的部分

### Array Accesses
low是array最開始的index，w是每個element的長度
A[2][3]代表的是長的有兩條，裡面的每格就是放[3]所以可以切成3格

#### Example

左邊那些cdoe都是gen的東西，i是* 4是因為int是4bit

另一個例子

three address code：

### Type Conversion

#### Widening conversions
較低的可以轉成較高的type

#### Narrowing conversions
跟上面的相反

### Example
if (a < b) v=a;


[詳細過程](https://youtu.be/oNsUKuJ8zYw?t=1006)

three address code

自己練習:

## CH7

### runtime enviroment
需要負責
1. source program中命名的對象的存儲位置的佈局和分配。
2. 目標程序用於訪問變量的機制
3. 程序之間的聯繫
4. 傳遞參數的機制
5. 操作系統接口、輸入/輸出
6. 設備和其他程序（loader / exit）。


### Environment and State

### Name Binding
When an **environment** maps name x to **storage**
location s, we say **“x is BOUND to s”**

Assignments change the state, but NOT the environment:
pi := 3.14
changes the value held in the storage location for pi, **but does NOT change the location** (the binding) of pi

### Example1

### Example2
因為char是1byte，所以offset+1 c就從1開始，int是4

因此struct的部分加起來是5，又前面a的部分是int，所以offset=4，E的部分從4開始

d就從4+5（sturct的）開始


### Scope
大括號代表一個區域，所以中間紅框的找不到x才會去外面找，紅框下一段的則是找原本第一個表格，而不是找紅框中的

#### Scope : Nested blocks

B2為最裡面那層，有w2, y2, z2那個，B1為第一行那層 B0應該是顯示的程式碼以外還有別的。
找東西是先從自己那層找，再往上去找

### Activations
==Every execution of a procedure is called an **ACTIVATION**==

#### Activation Tree
顯示The activations of procedures during the running of an entire program.

**Each node corresponds to one activation**

順序是從左到右開始看，且右要等左執行完


一開始呼叫read 之後呼叫qicksort，再呼叫partition以及兩個qicksort

#### Control Stack
We can use a stack to keep track of **currently active activations**

control link：指向caller的activation record
access link：定位被調用過程所需但在其他地方找到的數據e.g. in another activation record

main還沒執行結束所以不會不見


#### Example

c的步驟因為partition最接近qicksort那層所以access link指到q

### Garbage Collection
Data that cannot be referenced is generally known as garbage.

大致就是可以root可以access到的做記號，剩下沒做記號的都是垃圾

## CH8

### Basic Block

leader到碰到下個leader之前都是一個block

接下來有可能走到就畫箭頭，此為control-flow graph（CFG）

### Next-Use Information

線的區間為life range

### Finding Local Common Subexpressions
b0 c0為初始值，此圖為DAG

#### 範例


#### Dead Code Elimination

### Register and Address Descriptors
**Register descriptor**：
1. 每個register都有，會持續記錄暫存器中存放的是哪個變數的值
2. 一開始Register descriptor都是空的

**Address descriptor**：
1. 對於每個變數都有，會記錄變數目前的值在哪
2. The location might be a register, a memory address, a stack location
3. 資訊可以連結到symbol　table中

### Code Generation Algorithm

#### 範例
initial


把t的結果放在R2，而b的R2被用走了

第二道指令

R1拿去放u

第三道指令

第四道指令

第五道指令


register決定都是getReg(I)去做的

如果用LOAD指令，要改變R的register descriptor、x的address descriptor要把R加進去


### Design of the Function getReg
即使R3拿來使用裝其他東西，b的值還是找的到（在原先ｂ那格）


若挑R2要先把a的值存到a中

### Register Allocation
若暫存器不夠，先讓出R1，要用c值時再load

### Graph Coloring


#### Interference Graph

兩者的life range有重疊就連線，相鄰的不能塗同個顏色（例如ab）
也可以是這樣
如果有同個顏色代表可以放在同樣的register中也不會干擾，因為他們life range也沒有重疊

### Loop Construct

#### Dominator
We say node d of a flow graph dominates node
n, written **d dom n**.
代表每個到n的path都會經過d


an edge’s head dominates its tail. We call such edge **back edge** 假設是a -> b 則b為head a為tail。圖中的9->1也是back edge

### Data Dependence

#### Flow dependence (true dependence)
表示方法：

#### Anti-dependence

#### Output dependence

#### Example 1

#### Data Dependence with Conditionals
碰到條件式要假設任何路徑都會走
S4跟S6不會同時發生，所以不用看關係