四則運算解析

這幾天在密集地把四則運算解析的程式寫起來。我分別在下列二個專案裡,處理這個題目:

  1. erljscon :實作 Graham Hutton 的 parser combinators ,以此為基礎要解析 JSON 語法
  2. acie :顧名思義 Arithmetic Calculator in Erlang ,要能做四則運算。

Hutton 的論文 “Higher-Order Functions for Parsers" 真的厲害,而 parser 寫起來的感覺,是你可以知道:每個 parser 都專注處理它的資料,並且為它的左、右二項服務,可是,它並不知道左、右二項的細節是什麼。

以 parser combinators 的處理方式,擅長於處理整個區段的輸入,並且也處理到了最常匹配項 (the longest match) 。

ACIE 則是打算走 Erlang 風格的系統實作。在系統拆解為 actors 多程序平行、分散、互動的情況下,我想知道一個 parser 可以變成怎麼樣。我保持了輸入的基本順序,先在 lexing actor 裡頭將句子拆解為詞彙。然後以訊息發送方式,將詞彙傳遞給 parsing actor 。所以在 parsing actor 裡頭,要維護一個 waiting_tree() 資料結構。 waiting_tree() 是一個 tree 搭上 stack 的複合結構,我認為可以將它命名為 Accordion ,雖然有人早就指出 Haskell Zipper 這種資料結構。

不管稱為 Accordion 或者 Zipper ,用意是二者相當的。我需要這個結構,是能讓我丟一個詞彙進去,它就建構一個 parsing tree ,而且可能是半完成的 parsing tree 。之後,我可以要它退回一步,它就把最後一次丟進去的詞彙交還出來,而且退回為上一步的 parsing tree 。

Parser combinators 的程式非常好寫,而且能徹底跟隨著 BNF 。而我的 ACIE parsing 則比較不容易寫,在維護著 waiting_tree() 的同時,我需要隱約一致地 (virtual identically) 使此系統的運作結果符合語法樹。對於這個需求,即使早早地切換到 Test-Driven Development ,仍為了設計的穩當,感到膽戰心驚。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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