可配置語法分析器開發紀事（三）：生成下推自動機

下推自動機 (PDA) 基礎

PDA = 有限自動機 + 不定長棧。文法規則對應 PDA 狀態，點 ● 表示當前位置。

例子：IDList 文法

ID = NAME
IDList = ID | IDList "," ID

狀態：

ID0 = ● NAME
ID1 = NAME ●
IDList0 = ● (ID | IDList "," ID)
IDList1 = (ID | IDList "," ID) ●
IDList2 = (ID | IDList ● "," ID)
IDList3 = (ID | IDList "," ● ID)

轉移：ID0 -NAME-> ID1，IDList0 -ID-> IDList1，IDList0 -IDList-> IDList2，IDList2 -","-> IDList3，IDList3 -ID-> IDList1。

Shift / Reduce 機制

• Shift：遇非終結符，壓入當前狀態，跳轉子規則起始態。
• Reduce：到達子規則終結態，彈出棧頂驗證匹配，返回父規則後續態。

棧模擬函數調用：壓入返回地址，歸約時彈出返回。

連接兩規則 PDA

1. 處理 ID 引用：IDList0 shift-> ID0，ID1 reduce-> IDList1；IDList3 shift-> ID0，ID1 reduce-> IDList1。
2. 左遞歸 IDList0 -IDList-> IDList2：從 ID1 連 IDList2 並補 假shift IDList0。

解析模擬

輸入 A,B,C$，狀態/棧/輸入三元組逐步推演，最終棧空輸入盡到達 FINISH，驗證 PDA 正確性。

下一步：確定化 (NPDA→DPDA) 與 Lookahead 處理。