iT邦幫忙

2024 iThome 鐵人賽

DAY 14
0
Software Development

離塵指引.卷之一.試結丹:程式語言自舉系列 第 14

零.一版剖析器(三)回溯剖析與左遞迴問題

  • 分享至 

  • xImage
  •  

再整理一次音界咒語法。

音界咒檔 = 音界咒・檔案結尾

音界咒     = 句
          | 句・音界咒

句        = 變數宣告式
          | 算式

變數宣告式 = "元"・"・"・變數・"="・算式

算式   = 乘除式
      | 算式・+・乘除式
      | 算式・−・乘除式

乘除式 = 原子式
      | 乘除式・*・原子式
      | 乘除式・/・原子式

原子式 = 數字
      | 變數
      | "("・算式・")"

前文提到,有了語法規則定義,就能透過遞迴展開生成符(生成符,即在語法規則左側出現,還能繼續展開的符號),最終獲得所有長度小於 n 的展開式。

當吾人想要剖析時,也能利用這個想法,若一份文本長度為 n ,那遞迴生成出所有長度等於 n 的展開式,並一一與原始碼做比對,比到一種展開是一模一樣的,檢視當下的展開過程,就能得到語法樹了。

一直展開到長度 n 才比對,太浪費時間了,一發現當下的展開式已經跟文本不一樣,就可以放棄目前展開,回溯到上個還沒失敗的狀態。

寫成虛擬碼如下:

// 「剖析」函式嘗試以「展開式」來生成「文本」

「文本」為一全域變數

剖析(展開式)-> 成功|失敗:
    匹配展開式與文本,若相等,回傳成功

    首生成符 = 展開式中的第一個生成符
    
    遍歷首生成符的「生成規則」 {
        新展開式 = 在原展開式中,以「生成規則」展開首生成符
        若「新展開式」的前綴已與文本不同,嘗試下個規則

        若「剖析(新展開式)」成功,回傳成功
    }

    走到這裡表示所有規則都不行,回傳失敗

// 初始展開式僅為「音界咒檔」
剖析(音界咒檔)

以上虛擬碼為求簡單,省略了許多優化,例如說,首生成符的位置跟目前比對無誤的文本位置都應該紀錄起來,不用每次都從頭比對。另外,編譯器應用中,剖析應回傳語法樹,而非單單成功或失敗。

消除左遞迴

注意到剖析(展開式)是遞迴函式,它會嘗試以各種規則展開首生成符,然後繼繻呼叫剖析(新展開式)

觀察剖析(算式),只要第一個規則算式 = 乘除式 配對失敗,就會嘗試匹配算式 = 算式・+・乘除式,也就是呼叫剖析(算式・+・乘除式),此一規則並沒有消耗任何文本,第一個規則剛剛不能生效,此刻一樣不能生效,於是會再套用一次算式 = 算式・+・乘除式得到剖析(算式・+・乘除式・+・乘除式)......如此落入無窮遞迴。

若保證每個展開都能消耗掉至少一個字符,就能避免落入遞迴,但文本卻完全不變的狀況。再次改寫算式:

其中 e 代表空字串。

算式      = 乘除式・重複乘除式

重複乘除式 = +・乘除式・重複乘除式
          | −・乘除式・重複乘除式
          | e

乘除式    = 原子式・重複原子式

重複原子式 = *・原子式・重複原子式
         | /・原子式・重複原子式
         | e

原子式    = 數字
         | 變數
         | "("・算式・")"

算式被改寫了真多次,由此可見寫出易於剖析的語法不是一件易事。所幸,這是零・一版最後一次重寫語法了。


上一篇
零.一版剖析器(二)歧義消除
下一篇
零.一版剖析器(四)抽象語法樹
系列文
離塵指引.卷之一.試結丹:程式語言自舉32
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言