寫parser多簡單?

為了處理 Jabber/XMPP 的實作，勢必要考慮到 parser。

根據 Wikipedia 的說明，parser是指將一串輸入文字建立為 parse tree 的功能。根據文法，字串無法剖析為 parse tree 代表剖析錯誤。

用 Haskell 寫 parser 似乎比較簡單。 (?)

Parse tree

一般來說，(binary) tree 是指：

1. 「空無」情況是 tree ，或是


2. 以一項物件為基礎，擁有左子項和右子項，二個子項也是 tree 。

在 Haskell 定義 tree 資料結構為

data Tree = A | B | Bin (Tree, Tree)
deriving Show

看起來已經滿足一個 parse tree 的構成。

Parser

Parser 是一個函數，其輸入為一串資料，並輸出一些可能的 parse tree 和剩餘未 parsed 的資料。因此宣告 parser 的資料型態為：

type Parser a b = [a] -> [(b, [a])]

其中， a 是輸入資料的型態， b 是 parse tree 的型態。

根據 Parser a b 的型態規範，可以定義各式各樣的 parser 。例如：

永遠 parsed 的 parser 叫做 succeed

succeed :: Parser a ()
succeed xs = [((), xs)]

永遠 false-parsed 的 parser 叫做 fail

fail :: Parser a b
fail xs = []

讀取指定字元的 parser 叫做 lit (literal parser)

lit :: Eq a => a -> Parser a a
lit x (y:xs) | x == y = [(y, xs)]
lit x _ = []

執行情況：

lit 對字串 "Babcd" 要 parse 一個 `B' 字元，就得到一個 parsed `B'，並剩下 "abcd" 字串。

lit 對字串 "Aabcd" 要 parse 一個 `B' 字元， parse 失敗，於是得到一個 empty list [] 代表 false-parsed 。

(待續)