初窺Haskell：解析一個數學表達式

4 人贊了文章

最近在學習Haskell，不得不說，這真的是一門令我著迷的語言，lazy和純函數式等特性都非常吸引我，不過短時間內還無法掌握得很好，最重要是思維的轉變非常苦難。

曾幾何時我覺得Python是一門非常優雅的語言，但是現在我覺得還不夠，因為Python只是語法上非常簡潔，但是思維上不夠優雅，至少Python解決問題的思想是非常OOP的。

而現在我覺得通俗意義上的OOP和過程式解決問題非常的啰嗦，不如FP優雅和簡潔。

本篇文章所有源碼https://gist.github.com/vincentdchan/78435adcbb007df77e0c674201202925

學習一門語言最好的辦法就是多實踐，我還記得我寫過一片文章編譯原理學習筆記1：解析數學表達式

來講述怎樣去解析數學表達式，但是我沒有講如何去實現，現在剛好用Haskell實現一個。

gists里包含了我曾經在我的作業裡面用C#實現了一個過程式的數學表達式運算器，總代碼161行，而Haskell版只用了54行。FP的pattern matching在寫狀態複雜的程序的時候真的如虎添翼。

寫一個詞法分析器Tokenizer

我們要把字元串解析成一個個token，也就是我們平時所說的詞法分析器裡面的」詞「，想想一個數學表達式裡面有什麼類型的token？大概是只有數學符號和是數字？

data Token = Num Int | T_Plus | T_Sub | T_Mul | T_Div deriving (Show)

注意我在上一篇博文裡面提到的優先順序問題，我們需要有一個函數來返回操作符的優先順序，我們可以用pattern matching

getPrecedence:: Token -> IntgetPrecedence T_Plus = 1getPrecedence T_Sub = 1getPrecedence T_Mul = 2getPrecedence T_Div = 2

這種表達可以說是非常優雅了，然後開始寫一個詞法分析器……的定義

tokenizer:: String -> [Token]

haskell的類型定義，一個詞法分析器輸入一個字元串，然後輸出一串Token

接下來看我放大招

tokenizer函數將調用下面這個稍微複雜一點的_tokenizer來完成詞法分析操作，下面我來解釋一下這個函數的參數有什麼作用

1. 第一個參數就是待解析的字元串

2. 第二個參數是暫存的數據緩衝區，如果我們要讀入數字1234，那麼要先把123先緩存起來，讀入4後再一起解析

3. 第三個參數是**之前已經讀入的token**, 我們把這次解析出來的token連接進去，然後通過遞歸傳給下一次運算，最後直接返回下一次的遞歸調用返回的值，這種寫法叫做尾遞歸，可以減少內存的使用。關於尾遞歸這裡不詳細說。

_tokenizer:: String -> String -> [Token] -> [Token] -- 尾遞歸寫法_tokenizer "" [] previous = previous -- 所有字元都解析完畢_tokenizer "" buf previous = ((Num $ read $ reverse buf):previous) -- 字元都解析完畢，但是緩衝區還有數據_tokenizer (ch:expr) buf previous = if (Data.Char.isDigit ch) then -- 當前字元是一個數字 _tokenizer expr (ch:buf) previous -- 把數字放入緩衝區 else -- 當前字元不是數字 case buf of -- 檢查緩衝區是否為空 [] -> -- 緩衝區為空 case ch of -- 解析當前字元 + -> _tokenizer expr [] (T_Plus:previous) - -> _tokenizer expr [] (T_Sub:previous) * -> _tokenizer expr [] (T_Mul:previous) / -> _tokenizer expr [] (T_Div:previous) _ -> _tokenizer (ch:expr) [] ((Num $ read $ reverse buf):previous) -- 緩衝區不為空，讀取緩衝區字元

注意：緩衝區保存的數字緩衝是倒序的，當我們用`read`函數讀取數值的時候，要先用reverse函數反轉

然後tokenizer的定義就很簡單了，我們詞法分析出來的列表是倒序的，我們要用reverse函數來反轉。

tokenizer expr = reverse (_tokenizer expr [] [])

表達式求值

到此為止，詞法分析器就完成了，當我們對一串字元串調用tokenizer就可以得到一串token了，接下來就是如何對表達式進行求值，原理可以回顧編譯原理學習筆記1：解析數學表達式，這裡講講實現

-- 定義操作符運算evalOp :: Token -> Int -> Int -> IntevalOp T_Plus a b = a + bevalOp T_Sub a b = a - bevalOp T_Mul a b = a * bevalOp T_Div a b = a `div` b-- 搞一個好看點的包裝函數eval :: [Token] -> Inteval ((Num value):tokens) = _eval tokens [value] []-- 真正運作的函數在這裡_eval :: [Token] -> [Int] -> [Token] -> Int-- 操作數棧裡面只有一個數了，就是我們要求的值了_eval [] [value] _ = value-- 操作符棧數值為空，進行SHIFT操作_eval (op:(Num num):tokens) numStack [] = _eval tokens (num:numStack) [op]-- 操作符棧不為空_eval (op:(Num num):tokens) numStack (topOp:opStack) = if (getPrecedence op) > (getPrecedence topOp) then _eval tokens (num:numStack) (op:topOp:opStack) -- SHIFT else -- REDUCE case numStack of (num1:num2:stack) -> _eval (op:(Num num):tokens) ((evalOp topOp num1 num2):stack) opStack-- 棧里還有一些殘留的值，繼續運算_eval [] (num1:num2:numStack) (topOp:opStack) = _eval [] ((evalOp topOp num1 num2):numStack) opStack

這裡`_eval`的參數

1. 要解析的token集合

2. 操作數的棧

3. 操作符的棧

總結

總的來說，在pattern matching的幫助下，寫一個表達式求值的程序可以說非常簡潔明了。當你用過程式語言去寫tokenizer的時候，你需要控制一個指針在字元串上移來移去，非常容易出錯，如果用pattern matching，只需要定義好相應的字元串就可以了，非常優雅。

歡迎訪問我的博客