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))])]))