正剖 (Parsing) 反剖 (Unparsing)

 

以下所談,是有關於這一點點程式: arithmetic_calculator_in_erlang 專案: commit 9e4be26

為了寫一個說來簡單的四則運算算式的 parser ,我設定 parsing tree 需要能剖析,也能反轉剖析。 詞彙要能進來,也要能刪除。

由於算式是由前往後輸入,我的程式習慣是以 context 收集一個接著一個出現的詞彙,逐漸把 parsing tree 建立起來。因此,概略來說 parsing tree 有二種狀態:剖析完成的狀態,以及需要等待下一詞彙的狀態。

之前寫過一個版本,呆呆地使用一個 context ,每當收集資料,便從根部開始走訪。後來我回想到,那是個根本的問題:在 C++ 或 Java 之類的技術裡,可以用變數指向 parsing tree 的一個子樹根部,從那裏開始繼續做。可是,我在 Erlang 及 Functional Programming 裡,使用一個 context 累積資料,同時也是累積計算成本。

我需要做二件事情:

  1. 要限定下一詞彙到來時, context 的處理範圍。
  2. 建立的 parsing tree 要可以從尾端逐步拆解。

有網友推薦我看 Huet 所設計的 Functional Programming 資料結構,稱為 Zipper 。看了該篇 Functional Pearl 論文二頁,我了解到自己所需要的是一個 stack of trees 的結構。在我的程式裡,將 a stack of trees 結構命名為 waiting_tree() 。

Parsing with waiting_tree() 的演算法大概是這樣:

  1. 輸入:一串詞彙。詞彙是一個接著一個進來,但不必全都進來。
  2. 輸出:一個完成的 parsing tree ,或者一個等待完成的 parsing tree 。二者為共同的資料型態 waiting_tree() 。parsing tree 是一個 stack ,稱為 waiting_tree() 資料型態。
  3. 不變項:
    1. parsing tree 要嘛是 [] ,要嘛則是 [#expression{ full= true }] ,要嘛則是 [#expression{ full= false }|_]= WT, length(WT) > 1 。
    2. tree 元素 #expression{ op=, left=, right= } 每一欄位為 undefined 的情況,為下列幾種情況之一:(非 undefined 以 _ 表達)
      1. #expression{ op= undefined, left= undefined, right= undefined }
      2. #expression{ op= undefined, left= _, right= undefined }
      3. #expression{ op= _, left= _, right= undefined }
      4. #expression{ op= _, left= _, right= _ }
  4. 演算法名為 add_term ,步驟如下:
    1. 開始時,  parsing tree 為 [] 。
    2. 在處理下一詞彙之前,如果 parsing tree 為 [] ,則創造第一個虛擬的 tree [#expression{}] ,再做後續處理。
    3. 如果下一詞彙為數字,則要嘛填 parsing tree 的第一個元素的左項,如果左項為空,要嘛填第一個元素的右項,如果右項為空而運算符號已填。
    4. 如果下一詞彙為運算符號,並且 parsing tree 的第一個元素的左項已填,則填入中項。
    5. 如果下一詞彙是冪次 (factor) 符號,而 parsing tree 的第一個元素是 full 且 op 是加法詞彙,則搶奪該元素的右子樹 R ,放到新創的一個元素裡: #expression{ left= R } 。
    6. 如果下一詞彙為左括號,並且 parsing tree 的第一個元素要嘛是左項未填,要嘛是右項未填,則在 parsing tree 前頭新增一個元素。
    7. 如果 parsing tree 的第一個元素已填滿,則將該樹的 full 改為 true ,並且將 parsing tree 收攏。(所謂收攏 parsing tree ,是指從頭到尾依序,看 parsing tree 的元素如果是 full ,則將該樹收疊到下一個元素裡。)
    8. 如果下一個詞彙為右括號,並且 parsing tree 的第一個元素是 full ,另該元素命名為 E ,則將該元素收進一個新創的元素裡: #expression{ left= E }
    9. (程式中尚未寫上的:)如果前一個詞彙是加法,而下一個詞彙是冪次,則要將後者替換掉前者,作法為:將 parsing tree 刪除最後一個詞彙(使用另有名為 drop_term 的演算步驟),再使用 add_term 演算步驟將下一個運算符號加上。

 

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Uncategorized。將永久鏈結加入書籤。