7

我正在尝试在 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)
}

我尝试在其内部递归地引用 combinePredicate 产生式，但这会导致 stackoverflow。

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

4

3 回答 3

11

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

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

所以它永远不会堆栈溢出，因为要递归，它首先必须接受一个字符。这是重要的部分——如果您始终确保在不首先接受字符的情况下不会发生递归，那么您将永远不会陷入无限递归。当然，除非你有无限的输入。:-)

于 2009-11-26T11:35:32.683 回答
7

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

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

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

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

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

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

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

于 2009-11-27T04:51:16.930 回答
0

在阅读了有关运算符优先级的解决方案并提出以下建议后：

  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  <~ ")"

Wich 可能只是写@Daniel 所写内容的另一种方式；）

于 2009-11-26T19:23:35.160 回答