編譯原理實戰：遞歸下降語法分析器 C 語言完整實作（含詞法分析）

實驗目標

實作一個**遞歸下降語法分析器**，對簡單語言進行語法檢查。輸入單詞串（以 `#` 結束），輸出 `success` 或 `error`。語言文法（EBNF）如下：

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

核心架構

• 詞法分析器 `scaner()`：將字符流轉換為單詞符號（token），識別關鍵字、標識符、數字、運算符、界符。
• 語法分析器：每條文法規則對應一個函數（`lrparser`→`yucu`→`statement`→`expression`→`term`→`factor`），遞歸下降解析。
• 全域狀態：`syn` 當前單詞編碼，`token` 當前單詞字串，`prog` 輸入緩衝區，`p` 讀取指標，`kk` 錯誤標誌。

單詞編碼表

完整 C 代碼（可直接編譯執行）

#include <stdio.h>
#include <string.h>
#include <ctype.h>

char prog[1000], token[20], ch;
char *rwtab[6] = {"begin", "if", "then", "while", "do", "end"};
int syn, p, m, n, kk;

void scaner(void);
void lrparser(void);
void yucu(void);
void statement(void);
void expression(void);
void term(void);
void factor(void);

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

/* ===== 詞法分析 ===== */
void scaner(void) {
    m = 0;
    ch = prog[p++];
    while (ch == ' ') ch = prog[p++]; // 跳過空白

    if (isalpha(ch)) { // 標識符或關鍵字
        while (isalnum(ch)) {
            token[m++] = ch;
            ch = prog[p++];
        }
        p--; // 回退一個非字母數字字符
        token[m] = '\0';
        syn = 10; // 預設 ID
        for (n = 0; n < 6; n++) {
            if (strcmp(token, rwtab[n]) == 0) {
                syn = n + 1; // 關鍵字編碼 1-6
                break;
            }
        }
    }
    else if (isdigit(ch)) { // 數字
        while (isdigit(ch)) {
            token[m++] = ch;
            ch = prog[p++];
        }
        p--;
        token[m] = '\0';
        syn = 11; // NUM
    }
    else { // 運算符/界符
        token[0] = ch; token[1] = '\0';
        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;
        }
    }
}

/* ===== 語法分析：各非終結符對應函數 ===== */
void lrparser(void) { // <程序>
    if (syn == 1) { // begin
        scaner();
        yucu();
        if (syn == 6) { // end
            scaner();
            if (syn == 0 && kk == 0) printf("success!\n");
        } else {
            if (kk == 0) printf("the string haven't got a 'end'!\n");
            kk = 1;
        }
    } else {
        printf("haven't got a 'begin'!\n");
        kk = 1;
    }
}

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

void statement(void) { // <語句> ::= ID := <表達式>
    if (syn == 10) { // ID
        scaner();
        if (syn == 18) { // :=
            scaner();
            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) { // + -
        scaner();
        term();
    }
}

void term(void) { // <項> ::= <因子> { * <因子> | / <因子> }
    factor();
    while (syn == 15 || syn == 16) { // * /
        scaner();
        factor();
    }
}

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

測試範例

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

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

關鍵實作細節

1. scaner 回退機制：讀取標識符/數字結束時，`p--` 將首個非屬字符推回輸入流，供下次 `scaner` 處理。
2. 關鍵字優先識別：先按標識符規則讀完，再查表 `rwtab` 判斷是否為關鍵字，修正 `syn`。
3. 錯誤標誌 `kk`：一旦發現錯誤置 1，阻止後續誤報 `success`，但繼續解析以發現更多錯誤（簡易錯誤恢復）。
4. 遞歸下降對應文法：每個非終結符一個函數，函數體直接翻譯產生式右部，`while` 處理 `{...}` 重複，`if` 處理 `|` 選擇。

擴展方向

• 加入錯誤恢復：同步集合（如遇錯誤跳至 `;` 或 `end` 繼續）。
• 生成抽象語法樹（AST）節點結構，而非僅檢查。
• 支援更多語句類型（`if`、`while`、函數呼叫等）。
• 使用工具（Lex/Yacc、ANTLR）自動生成分析器。