继续上次的内容,上次虽然parser已经提供了~|等功能类似BNF的功能,但是我们感觉还是不够多,因为缺少诸如+*等重要功能,以及一些方便的脚手架。

更改Results

首先,我们继续搭一些脚手架,考虑这样一个问题,对于一个String我们自然知道一个Parser的单位是Char但是对于其他格式呢?比如RWH里面要处理的图片格式,所以,抽象还是要进一步。不只有Input格式不一样,Input中的每一个Elem也可能不同。同时提供相应的函数方便处理。

1
2
3
4
5
6
7
8

trait SimpleResults {
type Input
type Elem
def first(in: Input): Elem

def rest(in: Input): Input
...
}
1
2
3
4
5
6
7
8
9
10
trait StringParsers extends SimpleParsers {
type Input = String
type Elem = Char
private val EOI = 0.toChar

def first(in: Input): Elem = if(in == "") EOI else in(0)
def rest(in: Input): Input = if(in == "") in else in.substring(1)

def eoi = EOI
}

现在trait中加入声明,然后在StringParsers里面实现,增加了Elem的声明,利用firstrest函数提供取类似ListHeadTail的功能。

进一步,我们的accept是直接实现的,并不是依靠Parser Combinator,里面出现了一些针对Success以及Failure的操作,我们希望这种代码只在Result里面出现,而Parser中只有对其高阶函数的调用,隐藏处理细节。那该用哪种高阶函数处理这个问题呢?就是filter,我们放弃直接在生成Parser时得到真正的Parser的思路,改为先获取一个永远返回SuccessParser,然后利用filter,决定是不是成功。

1
2
3
4
5
6
7
8
9
10
11
// 永远返回Success的Parser
def consumeFirst: Parser[Elem] = Parser { in =>
Success(first(in), rest(in))(Failure("unknown failure", in))
}

// 利用filter
def acceptIf(p: Elem => Boolean): Parser[Elem] = consumeFirst filter p

// 重新完成accept
implicit def accept(e: Elem): Parser[Elem] =
acceptIf(_ == e).expected(e.toString)

更多的脚手架

我们来继续添加更多的,怎么加呢?来设想一下具体的应用场景,,我们对一些token关心的是值比如数字,对另一些token关心的是操作是+,那么我们需要一个能对Parser出来结果进一步操作的函数,就是map。还有一些字符可能只是格式要求,我们什么也不关心,比如空格。

1
2
3
4
5
6
7
8
// 只关心后面一个的内容
def ~> [U](p: ⇒ Parser[U]): Parser[U] = for(a <- this; b <- p) yield b

// 只关心前面一个的内容
def <~ [U](p: ⇒ Parser[U]): Parser[T] = for(a <- this; b <- p) yield a

// map
def ^^ [U](f: TU): Parser[U] = map(f)

由于在Results中,定义了足够的combinators,在parser中实现的时候就会变得十分简单,然后再向上封装库的时候也会更简单。

Error Reporting

先说好,这个Error Reporting的能力是有点差,不支持traceback什么的,看看就好。

有一些情况下,出现不匹配就不用替换了,可以直接报错。比如你要求两个东西一定是连起来出现了,但是只出现了第一个,A => BC | ED,在发现C不匹配的时候就可以直接报错了,避免回溯太远的距离。为了支持错误,首先要添加一个新的Error类型。由于我们之前依靠append函数来实现alternative的功能。那么现在Error就在出现一个在错误时不添加下一个,另外,还需要一个不论什么情况都直接出错的方法。

先在Result里面添加声明

1
2
3
4
5
6
7
8
9
10
11
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]
def filter(f: T => Boolean): Result[T] = this
def explain(ei: String): Result[T]
// 不论怎么样,都出错
def mkError(ei: String): Result[T] = Error(ei, next)
}

然后,添加新的Error

1
2
3
4
5
6
7
8
case class Error(msg: String, next: Input) extends Result[Nothing] {
def map[U](f: Nothing => U) = this
def append[U](alt: => Result[U]) = this
def flatMapWithNext[U](f: Nothing => Input => Result[U]) = this
def flatMap[U](f: Nothing => Result[U]): Result[U] = this
override def filter(f: Nothing => Boolean): Result[Nothing] = this
def explain(ei: String) = Error(ei, next)
}

为了给Parser提供相应的功能,还需要在Parser里面添加具体的函数。

1
2
3
4
5
def dontBacktrack: Parser[T] = Parser { in =>
this(in) mkError "Error"
}
def ~! [U](p: => Parser[U]): Parser[(T, U)]
= (dontBacktrack ~ p) dontBacktrack

一大波脚手架袭来

把这些搞定之后,终于要补充提到的功能了,对重复能力的实现,只能这样才能实现像正则里面+这种功能。

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
trait MoreCombinators extends SimpleParsers {

// 提供一个永远返回成功的Parser
def success[T](v: T): Parser[T]
= Parser { in => Success(v, in)(Failure("unknown failure", in))}

// 处理但不会失败,方便进行连接
def opt[T](p: => Parser[T]): Parser[Option[T]]
= (p ^^ {x: T => Some(x)}) | success(None)

// 重复,可以是0个
def rep[T](p: => Parser[T]): Parser[List[T]]
= rep1(p) | success(List())

// 至少一个
def rep1[T](p: => Parser[T]): Parser[List[T]]
= rep1(p, p)

def rep1[T](first: => Parser[T], other: => Parser[T]): Parser[List[T]]
= first ~ rep(other) ^^ mkList

// 重复序列
def repsep[T, S](p: => Parser[T], q: => Parser[S]): Parser[List[T]]
= rep1seq(p, q) | success(List())

// 重复序列至少一
def rep1seq[T, S](p: Parser[T], q: Parser[S]): Parser[List[T]]
= rep1seq(p, p, q)

def rep1seq[T, S](p: Parser[T], p1: Parser[T], q: Parser[S]): Parser[scala.List[T]]
= p ~ rep(q ~> p) ^^ mkList

def chainl1[T](p: Parser[T], q: => Parser[(T, T) => T]): Parser[T]
= chainl1(p, p, q)

def chainl1[T, U](first: Parser[T], p: Parser[U], q: Parser[(T, U) => T]): Parser[T]
= first ~ rep(q ~ p) ^^ {
case (x, xs) => xs.foldLeft(x) {(_, _) match { case (a, (f, b)) => f(a, b) }}
}

// 序列的隐式转换
implicit def acceptSeq[ES](es: ES)
(implicit ev1: ES => Iterable[Elem]): Parser[List[Elem]] = {
def acceptRec(pxs: Parser[List[Elem]], x: Elem) =
(accept(x) ~ pxs) ^^ mkList
es.foldRight[Parser[List[Elem]]](success(Nil))((x, y) => acceptRec(y, x))
}

private def mkList[T] = (y: (T, List[T])) => y match {
case (x, xs) => x::xs
}
}

利用现有的库

现在,虽然已经有了足够的能力,但是有一些时候直接写还是很麻烦,比如单个数字的Parser,就得写成

1
val digit: Parser[Char] = '0' or '1' or '2' or '3' or '4' ...

这种样子,显然很麻烦,如果可以直接使用正则就好了。这里就添加一个可以使用正则的Parser就好了,

1
2
3
4
5
6
7
8
implicit def regex(r: Regex): Parser[String] = Parser { in =>
val msg = "expect regex " + r
r.findPrefixOf(in) match {
case None => Failure(msg, in)
case Some(m) =>
Success(m, in.substring(m.length))(Failure("unknown error", in))
}
}

这样就可以直接利用正则模块来实现Parser了。

最后一个例子

最后给出一个简单的例子,利用这个Parser来做运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object ArithmericParsers extends MoreStringParsers with MoreCombinators { self =>

def number = chainl1("[1-9]".r, "[0-9]+".r,
empty ^^ { _ => (x:String, y:String) => x + y})

def double = (number ~ '.' ~ number) ^^ {
case ((x, y), z) => x + y.toString + z
} | number

def plus = '+' ^^ {_ => (x: Double, z: Double) => x + z}
def mins = '-' ^^ {_ => (x: Double, z: Double) => x - z}
def prod = '*' ^^ {_ => (x: Double, z: Double) => x * z}
def div = '/' ^^ {_ => (x: Double, z: Double) => x / z}

def expr = chainl1(term, plus or mins)
def term = chainl1(factor, prod or div)
def factor: Parser[Double] = '(' ~> expr <~ ')' or double ^^ {_.toDouble}

def main(args: Array[String]) = println(expr("13*12.5+4"))
}

利用已经定义的chain等函数,关键在中间BNF的定义上。他应该等价于

E => T + T | T - T

T => F / F | F * F

F = ( E ) | number

大概是这个意思。

可以看出两者的形式差别并不大。这可以看做一个EBNF的DSL,而且容易扩展。Scala自身的parsering库也并不难,可以看看源码。




X