再整理一次音界咒語法。
音界咒檔 = 音界咒・檔案結尾
音界咒 = 句
| 句・音界咒
句 = 變數宣告式
| 算式
變數宣告式 = "元"・"・"・變數・"="・算式
算式 = 乘除式
| 算式・+・乘除式
| 算式・−・乘除式
乘除式 = 原子式
| 乘除式・*・原子式
| 乘除式・/・原子式
原子式 = 數字
| 變數
| "("・算式・")"
前文提到,有了語法規則定義,就能透過遞迴展開生成符(生成符,即在語法規則左側出現,還能繼續展開的符號),最終獲得所有長度小於 n 的展開式。
當吾人想要剖析時,也能利用這個想法,若一份文本長度為 n ,那遞迴生成出所有長度等於 n 的展開式,並一一與原始碼做比對,比到一種展開是一模一樣的,檢視當下的展開過程,就能得到語法樹了。
一直展開到長度 n 才比對,太浪費時間了,一發現當下的展開式已經跟文本不一樣,就可以放棄目前展開,回溯到上個還沒失敗的狀態。
寫成虛擬碼如下:
// 「剖析」函式嘗試以「展開式」來生成「文本」
「文本」為一全域變數
剖析(展開式)-> 成功|失敗:
匹配展開式與文本,若相等,回傳成功
首生成符 = 展開式中的第一個生成符
遍歷首生成符的「生成規則」 {
新展開式 = 在原展開式中,以「生成規則」展開首生成符
若「新展開式」的前綴已與文本不同,嘗試下個規則
若「剖析(新展開式)」成功,回傳成功
}
走到這裡表示所有規則都不行,回傳失敗
// 初始展開式僅為「音界咒檔」
剖析(音界咒檔)
以上虛擬碼為求簡單,省略了許多優化,例如說,首生成符的位置跟目前比對無誤的文本位置都應該紀錄起來,不用每次都從頭比對。另外,編譯器應用中,剖析應回傳語法樹,而非單單成功或失敗。
注意到剖析(展開式)
是遞迴函式,它會嘗試以各種規則展開首生成符,然後繼繻呼叫剖析(新展開式)
。
觀察剖析(算式)
,只要第一個規則算式 = 乘除式
配對失敗,就會嘗試匹配算式 = 算式・+・乘除式
,也就是呼叫剖析(算式・+・乘除式)
,此一規則並沒有消耗任何文本,第一個規則剛剛不能生效,此刻一樣不能生效,於是會再套用一次算式 = 算式・+・乘除式
得到剖析(算式・+・乘除式・+・乘除式)
......如此落入無窮遞迴。
若保證每個展開都能消耗掉至少一個字符,就能避免落入遞迴,但文本卻完全不變的狀況。再次改寫算式:
其中 e 代表空字串。
算式 = 乘除式・重複乘除式
重複乘除式 = +・乘除式・重複乘除式
| −・乘除式・重複乘除式
| e
乘除式 = 原子式・重複原子式
重複原子式 = *・原子式・重複原子式
| /・原子式・重複原子式
| e
原子式 = 數字
| 變數
| "("・算式・")"
算式被改寫了真多次,由此可見寫出易於剖析的語法不是一件易事。所幸,這是零・一版最後一次重寫語法了。