編譯原理入門（五）：手寫 C 語言遞歸下降語法分析器實作

專案目標

接續詞法分析器，本文實作一個**遞歸下降語法分析器**，對簡易語言進行語法檢查與結構分析。採用「詞法分析 + 語法分析一體化」單檔案設計，驗證文法導向解析的核心機制。

目標語言文法（EBNF）

<程序>      ::= begin <語句串> end
<語句串>  ::= <語句> { ; <語句> }
<語句>    ::= <賦值語句>
<賦值語句> ::= ID := <表達式>
<表達式>  ::= <項> { + <項> | - <項> }
<項>      ::= <因子> { * <因子> | / <因子> }
<因子>    ::= ID | NUM | ( <表達式> )

對應優先序：賦值 < 加減 < 乘除 < 因子（標識符/常數/括號）。

實驗需求

• 輸入以 # 結尾的單詞串（由詞法分析器產生）。
• 語法正確輸出 success!，否則輸出具體錯誤訊息（如缺 begin、缺 :=、括號不匹配）。

完整 C 實作

#include 
#include 

char prog[100], token[8], ch;
char *rwtab[6] = {"begin", "if", "then", "while", "do", "end"};
int syn, p, m, n, sum;
int kk; // 錯誤旗標

// 前向宣告
void factor(void);
void expression(void);
void yucu(void);    // 語句串
void term(void);
void statement(void);
void lrparser(void); // 程序入口
void scanner(void);

int main(void) {
    p = kk = 0;
    printf("\nPlease input a string (end with '#'):\n");
    do {
        scanf("%c", &ch);
        prog[p++] = ch;
    } while (ch != '#');

    p = 0;
    scanner();   // 取第一個 Token
    lrparser();  // 啟動語法分析
    return 0;
}

// 程序 → begin 語句串 end
void lrparser(void) {
    if (syn == 1) { // begin
        scanner();
        yucu();
        if (syn == 6) { // end
            scanner();
            if (syn == 0 && kk == 0) printf("success!\n");
        } else {
            if (kk != 1) printf("The string haven't got an 'end'!\n");
            kk = 1;
        }
    } else {
        printf("Haven't got a 'begin'!\n");
        kk = 1;
    }
}

// 語句串 → 語句 { ; 語句 }
void yucu(void) {
    statement();
    while (syn == 26) { // ;
        scanner();
        if (syn != 6) statement(); // 非 end 才解析下一句
    }
}

// 語句 → ID := 表達式
void statement(void) {
    if (syn == 10) { // ID
        scanner();
        if (syn == 18) { // :=
            scanner();
            expression();
        } else {
            printf("The sign ':=' is wrong!\n");
            kk = 1;
        }
    } else {
        printf("Wrong sentence!\n");
        kk = 1;
    }
}

// 表達式 → 項 { +項 | -項 }
void expression(void) {
    term();
    while (syn == 13 || syn == 14) { // + -
        scanner();
        term();
    }
}

// 項 → 因子 { *因子 | /因子 }
void term(void) {
    factor();
    while (syn == 15 || syn == 16) { // * /
        scanner();
        factor();
    }
}

// 因子 → ID | NUM | ( 表達式 )
void factor(void) {
    if (syn == 10 || syn == 11) { // ID 或 NUM
        scanner();
    } else if (syn == 27) { // (
        scanner();
        expression();
        if (syn == 28) { // )
            scanner();
        } else {
            printf("The error on '('\n");
            kk = 1;
        }
    } else {
        printf("The expression error!\n");
        kk = 1;
    }
}

// 詞法分析器（同上一節精簡版）
void scanner(void) {
    sum = 0;
    for (m = 0; m < 8; m++) token[m] = '\0';
    m = 0;
    ch = prog[p++];
    while (ch == ' ') ch = prog[p++];

    if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
        while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')) {
            token[m++] = ch;
            ch = prog[p++];
        }
        p--;
        token[m] = '\0';
        syn = 10;
        for (n = 0; n < 6; n++)
            if (strcmp(token, rwtab[n]) == 0) { syn = n + 1; break; }
    }
    else if (ch >= '0' && ch <= '9') {
        while (ch >= '0' && ch <= '9') {
            sum = sum * 10 + (ch - '0');
            ch = prog[p++];
        }
        p--;
        syn = 11;
    }
    else {
        switch (ch) {
            case '<':
                ch = prog[p++];
                if (ch == '>') syn = 21;
                else if (ch == '=') syn = 22;
                else { syn = 20; p--; }
                break;
            case '>':
                ch = prog[p++];
                if (ch == '=') syn = 24;
                else { syn = 23; p--; }
                break;
            case ':':
                ch = prog[p++];
                if (ch == '=') syn = 18;
                else { syn = 17; p--; }
                break;
            case '+': syn = 13; break;
            case '-': syn = 14; break;
            case '*': syn = 15; break;
            case '/': syn = 16; break;
            case '(': syn = 27; break;
            case ')': syn = 28; break;
            case '=': syn = 25; break;
            case ';': syn = 26; break;
            case '#': syn = 0; break;
            default: syn = -1; break;
        }
    }
}

測試驗證

案例 1：正確程式

輸入: begin a:=9; x:=2*3; b:=a+x end #
輸出: success!

案例 2：缺 begin

輸入: x:=a+b*c end #
輸出: Haven't got a 'begin'!

案例 3：缺 :=

輸入: begin a=9 end #
輸出: The sign ':=' is wrong!

遞歸下降核心機制解析

1. 文法非終結符 → 函數： 每個非終結符（program, statement, expression...）對應一個解析函數。
2. 產生式選擇 → 條件判斷： 根據當前 Token (syn) 決定展開哪條產生式（LL(1) 特性）。
3. 終結符匹配 → 掃描下一 Token： 匹配成功呼叫 scanner() 推進輸入流。
4. 錯誤處理 → 全域旗標 + 錯誤訊息： kk 標記是否出錯，避免重複報錯；實際編譯器會採用恐慌模式/同步集合恢復。

左遞歸消除與優先序編碼

原文法 表達式 → 表達式 + 項 為左遞歸，遞歸下降無法直接處理。改寫為右遞歸等價形式：

表達式 → 項 { + 項 }
項      → 因子 { * 因子 }

在代碼中體現為 while (syn == +|-) { scanner(); term(); } 迴圈，隱含左結合語意。

局限性與工業級差距

總結

遞歸下降解析器以「函數調用鏈模擬文法推導」的直觀方式，完美詮釋了**語法分析 = 文法驅動的樹構建構**本質。雖手寫版功能有限，但掌握其「非終結符即函數、產生式即分支、Token 流即輸入帶」的核心模式，是通往 Yacc/Bison/ANTLR 等生成器工具、手寫優化解析器（如 Go/V8/Clang 前端）的必經之路。