# Compiler
## Chapter1 Introduction

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

### 編譯器主要為兩個部分
1. Analysis
* Linear Analysis (Lexical Analysis):掃描文字、標記Token並加到Symbol table
* Hierarchical Analysis (Syntax Analysis):將Tokens建成Tree
* Semantic Analysis

2. Synthesis
* Syntax Tree to IR
* Code optimization
* Code Generation

### 編譯器的流程

## Chapter2 Languages and Their Representations

### Alphabet and language

### 兩種方式來表達一種語言
1. 透過演算法來決定Sentence是不是語言
2. 透過Grammar來生成句子

### Formal Notation of a Grammar
* Four concepts
* Grammar(V_N, V_T, P, S)
* V<sub>N</sup> : nonterminals
* V_T : terminals
* P : productions α→β∈P
* S : start symbol
* Derivation
1. Derivation一次
2. Derivation很多次
* Example
* Type of grammars

## Chapter3 Lexical Analysis
### Lexical analyzer在幹嘛?
1. 讀輸入的文字
2. 將文字標記Token
3. 將Token加入至Symbol table
### Tokens, Patterns, and Lexemes
### Operation of Languages
* Example
### Regular Expressions
* Example
### Precedence
### Regular Definitions

### Regular Notational Shorthands
### FSM of Relational operators
### Deterministic Finite Automata (DFA)
* M = {S, Σ, δ, s₀, F }
* S :所有的state的集合且非為空的
* Σ :所有的字母集合
* δ :所有狀態轉換的集合 S -> Σ → S
* s₀ :起始狀態
* F :最終的狀態，也稱作Accepting edge

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

### Nondeterministic Finite Automata (NFA)
* M = {S, Σ, δ, s₀, F }
* S :所有的state的集合且非為空的
* Σ :所有的字母集合
* δ :所有狀態轉換的集合 S -> Σ → 2^S
* s₀ :起始狀態
* F :最終的狀態，也稱作Accepting edge
<font color="#f00">
### Constructing a DFA from an NFA</font>
<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(紅色圈圈)

* Example
<font color="#f00">
### Minimizing the Number of States</font>
* R.E. => NFA => DFA => mDFA
### Building Regular Grammar from NFA
* Example
### Building NFA from Regular Grammar

## 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
### Why Not Using Regular Languages
* 有些情況是無法用Regular Languages描述的

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

### [Left Factoring](https://)