解析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 vals而不是方法来定义语法,如下所示:

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

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

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

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