使用 scala-parser-combinators 的递归定义

Question

我一直在尝试使用 scala-parser-combinator 库构建一个 SQL 解析器，我已将其大大简化为下面的代码。

class Expression
case class FalseExpr() extends Expression
case class TrueExpr() extends Expression
case class AndExpression(expr1: Expression, expr2: Expression) extends Expression

object SimpleSqlParser {
  def parse(sql: String): Try[Expression] = new SimpleSqlParser().parse(sql)
}

class SimpleSqlParser extends RegexParsers {
  def parse(sql: String): Try[_ <: Expression] = parseAll(expression, sql) match {
    case Success(matched,_) => scala.util.Success(matched)
    case Failure(msg,remaining) => scala.util.Failure(new Exception("Parser failed: "+msg + "remaining: "+ remaining.source.toString.drop(remaining.offset)))
    case Error(msg,_) => scala.util.Failure(new Exception(msg))
  }

  private def expression: Parser[_ <: Expression] =
    andExpr | falseExpr | trueExpr

  private def falseExpr: Parser[FalseExpr] =
    "false" ^^ (_ => FalseExpr())

  private def trueExpr: Parser[TrueExpr] = "true" ^^ (_ => TrueExpr())

  private def andExpr: Parser[Expression] =
    expression ~ "and" ~ expression ^^ { case e1 ~ and ~ e2 => AndExpression(e1,e2)}
}

没有 'and' 解析，它工作正常。但是我希望能够解析 'true AND (false OR true)' 之类的东西。当我将 'and' 部分添加到表达式的定义时，我得到一个 WhosebugError，堆栈在 'and' 和 'expression' 的定义之间交替。

我明白为什么会这样——表达式的定义以 and 开头，反之亦然。但这似乎是模拟此问题的最自然方式。实际上，表达式也可以是 LIKE、EQUALS 等。是否有另一种方法可以对这种事物进行一般建模，以解决递归定义的问题。

Answer 1

scala.util.parsing.combinator.RegexParsers 无法处理 left-recursive 语法。您的语法可以通过以下产生式规则来概括：

expression -> andExpr | falseExpr | trueExpr
...
andExpr -> expression "and" expression

expression 通过 andExpr 间接左递归。

为避免无限递归，您需要重新表述语法，使其不再是左递归的。一种常用的方法是使用重复组合器，例如 chainl1:

  private def expression: Parser[_ <: Expression] =
    chainl1(falseExpr | trueExpr, "and" ^^^ { AndExpression(_, _) })

Live on Scastie

新的expression匹配一个或多个falseExpr/trueExpr，以"and"分隔，并将匹配的元素与AndExpression组合在左边-联想方式。从概念上讲，它对应于以下产生式规则：

expression -> (falseExpr | trueExpr) ("and" (falseExpr | trueExpr))*

如果您的语法包含许多错综复杂的左递归产生式规则，您可能需要考虑直接支持左递归的其他解析器组合器库，例如 GLL combinators。

使用 scala-parser-combinators 的递归定义

Recursive definitions with scala-parser-combinators

scala

parser-combinators

left-recursion