使用 Haskell 編寫靈活的 Parser （上）

01-26

為什麼我會想到去用 Haskell 寫 Parser 呢？因為 Haskell 的 do notation 對這種 Monad 組合子真的太友好了。

另一個原因是因為最近在 CodeWars 上做了不少 Parser 題，刷分巨快(因為 Parser 題都是紫色的)，很快把我推上了 1kyu 。

全文代碼如有誤歡迎指出，我會誠懇地改正。本文講的內容不多，主要是介紹，下篇文章會說怎麼解析帶優先順序/結合性的表達式。

首先我說說 Parser Combinator （就是函數式編程中採用的編寫 Parser 的方式）的基本使用。篇幅所限， Parsre Combinator 庫的編寫就不說了。它其實是將針對某種語法模塊的 Parser 單元組合起來成為可以解析複雜語法的 Parser 。比如我有一個可以解析數字的 Parser 和一個可以解析符號 + 的 Parser ，那麼組合他們就可以得到加法運算的 Parser 。大概是這樣：

plusParser :: Parser CharplusParser = xxxxnumberParser :: Parser IntnumberParser = xxxxdata Op a b = Op a b aplusOperationParser :: Parser (Op a b)plusOperationParser = do a <- numberParser plusParser b <- numberParser return $ Op a "+" b

是不是一目了然呢？

語法介紹

首先我有類型及對應構造器 Op 表示一個二元運算，然後有解析數字的 numberParser 和解析加號的 plusParser ，他們通過最下面那個超級簡單的 do notation （就是按從上到下的順序運行這些 Parser ，解析成功則返回解析好的那個東西（比如 Parser a 解析後就返回 a ，那麼同理上面的 plusParser 解析完後返回一個 Char 。而 numberParser 返回的是解析好的 Int ，我們通過那個箭頭的語法來捕獲它返回的值。後者我們需要保留解析後留下的數字，但前者我們都知道它返回的一定是 "+" ，因此再獲取這個返回的值意義不大，因此它就沒有箭頭，最後用一個 return 把返回值拼起來）組合到一起（事實上 do notation 只是 Monad 的系列套餐的一個語法糖，但這是一個非常厲害的語法糖。篇幅所限，本文不討論，也不需要讀者懂 do notation 展開後到底啥樣）。

總結

一個 Parser a 解析字元串，返回 a 類型的東西。

Parser a 之間可以互相組合，成為一個大 Parser b 。

構建最簡單的 Parser

首先我們有一個函數 satisfy ，通過一個 Char -> Bool 構造出一個 Parser Char ，也就是給定一個函數，把字元傳入，返回 True 則代表成功解析。舉個例子，這個函數接收一個 Char ，返回專門解析這個 Char 的 Parser ：

char :: Parser Charchar = satisfy . (==)

如果不 point-free 並進行 eta 展開的話就是這樣（如果看不懂上面的版本就看這個吧）：

char c = satisfy (x -> x == c)

而如果我們要編寫一個解析字元串 >>= 的 Parser ，則：

bind :: Parser Stringbind = do char ">" char ">" char "=" return ">>="

再抽象一下，解析某個長度為 3 的字元串（作為參數）的 Parser ：

three :: String -> Parser Stringthree s@[a, b, c] = do char a char b char c return s

再抽象一下，解析任意長度為 3 的字元串：

oneC :: Parser CharoneC = do c <- satisfy $ const True return c--three" :: Parser Stringthree" = do a <- oneC b <- oneC c <- oneC return [a, b, c]

到這裡你是不是已經大概清楚怎麼使用 Parser Combinator 了？想不想動手試試？

（有毒）具體在 GHCi 中使用

首先，大家可以選擇使用我在文章末尾提供的微型實現;

或者安裝：

版本算正常的 GHC
版本算正常的 Cabal

然後執行：

$ cabal install parsec...$ ghci...Prelude> :m +Text.ParserCombinators.ReadP

然後剩下的我也不會，我只知道我的 Parser 實現在這個庫中的等價物是（應該是） ReadP a。所以你們還是直接用我在附錄裡面放的網上找的那份獨立的吧（霧（其實我還魔改過一點點啦，編碼習慣啥的，不是大事））。

用法：

首先寫好你的 Parser （假設就是 myP ，直接和我給的代碼寫一起），然後打開 GHCi 載入你的文件，然後運行：

parseCode myP "the code you want to parse"

就可以看到返回的結果了。具體的例子：

Main> parseCode (satisfy (`elem` "jfly")) "j""j"Main> parseCode (satisfy (`elem` "jfly")) "f""f"Main> parseCode (satisfy (`elem` "jfly")) "g"*** Exception: Hugh?

讀者感興趣的話可以試試實現一個 Parser ，解析一個帶括弧的字元串，返回括弧內部的東西。

你學到了什麼

簡易的 Parser Combinator 的使用

預告

稍微複雜點的表達式的解析

（附） Parser Combinator 簡易實現

成功解析返回解析結果，失敗則 error "Hugh?" （模仿 dram）。

import Data.Charimport Data.Listimport Control.Monadimport Control.Applicative-------------------------------------------------------------------- my parser combinator ---------------------------------------------------------------------newtype Parser val = Parser { parse :: String -> [(val, String)] }parseCode :: Parser a -> String -> aparseCode m s = case parse m s of [(res, [])] -> res _ -> error "Hugh?"--instance Functor Parser where fmap f (Parser ps) = Parser $ p -> [ (f a, b) | (a, b) <- ps p ]--instance Applicative Parser where pure = return (Parser p1) <*> (Parser p2) = Parser $ p -> [ (f a, s2) | (f, s1) <- p1 p, (a, s2) <- p2 s1 ]--instance Monad Parser where return a = Parser $ s -> [(a, s)] p >>= f = Parser $ concatMap ((a, s1) -> f a `parse` s1) . parse p--instance MonadPlus Parser where mzero = Parser $ const [] mplus p q = Parser $ s -> parse p s ++ parse q s--instance Alternative Parser where empty = mzero p <|> q = Parser $ s -> case parse p s of [] -> parse q s rs -> rs--item :: Parser Charitem = Parser $ s -> case s of [ ] -> [] (h : t) -> [(h, t)]--satisfy :: (Char -> Bool) -> Parser Charsatisfy p = item >>= c -> if p c then return c else empty