[SP] 編譯器

5.1 Basic Compiler Concepts

source -> lexical analysis (token) -> syntax analysis (parse tree) 
-> intermediate code generation (intermediate code) 
-> code optimization  (intermediate code) -> code generation 
-> machine code

注: 直譯器不做程式碼最佳化，編譯器則會。

Lexical Analysis

lexical analyzer (Scanner)同一時間內只讀入一個 char， 產生的最小單位稱為token(type, value)。

Syntax Analysis

syntax analyzer (Parser)，文法合法的statements， 透過建樹確定文法是否合法，如果能建樹代表符合文法，可以從樹根或樹葉建樹兩個方向皆可。

Intermediate Code Generation

• LLVM Intermediate Representation (IR)

three address code:

(operator, operand1, operand2, result)

註解: tree address代表op1, op2, result的address

分解 statements 成多個 Three Address Code (TAC) 文法樹的形成引導中間碼 (Intermediate Code) 產生

Code Optimization

對中間碼與機器碼優化，使obj速度更快，並且花費更少空間

中間碼與asm十分相近

i++與i = i + 1的速度有待商榷，而現代編譯器大多有優化的功能。

Code Generation

如何最佳化暫存器使用，之後產生機器碼之後進行機器碼最佳化

Table Management And Error Handling

token, symbol table等建置，編譯器五大功能(或6個 在機器碼進行優化)都做一次， 將多個功能合併並可以透過2pass處理，問題是forward reference。

翻成機器碼的時候，例如if else無法知道機器碼的長度， 需要跳到true與false，而隱含forward reference。

5.2 Grammar

文法

Backus–Naur form Grammar

<cond> ::= <cond> * <cond> | <cond> / <cond>

terminal symbol (token) non-terminal symbol (尚未分解成token，可以包含其他文法的)

將輸入的內容分解non-terminal symbol直到成為terminal symbol (文法批配token)

Parse Tree (Syntex Tree)

• Precedence: 不同運算子優先順序(*/的優先級大於+-)
• Associativity: 相同運算子，左右方向(=、**(平方)要由右自左，一般的四則運算由左自右)

Ambiguous Grammar

混搖不清的文法，相同token可以產生多種不同的parse tree。

id - id + id
((id - id) + id)
(id - (id + id))

如何產生unambigous grammar

混淆不清為一個statement,不只一種parse tree

Precedence and Associativity

• Left Associativity: 由左到右
• Right Associativity: 由右到左

5.3 Lexical Analysis

token類型

• identifier
• delimiter
• reserved word
• constant integer, float, string

Identifier

<ident> ::= <letter> | <ident><letter> | <ident><digit>
<letter> ::= [a-zA-Z]
<digit> ::= [0-9]

Token Table

• delimiter與reserved word: 根據程式語言定義的delimiter與reserved word建立table
• integer, string
• identifier table (identifier, type保存類型, pointer存放的位置, scope保存勢力範圍)

5.4 Syntax Analysis

建立剖析樹的方法

• Top Down Method

  • 由root向下(derive/produce)，例如 Recursive Descent Parser ，相關的工具如 Antlr4 屬於這類型的 parser

• Bottom Up Method

  • 由note向上(reduce)，Operator Precedence Parser，如 yacc/bison 屬於這類工具

Operator Precedence Parser

1. 根據文法(grammar)產生 Precedence Matrix，為bottom up Parser， 可以回報混淆不清的文法出現的位置，並且能夠設計者可以進行調整。
2. token string 丟給 operator precedence parser 檢查是否符合syntax

假設輸入READ(id)，stack變化，如果遇到stack top比較大的情況， 則可以找出一個文法(問: 在stack top的是不是總是最大？)， 之後就可以做reduce to non terminal symbol

<id-list> ::= id
<read> ::= READ(<id-list>)

<
<READ
<READ = ( 
<READ = (  <id
<READ = (  <id> 
<READ = (  = id-list ) 
<READ = (  = id-list )>
read

註解: non terminal symbol不需要處理優先級

id + id - id為混淆不清的文法，而調整混搖不清的文法，可以有由左至右或由右自左等調整

<
<id
<term + 
<term + < id 
<term + < id >
<term + term > // top 為 +
<term - < // 因為 + > -  所以轉non terminal symbol
<term - < id >
<term - term >
term

註解: 轉成 non terminal symbol 當 stack empty

reduce to 時候就在生成樹

Error

1. 兩token比較為blank entry無法比較大小
2. 比左邊大且右邊大時必須reduce to，但是找不到syntax rule

Recursive Descent Parser

為Top Down Method從最左邊Match向下找到Syntax，從最起始的Non Terminal Symbol向下對映。

Left Recursive

遇到 left recursive 情形，將文法作 left factory 來修改順序即可。

left factory 的方法

待補

5.5 Code Genaration

rule 可以對映code generation routines(或semantic routine)， 如果沒辦法容易的翻出機器碼或機器碼太細小，則會先翻譯成intermediate form。

5.6 Intermediate Form

Three address code(Quadruple From)

如<term> = <term>1 + <term>2可以翻成

(+, <term>1, <term>2, <term>)

5.7 Machine Independent Compiler Features

Storage Allocation

• Static Allocation: 在編譯器時間分配空間
• Dynamic allocation: 在run time分配空間
  • auto: function call: 系統自動分配一個stack
  • Controlled: malloc(), free()，用heap保存，heap刪除之後就必須要清理垃圾(garbage)。

static與非static變數，前者在compiler time處理，後者為dynamic allocation (stack)。

Activation Record

函數被呼叫的時候，系統替函數產生 stack 內容，為 Activation Record。

Activation Record 存在的目的，在於保存回傳地址， 區域變數(Local definition), 傳入參數(Pass Parameters) 等， 在大多數的系統上都能看到。

Activation Record

• variables (如 return value, local define)
• return address
• next
• previous

範例: main function的return address會指向OS，並且Next/Previous為空

注: 實際上根據不同系統還是會有所差異。可以用gdb下去查看堆疊結構。

scope: 為變數有效的範圍

• static scope: 根據程式的結構，如存取巢狀結構外層var
• dynamic scope: 根據function被呼叫的次序，不同function call作用的var

Prologue and Epilogue

增加 code 在 call function中

• Prologue: 建立 activation record
• Epilogue: 移除 activation record

Structure Variable

例如定義二維陣列，以行優先或以列優先，而記憶體中必須以一維保存陣列資料(mapping to memory)。

假設陣列為array[column][row]

• 行優先: 優先排序row
• 列優先: 優先排序column

計算公式

定義type B[a-b][c-d](表示為type B[a:b][c:d])，定址到B[s][t]

• Row Major: [(s - a) * (d - c + 1) + (t - c)] * sizeof(Type) + base，假設index起始都是0，代表type B[b][d]，為[s * (d + 1) + t] * sizeof(Type) + base
• Column Major: [(t - c) * (b - a + 1) + (s - a)] * sizeof(Type) + base，假設起始為0，[t * (b + 1) + s] * sizeof(Type) + base

註: 以a, c做為index的起始，減去代表求長度，(b + 1)的部份是陣列計算大小的方法 c++ 為Row Major

為什麼需要區分這兩者

• 可以利用 Locality 性質，提高 cache 與 page 命中的機率

Code Optimization

對中間碼與機器碼進行優化。

1. Common Sub-Expression: 找出重複運算，並且將其提出。
2. Loop In-Variants: 迴圈內部不變的函數，可以提出迴圈外。
3. Reduction in Strength: 將運算慢的指令轉成較快的指令。

5.8 Compiler Design Option

1. Interpreter: 直接由source執行程式
2. p code compiler: Byte Code (機器無關語言)，可跨平台，如Java Interpreter與JRM
3. compiler-compiler: 傳入文法，yacc與lex，透過finite state automata解決問題。
4. cross compiler: 在工作站編譯原始程式出其他架構的機器碼。

參見

• The LLVM Instruction Set and Compilation Strategy