【译】用 Scala 的Parser Combinator 构建词法和语法分析器

| |

虽然有几个关于如何使用Parser Combinator构建简单解析器的资源，但迄今为止还没有描述如何从头开始构建完整的词法和语法分析器。

下面将介绍如何构建词法分析器来将文本转化成一系列token，以及构建解析器将token解析为抽象语法树（AST）。

语言概述

“workflow code”用来描述工作流，即 可执行的有向无环图指令。以下是有效程序的示例。 请记住，块是通过缩进定界的，类似于Python语言。

1
2
3
4
5
6
7
8
9
10
11
12
13
read input name, country
switch:
  country == "PT" ->
    call service "A"
    exit
  otherwise ->
    call service "B"
    switch:
      name == "unknown" ->
        exit
      otherwise ->
        call service "C"
        exit

我们希望将其解析成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
AndThen(
  ReadInput(List(name, country)),
  Choice(List(
    IfThen(
      Equals(country, PT),
      AndThen(CallService(A), Exit)
    ),
    OtherwiseThen(
      AndThen(
        CallService(B),
        Choice(List(
          IfThen(Equals(name, unknown), Exit),
          OtherwiseThen(AndThen(CallService(C), Exit))
        ))
      )
    )
  ))
)

这个语法的BNF表示如下。

1
2
3
4
5
6
7
8
9
10
11
12
<block> ::= (<statement>)+
<statement> ::= "exit"
              | "read input" (<identifier> ",")* <identifier>
              | "call service" <stringLiteral>
              | "switch" ":" INDENT (<ifThen>)+ [otherwiseThen] DEDENT
<ifThen> ::= <condition> "->" INDENT <block> DEDENT
<otherwiseThen> ::= "otherwise" "->" INDENT <block> DEDENT
<condition> ::= <identifier> "==" <stringLiteral>

Parser combinators

parser combinator 是一个接受解析器作为输入并返回一个新的解析器作为输出的函数，类似于高阶函数。

举个例子，假设我们有一个parser int来识别整数字面值，一个parserplus来识别 ‘+’ 字符，我们可以产生一个解析器来识别 int plus int序列为整数加法。

Scala标准库包括解析器组合器的实现：https://github.com/scala/scala-parser-combinators

构建词法分析程序

我们将会用到的标识符和字符串字面值的token，以及所有保留字和标点符号: exit, read input, call service, switch, otherwise, :, ->, ==, ,。

我们还需要生成代表缩进增加和减少的人造token：INDENT和DEDENT。 现在请忽略这些，因为我们将在以后的阶段中进行讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sealed trait WorkflowToken
case class IDENTIFIER(str: String) extends WorkflowToken
case class LITERAL(str: String) extends WorkflowToken
case class INDENTATION(spaces: Int) extends WorkflowToken
case object EXIT extends WorkflowToken
case object READINPUT extends WorkflowToken
case object CALLSERVICE extends WorkflowToken
case object SWITCH extends WorkflowToken
case object OTHERWISE extends WorkflowToken
case object COLON extends WorkflowToken
case object ARROW extends WorkflowToken
case object EQUALS extends WorkflowToken
case object COMMA extends WorkflowToken
case object INDENT extends WorkflowToken
case object DEDENT extends WorkflowToken

我们的词法分析器继承RegexParsers(一个Parsers的子类)。 RegexParsers是专门用于使用正则表达式构建字符解析器的。 它提供了从String和Regex到Parser [String]的隐式转换。

1
object WorkflowLexer extends RegexParsers {

我们首先指定哪些字符应该被忽略为空格。 我们不能忽略\ n，因为我们需要它来识别由它后面的空格数定义的标识级别。 每个其他空白字符都可以忽略。

1
2
override def skipWhitespace = true
override val whiteSpace = "[ \t\r\f]+".r

现在我们构建一个标识符的解析器：

1
2
3
def identifier: Parser[IDENTIFIER] = {
  "[a-zA-Z_][a-zA-Z0-9_]*".r ^^ { str => IDENTIFIER(str) }
}

^^操作符用来对解析结果进行映射。 正则表达式“[a-zA-Z _] [a-zA-Z0-9 _] *”.r被隐式转换为Parser [String]的一个实例，映射是一个(String => IDENTIFIER)函数，从而返回一个Parser[IDENTIFIER]实例。

字符串字面值和标识的解析器类似：

1
2
3
4
5
6
7
8
9
10
11
12
13
def literal: Parser[LITERAL] = {
  """"[^"]*"""".r ^^ { str =>
    val content = str.substring(1, str.length - 1)
    LITERAL(content)
  }
}
def indentation: Parser[INDENTATION] = {
  "\n[ ]*".r ^^ { whitespace =>
    val nSpaces = whitespace.length - 1
    INDENTATION(nSpaces)
  }
}

关键字的解析器：

1
2
3
4
5
6
7
8
9
def exit          = "exit"          ^^ (_ => EXIT)
def readInput     = "read input"    ^^ (_ => READINPUT)
def callService   = "call service"  ^^ (_ => CALLSERVICE)
def switch        = "switch"        ^^ (_ => SWITCH)
def otherwise     = "otherwise"     ^^ (_ => OTHERWISE)
def colon         = ":"             ^^ (_ => COLON)
def arrow         = "->"            ^^ (_ => ARROW)
def equals        = "=="            ^^ (_ => EQUALS)
def comma         = ","             ^^ (_ => COMMA)

现在我们将把所有这些parser组合成一个能识别每一个token的解析器。 我们将利用以下操作符：

  • |(or)，识别任何token解析器;
  • rep1，识别他参数一次或多次重复
  • phrase ，尝试消耗所有输入知道不再剩余
1
2
3
4
5
6
def tokens: Parser[List[WorkflowToken]] = {
  phrase(rep1(exit | readInput | callService | switch | otherwise | colon | arrow
     | equals | comma | literal | identifier | indentation)) ^^ { rawTokens =>
    processIndentations(rawTokens)
  }
}

请注意，操作数的顺序在处理歧义时很重要。 如果我们identifier放在其他token前面，我们的解析器将永远不会将它们识别为特殊关键字，因为它们将被成功地解析为标识符。

处理缩进

我们使用processIndentations方法对我们的解析结果进行简短的后处理步骤。 用于从INDENTATIONtoken中生成人造INDENT和DEDENTtoken。缩进级别的每次增加都被压入栈中以产生INDENT，缩进级别的缩小将从缩进堆栈弹出，生成DEDENT。

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
private def processIndentations(tokens: List[WorkflowToken],
                                indents: List[Int] = List(0)): List[WorkflowToken] = {
  tokens.headOption match {
    // if there is an increase in indentation level, we push this new level into the stack
    // and produce an INDENT
    case Some(INDENTATION(spaces)) if spaces > indents.head =>
      INDENT :: processIndentations(tokens.tail, spaces :: indents)
    // if there is a decrease, we pop from the stack until we have matched the new level,
    // producing a DEDENT for each pop
    case Some(INDENTATION(spaces)) if spaces < indents.head =>
      val (dropped, kept) = indents.partition(_ > spaces)
      (dropped map (_ => DEDENT)) ::: processIndentations(tokens.tail, kept)
    // if the indentation level stays unchanged, no tokens are produced
    case Some(INDENTATION(spaces)) if spaces == indents.head =>
      processIndentations(tokens.tail, indents)
    // other tokens are ignored
    case Some(token) =>
      token :: processIndentations(tokens.tail, indents)
    // the final step is to produce a DEDENT for each indentation level still remaining, thus
    // "closing" the remaining open INDENTS
    case None =>
      indents.filter(_ > 0).map(_ => DEDENT)
  }
}

现在所有的都设置好，这个token parser将把Reader[Char]解析成ParseResult[List[WorkflowToken]]。RegexParsers定义了自己的Reader [Char]，它由它提供的parser方法内部调用。 然后我们为WorkflowLexer定义一个apply方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
trait WorkflowCompilationError
case class WorkflowLexerError(msg: String) extends WorkflowCompilationError
object WorkflowLexer extends RegexParsers {
  ...
  def apply(code: String): Either[WorkflowLexerError, List[WorkflowToken]] = {
    parse(tokens, code) match {
      case NoSuccess(msg, next) => Left(WorkflowLexerError(msg))
      case Success(result, next) => Right(result)
    }
  }
}

应用下样例：

1
2
3
4
5
6
scala> WorkflowLexer(code)
res0: Either[WorkflowLexerError,List[WorkflowToken]] = Right(List(READINPUT, IDENTIFIER(name), COMMA,
IDENTIFIER(country), SWITCH, COLON, INDENT, IDENTIFIER(country), EQUALS, LITERAL(PT), ARROW, INDENT, 
CALLSERVICE, LITERAL(A), EXIT, DEDENT, OTHERWISE, ARROW, INDENT, CALLSERVICE, LITERAL(B), SWITCH, COLON, 
INDENT, IDENTIFIER(name), EQUALS, LITERAL(unknown), ARROW, INDENT, EXIT, DEDENT, OTHERWISE, ARROW, 
INDENT, CALLSERVICE, LITERAL(C), EXIT, DEDENT, DEDENT, DEDENT, DEDENT))

构建语法分析器

现在我们已经进行了词法分析，我们仍然缺少语法分析步骤，即将token序列转换为抽象语法树（AST）。 与生成String解析器的RegexParsers不同，我们将需要一个WorkflowTokenparser。

1
2
object WorkflowParser extends Parsers {
  override type Elem = WorkflowToken

我们需要定义Reader[WorkflowToken]，被parser用来从WorkflowToken序列中读取数据：

1
2
3
4
5
6
class WorkflowTokenReader(tokens: Seq[WorkflowToken]) extends Reader[WorkflowToken] {
  override def first: WorkflowToken = tokens.head
  override def atEnd: Boolean = tokens.isEmpty
  override def pos: Position = NoPosition
  override def rest: Reader[WorkflowToken] = new WorkflowTokenReader(tokens.tail)
}

构建语法分析器和够贱词法分析器的过程类似。我们定义简单的解析器然后将他们组合成更复杂的解析器。只不过这次parser返回的是AST而不是token:

1
2
3
4
5
6
7
8
9
10
11
12
13
sealed trait WorkflowAST
case class AndThen(step1: WorkflowAST, step2: WorkflowAST) extends WorkflowAST
case class ReadInput(inputs: Seq[String]) extends WorkflowAST
case class CallService(serviceName: String) extends WorkflowAST
case class Choice(alternatives: Seq[ConditionThen]) extends WorkflowAST
case object Exit extends WorkflowAST
sealed trait ConditionThen { def thenBlock: WorkflowAST }
case class IfThen(predicate: Condition, thenBlock: WorkflowAST) extends ConditionThen
case class OtherwiseThen(thenBlock: WorkflowAST) extends ConditionThen
sealed trait Condition
case class Equals(factName: String, factValue: String) extends Condition

作为WorkflowToken的parser我们继承了从WorkflowToken到Parser[WorkflowToken]的隐式转换。这对于解析无参token（如 EXIT，CALLSERVICE等）非常有用。对于INENTIFIER和LITERAL我们可以使用accept方法对这些token进行匹配。

1
2
3
4
5
6
7
private def identifier: Parser[IDENTIFIER] = {
  accept("identifier", { case id @ IDENTIFIER(name) => id })
}
private def literal: Parser[LITERAL] = {
  accept("string literal", { case lit @ LITERAL(name) => lit })
}

语法规则可以这样实现：

1
2
3
def condition: Parser[Equals] = {
  (identifier ~ EQUALS ~ literal) ^^ { case id ~ eq ~ lit => Equals(id, lit) }
}

这与我们以前生成token类似; 这里我们将解析结果（identifier，EQUALS和literal）转换成Equals实例。注意~的用法。

剩下的规则的实现和我们上面的类似：

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
def program: Parser[WorkflowAST] = {
  phrase(block)
}
def block: Parser[WorkflowAST] = {
  rep1(statement) ^^ { case stmtList => stmtList reduceRight AndThen }
}
def statement: Parser[WorkflowAST] = {
  val exit = EXIT ^^ (_ => Exit)
  val readInput = READINPUT ~ rep(identifier ~ COMMA) ~ identifier ^^ {
    case read ~ inputs ~ IDENTIFIER(lastInput) => ReadInput(inputs.map(_._1.str) ++ List(lastInput))
  }
  val callService = CALLSERVICE ~ literal ^^ {
    case call ~ LITERAL(serviceName) => CallService(serviceName)
  }
  val switch = SWITCH ~ COLON ~ INDENT ~ rep1(ifThen) ~ opt(otherwiseThen) ~ DEDENT ^^ {
    case _ ~ _ ~ _ ~ ifs ~ otherwise ~ _ => Choice(ifs ++ otherwise)
  }
  exit | readInput | callService | switch
}
def ifThen: Parser[IfThen] = {
  (condition ~ ARROW ~ INDENT ~ block ~ DEDENT) ^^ {
    case cond ~ _ ~ _ ~ block ~ _ => IfThen(cond, block)
  }
}
def otherwiseThen: Parser[OtherwiseThen] = {
  (OTHERWISE ~ ARROW ~ INDENT ~ block ~ DEDENT) ^^ {
    case _ ~ _ ~ _ ~ block ~ _ => OtherwiseThen(block)
  }
}

就像我们用词法分析器一样，我们还定义了一个apply方法：

1
2
3
4
5
6
7
8
9
10
11
12
case class WorkflowParserError(msg: String) extends WorkflowCompilationError
object WorkflowParser extends RegexParsers {
  ...
  def apply(tokens: Seq[WorkflowToken]): Either[WorkflowParserError, WorkflowAST] = {
    val reader = new WorkflowTokenReader(tokens)
    program(reader) match {
      case NoSuccess(msg, next) => Left(WorkflowParserError(msg))
      case Success(result, next) => Right(result)
    }
  }
}

Pipelining

我们现在已经实现了词法和语法分析器。 剩下的就是将它们串起来：

1
2
3
4
5
6
7
8
object WorkflowCompiler {
  def apply(code: String): Either[WorkflowCompilationError, WorkflowAST] = {
    for {
      tokens <- WorkflowLexer(code).right
      ast <- WorkflowParser(tokens).right
    } yield ast
  }
}

试一下样例：

1
2
3
4
scala> WorkflowCompiler(code)
res0: Either[WorkflowCompilationError,WorkflowAST] = Right(AndThen(ReadInput(List(name, country)),
Choice(List(IfThen(Equals(country,PT),AndThen(CallService(A),Exit)),OtherwiseThen(AndThen(CallService(B),
Choice(List(IfThen(Equals(name,unknown),Exit), OtherwiseThen(AndThen(CallService(C),Exit))))))))))

我们的编译器已被证明能够解析代码。

错误处理

现在我们来尝试解析一个语法上无效的程序。 假设我们忘了在第一个switch case上引用PT：

1
2
scala> WorkflowCompiler(invalidCode)
res1: Either[WorkflowCompilationError,WorkflowAST] = Left(WorkflowParserError(string literal expected))

我们得到一个明确的错误消息，告诉我们预期一个字符串字面量，但在哪里？ 知道这个错误的源位置就好了。 幸运的是，Scala的parser combinator支持记录token的原始源位置。

为了做到这一点，首先，我们的WorkflowToken和WorkflowAST trait 必须与Positional混合。 这提供了一个可变的pos变量和一个setPos方法，该方法可以用行号和列号修饰对应的实例。

其次，我们必须在每个解析器上使用positioned运算符。 例如，IDENTIFIER token 的解析器将被写为：

1
2
3
def identifier: Parser[IDENTIFIER] = positioned {
  "[a-zA-Z_][a-zA-Z0-9_]*".r ^^ { str => IDENTIFIER(str) }
}

Positional Mixin的一个丑陋的副作用是，我们所有的令牌现在都必须成为case class 而不是case object，因为每个人现在都拥有可变状态。

我们的WorkflowCompilationError子类型现在包括位置信息…

1
2
3
4
5
6
case class WorkflowLexerError(location: Location, msg: String) extends WorkflowCompilationError
case class WorkflowParserError(location: Location, msg: String) extends WorkflowCompilationError
case class Location(line: Int, column: Int) {
  override def toString = s"$line:$column"
}

…由每个阶段的apply方法报告：

1
2
3
4
5
6
def apply(code: String): Either[WorkflowLexerError, List[WorkflowToken]] = {
  parse(tokens, code) match {
    case NoSuccess(msg, next) => Left(WorkflowLexerError(Location(next.pos.line, next.pos.column), msg))
    case Success(result, next) => Right(result)
  }
}

现在我们再试一次解析无效的代码：

1
2
scala> WorkflowCompiler(invalidCode)
res1: Either[WorkflowCompilationError,WorkflowAST] = Left(3:14,WorkflowParserError(string literal expected))

Final notes

我们从一个文本流分解成一系列token，最终将它们组合成一个类型化的抽象语法树，从而导致一个更有效的方法来推导程序。

我们现在可以扩展编译器以执行其他非解析相关任务，比如验证（例如，确保所有代码路径以exit关键字结尾）或代码生成，即遍历此AST以生成指令序列。

如果您想继续使用Scala的parser combinator，则可以在以下网址获取本教程的最终代码：https://github.com/enear/parser-combinators-tutorial