# 2020 NCTU Compiler, 楊武

## 大推的影片&網站
- [Youtube Compiler Design](https://www.youtube.com/playlist?list=PLEbnTDJUr_IcPtUXFy2b1sGRPsLFMghhS)
- [NCTU Course的筆記](https://hackmd.io/_TA5Mfs5SBCkJqEAH7Jq5A)

## HW(Github)
- 修完再來放

## Course
### CH1 Introduction
- [NCTU Course的筆記](https://hackmd.io/_TA5Mfs5SBCkJqEAH7Jq5A) <-這個佬筆記寫得很完整ㄌ
- Bootstrapping(考古2019)

### CH2 Simple Compiler
- [NCTU Course的筆記](https://hackmd.io/_TA5Mfs5SBCkJqEAH7Jq5A) <-這個佬筆記寫得很完整ㄌ
- 這章大概介紹了Compiler會經歷的各個phases, 沒有特別的重點
- 

### CH3 Scanner
- Scanner HW寫完就知道ㄌ
- 重點: r.e. => fa
- Regular expression寫法
- NFA
- DFA
- Minimum DFA
- NFA(很直觀)
- [NFA=> DFA](https://www.youtube.com/watch?v=jN8zvENdjBg&t=336s)
用closure算比較不會有問題, 其他算法容易會有問題
($\lambda$如果是第一個, 用簡易算法Initial state會消失)
- [DFA => Minimal DFA](https://www.youtube.com/watch?v=0XaGAkY09Wc)
做到直到equivalence不再改變(e.g. 2&3 equivalence in the picture)
-

### CH4 Grammer
- [NCTU Course的筆記](https://hackmd.io/_TA5Mfs5SBCkJqEAH7Jq5A) <-這個佬筆記寫得很完整ㄌ
- 重點: First set, Follow set
- First set
- 找每個Rule RHS的第一個字
- 如果是 $\lambda$ 那就往下找下一個的第一個字
- 如果不是那就找到了
- Follow set
- 找每個non-terminal(RHS)後面接的第一個字(也就是First)
- 如果是後面接的是terminal或First(後面的non-terminal)=terminal;那就找到了,並加入要找的terminal的follow set
- 如果要找的那個terminal後面沒有接任何東西, e.g. 要找follow(B), $S \rightarrow B$, 要將S的follow加到B的follow
- 重複直到follow set不再變化

- 需要釐清的名詞
sentential form: 還沒做完的sentence
handle: **leftmost** simple phrase(rm在處理的就是每個handle)

### CH5 LL parsing(Top-down parsing)
- Two kinds of top-down parsers:
- Recusrive descent parsers
- Table-driven LL parsers

- Recursive descent LL(1) Parsers
- Predict set:
Predict(A),
1. A's RHS最左邊是terminal $A\rightarrow aa$, 則拿那個terminal
2. A's RHS最左邊是其他non-terminal $A\rightarrow Ba$, 則拿Predict(B)
3. A's RHS最左邊是$\lambda$, 則拿Follow(A)
- Example of Recursive descent(問題:Stack可能會爆!!)

    procedure match(input_char c)
    {
        if(c == lookahead)
        {
            lookahead = getchar()
        }
        else
        {
            printf("error")
        }
    }

- Table-driven LL(1) tables
- 先算First set, Follow set
- 如果rule 裡有$\lambda$那就填follow set
- 沒有的話就填First set到table
- Parse stack的狀況(懶得把自己畫的丟上來ㄌ)

- 判斷是不是LL(1)
- Common Prefix, 從table上很好看出conflict
- Left recursion,

- Properties of LL(1) parsers

- 壓縮 LL(1) table
- 一堆entry是沒有值的, 所以希望能夠壓縮
- Binary search
- Hash table
- Compression rows
- 每一行塞滿在換下一行, row table裡面紀錄每一行的start position
- 
- Double-offset
- 用對齊的方式去塞滿每一行, 塞完之後row table也是一樣記錄每一行的start position
- 

### CH6 LR parser(Bottom up parsing)
- LR(0) parser, SLR(1) parser $\rightarrow$ 使用LR(0) items
- 區別:
- LR(0) 會無腦填Reduce在action table $\rightarrow$也因為如此很容易會有Conflicts在table中出現
- SLR(1) 當有Reduce出現時, 會先去找那個Rule的follow set,
- ex: $A \rightarrow AC.$, 要填這個表的reduce則先去找Follow(A), 以這種方式去減少Reduce/Shift Conflict!!
- 另外stack的狀況和LL(1)也有些不同
- LL(1) initial: [$S], S是startsymbol,每次換完rule會去做"match"
- LR(0) initial: [0], 0是state,開始照表作reduce/shift

- Not ambigous, but not LR(k)
- 不知道要看lookahead看到啥時, 不屬於LR(k)
- 

- LR(1) parser, LALR(1) parser
- LALR(1) parser是把長的完全一樣(除了looahead)的LR(1) state merge成同一個state, 不過這個行為會造成conflict
- LR(1) parser, LR(0) items + lookahead(1)

- Properties
- 

- 中間太多ㄌ, 寫不完...
- [額外補充yacc precedence](http://jiayaowei.blogspot.com/2007/12/lexyaccyacc_03.html)
### CH7

###### tags: `Compiler`