解析scala中的递归结构

Question

我正在尝试在scala中构造一个解析器，它可以解析类似SQL的字符串。我已经掌握了基础知识并且可以解析类似的东西：

select id from users where name = "peter" and age = 30 order by lastname

但现在我想知道如何解析嵌套和类，即

select name from users where name = "peter" and (age = 29 or age = 30)

我的'combinedPredicate'的当前产量如下：

def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ {
  case l ~ "and" ~ r => And(l,r)
  case l ~ "or" ~ r => Or(l,r)
}

我尝试在其自身内递归引用combinedPredicate生产，但这会导致堆栈溢出。

顺便说一下，我只是在这里试验......没有实现整个ansi-99规范;）

Answer 1

好吧，递归必须以某种方式划界。在这种情况下，您可以这样做：

def combinedPredicate = predicate ~ rep( ("and" | "or" ) ~ predicate )
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate
def simplePredicate = ...

所以它永远不会堆叠溢出，因为，为了递归，它首先必须接受一个字符。这是重要的部分 - 如果你总是确保在没有首先接受一个字符的情况下不会发生递归，你将永远不会进入无限递归。当然，除非你有无限的输入。 ： - ）

Answer 2

您遇到的堆栈溢出可能是左递归语言的结果：

def combinedPredicate = predicate ~ ...
def predicate = combinedPrediacate | ...

Scala 2.7中的解析器组合器是递归下降解析器。递归下降解析器有这些问题，因为他们不知道终端符号在第一次遇到它时是如何的。其他类型的解析器（如Scala 2.8的packrat解析器组合器）对此没有任何问题，但您需要使用 lazy val 而不是方法来定义语法，如下所示：

lazy val combinedPredicate = predicate ~ ...
lazy val predicate = combinedPrediacate | ...

或者，您可以重构语言以避免左递归。从你给我的例子中，要求使用这种语言的括号可以有效地解决问题。

def combinedPredicate = predicate ~ ...
def predicate = "(" ~> combinedPrediacate <~ ")" | ...

现在每个更深层次的递归对应于另一个解析的括号。你知道当你用完括号时你不必再深入了解。

Answer 3

在阅读了关于运算符优先级的解决方案之后，提出了以下内容：

  def clause:Parser[Clause] = (predicate|parens) * (
            "and" ^^^ { (a:Clause, b:Clause) => And(a,b) } |
            "or" ^^^ { (a:Clause, b:Clause) => Or(a,b) } )

  def parens:Parser[Clause] = "(" ~> clause  <~ ")"

可能只是写出@Daniel所写的另一种方式;）