可配置語法分析器開發紀事（六）：構造真正可用的狀態機（下）

右遞歸處理

上文已處理左遞歸，本文解決右遞歸。右遞歸產生 reduce 循環（左遞歸是 shift 循環）。

狀態機構造回顧

• 非終結符引用通過 shift/reduce (ε-邊) 連接子狀態機。
• 若 A 以 B 結尾且非右遞歸，無循環問題。

右遞歸形成

當規則引用自身且位於尾部：A → α A。狀態機出現 reduce ε-循環。

解決策略：延遲減歸

不壓縮 ε-循環，改在運行時「試探」：

1. 狀態機無路可走時，檢查是否有右遞歸 reduce 可用。
2. 因無其他邊產生相同棧匹配結構，嘗試安全。
3. 成功則彈出狀態繼續，實現遞歸歸約。

此法保留語法樹構造所需的語義動作，不簡化為正則表達式。

未解決的上下文相關難題

C 語言兩大難題仍需非確定性下推自動機 (NPDA) 處理：

1. 變量聲明歧義：A * B; 可能是乘法或指針聲明，需符號表輔助或保留歧義節點。
2. 強制類型轉換：(A*****)B 括號內類型/表達式無限長，lookahead 無效，需 NPDA 並行探索。

下一篇將講解非確定性解析器實現。