使用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)}
}

没有“和”解析，它可以正常工作。但是我希望能够解析诸如“ true AND（false or true）”之类的东西。当我在表达式的定义中添加“和”部分时，我得到一个StackOverflowError，堆栈在“和”与“表达式”的定义之间交替。

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

Answer 1

scala.util.parsing.combinator.RegexParsers无法处理左递归语法。您的语法可以通过以下生产规则来概括：

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

expression通过间接地左递归andExpr。

为了避免无限递归，您需要重新格式化语法，以使其不再是左递归。一种常用的方法是使用重复组合器，例如chainl1：

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

Live on Scastie

新的expression匹配一个或多个falseExpr/ trueExpr，由分隔"and"，并AndExpression以左关联方式将匹配的元素组合在一起。从概念上讲，它符合以下生产规则：

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

如果您的语法包含许多纠结的左递归生成规则，则可能要考虑直接支持左递归的其他解析器组合器库，例如GLL组合器。