Scala学习笔记 之 Combinator Parsing

Scala在scala.util.parsing.combinator中提供了强大的自定义解析功能,被称作combinator parsing(额,实在不造如何翻译),今天就来简单的探索一下。

这个功能被Scala划分的额外的模块中,所以要引用该模块需要添加额外的依赖,如下:

1
2
3
4
5
<dependency>
<groupId>org.scala-lang.modules</groupId>
<artifactId>scala-parser-combinators_2.11</artifactId>
<version>1.0.4</version>
</dependency>

这里给出一个简单的算数表达式的解析作为示例。

首先需要定义出算数表达式的语法。算数表达式包含带括号的加减乘除四则运算,其语法定义如下:

1
2
3
expr ::= term {"+" term | "-" term}
term ::= factor {"*" factor | "*" factor}
factor ::= floatingPointNumber | "(" expr ")"

以上的语法描述中。{}表示重复0到N次,|表示或,floatingPointNumber表示一个浮点数(或整数)。

根据上面的语法,就可以开始写代码了,首先将上面的语法翻译成代码:

1
2
3
4
5
6
import scala.util.parsing.combinator._
class ArithmeticParser extends JavaTokenParsers {
def expr: Parser[Any] = term~rep("+"~term | "-"~term)
def term: Parser[Any] = factor~rep("*"~factor | "/"~factor)
def factor: Parser[Any] = floatingPointNumber | "("~expr~")"
}

在继承了JavaTokenParsers类后,就可以获得一些方法(也有些是通过import进来的)。~方法表示连接(实际上构造了一个名为~的case类,取左右分别为其参数),|表示或,rep表示重复,floatingPointNumber是一个内置的解析方法,它将解析浮点数,返回Parser[String]类型。这与我们定义的语法是差不多的。

现在虽然已经可以解析了,但是此解析的结果并没有经过计算,还没有什么意义,这时需要将解析的结果进行进一步的处理。这里给出最终的代码:

实现代码

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
/**
* Created by Zorro on 8月3日.
*/
package me.mzorro.scala.what.parsing

import scala.util.parsing.combinator._

/**
* This is a simple arithmetic parser, should be able
* to parse simple arithmetic expressions that consists
* of float numbers, +, -, *, /, and ()
* for example "1 + 2 * (3 + 4)" should be parsed as 15.0
*/
object ArithmeticParser extends JavaTokenParsers {

private def expr: Parser[Double] =
term ~ (("+" | "-") ~ term).* ^^ {
case t ~ list =>
var result = t
list.foreach {
case "+" ~ t0 => result += t0
case "-" ~ t0 => result -= t0
}
result
}

private def term: Parser[Double] =
factor ~ (("*" | "/") ~ factor).* ^^ {
case f ~ list =>
var result = f
list.foreach {
case "*" ~ f0 => result *= f0
case "/" ~ f0 => result /= f0
}
result
}

private def factor: Parser[Double] =
floatingPointNumber ^^ (_.toDouble) | "(" ~> expr <~ ")"

/**
* This is the parse method
* @param source a String source to be parsed
* @return Double type result
*/
def parse(source: String) = {
parseAll(expr, source).get
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Created by Zorro on 8月3日.
*/
package me.mzorro.scala.what.parsing

import me.mzorro.scala.what.UnitSpec

class ParserSpec extends UnitSpec {
"ArithmeticParser" should "work fine" in {
ArithmeticParser.parse("1+7-3") should be (5.0)
ArithmeticParser.parse("1 + 2 + 3") should be (6.0)
ArithmeticParser.parse("1 + 2 * 7 + 3 / 4") should be (15.75)
ArithmeticParser.parse("1 + 2 * (7 + 3) / 4") should be (6.0)
ArithmeticParser.parse("1 + 2 / 0") should be (Double.PositiveInfinity)
}
}