---
# System prepended metadata

title: Compiler

---

# Compiler
## Chapter1 Introduction
![](https://i.imgur.com/MiPtY50.png)

### 編譯器是甚麼?
* 是一個程式
* 將Source program language翻譯成Target program language

### 編譯器主要為兩個部分
![](https://i.imgur.com/FKhk2I2.png)
1. Analysis
![](https://i.imgur.com/BG6Ia2o.png)
    * Linear Analysis (Lexical Analysis):掃描文字、標記Token並加到Symbol table
![](https://i.imgur.com/B7cOIeo.png)
    * Hierarchical Analysis (Syntax Analysis):將Tokens建成Tree
![](https://i.imgur.com/D1skQfR.png)
    * Semantic Analysis
![](https://i.imgur.com/fGyjRWG.png)

2. Synthesis
    * Syntax Tree to IR
    ![](https://i.imgur.com/mHDl5J7.png)
    * Code optimization
    ![](https://i.imgur.com/z2MKT1l.png)
    * Code Generation

### 編譯器的流程
![](https://i.imgur.com/DI4SvXb.png)

## Chapter2 Languages and Their Representations

### Alphabet and language
![](https://i.imgur.com/kUhlaOE.png)

### 兩種方式來表達一種語言
1. 透過演算法來決定Sentence是不是語言
2. 透過Grammar來生成句子
![](https://i.imgur.com/dyKdPqY.png)

### Formal Notation of a Grammar
* Four concepts
![](https://i.imgur.com/m5UNfkj.png)
* Grammar(V<sub>N</sub>, V<sub>T</sub>, P, S)
    * V<sub>N</sup> : nonterminals
    * V<sub>T</sub> : terminals 
    * P : productions α→β∈P
    * S : start symbol
* Derivation
    1. Derivation一次
![](https://i.imgur.com/NDNheyZ.png)
    2. Derivation很多次
![](https://i.imgur.com/wZ3N1PZ.png)
    * Example
![](https://i.imgur.com/D0kILbh.png)
    * Type of grammars
![](https://i.imgur.com/oDY3vw9.png)

## Chapter3 Lexical Analysis
### Lexical analyzer在幹嘛?
1. 讀輸入的文字
2. 將文字標記Token
3. 將Token加入至Symbol table
![](https://i.imgur.com/2nWAb9V.png)
### Tokens, Patterns, and Lexemes
![](https://i.imgur.com/H76NR24.png)
### Operation of Languages
![](https://i.imgur.com/AfTYRQl.png)
* Example
![](https://i.imgur.com/cRBXFJr.png)
### Regular Expressions
![](https://i.imgur.com/Nip1qE6.png)
* Example
![](https://i.imgur.com/ChyehUB.png)
### Precedence
![](https://i.imgur.com/V5vF7EO.png)
### Regular Definitions
![](https://i.imgur.com/Jhr9IHu.png)

![](https://i.imgur.com/VvTWsSM.png)
### Regular Notational Shorthands
![](https://i.imgur.com/yqttxmZ.png)
### FSM of Relational operators
![](https://i.imgur.com/lQXpWXp.png)
### Deterministic Finite Automata (DFA)
* M = {S, Σ, δ, s<sub>0</sub>, F }
    * S :所有的state的集合且非為空的
    * Σ :所有的字母集合
    * δ :所有狀態轉換的集合 S -> Σ → S
    * s<sub>0</sub> :起始狀態
    * F :最終的狀態，也稱作Accepting edge

* <font color="#f00">沒有є-transition -> 空字元</font>
* <font color="#f00">不會同時有兩個edge可以走的情況</font>

### Nondeterministic Finite Automata (NFA)
* M = {S, Σ, δ, s<sub>0</sub>, F }
    * S :所有的state的集合且非為空的
    * Σ :所有的字母集合
    * δ :所有狀態轉換的集合 S -> Σ → 2<sup>S</sup>
    ![](https://i.imgur.com/YZGoXxL.png)
    * s<sub>0</sub> :起始狀態
    * F :最終的狀態，也稱作Accepting edge
<font color="#f00">
### Constructing a DFA from an NFA</font>
![](https://i.imgur.com/4y67WO7.png)
![](https://i.imgur.com/maEk2cr.png)
<font color="#f00">
### Constructing NFA from Regular Expression</font>
* 每次operation最多會增加兩個新state
* 只有一個start state
* 只有一個accepting state
* Each state has either one outgoing 
transition on a symbol(藍色圈圈) or at most two 
outgoing є-transition(紅色圈圈)
![](https://i.imgur.com/Bt8vdH8.png)

![](https://i.imgur.com/lvVbYIr.png)
* Example
![](https://i.imgur.com/VyCuZ6D.png)
<font color="#f00">
### Minimizing the Number of States</font>
* R.E. => NFA => DFA => mDFA
![](https://i.imgur.com/7tw5yKp.png)
### Building Regular Grammar from NFA
![](https://i.imgur.com/cHRLL6k.png)
* Example
![](https://i.imgur.com/EKljUUL.png)
### Building NFA from Regular Grammar
![](https://i.imgur.com/6NlHWQx.png)

## Chapter4 Syntax Analysis
### Syntax analyzer在幹嘛?
* 接收一連串從scanner分析完的tokens
* To verify the string can be generated by the grammar
* Three general types of parsers for grammars
    *  Universal parsing methods
    *  Top-down
    *  Bottom-up
### Context-Free Grammars
![](https://i.imgur.com/OUToUP0.png)
### Why Not Using Regular Languages
* 有些情況是無法用Regular Languages描述的
![](https://i.imgur.com/fZ4i4tx.png)

<font color="#f00">(重要可能會考證明)
* 用Pumping Lemma證明它不是Regular language </font>
https://www.youtube.com/watch?v=Ty9tpikilAo&ab_channel=NesoAcademy
![](https://i.imgur.com/Vil1puy.png)
<font color="#f00">
### Pushdown Automata 要會推 </font>
* M = {K, Σ, Γ, δ, q<sub>0</sub>, Z<sub>0</sub>, F }
    * K :所有的state的集合且非為空的
    * Σ :所有的字母集合
    * Γ :Pushdown alphabet
    * δ :所有狀態轉換的集合 K ⨉ (Σ ∪ є) ⨉ Γ  → K ⨉ Γ<sup>*</sup>
    * q<sub>0</sub> :起始狀態
    * Z<sub>0</sub> :Initial pushdown symbol 
    * F :最終的狀態，也稱作Accepting edge
![](https://i.imgur.com/AfyERV4.png)
![](https://i.imgur.com/wA4VYGM.jpg)
### Parse trees and Derivations
![](https://i.imgur.com/pOxZmMb.png)
![](https://i.imgur.com/BalciD5.png)
### Ambiguity
* 一句句子有超過一個以上的Parse tree
* To eliminate ambiguity
    * Precedence and associativity
    * Rewriting the grammar
* Example
![](https://i.imgur.com/qz6k7sd.png)
![](https://i.imgur.com/0397JSk.png)
<font color="#f00">
### Eliminating Ambiguity</font>
![](https://i.imgur.com/DkH1UK2.png)
<font color="#f00">
### Left Recursion</font>
* 因為Grammar通常採用leftmost precedence，所以會一直往左邊去找，形成一個loop
![](https://i.imgur.com/taVzePg.png)
<font color="#f00">
### [Eliminating Left Recursion](https://www.youtube.com/watch?v=H7iGUr2W5N8&ab_channel=TheBootStrappers)</font>
* 變成Right recursion就不會loop了

![](https://i.imgur.com/EWvt9HR.png)
![](https://i.imgur.com/czrqIm4.png)
![](https://i.imgur.com/k1N5NWo.png)
### [Left Factoring](https://)
![](https://i.imgur.com/rpw7e7v.png)
![](https://i.imgur.com/p2HT3QU.png)
