深入理解運算原理｜從簡單的機器到無所不能的程式

只想加入運算能力

|

137

狀態 接受與否？ 堆疊內容 剩下的輸入 動作

2 否 M}$ n} 提出 M, 推入 T

2 否 T}$ n} 提出 T, 推入 n

2 是 n}$ n} 讀取 n, 提出 n

這項執行追蹤讓我們知道機器如何在符號和符記規則之間不斷來回：符號規則重複展開

堆疊頂端的符號，直到符記換掉它，然後符記規則處理堆疊（和輸入）裡的資料，直

到它們命中符號。只要文法規則可以產生輸入字串，這樣的來來回回最終會導致空的堆

疊

8

。

PDA 如何知道在每個執行步驟要選擇哪條規則？沒錯，這就是非決定論的威力：我們

的 NPDA 模擬物會嘗試所有可能的規則，所以只要出現能獲得空堆疊的方式，我們就

會找到它。

實踐

這種解析過程雖然依賴非決定論，但在實際應用最好避免非決定論，因為決定論 PDA

比非決定論的版本快很多，而且更容易模擬。所幸只要使用輸入符記本身來決定每個階

段要套用哪一項符號規則，幾乎可以完全排除非決定論（一種稱為

前看

[

lookahead

] 的

技巧），但是這會讓 CFG 轉換到 PDA 的過程更加複雜。

它也不是真的好到只能識別有效的程式。如同我們在第 61 頁的『實現解析器』所見，

解析程式的整個重點是將它轉換成接著我們可以做些益事的結構化表示方式。在實踐的

過程，只要將我們的 PDA 模擬物工具化，並且記錄它所遵循的一組規則，進而達到接

受狀態，就可以建立這種表示方式，這提供了構造解析樹的足夠資訊。舉例來說，以上

的執行追蹤告訴我們如何展開堆疊裡的符號，進而形成所需要的符記序列，並且也告訴 ...