Vincent Chan 的巴士站 🚉

初窥 Racket:解析一个数学表达式

当 Haskell 这些静态类型的函数式语言玩久了,就想尝试一下动态类型的函数式语言,比如 Lisp,最古老的编程语言之一。不过现在写 Lisp 是不现实,因为原始的 Lisp 是 dynamic scope 的,写起来会异常痛苦。所以我打算从 Lisp 的一些比较现代方言下手,比如说 Racket 这种广受赞誉的语言。

看了一下官方文档之后感觉还是应该写点什么实际的东西感受一下,个人比较喜欢写数学表达式解析器了。之前写过一篇「初窥Haskell:解析一个数学表达式」。所以这次打算用 Racket 写解析一个数学表达式程序。

Racket 不是一个“纯”的语言,所以在 Racket 里面写有副作用的代码是没有问题的,说不定还会有更高的效率。但是这次我没有这么做,因为受到 Haskell 的影响,所以我还是用“纯”函数式的方法去实现。

(define (char->op ch)
  (cond
    [(char=? ch #\+) 'add]
    [(char=? ch #\-) 'sub]
    [(char=? ch #\*) 'mul]
    [(char=? ch #\/) 'div]))

(struct token (type value)
  #:prefab)

(define (tokenizer content)
  (letrec (
    [char-list (string->list content)]
    [my-tokenizer (lambda (reading-buffer number-buffer token-buffer)
      (if (null? reading-buffer)
        (if (null? number-buffer)
          token-buffer ;;; 所有字符都已经解析完毕
          (cons  ;;; 还有 number-buffer 的字符串
            (token 'number 
              (string->number (list->string (reverse number-buffer)))) 
            token-buffer))
        (let (
          [first-char (car reading-buffer)]
          [buffer-tail (cdr reading-buffer)]
        ) (if (char-numeric? first-char) ;;; 当前字符是一个数字
              (my-tokenizer buffer-tail (cons first-char number-buffer) token-buffer)
              (if (null? number-buffer)
                (let (
                  [current-token (token 'operator (char->op first-char))])
                  (my-tokenizer buffer-tail (list) (cons current-token token-buffer)))
                (let (
                  [number-token 
                    (token 'number 
                      (string->number 
                        (list->string 
                          (reverse number-buffer))))]
                ) (my-tokenizer 
                    reading-buffer 
                    (list) 
                    (cons number-token token-buffer))))))))]
  ) (my-tokenizer char-list (list) (list))))

以上代码实现了一个 tokenizer,是用尾递归的方法来实现的。

Lisp 的括号语法一直饱受争议,但是这样做不是没有好处的,就是整个 Lisp 写起来其实没有太多复杂的语法,而且语法都显得很一致,很容易组合,而且 Racket 有很强的宏编程能力,关于这点我还没有了解。有人把 Lisp 理解成手写 AST(Abstract Syntax Tree),这种说法我觉得也没有问题。

一般的类 C 语言的变量名喜欢用下划线或者驼峰标记法来区分,而在 Racket 里面,则可以用 this-is-a-variable 这种小短杠来表示,个人觉得看上去还是很舒服的。另一方面,很多标点符号也可以用来作为变量名,比如 string? 是一个用来判断变量是否为 string 的函数。比如 string->numer 用来表示字符串转数字的函数,个人感觉非常直观。

和 Haskell 相比起来会麻烦一点的地方就是要自己去判断变量的类型,但是这也意味着给语言提供更大的灵活性。

(define (get-precedence x) 
  (match x
    ['add 1]
    ['sub 1]
    ['mul 2]
    ['div 2]))

(define (eval tokens)
  (letrec (
    [get-handler (lambda (op)
                  (match op
                    ['add +]
                    ['sub -]
                    ['mul *]
                    ['div /]))]
    [my-eval (lambda (tokens num-stack op-stack)
                (if (null? tokens)
                  (match op-stack
                    [null (car num-stack)]
                    [(cons top-op op-stack-tail)
                      (let* 
                        (
                          [num1 (car num-stack)]
                          [num2 (car (cdr num-stack))]
                          [num-stack-tail (cdr (cdr num-stack))]
                          [handler (get-handler top-op)]
                          [result (handler num1 num2)]
                        )
                        (my-eval (list) (cons result num-stack-tail) op-stack-tail))])
                  (let* (
                    [next-op (token-value (car tokens))]
                    [next-number (token-value (car (cdr tokens)))]
                    [tokens-tail (cdr (cdr tokens))]
                  ) (match op-stack
                      [null 
                        (my-eval 
                          tokens-tail 
                          (cons next-number num-stack) 
                          (cons next-op op-stack))]
                      [(cons top-op op-stack-tail)
                        (let* (
                            [op-stack-tail (cdr op-stack)]
                            [top-op (car op-stack)]
                            [top-op-precedence (get-precedence top-op)]
                            [next-op-precedence (get-precedence next-op)]
                          ) (if (> next-op-precedence top-op-precedence)
                              (my-eval 
                                tokens-tail 
                                (cons next-number num-stack) 
                                (cons next-op op-stack))
                              (let* (
                                [num1 (car num-stack)]
                                [num2 (car (cdr num-stack))]
                                [num-stack-tail (cdr (cdr num-stack))]
                                [handler (get-handler top-op)]
                                [result (handler num1 num2)]
                              ) (my-eval tokens (cons result num-stack-tail) op-stack-tail))))]))))]
    [num (token-value (car tokens))]
    [token-tail (cdr tokens)]
  ) (my-eval token-tail (list num) (list))))

上述代码定义了一个 eval 函数,用优先级解析的方法去解析上面写的函数生成的 tokens

代码写起来会比 Haskell 版本的稍长一点,但是个人感觉非常清晰,语法也很一致和漂亮。个人感觉是 Racket 确实是一门非常漂亮的语言,也没有像 Haskell 玩各种概念这么烧脑,还是动态类型的,平时娱乐一下开拓一下眼界感觉非常好。