Assembler

ZASM vision and scope

將我開發 ZASM (Zerg 專用的組譯器) 的過程與方式記錄下來

語法 (GRAMMAR)

在設計任何一種程式語言之前，需要決定這個程式本身的 語法 。 ZASM 本身就是一個 組譯器 (Zerg Assembler)，本身也傾向方便閱讀的特性。 就 Grammar 本身僅只有以下 11 條規則：定義 6 種主要語法跟 4 個補充描述語法

stmt      : ( code | label | define | data | block | include )? [ COMMENT ] NEWLINE
code      : OPCODE    ( operand )*
label     : TOKEN     ':' ( decorator )*
include   : 'include' STRING
define    : 'define'  TOKEN  ( IMM | STRING )
block     : 'block'   STRING [ range ]
data      : 'data'    TOKEN  STRING

operand   : REG | MEM | IMM | reference
decorator : '@' TOKEN [ ':' TOKEN ]
reference : '&' TOKEN | '$' | '$$'
range     : IMM | ( ( IMM | reference ) '~' ( IMM | reference ) )

在 ZASM 中每一行都代表一個完整的 陳述句 (statement) ，根據內容直接編譯成相對的 機械碼 。 這個過程就被稱之為組譯 (assemble)。另外還需要訂定一個制式的語法：目前主流的語法有 Intel 與 AT&T 兩種風格。在 ZASM 我們使用以下的風格：

• 運算順序為 OPCODE DST SRC
• 暫存器、數字保持原樣
• 數字使用二進位 (0b)、八進位 (0o)、十進位與十六進位 (0x)
• 記憶體相關
  • 記憶體長度用 byte、word、dword、qword 表示
  • 記憶體位址之值使用 [ &var ] 表示
  • 記憶體位址使用 &var 表示
  • 記憶體定址 [ seg:base + index * scale + imm ]

保留字

在 ZASM 中使用了以下幾種保留字：記憶體長度修飾、位址修飾與其他。 描述記憶體大小時，會使用四種不同的修飾詞來表示長度：byte、word、dword、qword。 另外描述記憶體位址時，會使用兩種保留字來呈現不同的位址：$ 表示當下指令位址、$$ 表示當下 section 開頭的位址。

其他保留字則有其他的用途，像是：

• include 引用外部檔案
• define 定義一個變數且後續所有使用到的變數都會被直接替換
• data 定義一個字串並直譯成二進位資料，如有額外的變數則會被輸出成符號表
• block 匿名定義一個記憶體空間內容

設計 (Design)

在設計組譯器之前，需要了解到他本身具有的幾項功能：詞法分析 (Lexer)、語法分析 (Parser)、 組譯 (Assemble)。這分別代表ZASM 產生機械碼時會經過以下幾個階段： 讀檔、分詞、語法分析 (Phase I:紀錄變數、紀錄符號位址)、語法分析(Phase II: 定址)、產生機械碼。

為了減少 ZASM 對於第三方套件的依賴性，每個步驟都盡可能減少使用外部函式庫。 讀檔階段 ZASM 使用兩種外部函數：Zasm::assembleF 與 assembleL。前者用來處理、分析整的檔案， 後者則是處理單一語法並且最終產生機械碼。Zasm::assembleF 會讀取整的檔案，並且將每一行內容傳送給 Zasm::assembleL。Zasm::assembleF 會執行兩次來正確處理引用的變數、符號。

在 assembleL 階段會呼叫 Zasm::parser 來產生機械碼：本身透過簡單的 Recursive Descent Parser 實作，處理來自 Zasm::lexer 獲得的可用單詞，並根據 Zasm::type 提供的型態來決定適用哪一個語法， 根據最後決定的語法挑選 opcode 並產生相對的機械碼。為了能夠讓相同的邏輯使用在 Zerg，ZASM 提供的 assembleL 可以單獨運行，並透過 Zasm 本身的檔案輸出來產生目的檔案。為了這個目的，每次透過 assembleL 處理完的機械碼都必須有暫存的能力：為了避免在 Zerg 編譯完之後需要產生暫存的 ZASM 程式碼 。

虛擬機械碼 (Pseudo MachineCode)

虛擬機械碼 ZasmCode 幾乎接近最終的機械碼：只需要在 two-pass 的第二階段填入正確的記憶體位址。 因此本身需要：1) 紀錄機械碼、2) 機械碼的長度、3) 填入記憶體位址、4) 代表的符號。這代表 ZasmCode 有兩種能力：機械碼的儲存器與符號的位址。在這種情況下 ZasmCode 需要兩種不同情境的建構子， 分別用來決定是否這個虛擬機械碼本身帶有符號。最後需要將 ZasmCode 輸出成機械碼，需要支援 fstream operand« 的 運算子重載 overloading ：直接將組譯後的機械碼輸出。

在 label 階段可能有一或多個修飾詞，這時 ZasmCode 就需要針對各種不同的修飾詞改變 ZasmCode 的性質， 並在之後的產生機械碼時可以獲得屬性。而要能夠在 two-pass 階段填入適當的記憶體位址，需要在 ZasmCode 增加 setMemory 的功能。而 ZasmCode::setData 則是用來產生區塊記憶體空間的方式 (預設產生一次)， 也就是根據第二個參數的 count 來決定重複幾次資料。當設置第三個參數時代表這是一個範圍的數量， 因此需額外處理特殊的條件，像是：1) 未知的符號與 2) 範圍值。

詞法分析器 (Lexer)

Zasm::lexer 是將原始碼分割為若干有效的單詞。本身不處理任何語法上的問題，但在這個階段找到詞法錯誤 ，也就是錯誤或不存在的單詞。可以透過一個簡單的 有限狀態機 (FSM) 來實做 Zasm::lexer： 從每一行程式碼中讀取一個字元 (char)，再根據當下字元來決定屬於哪一種單詞。 在 ZASM 中的單詞都透過空白字元來做分隔，不合法的詞法多出現在：1) 字串 與 2) 記憶體 兩種情況。

在語法階段隨時都可定義 (define) 一個替代用的符號，所以在 Zasm::lexer 的輸出階段需要做額外的檢查： 當單詞屬於符號且已經有定義，則替換成定義後的單詞。

語法分析器 (Parser)

跟詞法分析器一樣 Zasm::parser 也是一個 FSM：根據從 Zasm::lexer 獲得的有效單詞，透過 Zasm::type 來獲得詞法屬性並根據屬性來判斷屬於哪一個有效的語法。

Zasm::parse_define 定義一個符號用來代替特定詞句，在這個語法中嚴格限制有兩個運算元 (operand)： 前面的運算元一定是 ZASMT_TOKEN 型態，代表一個尚未定義的符號、後者可以是數字、字串等。 Zasm::parse_label 則是定義一個定位符號：在 ZasmCode 中代表一個虛擬機械碼，本身沒有長度且帶有符號 在 Zasm::parse_label 的例子中，可能會遇到使用一個或多個修飾詞 (decorator)：在 Zasm::parser 處理上就可以透過遞迴的方式來處理多個 decorator。。Zasm::parse_include 則是引用外部程式碼： 本身帶有一個運算元且嚴格限制型態為字串。Zasm::parse_block 則是宣告一個匿名的記憶體空間內容， 同時也提供簡單的 syntax sugar：當 block 只有一個運算元時代表只重複一次。

而 Zasm::parse_data 則是直接一個記憶體空間的內容並給予一個符號。這是一種 syntax sugar 語法 ，可以用 label 跟 block 來達到一樣的操作，代表定義個一個 label 並透過 block 產生只有一次的資料 。這代表下面兩種語法是等價的：

# grammar : data
data	banner		'Welcome ZASM\n'

# grammar : label and block
label banner:
    block	'Welcome ZASM\n'

最後 Zasm::parser 會處理合法程式碼並產生 ZasmCode，這部分透過一個簡單的狀態機來處理：頻繁處理 Zasm::parse_operand 來獲得一個 CodeOperand，每次一次執行都會找到一個合法的運算元， 並更新下一個可用的單詞。當遇到換行符號時，則停止 ZasmCode::parse_code 並產生 ZasmCode 暫存碼。

機械碼射出器 (emit)

在 ZasmCode 中最重要的一個環節就是產生機械碼：透過 ZasmCode::emit 可以透過參數帶入 ZASM 原始碼， 之後產生相對的機械虛擬碼。在這個環節中會使用到 CodeOperand 用來代表被操作的運算元，本身有兩個參數 ：運算元與運算元的修飾字。運算元本身可以是寄存器、記憶體空間、立即數跟引用符號四種， 而修飾詞都跟運算元的大小有關。

之後透過各自的在 src/zasm/architecture 下的實作決定 emit 的邏輯，也就是如何產生相對的機械碼。 依照 x86 架構為例：1) 判斷是 x86 或 x86-64 架構、2) 決定 opcode、3) 判斷運算元大小、4) 產生機械碼 。在 x86 架構中機械碼長度是不定長度的 CISC 架構 ，長度從 1 byte 到 16 bytes 都有可能： 其中包含了五個部分：1) 0 ~ 4 bytes 的 prefix、2) 1 ~ 2 bytes 的 opcode、3) MoD R/M、4) SIB 與 5) 共用 8 bytes 的位置、常數欄位。接著透過 ZasmCode::match 來判斷是否為合適的 opcode 並且在 Zasm::emit 中決定相對的機械碼。

0               4        6     7     8                         16
|---------------|--------|-----|-----|--------------------------|
  Legacy Prefix   OpCode   Mod   SIB   Displacement / Immediate

在尋找適合的 opcode 時，會透過下面的順序來尋找：1) 相符的 opcode 與 2) 正確的運算元。判斷運算元時 ，會同時判斷運算元的型態與大小，同時符合所有條件時才會開始射出 (emit) 相對的機械碼。 X86 的環境下首先判斷機械碼的 prefix，而 prefix 又可以分成四大類，分別對應到不同的使用情境。

在 Mod R/M 的欄位中用來 1) 編碼使用的 register 或 2) opcode 的延伸，通常會用在記憶體操作的機械碼 。在使用上，最高的兩位用來判斷記憶體運算元的形式，像是 00 表示包含 index 的記憶體位址、10 則是 偏移量在 7 bits 以內的正負數。接下來的三個 bits 則是用來編碼會使用到的 register 或機械碼延伸使用 。最後三個 bit 的 rm 欄位，則是用來描述使用到記憶體的 base register。

使用 Mod R/M 的情況之下的記憶體有使用 index 欄位，就會使用 SIB byte 來描述其中的 index 狀態： 最高兩個 bit 是用來描述 index 的 scale 量級，內容可以為 0 ~ 3 分別表示二的冪次。接下來的 3 bits 則用來表示 index 使用到的 register、最後的 3 bits 則是用來表示 base register。

Two-pass

在 ZASM 中使用 two-pass 來處理程式碼。高階組譯器都支援變數 (Variable)、符號 (Symbol) 來加速開發流程。當引用到的變數、符號是在之前已經定義時，one-pass 可以直接使用與引用。 但變數、符號在使用時尚未定義，則就需要使用 two-pass 來處理程式碼： 在第一次掃瞄程式碼時先決定語法位址、儲存所有變數、符號的位址與處理虛擬指令， 第二次掃瞄時再填入正確的記憶體位址。

可以直接透過判斷 ZasmCode 的數值 (int) 來決定是否需要重新定址：對於需要重新定址的函數用重載過的 == 符號，來判斷是否是一樣的符號來判斷。通常來說 ZasmCode 需要比對一個特定符號，案順序優先往回尋找 。在實作上，會透過 Zasm::_symbol_ 來記錄目前這份 ZASM source 中使用到的所有符號並記錄他的位址， ZasmCode 則直接尋找符號位址並更改原本的預設值。

另外還有兩種特殊的狀況：定位符號與範圍值。對於定位符號則重新計算當下的位址、往回算上一個符號為止 。尋找上一個節 (section) 失敗時，則視為是程式的開頭。範圍值則需要計算兩個值得差異，原本是透過 ZasmCode::setData 來填入範圍值，但在 parse Phase I 階段可能尚未決定符號的位址， 在遇到符號的情況之下則暫存在 _rangeFrom_ 跟 _rangeTo_ 中。現階段實作僅支援其中一個為未決定值 ，這代表無法同時兩者為定位符號。