最近需要學習用 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 裡面沒有那種用一根線把真正有用的部分串起來返回，或者直接返回 None，Err(_) 之類的操作（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))])]))
|