編譯原理經典實驗:輸入整數四則運算表達式 (含 `+ - * / ( )`),經**詞法分析**產生 Token 流,**語法分析**建構語法樹 (AST),**語法導向翻譯**生成 x86 組合語言程式碼。開發環境:C 語言 + VC++。
// 原始左遞迴文法
E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | num
// 消除左遞迴後 (LL(1) 文法)
E -> T E'
E' -> + T E' | - T E' | ε
T -> F T'
T' -> * F T' | / F T' | ε
F -> ( E ) | num
每個非終結符對應一個綜合屬性 `nptr` (AST 節點指標) 或 `s` (翻譯後代碼片段)。
E ::= T { E'.i := T.nptr } E' { E.nptr := E'.s }
E' ::= + T { E'1.i := mknode('+', E'.i, T.nptr) } E'1 { E'.s := E'1.s }
| - T { E'1.i := mknode('-', E'.i, T.nptr) } E'1 { E'.s := E'1.s }
| ε { E'.s := E'.i }
T ::= F { T'.i := F.nptr } T' { T.nptr := T'.s }
T' ::= * F { T'1.i := mknode('*', T'.i, F.nptr) } T'1 { T'.s := T'1.s }
| / F { T'1.i := mknode('/', T'.i, F.nptr) } T'1 { T'.s := T'1.s }
| ε { T'.s := T'.i }
F ::= ( E ) { F.nptr := E.nptr }
| num { F.nptr := mkleaf(num, num.val) }
#define MAX_EXPR_LEN 100
#define MAX_NODES 200
typedef enum { ERR=-1, END, NUM, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN } TokenType;
char expr[MAX_EXPR_LEN];
int expr_idx = 0;
char token_text[MAX_EXPR_LEN];
// AST 節點
typedef struct Node {
char op; // 運算子: '+','-','*','/' 或 0 表葉子
int val; // 葉子數值
struct Node *left, *right;
} Node;
Node node_pool[MAX_NODES];
int node_cnt = 0;
Node* mkleaf(int val) {
Node* p = &node_pool[node_cnt++];
p->op = 0; p->val = val; p->left = p->right = NULL;
return p;
}
Node* mknode(char op, Node* l, Node* r) {
Node* p = &node_pool[node_cnt++];
p->op = op; p->val = 0; p->left = l; p->right = r;
return p;
}
TokenType get_token()
{
char ch;
int j = 0;
if (expr[expr_idx] == '\0') { token_text[0]='#'; token_text[1]='\0'; return END; }
while (1) {
ch = token_text[j++] = expr[expr_idx++];
if (isspace(ch)) { j--; continue; } // 跳過空白
if (isdigit(ch)) { // 數字
while (isdigit(expr[expr_idx]))
token_text[j++] = expr[expr_idx++];
token_text[j] = '\0';
return NUM;
}
switch (ch) {
case '+': token_text[j]='\0'; return PLUS;
case '-': token_text[j]='\0'; return MINUS;
case '*': token_text[j]='\0'; return MUL;
case '/': token_text[j]='\0'; return DIV;
case '(': token_text[j]='\0'; return LPAREN;
case ')': token_text[j]='\0'; return RPAREN;
default: return ERR;
}
}
}
Node* parse_E(); // 前向宣告
Node* parse_E1(Node* inherited);
Node* parse_T();
Node* parse_T1(Node* inherited);
Node* parse_F();
Node* parse_E() {
Node* t = parse_T();
return parse_E1(t);
}
Node* parse_E1(Node* inh) {
if (strcmp(token_text, "+")==0 || strcmp(token_text, "-")==0) {
char op = token_text[0];
get_token();
Node* t = parse_T();
Node* node = mknode(op, inh, t);
return parse_E1(node);
}
// Follow(E') = {#, ')'}
if (strcmp(token_text, "#")!=0 && strcmp(token_text, ")")!=0)
error("Syntax error in E'");
return inh; // ε 產生式:直接回傳繼承屬性
}
Node* parse_T() {
Node* f = parse_F();
return parse_T1(f);
}
Node* parse_T1(Node* inh) {
if (strcmp(token_text, "*")==0 || strcmp(token_text, "/")==0) {
char op = token_text[0];
get_token();
Node* f = parse_F();
Node* node = mknode(op, inh, f);
return parse_T1(node);
}
if (strcmp(token_text, "+")!=0 && strcmp(token_text, "-")!=0 &&
strcmp(token_text, "#")!=0 && strcmp(token_text, ")")!=0)
error("Syntax error in T'");
return inh;
}
Node* parse_F() {
if (strcmp(token_text, "(")==0) {
get_token();
Node* e = parse_E();
if (strcmp(token_text, ")")!=0) error("Missing )");
get_token();
return e;
}
if (current_token == NUM) {
int val = atoi(token_text);
get_token();
return mkleaf(val);
}
error("Expect number or (");
return NULL;
}
void gen_asm(Node* root) {
if (!root) return;
if (root->op == 0) { // 葉子:載入數值到 EAX
printf(" MOV EAX, %d\n", root->val);
return;
}
// 內部節點:先算右子樹存入記憶體/暫存器,再算左子樹在 EAX,最後運算
gen_asm(root->right);
printf(" PUSH EAX\n"); // 保存右運算元
gen_asm(root->left); // 左運算元結果在 EAX
printf(" POP EBX\n"); // 取回右運算元到 EBX
switch (root->op) {
case '+': printf(" ADD EAX, EBX\n"); break;
case '-': printf(" SUB EAX, EBX\n"); break;
case '*': printf(" IMUL EAX, EBX\n"); break;
case '/': printf(" CDQ\n IDIV EBX\n"); break; // 有號除法
}
}
int main()
{
gets(expr); // 注意:gets 不安全,教學用;實務用 fgets
expr_idx = 0;
get_token(); // 預讀第一個 token
Node* ast = parse_E();
if (current_token != END) error("Extra tokens after expression");
printf("; Generated x86 Assembly\n");
printf(".CODE\n");
gen_asm(ast);
printf(" RET\n");
return 0;
}
輸入: 3+4*5
輸出:
; Generated x86 Assembly
.CODE
MOV EAX, 5
PUSH EAX
MOV EAX, 4
POP EBX
IMUL EAX, EBX ; EAX = 20
PUSH EAX
MOV EAX, 3
POP EBX
ADD EAX, EBX ; EAX = 23
RET
本實作展示了**詞法分析 (狀態機) → 語法分析 (遞迴下降) → AST 建構 → 代碼生成 (後序遍歷)** 的完整編譯器前端流程。理解此流程是掌握程式語言實作、靜態分析工具開發、DSL 設計的基石。