編譯原理實驗：四則運算表達式編譯為匯編代碼全過程 (詞法、語法、語義、代碼生成)

編譯原理經典實驗：整數四則運算表達式 → 抽象語法樹 (AST) → 四元式 → x86 匯編代碼。C 語言實現，VC 環境。

1. 文法與翻譯模式 (消除左遞歸)

E  → T E'
E' → + T E' | - T E' | ε
T  → F T'
T' → * F T' | / F T' | ε
F  → ( E ) | num

語法導向翻譯構建 AST，屬性傳遞：綜合屬性 .nptr (節點指針)，繼承屬性 .i。

2. 全局定義 test.c

#define MAX_EXPRESSION_LENGTH 50
char expression[MAX_EXPRESSION_LENGTH];
int expression_index = 0;
char strToken[MAX_EXPRESSION_LENGTH/2];
enum Symbol { ERR=-1, END, NUM, PLUS, MINUS, TIMES, SLASH, LPAREN, RPAREN };
// AST 節點
typedef struct ASTNode { Symbol sym; int val; struct ASTNode *left, *right; } ASTNode;
// 四元式
typedef struct Quaternion { char op; char arg1[20], arg2[20], result[20]; } Quaternion;
Quaternion quaternion[40]; int qcount = 0;

3. 詞法分析 test1.c - 狀態圖法

狀態 0: 起始 → 識別數字/運算符/括號/空白/結束。狀態 1: 數字序列。返回枚舉 Symbol 及 strToken。

4. 語法分析 test2.c - 遞歸下降

每個非終結符對應一函數 (E(), E1(), T(), T1(), F())，調用 getToken() 獲取下一符號，錯誤調用 error() 退出。

5. 語義分析 test3.c - 構建 AST + 生成四元式

• mknode(op, left, right) 創建運算符節點。
• mkleaf(NUM, val) 創建葉子節點。
• 翻譯模式駅動構建：E() 返回根節點。
• 中序遍歷 驗證 AST 結構 (還原中綴表達式)。
• 後序遍歷 生成四元式：棧存操作數，遇運算符彈出兩個操作數生成四元式，結果壓棧 (臨時變量 t+4, t+8...)。

6. 代碼生成 test4.c - 四元式轉 x86 匯編

void print_code(Quaternion q) {
    if (q.op == '+') { printf(" mov eax,%s\n add eax,%s\n mov %s,eax\n", q.arg1, q.arg2, q.result); }
    else if (q.op == '-') { printf(" mov eax,%s\n sub eax,%s\n mov %s,eax\n", q.arg1, q.arg2, q.result); }
    else if (q.op == '*') { printf(" mov eax,%s\n mov ebx,%s\n mul ebx\n mov %s,eax\n", q.arg1, q.arg2, q.result); }
    else if (q.op == '/') { printf(" mov eax,%s\n mov ebx,%s\n div ebx\n mov %s,eax\n", q.arg1, q.arg2, q.result); }
}

輸出 MASM 風格匯編：.386, .MODEL FLAT, 數據段定義臨時變量 t DWORD 40 DUP(?), 代碼段調用 dtoa / output (Irvine 库) 顯示結果。

7. 運行示例

輸入: 3+4*2
中序: 3 + 4 * 2
四元式:
*       4       2       t+4
+       3       t+4     t+8
匯編:
 mov eax,4
 mov ebx,2
 mul ebx
 mov t+4,eax
 mov eax,3
 add eax,t+4
 mov t+8,eax
 ...

8. 核心難點與收穫

• 左遞歸消除與屬性文法設計。
• AST 動態內存管理 (malloc/free)。
• 後序遍歷生成四元式的棧機制。
• 匯編指令選擇 (mul/div 使用 eax/edx)。
• 完整編譯器前端+後端微縮實現，深刻理解編譯流程。

總結

從字符流到匯編代碼：**詞法分析 (狀態機) → 語法分析 (遞歸下降) → 語義分析 (AST+四元式) → 代碼生成 (模式匹配)**。每階段輸出為下階段輸入，結構清晰。此實驗奠定編譯器構建基礎，理解現代編譯器 (LLVM/GCC) 前端中端後端架構的微縮模型。