<h1 style="text-align: center;">系統程式 期末專題 SIC/XE 組譯器</h1>

### **1131 NTNU CSIE System Programming**
* 課程名稱與代碼: 系統程式 CSU0027 (三校聯盟課程代碼: 3N1383701)
* 老師: 黃冠寰
* 學生: NTUST M11212913 戴聖宴
* 本次作業用 C 語言來實現支援部分 SIC/XE 指令的組譯器: [我的 Github 連結](https://github.com/Pathfinder1996/SIC-XE-Assembler-System-Programming)
* 本次作業筆記: [我的 HackMD 連結](https://hackmd.io/@Dylan-Dai/rJlpnliIye)
* 如果想要每週作業和期中期末考古題，歡迎來信: [e-mail]
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/By1LAlo81e.jpg" alt="63750" style="width: 200px; height:250px; margin-left: 30px;">
</div>

---
### **Figure 2.6 SIC/XE 程式**
* 只需實現支援課本 Figure 2.6 上的 SIC/XE 程式碼的組譯器。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/SJMypbo8yx.png" alt="63750" style="width: 400px; height:600px; margin-left: 30px;">
</div>

---
* 並產出課本 Figure 2.8 格式的 object program。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S1pL4Zs8kl.png" alt="63750" style="width: 400px; height:200px; margin-left: 30px;">
</div>

---
### **組譯器架構設計**
* 本次專題組譯器的實現是依二階段(two passes)的方式，來處理 Figure 2.6。
* 第一階段(pass1):
* 掃描程式碼的 label，並計算其位址(如 Figure 2.6 的 LOC 欄)，記錄到 symbol table。
* 第二階段(pass2):
* 根據 mnemonic 的格式轉成對應的機器語言，例如 Figure 2.6 Line 10 的 STL 轉成 14。
* 把 symbol 的運算元轉為對應的位址，例如 Figure 2.6 Line 10 的 RETARD 轉成 1033。
* 處理常數資料，例如 Figure 2.6 Line 80 的 EOF 轉成 454F46。
* 產生 assembler table 的 object code 並輸出 object program。

* 以下為組譯器主架構:

<div style="display: flex; justify-content: center;">
<table border="1" style="border-collapse: collapse; text-align: left;">
<tr>
<th>模組</th>
<th>功能</th>
</tr>
<tr>
<td>OPTAB</td>
<td>用來儲存有支援 mnemonic 的 opcode 及其格式，並在 Pass1 階段用。</td>
</tr>
<tr>
<td>Pass1 階段(定義符號)</td>
<td>
1. 計算程式中 directive 跟 mnemonic 的 LOC。<br>
2. 處理好 directive，像是 BYTE 或 RESW 佔用多少 LOC。<br>
3. 檢查 label 有無重複定義，還有 label 不能跟 directive 或 mnemonic 一樣。<br>
</td>
</tr>
<tr>
<td>ASMTAB</td>
<td>Pass1 階段產生的 assembler table 只是用來存要給 Pass2 翻譯的程式，同時更新 LOCCTR，這階段還沒產生 object code。</td>
</tr>
<tr>
<tr>
<td>SYMTAB</td>
<td>Pass1 階段產生的 symbol table，用來記錄程式每當處理過程遇到一個 label 時，LOCCTR 的現行值就是該 symbol 的位址，Pass2 階段用。</td>
</tr>
<tr>
<td>REGTAB</td>
<td>用來儲存有支援的暫存器，給 pass2 在跟 register 有關的 mnemonic 翻譯用。 </td>
</tr>
<tr>
<td>Pass2 階段(翻譯並產生object program)</td>
<td>
1. 翻譯程式（根據不同格式找到其位址）。<br>
2. 處理 BYTE 等 directive 的值到 ASMTAB 的 object code 欄。<br>
3. 輸出 object code 到 record。<br>
</td>
</tr>
<tr>
<td>OBJTAB</td>
<td>儲存 Pass2 階段 ASMTAB 產生的 object code，輸出 object program 用。 </td>
</tr>
<tr>
<td>modify</td>
<td>處理程式中需要重定位的位址。
</td>
</tr>
<tr>
<td>record</td>
<td>
Header record: 記錄程式的名稱、起始址、長度。<br>
Text record: 這段機器碼的起始址、長度、object code。<br>
Modification record: 被修改的起始位址、長度。<br>
End record: 程式中第一個可執行指令的位址(也可指定 label 位址)。<br>
</td>
</tr>
</table>
</div>

---
### **Pass1 階段**
* 建立 OPTAB:
* 儲存 mnemonic 的 opcode 及其格式。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S15iUiiUyg.png" alt="63750">
</div>

* Pass1 階段產生的 ASMTAB:
* 記錄吃進來的每一行程式的資訊。每一行分割 token 後，分別儲存到 ASMTAB 的 loc、label、opcode、operand，同時更新 LOCCTR。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/H1UVKss81l.png" alt="63750">
</div>

* Pass1 階段產生的 SYMTAB:
* 每當 ASMTAB 處理過程遇到一個 label 時，LOCCTR 的現行值就是該 symbol 的位址，就把 label 跟位址新增到 SYMTAB，給 Pass2 階段翻譯用（例如分支或直接定址的指令）。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HkcOehi8ke.png" alt="63750">
</div>

---
### **Pass2 階段**
* 建立 REGTAB:
* 儲存課本定義的 register 及其對應的號碼，翻譯過程碰到與暫存器有關的指令時查表用。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BydJoe281x.png" alt="63750">
</div>

* 逐行翻譯並產生 object code:
* directive 的處理方式:
* BASE :
* 設定基址（base address）。使用基底相對位址（base relative addressing）時需要設定。
* BYTE :
* 如果運算元的開頭是 C 會將單引號裡面的字元轉成其對應的十六進制 ASCII 碼，複製到 OBJTAB。(例如 ASMTAB Line 17 的 EOF BYTE C'EOF' 中的 E O F 轉成 45 4F 46)。
* 而如果運算元的開頭是 X，就直接取出單引號裡面的字元，複製到 OBJTAB。(例如 ASMTAB Line 35 INPUT BYTE X'F1' 中的 F1)。
* START / RESW / RESB / END:
* 上述這四種 directive 就不產生 object code。

* mnemonic 的處理方式:
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/H1JaHz3UJl.png" alt="63750" style="width: 450px; height:500px; margin-left: 30px;">
</div>

* format 2 的處理方式:
* 翻譯 ASMTAB 時，會去 OPTAB 看 mnemonic 是什麼格式，再看運算元是一個還是兩個 register ，去 REGTAB 查詢 register 對應的號碼，再加上 mnemonic 的 opcode 來產生 object code，並複製到 OBJTAB。(只有一個 register 的話 r2 一律帶 0)

* 範例1: ASMTAB Line 21 的 CLEAR X。

* 範例2: ASMTAB Line 28 的 COMPR A,S。

* format 3 的處理方式:
* 翻譯 ASMTAB 時，會去 OPTAB 看 mnemonic 是什麼格式。
* Opcode: 只佔 6 bits ，所以轉成二進制時最右邊的兩個 bits 會被去掉。
* 初始化 flag n, i, x, b, p, e 為零。
* 設置 flag n, i: 定址模式:
* n = 1, i = 1, simple 直接定址模式
* n = 0, i = 1, immediate 立即定址模式 (運算元最前面有 #)
* n = 1, i = 0, indirect 間接定址模式 (運算元最前面有 @)
* 設置 flag x: index 定址模式:
* 如果運算元有,X 則 flag x = 1。
* 設置 flag e: 格式3固定為 0。
* 設置 flag b, p: 決定相對基底位址(base relative)模式或相對程式計數器位址(program-counter relative)模式:
* 先試 program-counter relative 公式:
* disp = TA - (PC)。如果 disp 在 [-2048, 2047] 之間，flag b 設置為 0, p 設置為 1，表示使用 PC relative 模式。
* 如果算出來是負值，會將 disp 加上 0x1000，並轉換為12位元的十六進制的正值。
* 而如果 disp 超出上面 PC relative 範圍，則嘗試 base relative 公式:
* disp = TA - (B)。如果 disp 在 [0, 4095] 之間，flag b 設置為 1，p 設置為 0，表示使用 base relative 模式，並轉換為12位元的十六進制的正值。
* 否則:
* 都不在上述範圍應該要報錯或嘗試格式4? (不在這次作業範圍，沒特別處理)
* 範例1: ASMTAB Line 26 的 JEQ RLOOP。
* 先試 PC: TA = 1040, PC = 1046 --> disp = TA - (PC) = 1040 - 1046 = -6(十六進制) = -6(十進制)，disp 有在 PC 範圍內，再把 -6 + 0x1000 = FFA。
* 使用 PC，flag p 設置為 1。
* 範例2: ASMTAB Line 40 的 LDCH BUFFER,X。
* 先試 PC: TA = 0036, PC = 106B --> disp = TA - (PC) = 0036 - 106B = -1035(十六進制) = -4149(十進制)，disp 不在 PC 範圍內。
* 換試 base: TA = 0036, B = LENGTH = 0033 --> disp = TA - (B) = 0036 - 0033 = 3(十六進制) = 3(十進制)，disp 在 base 範圍內。
* 使用 base，flag b 設置為 1。

* format 4 的處理方式:
* 翻譯 ASMTAB 時，若 mnemonic 前面有 + 號直接用格式4處理，用於支援 20 bits 的 target address，並將翻譯出來 object code 複製到 OBJTAB。
* Opcode: 只佔 6 bits ，所以轉成二進制時最右邊的兩個 bits 會被去掉。
* 初始化 flag n, i, x, b, p, e 為零。
* 設置 flag n, i: 定址模式:
* n = 1, i = 1, simple 直接定址模式
* n = 0, i = 1, immediate 立即定址模式 (運算元最前面有 #)
* n = 1, i = 0, indirect 間接定址模式 (運算元最前面有 @)
* 設置 flag x: index 定址模式:
* 如果運算元有,X 則 flag x = 1。
* 設置 flag b, p: 基底或相對位址模式（格式4固定為 0）。
* 設置 flag e: 格式4固定為 1。
* address: target address 佔 20 bits (沒滿的部分高位補 0)。
* 範例1:
* ASMTAB Line 5 的 +JSUB RDREC。
* 範例2:
* ASMTAB Line 24 的 +LDT #4096。

* format 4 需要重定位的處理方式:
* 只要運算元不是 # 開頭就會記錄該 mnemonic 的位址再加上 1，進行重定位。
* 05 固定長度，表示需要修改 20 bits。
* 課本定義格式3與格式4的 flag 設置方式等(黃底為格式4):

* 最終 Pass2 產生的 ASMTAB:
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Hk8FSvnLkg.png" alt="63750">
</div>
---
### **Object Program**
* 根據 OBJTAB 及其他資訊打印 record:
* OBJTAB:
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BkYPUv2Iyl.png" alt="63750">
</div>

* Header record: 程式的基本資訊。
* H^<program Name>^<start Address>^<program Length>
* program name: 程式名稱（佔 6 位）。
* start address: 程式的起始位址，轉換為十六進制(佔 6 位)。
* program length: 程式長度（LOCCTR - start address），轉換十六進制(佔 6 位)。

* Text record: object code 存放到多個 text record 中，並控制每條 record 的大小。
* T^<start address>^<record length>^<object code...>
* start address: 當前記錄的起始位址（object code 起始址）。
* record length: 累計的 object code 大小（以位元組計算，上限為 0x1D = 29 bytes）。
* object code: 放 object code 進去，並統計當前 text record 中的指令數量。

* Modification record: 處理 object program 中需要重定位的位址（如外部符號）。
* M^<modify address>^<length>
* modify address: 需要修改的位址。
* Length: 修改位元長度（5 半位，或 20 bits）

* End record: 標記程式結束並指定起始執行位址。
* E^<start address>
* start address：程式的入口位址，轉換為十六進制(佔 6 位)。

* 最終產出的 object program
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/ByIGoD3Uyx.png" alt="63750">
</div>