week3

圖片來源1

圖片來源2

語法理論

高階語言使用的語法，主要分為

1. 詞彙層次: 使用正規表達式(RE: Regular Expression)
2. 語句層次: 使用Context-free Grammar(CFG)

生成規則

用來描述「自然語言」的語法,像是中文、英文等。

• 宣告變數有給初始值放在data段
• 宣告變數沒有給初始值放在bss段
• malloc動態矩陣放在heap
• 區域變數，函數返回點放在stack

正規表達式

[0-9]+(\.[0-9]*)?: 可以出來 3.72、32、245.7191

• [0-9]+: 0到9選擇一個數，選擇1次以上
• (\.[0-9]*)? : (. + 0到9選擇一個數，選擇0次以上)，可以選擇不執行(執行1次或是0次)
• 在正規表達式.有特殊涵意(代表所有字元)，要用.字符需要在前面加\
• [a-zA-Z]: 代表所有字母

BNF語法(以生成數學式為例)

E = N | E [+-*/] E
N = [0-9]+
這樣寫會有歧義，所以需要改成下面的寫法

E = T | E [+-] T
T = F | T [*/] F
F = N | '(' E ')'  // 加減就()起來先做
N = [0-9]+
BNF 會有左遞迴，所以把他改成EBNF，就不會陷入無窮迴圈


E = T ([+-] T)*
T = F ([*/] F)*
F = N | '(' E ')'
N = [0-9]+

下面是生成樹的樣子
(3+5)*8-6

1. BNF                        2. EBNF

           E                              E
      E    -     T                  T     -     T
      T          F               F  *  F        F
   T  * F        N              (E)    N        N
   F   (E)       6             T + T   8        6
   N  E + T                    F   F
   8  T   F                    N   N
      F   N                    3   5
      N   5
      3

C0語言

編譯器六階段

1. 詞彙掃描(Scan | Lexical Analysis)

將整個程式碼分成一個一個的基本詞彙 (token)

2. 語法剖析(Parsing | Syntax Analysis)

剖析器利用語法規則進行比對，逐步建立語法樹

3. 語意分析(Semantic Analysis)

為語法數加註節點型態，並檢查型態是否相容，然後輸出語意樹，告訴系統誰先做誰後做

4. 中間碼產生(Pcode Generator)

語意樹被轉換成中間碼

5. 最佳化(Optimization)

考慮暫存器的配置問題，降低指令數，增加效率，但有時候增加速度代碼反而變多

6. 組合語言產生(Assembly Code Generator)

將中間碼轉換為組合語言輸出