編譯器前端的詞法/語法分析階段，核心任務之一就是驗證原始碼中的成對符號（括號、大括號、方括號、引號、尖括號）是否正確匹配。這正是**堆疊**的經典應用場景：遇左符號入堆疊，遇右符號出堆疊比對，最後堆疊為空且掃描結束即匹配成功。
( [ { < ' " → 將其位址壓入堆疊) ] } > ' " → 堆疊彈出頂元素，比對是否對應左符號
// 假設已有 LinkStack 模組 (建立/銷毀/推入/彈出/取頂/判空)
typedef struct LinkStackNode {
void *data;
struct LinkStackNode *next;
} LinkStackNode;
typedef struct {
LinkStackNode *top;
int size;
} LinkStack;
// 介面宣告 (實作略)
LinkStack *LinkStack_Create(void);
void LinkStack_Destroy(LinkStack *s);
int LinkStack_Push(LinkStack *s, void *data);
void *LinkStack_Pop(LinkStack *s);
void *LinkStack_Top(LinkStack *s);
int LinkStack_IsEmpty(LinkStack *s);
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkstack.h" // 鏈式堆疊模組
// 判斷是否為左符號
int is_left(char c) {
return (c=='(' || c=='[' || c=='{' || c=='<' || c=='\'' || c=='\"');
}
// 判斷是否為右符號
int is_right(char c) {
return (c==')' || c==']' || c=='}' || c=='>' || c=='\'' || c=='\"');
}
// 比對左、右符號是否成對
int match(char left, char right) {
return (left=='(' && right==')') ||
(left=='[' && right==']') ||
(left=='{' && right=='}') ||
(left=='<' && right=='>') ||
(left=='\'' && right=='\'') ||
(left=='\"' && right=='\"');
}
// 主掃描函式
int scan_symbols(const char *code) {
LinkStack *stack = LinkStack_Create();
if (!stack) return 0;
int i = 0;
while (code[i] != '\0') {
char c = code[i];
if (is_left(c)) {
// 壓入字元位址 (展示堆疊存儲 void* 通用性)
LinkStack_Push(stack, (void*)(code + i));
} else if (is_right(c)) {
char *left_ptr = (char*)LinkStack_Pop(stack);
if (left_ptr == NULL || !match(*left_ptr, c)) {
printf("符號不匹配: 位置 %d 字元 '%c'\n", i, c);
LinkStack_Destroy(stack);
return 0;
}
}
i++;
}
// 掃描結束檢查
if (LinkStack_IsEmpty(stack)) {
printf("✅ 符號匹配檢測通過：編譯成功\n");
LinkStack_Destroy(stack);
return 1;
} else {
printf("❌ 有未閉合的左符號\n");
LinkStack_Destroy(stack);
return 0;
}
}
// 測試主程式
int main() {
const char *test_code =
"#include \n"
"#include \n"
"int main() {\n"
" int a[5][5];\n"
" int (*p)[5];\n"
" p = a[0];\n"
" printf(\"%d\", &a[3][3] - &p[3][3]);\n"
"}";
scan_symbols(test_code);
return 0;
}
LinkStack_Push(stack, (void*)(code + i));
利用 void* 通用性，直接存字元在原字串中的位址。彈出時轉回 char* 解參考取值。這避免了額外複製字元，也展示了鏈式堆疊「存任意資料指標」的靈活性。
採用三個小函式 is_left、is_right、match，邏輯清晰、易擴充 (如支援註解 /* */、字串字面值內的括號忽略等)。
記錄索引 i，錯誤時可輸出具體位置與字元，方便除錯。
真實編譯器需忽略下列內容中的括號：
"... ( ) [ ] ..."'(', ')'// .../* ... */需引入**狀態機**掃描：NORMAL、IN_STRING、IN_CHAR、IN_LINE_COMMENT、IN_BLOCK_COMMENT、ESCAPE (處理 \\、\" 轉義)。
| 特性 | 鏈式堆疊 | 陣列堆疊 |
|---|---|---|
| 記憶體分配 | 動態、按需 | 固定大小或手動擴容 |
| 溢出風險 | 僅受限於記憶體 | 固定容量易滿 |
| 快取局部性 | 較差 (節點分散) | 極佳 (連續記憶體) |
| 適合場景 | 未知深度、長生命週期 | 已知最大深度、高效能需求 |
編譯器前端通常採用**動態陣列堆疊** (如 std::vector 或手擴容陣列)，兼顧效能與彈性；教學演示常用鏈式堆疊展示指標操作。
// linkstack.h #ifndef LINKSTACK_H #define LINKSTACK_H typedef struct LinkStack LinkStack; LinkStack *LinkStack_Create(void); void LinkStack_Destroy(LinkStack *s); int LinkStack_Push(LinkStack *s, void *data); void *LinkStack_Pop(LinkStack *s); void *LinkStack_Top(LinkStack *s); int LinkStack_IsEmpty(LinkStack *s); #endif // linkstack.c #include#include "linkstack.h" struct LinkStackNode { void *data; struct LinkStackNode *next; }; struct LinkStack { struct LinkStackNode *top; int size; }; LinkStack *LinkStack_Create(void) { LinkStack *s=malloc(sizeof(LinkStack)); if(s){s->top=NULL;s->size=0;} return s; } void LinkStack_Destroy(LinkStack *s) { while(s->top){struct LinkStackNode *n=s->top; s->top=n->next; free(n);} free(s); } int LinkStack_Push(LinkStack *s, void *data) { struct LinkStackNode *n=malloc(sizeof(*n)); if(!n) return 0; n->data=data; n->next=s->top; s->top=n; s->size++; return 1; } void *LinkStack_Pop(LinkStack *s) { if(!s->top) return NULL; struct LinkStackNode *n=s->top; void *d=n->data; s->top=n->next; free(n); s->size--; return d; } void *LinkStack_Top(LinkStack *s) { return s->top ? s->top->data : NULL; } int LinkStack_IsEmpty(LinkStack *s) { return s->top == NULL; } // main.c (含上方 scan_symbols 實作) #include #include "linkstack.h" /* ... is_left, is_right, match, scan_symbols, main ... */
符號匹配是堆疊的教科書級應用，也是編譯器前端的基石邏輯。透過鏈式堆疊實作，不僅掌握了**資料結構操作**，更理解了**編譯器如何靜態分析程式結構**。進階方向：加入狀態機處理字串/註解、建立 AST 節點、錯誤恢復策略、語法導向翻譯。
