編譯原理入門（四）：手寫 C 語言簡易詞法分析器完整實作

專案目標

為了驗證詞法分析理論，本文實作一個**教學級簡易詞法分析器**，支援關鍵字、標識符、整數常數、運算子/界符，輸出 <類別碼, 屬性> 序列。程式碼採用**單通道掃描 + 狀態機硬編碼**風格，無外部依賴，適合初學者研讀。

支援語言子集定義

保留字（6 個）

begin  if  then  while  do  end

運算子與界符（13 個）

:  :=  +  -  *  /  <  <=  <>  >  >=  =  ;  (  )  #

標識符與常數正則

ID  = letter (letter | digit)*
NUM = digit digit*

類別碼對照表

完整 C 實作（含詳細註解）

#include 
#include 

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

void scanner(void);

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

    p = 0;
    do {
        scanner();
        switch (syn) {
            case 11:  // NUM
                printf("( %-10d %5d )\n", sum, syn);
                break;
            case -1:  // Error
                printf("You have input a wrong string\n");
                return 0;
            default:  // ID, keyword, operators
                printf("( %-10s %5d )\n", token, syn);
                break;
        }
    } while (syn != 0);
    return 0;
}

void scanner(void) {
    sum = 0;
    for (m = 0; m < 8; m++) token[m] = '\0';
    m = 0;
    ch = prog[p++];

    // 跳過空白
    while (ch == ' ' || ch == '\n') 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; // 預設 ID
        // 查保留字表
        for (n = 0; n < 6; n++) {
            if (strcmp(token, rwtab[n]) == 0) {
                syn = n + 1; // 1~6
                break;
            }
        }
    }
    // 數字常數
    else if (ch >= '0' && ch <= '9') {
        while (ch >= '0' && ch <= '9') {
            sum = sum * 10 + (ch - '0');
            ch = prog[p++];
        }
        p--;
        syn = 11; // NUM
    }
    // 運算子 / 界符
    else {
        switch (ch) {
            case '<':
                token[m++] = ch;
                ch = prog[p++];
                if (ch == '>') { syn = 21; token[m++] = ch; }      // <>
                else if (ch == '=') { syn = 22; token[m++] = ch; } // <=
                else { syn = 20; p--; }                            // <
                break;
            case '>':
                token[m++] = ch;
                ch = prog[p++];
                if (ch == '=') { syn = 24; token[m++] = ch; } // >=
                else { syn = 23; p--; }                       // >
                break;
            case ':':
                token[m++] = ch;
                ch = prog[p++];
                if (ch == '=') { syn = 18; token[m++] = ch; } // :=
                else { syn = 17; p--; }                       // :
                break;
            case '+': syn = 13; token[m++] = ch; break;
            case '-': syn = 14; token[m++] = ch; break;
            case '*': syn = 15; token[m++] = ch; break;
            case '/': syn = 16; token[m++] = ch; break;
            case '(': syn = 27; token[m++] = ch; break;
            case ')': syn = 28; token[m++] = ch; break;
            case ';': syn = 26; token[m++] = ch; break;
            case '#': syn = 0;  token[m++] = ch; break;
            default:  syn = -1; break; // 非法字元
        }
    }
    token[m] = '\0';
}

測試範例

輸入

begin x:=9; if x>9 then x:=2*x+1/3; end #

輸出

( begin       1 )
( x          10 )
( :=         18 )
( 9          11 )
( ;          26 )
( if         2 )
( x          10 )
( >          23 )
( 9          11 )
( then       3 )
( x          10 )
( :=         18 )
( 2          11 )
( *          15 )
( x          10 )
( +          13 )
( 1          11 )
( /          16 )
( 3          11 )
( ;          26 )
( end        6 )
( #          0 )

核心邏輯解析

1. 緩衝區管理： prog[] 存全程式，p 為讀取指標，token[] 暫存當前 Token 字串。
2. 狀態機硬編碼： 以 if-else + switch 直接實現 DFA 轉移，無顯式狀態表。
3. 回退機制： 讀取到不屬於當前 Token 的字元時 p--，使該字元下次掃描重新處理。
4. 保留字識別： 先按 ID 規則掃描完整標識符，再查表 rwtab 判斷是否為關鍵字。
5. 數值累積： sum = sum*10 + (ch-'0') 邊掃描邊計算整數值。

局限性與擴展方向

總結

這個簡易掃描器雖然功能有限，但完整展示了詞法分析的核心要素：**輸入緩衝、空白跳過、模式識別、屬性計算、Token 輸出**。閱讀並單步除錯此程式碼，能讓初學者建立「字元流如何變為 Token 流」的具體心智模型，為後續學習語法分析、工具生成器打下堅實基礎。