swift-纯函数式的解释器设计学习总结

前言

我在知道函数式编程之后,就对这种编程范式相当着迷。但函数式编程的学习曲线比较陡峭,加自己有非骨骼惊奇之辈只能一直在此死磕。最近看了一个《纯函数式的解释器设计》感触很深,于是我把视频看了2~3遍(资质有限只能死磕)。写下了这篇总结,也希望这篇总结对和我一样对函数编程感兴趣的同学在学习函数编程上有一定的帮助。

解释器组成

  • AST(Abstract Syntax Tree)
  • Frontend
  • Backend

解析器

AST

  • 表达式
  • 命令
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
indirect enum Exp{
case Constant (Int) // 常量
case Var (String) // 变量
case Add (Exp,Exp) // 加法
case Times (Exp,Exp) // 乘法
case Equal (Exp,Exp) // 等于
case Greater (Exp,Exp) // 大于
case Less (Exp,Exp) // 小于
var pConstant : Int {
switch self{
case let .Constant(x):
return x
default:
return 0
}
}
}
indirect enum Com{
case Assign (String,Exp) // 赋值
case Seq (Com,Com) // 结果
case Cond (Exp,Com,Com) // if 语句
case While (Exp,Com) // 循环
case Print (Exp) // 打印
}

这里就是一个简单的解析器的AST的定义。

Frontend

定义Parser

什么是Frontend?其实Frontend就是Parser。

什么是Parser?

String -> AST

将字符串转换成AST 就是
Parser。但是我们有可能Parser出一个AST后还有字符串没有Parser。所以我们需要把Parser定义成:

String -> (AST, String)

这样我们就可以继续Parser后面的字符串了。在我们的Parser不一定直接Parser出AST,我们也可以Parser个Int或者其他,所以我们需要定义成:

String -> (a, String)

我们使用一个泛型变量a,来表示任意类型,Int, Character, String, AST, etc。

为了方便我们在Parser失败后,能尝试Parser其他的类型,例如我们Parser个Int,失败后我们可以尝试Parser个String。因此我们最终需要这样定义一个Parser:

String -> [(a, String)]

1
2
3
struct Parser<a>{
let p : String -> [(a,String)]
}

这就是我们代码定义的一个Parser的结构,p 就是一个Parser(输入String,输出[(a, String)], a可以是Int,AST等任意类型)。其实我们, 整个Parser就是一个函数。

基本元素

mzero

这个函数很简单, 返回一个空的Parser

1
2
3
func mzero<a>()->Parser<a>{
return Parser { xs in [] }
}

pure

完成把一个普通元素wrap进一个compulational context 的操作。

1
2
3
func pure<a>(item : a) -> Parser<a>{
return Parser { cs in [(item,cs)] }
}

或许这样解释不是太好理解,我们还是写个测试代码看看分析一下吧。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func pure<a>(item : a) -> Parser<a>{
// puretest.p("Hello, World!"), 因此cs = "Hello, World!"
return Parser { cs in [(item,cs)] }
// 最后这个Parser<a>,就是一个返回[("1", "Hello, World!")] 的函数
}
// 输入"1", item = "1", let puretest = pure("1")
let puretest = pure("1")
// 这里的p,就是 Parser { cs in [(item, cs)] }
print(puretest.p("Hello, World!"))
/*
输出结果:
[("1", "Hello, World!")]
*/

satisfy

这个函数入参是个闭包,这个闭包入参是个Character,返回Bool。同时这个函数本身会返回一个Parser。

我们分析一下这个函数都做了些什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 输入一个condition (这是个闭包), 输入一个Parser<Character>
func satisfy(condition : Character -> Bool) -> Parser<Character>{
// 返回一个Parser<Character>
return Parser { x in // x 是个String,
回想一下Parser的定义,所有Parser的入参都是String
// 成功或者x的首字母,并且闭包condition true,则继续执行,否返回空数组。
guard let head = x.characters.first where condition(head) else{
return []
}
// 返回一个[(首字母, 删除首字母后String)]
return [(head,String(x.characters.dropFirst()))]
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
let satisfytest = satisfy { (c) -> Bool in
return c == "H" // 如果c 等于 H,返回true
}
//输出结果:[("H", "ello, World!")]
print(satisfytest.p("Hello, World!"))
//输出结果:[]
//由于首字母不为"H"所以返回空
print(satisfytest.p("Say Hello, World!"))

parserChar

其实这个函数,就是完成我们刚才satisfy 示例的功能。只是satisfy
比更加灵活点,parserChar 接受的只是个Character。

我们还是分析一下这个函数吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 输入一个Character,输出一个Character
func parserChar(c : Character) -> Parser<Character>{
// 返回一个Parser<Character>
return Parser { x in
// 如果首字母等于c 则继续执行,否则返回空数组
guard let head = x.characters.first where head == c else{
return []
}
// 返回一个[(首字母, 删除首字母后String)]
return [(c,String(x.characters.dropFirst()))]
}
}

定义组合规则

>>=

我们定义的这个运算符,在函数式编程中叫bind,实现了串联的功能。

我们先来分析一下这个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
infix operator >>= {associativity left precedence 150}
// 它有两个泛型参数 a,b
// 两个入参一个是 Parser<a> ,另一个是个将a转换为Parser<b>的闭包
// 函数返回值试过 Parser<b>
func >>= <a,b>(p : Parser<a>, f : a->Parser<b>) -> Parser<b>{
// 返回一个Parser<b>
return Parser { cs in
// parse 是用来 Parser p的。稍后我们在分析一下这个函数。我们知道p1是p Parser出来的结果就ok了
let p1 = parse(p, input: cs)
// parser 失败则返回,空数组
guard p1.count>0 else{
return []
}
// 取出p1 Parser出来的结果
let p = p1[0]
// f 是 a->Parser<b>
// 也就是说,我们把p Parser 出来的结果,传给f
// f 返回个 Parser<b>, 我们再用Parser<b>去尝试Parser出一个新的结果 p2
let p2 = parse(f(p.0), input: p.1)
// 如果Parser 失败,则返回空数组
guard p2.count > 0 else{
return []
}
// 成功则返回f Parser出来的结果。
return p2
}
}

了解 >>= 我们在看看 >>= 中使用到的 parse

1
2
3
4
5
6
7
8
9
10
11
12
// 函数入参一个Parser, 另一个是string
func parse<a>(parser : Parser<a> , input: String) -> [(a,String)]{
var result :[(a,String)] = []
// 使用parser 去 Parser inpuA, 成功则将结果存放在数组中
for (x,s) in parser.p(input){
result.append((x,s))
}
// 返回Parser 出来的结果
return result
}

到这来我们就可以这样理解 >>=

>>= 输入Parser<a>一个函数,得到一个Parser<b>
而这个Parser<b> 的结果是,Parser<a>,Parser出来的结果a,然后将a喂给一个函数,这个函数返回一个Parser。然后使用这个Parser继续 Parser。如果两次Parser都成功则返回Parser的结果,否则返回失败。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 这里我希望Parser 一个"H" 后继续 Parser 一个 "e"
let test = parserChar("H") >>= { _ in
return parserChar("e")
}
// Parser成功,输出:[("e", "llo, World!")]
print(test.p("Hello, World!")),
// Parser "H"时,失败,输出:[]
print(test.p("Say Hello, World!"))
// Parser "e"时,失败,输出:[]
print(test.p("H,ello, World!"))

+++

刚刚我们定义的>>= 相当于是的 &&,也就是说>>=只有在两个Parser
都Parser成功才能返回结果。而我们现在定义的+++就是个
||,+++输入两个Parser,第一个Parser
Parser成功则返回第一个Parser的结果,否则则返回第二个Parser的结果。

好我们来分析一下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
infix operator +++ {associativity left precedence 130}
// 这个函数有两个参数,一个左值Parser,一个右值Parser;输出一个Parser
func +++ <a>(l : Parser<a>, r:Parser<a>) -> Parser<a> {
// 这里函数直接返回一个Parser,我们接着看这个Parser做了些什么
return Parser { x in
// 尝试去Parser 左值
let result = l.p(x)
if result.count > 0{
// 左值Parser成功则返回左值结果
return result
}else{
// 左值Parser失败,返回右值结果
// 这里如果左右值都失败,会返回[]
return r.p(x)
}
}
}

这个操作符很简单。也很容易理解,我们通过实例代码来看看整个结果吧。

测试代码

1
2
3
4
5
6
7
8
9
10
11
// 这里我先尝试Parser 一个 "S",如果"S" Parser失败则去Parser "H"
let test = parserChar("S") +++ parserChar("H")
// "S" Parser失败,"H" Parser成功。输出结果:[("H", "ello, World!")]
print(test.p("Hello, World!"))
// "S" Parser成功,输出结果:[("S", "ay Hello, World!")]
print(test.p("Say Hello, World!"))
// "S"和"H"都Parser失败。输出结果:[]
print(test.p("hello, World!"))

many, many1

many 运算符,会尝试把同一个 parser 运行多次,直到失败。然后把每次运行的结果放在数组中返回(返回的仍然是 Parser 类型,只是参数为[a])。many1 是 many 的变体,代表至少需要成功一次。

这需要怎么理解呢?我们先看代码。

在看代码之前我们先复习一下之前定义的几个函数

  • pure 输入一个item,返回一个Parser;这个Parser的返回结果是[(item, cs)],
    cs是Parser的入参
  • >>= 输入一个Parser和一个函数,返回一个新的Parser。这个Parser就是把左值Parser
    Parser成功将结果传给右值函数,右函数继续Parser,Parser成功结果回传处理
  • +++ 输入两个Parser,左值Parser解析失败,则返回右值Parser得结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// many 输入一个Parser;输出一个Parser,结果是个a类型的数组。
func many<a>(p: Parser<a>) -> Parser<[a]>{
// 这里调用many1
// 如果many1返回的Parser,能够Parser成功则返回,这个Parser<[a]>
// 否则返回一个空数组的Parser
// 也就是说不管成功还是失败,返回的Parser必然能Parser成功
// 返回pure([]),Parser的结果结果是[[], String],
return many1(p) +++ pure([])
}
// many1和many一样输入一个Parser;输出一个Parser,结果是个a类型的数组。
func many1<a>(p : Parser<a>) -> Parser<[a]>{
// 这里返回的一个Parser
// 这里使用了 >>=, 我们回想一下 >>= 的实现。
// >>= 是把左值Parser得结果喂给右值Parser
// 也就是说这里是的x,是左值Parser的结果
return p >>= { x in
// 这里调用了many,刚才说了,many无论如何都能Perser成功,所以这里必然能把值传个xs
many(p) >>= { xs in
这里则把结果返回wrap到Perser中,然后返回。
pure([x] + xs)
}
}
}

看到这里大家或许有点蒙圈。。。没关系我们在通过测试代码进一步分析。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 这个函数用于判断字符是否是数字,是数字则返回true
func isNum(c: Character) -> Bool {
let s = String(c)
return Int(s) != nil
}
// test1 获取many 返回的Parser
let test1 = many(satisfy({ (c) -> Bool in
return isNum(c)
}))
// test2 获取many1 返回的Parser
let test2 = many1(satisfy({ (c) -> Bool in
return isNum(c)
}))
// 输入"123" many 都能Parser成功,输出结果:[(["1", "2", "3"], "")]
print(test1.p("123"))
// 输入"123a" many Parser到"a" 发现Parser失败,所以输出结果:[(["1", "2", "3"], "a")]
print(test1.p("123a"))
// 输入" 123" many Parser到" " 就失败了,输出结果:[([], " 123")]
print(test1.p(" 123"))
// 输入"123" many1 都能Parser成功,输出结果:[(["1", "2", "3"], "")]
print(test2.p("123"))
// 输入"123a" many1 Parser到 "a" 就失败了,输出结果:[(["1", "2", "3"], "a")]
print(test1.p("123a"))
// 输入" 123" many1 Parser到 " " 就失败了,输出结果:[]
print(test2.p(" 123"))

从测试代码输出结果可以看出来,many不论成功失败都能返回结果,我们可以拿这个结果继续Parser,而many1失败则直接返回[]结果。

相信大家看到这里会有点感觉,我们在分析many和many1的时候发现这个函数是相互嵌套的,接下了我们结合测试代码来分析一下我们调用many和many1我们的代码是怎么运行的。

我们再来分析下print(test1.p("123"))的执行逻辑吧

  • test1 调用 p 进行解析。
  • p 其实是调用了many,many 的入参是 执行satisfy返回的Parser
  • satisfy 返回的Parser,如果string中第一个字母是数字则,返回[(首字母, 删除首字母的字符串)], 如果首字母不为数字则返回[]
  • many 接收了一个这样的Parser, 将这个Parser p传给many1, 如果p 能解析成功就返回many1 返回的 Parser, 解析时间就返回Parser []
  • many1 如果p 能解析成功就返回个下面的一个,这里many1和many是互为递归的关系。也就是many(p)返回的也是这样的一个Parser,这样就相当于把p和{ xs in pure([x] + xs)}串联起来了,直到p Parser失败。
1
2
3
many(p) >>= { xs in
pure([x] + xs)
}

看到这里相信大家对many和many1理解上应该有的感觉了吧。

定义高级组合子

string

这个函数用于解析一个字符串。是的,我们现在可以用我们之前定义的基本元素去解析字符串了。

直接看代码实现吧!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func string(str : String) -> Parser<String> {
// 如果解析的str为空则返回空的Parser
guard str != "" else {
return pure("")
}
// 取得第一个字符
let head = str.characters.first!
// 返回一个不断Parser字符,直达Parser失败的Parser
return parserChar(head) >>= { c in
// 这里递归调用string
string(String(str.characters.dropFirst())) >>= { cs in
let result = [c] + cs.characters
return pure(String(result))
}
}
}

解析一个字符串就是如此的简单#^_^#

space

这个是很有意思的函数,吃掉空格的Parser。

我们通过代码来看看它是如何实现吃掉空格的吧。

1
2
3
4
5
6
7
8
func space()->Parser<String> {
// 这里用到了many,many是返回一个Parser,这个Parser会尝试0-n次的Parser,直达失败。
// satisfy(isSpace)表示,如果是空格则Parser成功。
// 如果空格Parser 成功,则返回一个空的Parser,实现吃掉空格
return many(satisfy(isSpace)) >>= { x in pure("") }
}

so easy!!

number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// isDigit这个方法用于判断一个字符是否是数字
func isDigit(c : Character) -> Bool {
let s = String(c)
return Int(s) != nil
}
// digit 这个方法判断如果该字符是数字则返回一个wrap一个常量的闭包。
func digit() -> Parser<Exp> {
return satisfy(isDigit) >>= { x in
pure(Exp.Constant(Int(String(x))!))
}
}
// 这个函数返回一个解析数字的Parser
func number() -> Parser<Exp> {
// 尝试解析一个数字,如果解析失败返回空。解析成功则返回一个闭包
return many1(digit()) >>= { cs in
// 这是解析成功返回的闭包
// 这个闭包会去吃掉空格,这里吃空格必然会成功的。
space() >>= { _ in
// 然后将many1(digit())解析出来的结果cs,通过reduce函数进行累加。many1 解析结果是个数组
let sum = cs.reduce(Exp.Constant(0), combine: { (exp1, exp2 ) -> Exp in
// 这里将数组的元素拼接成一个完整的数字。如解析123,返回的结果数组应该是[1, 2, 3],
// 则 0 * 10 + 1, 1
// 1 * 10 + 2, 12
// 12 * 10 + 3, 123
// sum 的结果是123
return Exp.Constant((exp1.pConstant * 10 + exp2.pConstant))
})
// 这里返回123
return pure(sum)
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
let test = number()
// 输出结果:[]
print(test.p(" 123"))
// 输出结果:[]
print(test.p("a123"))
// 输出结果:[(ParserCombinator.Exp.Constant(123), "")]
print(test.p("123"))

symbol

这个函数用于解析一个symbol。我们通过代码可以看出来这个函数是在string基础上,组合了吃空格的Parser

1
2
3
4
5
6
7
8
9
10
11
12
13
// 解析symbol 返回一个 String 的Parser
func symbol(sym : String) -> Parser<String>{
// 尝试解析一个字符串, 解析成功则返回一个闭包
return string(sym) >>= { sym in
// 先吃掉空格,然后weap 一个字符串
space() >>= { _ in
pure(sym)
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
// 这里我要解析一个+号
let test = symbol("+")
// 输出结果:[]
print(test.p(" +"))
// 输出结果:[]
print(test.p("123"))
// 输出结果:[("+", "")]
print(test.p("+"))

identifier

这个函数用于解析一个标识符。标识符一般是首字符是字母,后面部分是数字和字母组成的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 这个函数很简单,用于判断字符是否是字母
func isAlpha(c : Character) -> Bool{
if c >= "a" && c <= "z" || c >= "A" && c <= "Z"{
return true
}else{
return false
}
}
// 函数返回一个解析标识符的闭包
func identifier() -> Parser<String>{
// 如果首字母是字符则将结果传递给下个函数去解析
return satisfy(isAlpha) >>= { c in
// 不断的解析字母或数字,解析成功则将结果传个下一个函数
many(satisfy({ (c) -> Bool in isAlpha(c) || isDigit(c) })) >>= { cs in
// 吃掉空格,将所有结果拼接成一个String wrap起来
space() >>= { _ in
pure(String([c] + cs))
}
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let test = identifier()
// 输出结果:[]
print(test.p("123"))
// 输出结果: []
print(test.p(" 123"))
// 输出结果: []
print(test.p("_123"))
// 输出结果: [("aa123", "")]
print(test.p("aa123"))
// 输出结果: [("abc", "")]
print(test.p("abc"))

variables

解析一个变量。解析变量其实在identifier 的基础上,结合我们之前定义的AST
来表示一个变量就可以了。

1
2
3
4
5
6
7
8
func variables() -> Parser<Exp>{
// 解析标识符成功,则将标识符wrap 起来
return identifier() >>= { name in
pure(Exp.Var(name))
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let test = variables()
// 输出结果:[]
print(test.p("123"))
// 输出结果:[]
print(test.p(" 123"))
// 输出结果:[]
print(test.p("_123"))
// 输出结果:[(ParserCombinator.Exp.Var("aa123"), "")]
print(test.p("aa123"))
// 输出结果:[(ParserCombinator.Exp.Var("abc"), "")]
print(test.p("abc"))

处理表达式

文法

1
2
3
4
5
6
7
8
9
expr : expr '+' term
| expr '-' term
| term
term : term '*' factor
| term '/' factor
| factor
factor : NUMBER
| '(' expr ')'

这里表示是一个简单的表达式的组成部分。

  1. expr, 以下3种情况都可以组成一个expr

    • expr + term
    • expr - term
    • term
  2. term, 以下3种情况可以组成一个term

    • term * factor
    • term / factor
    • factor
  3. factor,以下3种情况可以组成一个factor

    • NUMBER
    • ‘(‘ expr ‘)’

分成这三大部分其实主要是要处理运算符优先级的问题,首先factor运算符的优先级是最高的。也就是说括号括起来的表达式和数字运算符的优先级是最高的。之后的优先级就是乘和除,所以我们的term就是和factor的乘除组成。最后的优先级就是加和减。到这时候我们的通过factor已经形成了一个个的expr和term了,这时我们就可以用简单的加减来计算表达式了。

factor

这个函数用于解析一个factor。

1
2
3
4
5
6
7
8
9
10
11
12
13
func factor()->Parser<Exp>{
// 如果解析到一个变量或者是数字 或者是括号括起来的表达式则将解析结果返回。
// 这里如果到'(' 或就解析 expr ,expr 解析成功后就继续解析),都解析成功了就将表达是结果wrap 起来返回。
return variables() +++ number() +++ (symbol("(") >>= { c in
expr() >>= { n in
symbol(")") >>= { _ in
pure(n)
}
}
})
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let test = factor()
// 输出结果:[(ParserCombinator.Exp.Constant(1123), "abc")]
print(test.p("1123abc"))
// 输出结果:[]
print(test.p("("))
// 输出结果:[]
print(test.p(")"))
// 输出结果:[]
print(test.p("()"))
// 输出结果:[(ParserCombinator.Exp.Constant(1), "")]
print(test.p("(1)"))
// 输出结果:[(ParserCombinator.Exp.Add(ParserCombinator.Exp.Constant(1), ParserCombinator.Exp.Constant(2)), "")]
print(test.p("(1 + 2)"))
// 输出结果:[(ParserCombinator.Exp.Constant(123), "")]
print(test.p("123"))
// 输出结果:[(ParserCombinator.Exp.Var("adf"), "")]
print(test.p("adf"))")"))

addop

这个函数用于解析一个加法运算符,解析成功返回一个加法运算的Parser

1
2
3
4
5
6
7
8
9
10
11
12
func addop() -> Parser<(Exp,Exp)->Exp>{
// Parser '+' ,成功则wrap 一个加法运算
return symbol("+") >>= { _ in
// 输入两个参数 返回一个Exp.Add
pure({(x,y) -> Exp in
Exp.Add(x, y)
})
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
let test = addop()
// 输出结果:[]
print(test.p("1"))
// 输出结果:[]
print(test.p("a"))
// 输出结果:Add(ParserCombinator.Exp.Constant(1), ParserCombinator.Exp.Constant(2))
// 这里成功解析出加号
print(test.p("+")[0].0(Exp.Constant(1),Exp.Constant(2)))

mulop

这个函数用于解析一个乘法运算符,解析成功返回一个乘法运算的Parser

代码实际其实和加法的基本一致。

1
2
3
4
5
6
7
8
9
10
11
12
func mulop() -> Parser<(Exp,Exp) -> Exp>{
// Parser '*', 成功则wrap 一个乘法运算
return symbol("*") >>= { _ in
// 输入两参数,返回一个Exp.Times
pure({ (x,y) -> Exp in
Exp.Times(x, y)
})
}
}

>=<, expr, term

>=< 是一个辅助函数,他能让我们更简单的去解析expr 和 term。

我们一起来看看 >=< 的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 自定义操作符
infix operator >=< {associativity left precedence 130}
// 这个操作符 左值接受一个参数Parser,右值接受一个方法,返回一个Parser
func >=<<a>(p : Parser<a>, op : Parser<(a,a) -> a>) -> Parser<a>{
// p Parser成功则 将x 传给rest
return p >>= { x in
// rest 接受3个参数 p,x,op
rest(p, x: x, op: op)
}
}
func rest<a>(p : Parser<a>, x : a, op : Parser<(a,a) -> a>) -> Parser<a> {
// 尝试去Parser op ,成功则把结果f,传给下一个闭包;失败则返回 x
return op >>= { f in
// 尝试去Parser p,成功则把结果 y,传给下个闭包
p >>= { y in
// 递归调用rest 传入p,op Parser出来的方法f计算出来的结果,op。
rest(p, x: f(x,y), op: op)
}
} +++ pure(x)
}
/**
接下来我们结合解析 expr和term, 看看 >=< 这个操作符。
**/
// 解析表达式
fun expr() -> Parser<Exp>{
/** 回顾一下我们刚才的文法
expr : expr '+' term
| expr '-' term
| term
这里先Parser出一个term,如果Parser 加法 失败则返回term的值。
如果Parser 加法成功则继续计算并Parser 加法。
这样我们就实现上述的文法。
**/
return term() >=< addop()
}
// 解析term
func term() -> Parser<Exp>{
/** 我们在看看之前定义的term的文法
term : term '*' factor
| term '/' factor
| factor
这里先Parser出一个factor,factor Parser成功,再去尝试Parser一个乘法
如果Parser乘法失败,则返回factor Parser的结果
如果Parser乘法成功,在尝试继续解析下一个factor,直达解析失败返回计算结果。
**/
return factor() >=< mulop()
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let test = expr()
// 输出结果:[(ParserCombinator.Exp.Var("aa"), "")];解析出一个变量
print(test.p("aa"))
// 输出结果:[(ParserCombinator.Exp.Constant(11), "")];解析出一个常量11
print(test.p("11"))
// 输出结果:[(ParserCombinator.Exp.Add(ParserCombinator.Exp.Constant(11), ParserCombinator.Exp.Constant(2)), "*")]; 解析出11+2,*解析不出来
print(test.p("11 + 2 *"))
// 输出结果:[(ParserCombinator.Exp.Add(ParserCombinator.Exp.Constant(11), ParserCombinator.Exp.Times(ParserCombinator.Exp.Constant(2), ParserCombinator.Exp.Constant(2))), "")];解析出 11+2*2
print(test.p("11 + 2 * 2"))
// 输出结果:[(ParserCombinator.Exp.Add(ParserCombinator.Exp.Var("aa"), ParserCombinator.Exp.Times(ParserCombinator.Exp.Constant(2), ParserCombinator.Exp.Constant(2))), "")];解析出 变量aa + 2 * 2
print(test.p("aa + 2 * 2"))

解析命令

assign

好了,我们现在开始解析赋值。有了之前的一个高阶函数的定义,解析赋值就变得异常的简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func assign() -> Parser<Com>{
// 先解析标识,因为赋值前面必然有标识
return identifier() >>= { name in
// 解析=符号
symbol("=") >>= { _ in
// 解析表达式
expr() >>= { exp in
// wrap 一个赋值AST
pure(Com.Assign(name, exp))
}
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
let test = assign()
// 输出结果:[]
print(test.p("a"))
// 输出结果:[]
print(test.p("11"))
// 输出结果:[(ParserCombinator.Com.Assign("a", ParserCombinator.Exp.Constant(1)), "")]
print(test.p("a = 1"))

print

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
解析print命令
func print() -> Parser<Com>{
// 尝试Parser print
return symbol("print") >>= { _ in
// Parser print 成功,再尝试Parser 表达式
expr() >>= { exp in
// 都Parser成功则,wrap print命令返回
pure(Com.Print(exp))
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let test = print()
// 输出结果:[]
print(test.p("1"))
// 输出结果:[]
print(test.p("2*2"))
// 输出结果:[]
print(test.p("1+2"))
// 输出结果:[(ParserCombinator.Com.Print(ParserCombinator.Exp.Constant(1)), "")]
print(test.p("print(1)"))
//
输出结果:[(ParserCombinator.Com.Print(ParserCombinator.Exp.Times(ParserCombinator.Exp.Constant(2), ParserCombinator.Exp.Constant(2))), "")]
print(test.p("print(2*2)"))
//
输出结果:[(ParserCombinator.Com.Print(ParserCombinator.Exp.Add(ParserCombinator.Exp.Constant(1), ParserCombinator.Exp.Constant(2))), "")]
print(test.p("print(1+2)"))

whileloop

接下我们来看看如果Parser一条循环语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func relop() -> Parser<(Exp,Exp) -> Exp>{
// 这里Parser "<"
return symbol("<") >>= { _ in
// 成功则将条件表达式(小于),给wrap起来
pure({(x,y) -> Exp in
Exp.Less(x, y)
})
}
}
func rexp() -> Parser<Exp>{
// Parser 一个表达式
// Parser成功,将结果作为左值传给 relop
// 然后在 relop 会尝试Parser "<"
// Parser 成功,则继续Parser右值
// 最终得出一个条件表达式,把他wrap起来
return expr() >=< relop()
}
func whileloop() -> Parser<Com>{
// Parser while 成功则继续
return symbol("while") >>= { _ in
// Parser 一个条件表达式
rexp() >>= { cond in
// 条件表达式Parser成功,则尝试Parser "{"
symbol("{") >>= { _ in
// "{" Parser成功,则尝试Parser一条或多条命令,com这个函数会在下面和大家一起分析
com() >>= { stmt in
// 命令 Parser成功,则最后尝试Parser "}"
symbol("}") >>= { _ in
// 全部Parser成功 则将循环语句wrap
pure(Com.While(cond, stmt))
}
}
}
}
}
}

是的,解析一个循环语句就是如此的简单。分析代码是大家或许能发现这代码存在一个bug。这代码只对”<”进行Parser了。其实条件表达式还有”==”和”>”这里并没有Parser。大家可以尝试去解决这个bug,验证自己的理解。

seq/com/com1

seq、com、com1需要放在一起看。

seq其实就像序列,用于表示我执行了一条命令后,接下来执行哪一条命令。所以我们可以看到在AST定义中seq是由2个Com组成。

com、com1都是用于解析命令的。为什么定义两个呢?这也是分享者在视频中提出的问题。

我们就带着这个问题一起分析一下代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func com() -> Parser<Com>{
// 尝试 Parser 一个序列, Parser 失败则返回一条命令
return seq() +++ com1()
}
func com1() -> Parser<Com>{
// 尝试 Parser 一条赋值语句,失败则 Parser 循环语句, 失败则 Parser 打印语句
return assign() +++ whileloop() +++ print()
}
func seq() -> Parser<Com>{
// 这里需要 Parser 一个序列,所以通过 com 和 seq 递归实现
// com1 的作用是 Parse 一条命令,Parser 命令的工作都由 com1 来完成,com1 成为整个递归的终结者
return com1() >>= { stmt in
// 程序跑的这里,说明我们可以成功 Parser 出一条命令了
// 那再去调用 com 进行 parser 命令,因为后面的有可能还有一序列命令
com() >>= { stmt2 in
// 这里就是 warp 一个 Seq
pure(Com.Seq(stmt, stmt2))
}
}
}

2016-8-28 更新
个人理解刷新: com 需要 Parser seq ,而 seq 也需要 Parser com ,所以这里形成一个需要调用。
那这个递归的终结就由 com1 来完成,com1 只完成单个命令的 Parser。 这样就不会导致循环调用的永无终止。(ps:本人递归没学好#^_^#)

感谢分享者(小莲老师)点出我这里的理解错误
注释已更新#^_^#

大神指点:
com和com1的区别主要是为了消除seq parser中的左递归。
试想如果seq的第一步不是com1,而是com,而com的第一条也是seq。这样这个循环调用就永远都无法终止

看到这里大家应该和我一样理解为什么需要2个com了吧。在分享者的代码中并没有Parser我们之前在AST定义的Cond的函数。如果大家感兴趣可以尝试去定义这个函数,校验自己的学习成果。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let c: String = " i = 0 print i sum = 0 while i<100 {sum=sum+i i=i+1 } print sum"
let ast = (space() >>= {_ in com()}).p(c)[0].0
// 输出结果:
// Seq(ParserCombinator.Com.Assign("i",
// ParserCombinator.Exp.Constant(0)),
// ParserCombinator.Com.Seq(ParserCombinator.Com.Print(ParserCombinator.Exp.Var("i")),
// ParserCombinator.Com.Seq(ParserCombinator.Com.Assign("sum",
// ParserCombinator.Exp.Constant(0)),
// ParserCombinator.Com.Seq(ParserCombinator.Com.While(ParserCombinator.Exp.Less(ParserCombinator.Exp.Var("i"),
// ParserCombinator.Exp.Constant(100)),
// ParserCombinator.Com.Seq(ParserCombinator.Com.Assign("sum",
// ParserCombinator.Exp.Add(ParserCombinator.Exp.Var("sum"),
// ParserCombinator.Exp.Var("i"))), ParserCombinator.Com.Assign("i",
// ParserCombinator.Exp.Add(ParserCombinator.Exp.Var("i"),
// ParserCombinator.Exp.Constant(1))))),
// ParserCombinator.Com.Print(ParserCombinator.Exp.Var("sum"))))))
print(ast)

Backend

好了,最复杂的AST解析我们已经完成了。接下我们就要执行我们解析出来的AST,得到最终的运行结果。

Backend 主要分成两部分:1.求表达式 2.执行命令

求表达式

eval

这个函数用于获得AST 表达式结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func eval(exp : Exp) -> Int{
switch exp {
// 如果是常量直接返回x
case let Exp.Constant(x):
return x
// 变量则获取变量对应的数值
// var varTable : [String:Int] = [:]
// func getvar(name : String) -> Int{
// return varTable[name]!
// }
// 我们通过varTable来存储变量和值之间的对应关系
case let Exp.Var(name):
return getvar(name)
// 加法运算是两个表达式直接相加,所以这里继续递归调用
case let Exp.Add(exp1, exp2):
return eval(exp1) + eval(exp2)
// 小于,两个表达式的结果进行比较,这里也需要递归调用
case let Exp.Less(exp1, exp2):
let a = eval(exp1)
let b = eval(exp2)
if a > b {
return 0
}else{
return 1
}
// 乘法,两个表达式的结果进行乘法运算
case let Exp.Times(exp1, exp2):
return eval(exp1) * eval(exp2)
default:
return 0
}
}

求表达式就是如此的简单#^_^#

这里一样有一些表达式没定义,大家可以尝试去定义自己想要的表达式。

执行命令

执行命令的处理和求表达式其实是大同小异的。我只需要interpreter函数就能完成这个操作。

interpreter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func interpreter(stmt : Com) {
// 我们需要一个辅助函数loopHelper帮助我们实行循环命令
func loopHelper(cond : Exp,st : Com){
// 如果表达式结果等于0 则退出
if eval(cond) == 0{
return
}else{
// 继续执行命令
interpreter(st)
// 继续循环执行
loopHelper(cond, st: st)
}
}
switch stmt {
// 赋值,将变量名存放到变量对应表中
case let Com.Assign(name, exp1):
varTable[name] = eval(exp1)
// 序列,一条一条的命令执行
case let Com.Seq(st1, st2):
interpreter(st1)
interpreter(st2)
// 循环,调用loopHelper实现循环执行
case let Com.While(cond, st1):
loopHelper(cond, st: st1)
// 打印,将表达式的结果打印出来
case let Com.Print(exp):
print(eval(exp))
default:
return
}
}

到这来我们就把解析器给完成了。虽然例子中有一些异常场景没有考虑。如解析失败的处理,变量名重复的处理。但这毕竟不是实现一个强大的功能库,只是个教学用的Dome。

现在我们就来验证一些我们的代码吧。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
// 我们要实现从1累加到100
let c: String = " i = 0 print i sum = 0 while i<100 {sum=sum+i i=i+1 } print sum"
// 我们先吃掉空格,然后执行解析命令,得到我们的AST
let ast = (space() >>= {_ in com()}).p(c)[0].0
// 一条条的执行AST 中的命令
// 输出结果:
// 0
// 5050
interpreter(ast)

@ο@) 哇~ 完美

总结

相信大家通过这个例子和我一样都感受到函数式编程的魅力了吧。例子中定义了大量的高级函数和辅助函数,然后通过这些函数的组合使用一个个复杂的功能。例子中定义的Parser和pure就是Monad的概念(ps:希望我没有理解错 呵呵),通过自定义操作符>>=实现了bind。

感谢视频分享者,让我在函数式编程的学习道路是又进一步。

相关资料

视频

keynote

代码