megrxu

Parser and Evaluator Exercises

Aug 11, 2020  「PL」  

最近需要学习用 ML 族的语言写一个 VHDL 的 Parser,于是就有了一系列的尝试,顺便完成了几道 Codewars 上的习题。

Tutorial

最开始是读了 ML for the working programmer 一书,里面有相应的章节来教如何函数式地写一个 Parser,笔记

Evaluate mathematical expression

Exercise Link

用了 racket 来完成。基本思路就是按照读的书来写的,也没有再用额外的库。因此对于 parser combinator 的理解只能说是非常初步,停留在已经给出的几个例子中。

Parser 的组合也是手写的,错误类型就用 #f 来表示(非常原初)。例如:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
(define (try-both p1 p2)
  (lambda (tl)
    (let [(res (p1 tl))]
      (if res
          res
          (p2 tl)))))
(define (try-all . pl)
  (foldr try-both (lambda (x) x) pl))
(define (repeat p)
  (lambda (tl)
    (let* [(res (p tl))
           (nxt (p res))]
      (if nxt
          ((repeat p) res)
          res))))

而在 parse 嵌套括号的时候用了更加原始的方法:使用一个被 iter 传来传去的中间参数 n 作为嵌套深度来进行处理。仿佛回到了刚学函数式编程的时候。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(define (get-block tl)
  (define (get-first-block tl)
    (define (iter n pre post)
      (cond [(zero? n) (cons (reverse (cdr pre)) post)]
            [(null? post) error "Unmatched paren."]
            [(eq? (car post) #\)) (iter (- n 1) (cons (car post) pre) (cdr post))]
            [(eq? (car post) #\() (iter (+ n 1) (cons (car post) pre) (cdr post))]
            [else (iter n (cons (car post) pre) (cdr post))]))
    (iter 1 '() tl))
  (cond [(null? tl) #f]
        [(false? tl) #f]
        [(eq? (car tl) #\() (let [(res (get-first-block (cdr tl)))]
                              (if res
                                  (append (real-parse (car res))
                                                      (cdr res))
                                  #f))]
        [else #f]))

Simple Interactive Interpreter

Exercise Link

需要实现一个可以定义函数的,仅有浮点数类型,支持定义变量及计算的小的解释器,用了 Rust 来实现。

当然选 Rust 的原因没别的,只是想试试看怎么样。最后的代码质量也很差,仍然有很多 bug。其思路与上一个尝试基本没有任何长进,甚至处理括号的方式也如出一辙。

更糟糕的是,Rust 里面没有那种用一根线把真正有用的部分串起来返回,或者直接返回 NoneErr(_) 之类的操作(Monad),所以代码也会相当难看,使用了巨量的 if let ... else ...

虽然后来用 or_else 或者 ? 之类的函数优化了一些,不过某些地方仍然无法完全消除掉 if 嵌套。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 消除了
fn parse_factor(tl: &[Token]) -> Option<(Factor, usize)> {
    parse_assignment(tl)
        .or(parse_paren_expression(tl))
        .or(parse_function_call(tl))
        .or(match tl.first() {
            Some(Token::Id(id)) => Some((Factor::Id(id.to_string()), 1)),
            _ => None,
        }
        .or(parse_val(tl).or(None)))
}

// 没办法,因为第二个分支必须用 if let 来 destruct parse_factor 的返回值
fn parse_expr(tl: &[Token]) -> Option<(Expr, usize)> {
    if let Some(res) = parse_expr_combination(tl) {
        Some(res)
    } else if let Some((f, n)) = parse_factor(tl) {
        Some((Expr::Factor(f), n))
    } else {
        None
    }
}

I love Lisp

Exercise Link

这个练习的数据结构都已经给出,并且最终要实现的函数接口也已给出。就只要按照模式匹配慢慢实现就好了。而且 Haskell 中本身就已经有定义好的 Parser Combinator 库了(而且不止一个),带来了很多方便。写的时候思路就更加清晰了。这里用了 Text.ParserCombinators.ReadP

像各种小单元的 Parse 就相当轻松,从头开始实现也不麻烦:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
digit :: ReadP Char
digit = satisfy (\char -> char >= '0' && char <= '9')

number :: ReadP Int
number = do
  n <- many1 digit
  return $ read n

ident :: ReadP String
ident = do
  h <- identZ
  ss <- many identS
  return $ h : ss

AST 的 Parser 只要看看 BNF 范式就能写出来了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
nodParser :: ReadP AST
nodParser = do
  optional sep
  char '('
  optional sep
  s <- astParser
  _ <- optional sep
  asts <- sepBy astParser sep
  optional sep
  char ')'
  optional sep
  return $ Nod s asts

astParser :: ReadP AST
astParser = do
  ast <- nodParser <|> litParser
  return ast

(不过感觉还是不够好,optional sep 用的有点多,不知道还能怎么办)

各种语言 的 Parser Combinator 库

Haskell 就不必说了。

Rust 有 nom

OCaml 有 Angstrom

1
2
let skip_spaces = skip_many (char ' ')
let parens p = char '(' *> skip_spaces *> p <* skip_spaces <* char ')'

Evaluator

这几个例子的求值器实现都好直接,以下是我比较喜欢的几个函数。

好吧。真的没有。太直接了。

1
2
3
4
5
6
7
8
9
(define (eval exp)
  (cond [(number? exp) exp]
        [(list? exp)
         (match exp
           [(list a) (eval a)]
           [(list '* a b) (* (eval a) (eval b))]
           [(list '- a b) (- (eval a) (eval b))]
           [(list '/ a b) (/ (eval a) (eval b))]
           [(list '+ a b) (+ (eval a) (eval b))])]))