Parsing Combinators in Haskell

今天排定的進度算結束了，唸編譯器是其中一項，所以就順勢來做 scm 老師這次的 Haskell exercises。目標是寫出一組可合成 context-free parser 的 higher-order functions，精神和 Boost spirit library 應該是一樣的。後者我是上了大學才聽聞，沒怎麼研究過。

看來兩者產生的都是 recursive-descent (hence LL) parsers。然後 Haskell 版處理 nondeterminism 的方式是用標準的 subset construction，其中 sets 以 lists 實作。

--
先貼一篇佔位，之後會補完 XD。

---

(3:06AM) 寫了一個很簡單的算式求值器，支援 "reversed binary numbers" 的加法與乘法，可用小括號表示子算式。架構是標準的 tokenisation → parsing → tree flattening。為了讓加和乘是 left-associative，我寫出來的 grammar 是 left-recursive，所以還用上才剛讀到的 left-recursion elimination。

--
顯然又是寫篇 literate Haskell 的時候了，待續 XD。

---

我直接在 blog 上寫一篇好了，parsing combinator 的符號和 lhs2TeX 不太有默契 XD。

--
請見《Parser Combinators in Haskell》XD。