萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

四則運算表達式編譯器實作:詞法分析、語法分析、語法導向翻譯生成組合語言

專案簡介

編譯原理經典實驗:輸入整數四則運算表達式 (含 `+ - * / ( )`),經**詞法分析**產生 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

二、語法導向翻譯模式 (構建 AST 並生成代碼)

每個非終結符對應一個綜合屬性 `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;
        }
    }
}

五、遞迴下降語法分析器 (對應 LL(1) 文法)


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;
}

六、AST 後序遍歷生成 x86 組合語言 (以 EAX 為累加器)


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

八、擴展方向

  • 支援變數賦值、函式呼叫、關鍵字 (if/while) → 完整編譯器前端。
  • 目標代碼優化:常數摺疊、公共子表達式消除、暫存器分配 (圖著色)。
  • 錯誤恢復:Panic mode、Phrase level recovery。
  • 使用 Lex/Yacc (Flex/Bison) 自動生成分析器。

總結

本實作展示了**詞法分析 (狀態機) → 語法分析 (遞迴下降) → AST 建構 → 代碼生成 (後序遍歷)** 的完整編譯器前端流程。理解此流程是掌握程式語言實作、靜態分析工具開發、DSL 設計的基石。

copyright © 萬盛學電腦網 all rights reserved