最近有写个Parser的需求,回想起《Real World Haskell》以及《Functional Programming in Scala》各种书里面其实都有这个内容。Parser Combinators也并不是函数式语言的特例,javaANTLR4也是composable的。不过这确实是个内部DSL-Domain Specific Language的好例子,简单的例子难度也不高。

Scala的语法本来也算是比较容易理解的,一些语法特性我也会介绍。不过,熟悉Haskell等语言的人可能会感觉Scala做这种事情,语法有些啰嗦了。整体文章是从这篇文章抄袭而来,为了保证完全跑起来改了一些东西。完整的代码在这里。关于Monadic Parser Combinators还可以看Erik Meijer的论文

什么是Parser

我们什么时候需要一个Parser,首先第一个编译器肯定是需要parser的,为了生成抽象语法树就需要Parser,然后对于一些和编译前端很像的任务也需要Parser,比如解析JSONXML或者一些奇奇怪怪的配置文件(这些其实可以看做外部DSL)。

首先是有个EBNF,然后按照他弄出来个Parser,而我们的目的就是简化这个过程。编译里面会教你推LL或者LR的表,然后每次查表就可以了,但是总不能每次都这样吧。

要实现一个Parser首先要看看他是干什么的。那么对于Parser的输入是什么?字符串?输出呢?任意类型?比如处理JSON就是输入一个json string然后返回一个json object,处理xml就是输入一个xml string返回一个xml object。这样我们就得到了现在认为的Parser类型,String => T。我这里使用这种方式表达类型,=>可以看做给前面类型的输入,然后返回后面类型的输出。String => T就是代表给String类型的输入,就返回一个T类型,当然这里T是用来当做泛型的参数。

不过这个结果明显不太对。先考虑输出,很明显,并不是每个输入都能被Parser成正确的结果,一个不对的输入返回什么呢?抛个异常?哦不!这可不行,不要忘了,我们的目的不止是一个Parser而是Parser Combinators。直接抛异常是不能够Combinator的。原因很简单,如果依靠异常来处理失败的情况,那么整个过程就很难流方便的组合起来了。

举个例子,编译里面常见的的EBNF还记得吧!A := B | C,(好吧!我不记得符号了,反正应该看得懂),这代表非终结符A可以展开为非终结符B或者C,如果Parser不对了就报异常,那么我们在parser B失败了换成C的操作难道在异常里面写嘛。

所以,返回值的类型要改。输入呢?更是要改啊,你看看就算是编译器里,也是先进行词法分析然后给Parser的吧,那输入是个元组的序列,像[(int, type),(a, identifier),(9, Number)]这种。

所以要改就彻底的改,改成Input => Result[T]类型,这下好了,输入类型不确定,输出类型可以辨识失败。

1
2
3
4
5
6
7
8
9
trait SimpleResults {
type Input
trait Result[+T] {

def next: Input
}
case class Success[+T](result: T, next: Input) extends Result[T]

case class Failure(msg: String, next: Input) extends Result[Nothing]
}

trait可以看做抽象类或者可以有具体内容的接口(这不是java8加进去的特性嘛),不过它还支持一种mixin。这不是我们关注的内容就不管了。type定义了一种类型不过这种类型,可以看做typedef但是这里只是声明了没有赋值,留给实现的时候赋值。case class可以先看做普通的class,不过在模式匹配的时候,会导出构造函数。泛型参数的+表示协变。

Result的含义很简单,给一个Input,然后Parser掉其中满足的一部分,成功的话就返回Parser的结果以及剩下的一部分,失败的话就给个原因(万一这个是最后一个parser,识别不出来要报错呢),以及接下来要parser的内容(想想之前那个A:= B | C的例子)。

这样就可以写出来第一个简单的Parser了。

1
2
3
4
5
6
7
object XParser extends SimpleResults {
type Input = String
val accept: Input => Result[Char] = { (in: String) =>
if (in.CharAt(0) == 'x') Success('x', in.substring(1))
else Failure("expect an x", in)
}
}

这个Parser只能用来parser一个x。不过马上就可以更复杂了。

来个简单的Parser

回到刚才的那个例子改一点,A := Bd | C,这下我们得到两个希望有的功能,即可以把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

trait SimpleParsers extends SimpleResults {
trait Parser[+T] extends (InputResult[T]) {
def apply(in: Input): Result[T]
def | [U >: T](p: ⇒ Parser[U]): Parser[U]
= new Parser[U]{ def apply(in: Input) =
Parser.this(in) match {
case Failure(_, _) ⇒ p(in)
case Success(x, n) ⇒ Success(x, n)
}
}

def ~ [U](p: ⇒ Parser[U]): Parser[([T, U])]
= new Parser[Pair[T, U]]{ def apply(in: Input) =
Parser.this(in) match {
case Success(x, next) ⇒ p(next) match {
case Success(x2, next2) ⇒ Success((x, x2), next2)
case Failure(m, n) ⇒ Failure(m, n)
}
case Failure(m, n) ⇒ Failure(m, n)
}
}
}
}

先解释一下语法,首先,Scala里面其实没有什么运算符重载的概念,大家都是一样的函数就是你用字母取名,我用符号取名而已,然后在|这个函数的参数是p: => Parser[U],这个含义是call by name,只有用到这个变量的时候才会计算。对于apply函数,可以看做一个语法糖。

1
2
3
4
5
6

object add {
def apply(a: Int, b: Int): Int = a + b
}

add(1,3)

即在用函数的方式调用object时,会隐式的调用其apply函数。而一个Parser其实就是一个函数类型为Input => Result[T],在apply函数中实现。match是模式匹配,在HaskellOCaml里面都有,据说C#也要加。之前也提过case class就是为了pattern matching提供方便的。

这里的逻辑比较简单,无非就是前面匹配对了,就直接返回,不对继续下一个。不过这个抽象类太抽象了。来个具体的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
trait StringParsers extend SimpleParsers {
type Input = String
private val EOI = 0.toChar

def accept(expect: Char) = new Parser[Char] {
def apply(in: String) =
if (in = "") {
if (expected = EOI)
Success(expected, "")
else
Failure("no more input", in);
} else if (in.charAt(0) == expected)
Success(expected, in.substring(1))
else
Failure("expected \'" + expected + "\'")
}
implicit def accept(e: Char): Parser[Char] = accept(e)

def eoi = accept(EOI)
}

然后具体写一个parser

1
2
3
4
5

object OXOParser extends StringParsers {
def oxo = 'o' ~ 'x' ~ 'o'
def oxos = (oxo ~ ' ' ~ oxo) | oxo
}

这里利用accept来实现隐式类型转换,这个也算是scala实现DSL的重要功能之一了,在对象OXOParser里面,虽然Char类型的o没有函数~但是,通过搜索隐式类型转换找了Char => Parser[Char]类型的函数,所以写的时候就可以直接用了。这样是不是写起来就简单多了,而且~|弄得和EBNF逐渐接近。这种设计api的方式就可以叫做实现DSL

改进一点代码

不过到这里,还有一点问题。Parser里面有太多显示的match,不好看,也不方便扩展,为了解决这个问题,我们需要Result里面提供更多的高阶函数。到底需要哪些高阶函数呢?首先需要一个能把两个不同的Result组合的功能,比如,在|中,我们希望把两个结果组合起来,哪个能用就用哪个的结果。而且,两个Result的泛型参数还不一定是一个类型的。

1
def append[U >: T](alt: => Result[U]) = ???

这里[u >: T]是为了保证U是T的子类。为了满足协变。

还需要一个可以两个Parser的结果连接起来的功能。所以Result里面也要有相应的支持,即对于前一个结果以及剩下的内容,可以处理完,然后把连起来的结果返回出来。

1
def flatMapWithNext[U](f: T => Input => Result[U]) = ???

另外,如果Parser希望对已经Parser出来的结果进行处理的话,还需要一个可以把Parser结果打开处理完,然后包回去的函数即map。

1
def map[U](f: U => T): Result[U]

具体实现挺简单的

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

trait SimpleResults {
type Input

trait Result[+T] {
def next: Input
def map[U](f: T => U): Result[U]
def flatMapWithNext[U](f: T => Input => Result[U]): Result[U]
def append[U >: T](alt: => Result[U]): Result[U]
def flatMap[U](f: T => Result[U]): Result[U]
}

case class Success[+T](result: T, next: Input) extends Result[T] {
def map[U](f: T => U) = Success(f(result), next)
def flatMapWithNext[U](f: T => Input => Result[U]) = f(result)(next)
def append[U >: T](alt: => Result[U]) = this
def flatMap[U](f: T => Result[U]): Result[U] = f(result)
}

case class Failure(msg: String, next: Input) extends Result[Nothing] {
def map[U](f: Nothing => U) = this
def flatMapWithNext[U](f: Nothing => Input => Result[U]) = this
def append[U](alt: => Result[U]) = alt
def flatMap[U](f: Nothing => Result[U]): Result[U] = this
}

}

然后修在Parser里面的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def Parser[T](f: Input => Result[T]) = 
new Parser[T]{ def apply(in: Input) = f(in) }

def flatMap[U](f: T => Parser[U]): Parser[U]
= Parser { in => Parser.this(in).flatMapWithNext(f)}

def map[U](f: T => U): Parser[U] = Parser {
in => Parser.this(in).map(f)
}

def | [U >: T](p: => Parser[U]): Parser[U] = Parser {
in => Parser.this(in).append(p(in))
}

def ~ [U](p: => Parser[U]): Parser[(T, U)] = for {
x <- this
y <- p
} yield (x, y)

这里的for也是个语法糖,对于

1
2
3
4
5
for {
x <- a
y <- b
z <- c
} yield(x + y + z)

可以看成

1
a.flatMap(x => b.flatMap(y => c.map(z => (x + y + z))))

先使用Parser函数,简化了构件Parser的语法,然后使用高阶函数,又是代码简洁了不少。

现在,parser其实已经有一定的描述能力了,但是还是有一些重要的功能没有,比如正则里面的a+b对于这样的重复不能处理,这些功能,下一篇里面在考虑。




X