🚉 Vincent's bus station
文章
初窥 Haskell：解析一个数学表达式
Posted at 2017-10-30

最近在学习 Haskell，不得不说，这真的是一门令我着迷的语言，lazy 和纯函数式等特性都非常吸引我，不过短时间内还无法掌握得很好，最重要是思维的转变非常苦难。

学习一门语言最好的办法就是多实践，我还记得我写过一片文章编译原理学习笔记1：解析数学表达式 来讲述怎样去解析数学表达式，但是我没有讲如何去实现，现在刚好用 Haskell 实现一个。

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

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 -> Int
getPrecedence T_Plus = 1
getPrecedence T_Sub = 1
getPrecedence T_Mul = 2
getPrecedence 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 -> Int
evalOp T_Plus a b = a + b
evalOp T_Sub a b = a - b
evalOp T_Mul a b = a * b
evalOp T_Div a b = a `div` b

-- 搞一个好看点的包装函数
eval :: [Token] -> Int
eval ((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，只需要定义好相应的字符串就可以了，非常优雅。

© 2024, Built with Gatsby