最近需要学习用 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))])]))
|