Scala解析器组合器:递归

Question

我正在为布尔表达式编写解析器，并尝试解析"true and false"等输入

def boolExpression: Parser[BoolExpression] = boolLiteral | andExpression 
def andExpression: Parser[AndExpression] = (boolExpression ~ "and" ~ boolExpression) ^^ {
case b1 ~ "and" ~ b2 => AndExpression(b1, b2)
}
def boolLiteral: Parser[BoolLiteral] = ("true" | "false") ^^ {
s => BoolLiteral(java.lang.Boolean.valueOf(s))
}

上面的代码不解析"true and false"，因为它只读取"true"并立即应用规则boolLiteral

但是如果我把规则boolExpression改成这样:

def boolExpression: Parser[BoolExpression] = andExpression | boolLiteral

然后，当解析"true and false"时，由于无限递归，代码抛出StackoverflowError

java.lang.StackOverflowError
at Parser.boolExpression(NewParser.scala:58)
at Parser.andExpression(NewParser.scala:62)
at Parser.boolExpression(NewParser.scala:58)
at Parser.andExpression(NewParser.scala:62)
...

如何解决这个问题?

Answer 1

这似乎是在解析一个由"one_answers"分隔的布尔常量字符串。最好在解析器中使用chainl1原语。这是一个从左到右优先级的a op b op c op d操作链。

它可能看起来像这样完全未经测试的代码:

trait BoolExpression
case class BoolLiteral(value: Boolean) extends BoolExpression
case class AndExpression(l: BoolExpression, r: BoolExpression) extends BoolExpression
def boolLiteral: Parser[BoolLiteral] =
("true" | "false") ^^ { s => BoolLiteral(java.lang.Boolean.valueOf(s)) }
def andExpression: Parser[(BoolExpression, BoolExpression) => BoolExpression] =
"and" ^^ { _ => (l: BoolExpression, r: BoolExpression) => AndExpression(l, r) }
def boolExpression: Parser[BoolExpression] =
chainl1(boolLiteral, andExpression) ^^ { expr => expr }

假设需求比这更复杂，但是chainl1解析器是一个很好的起点。

Answer 2

问题的核心是通常的解析器组合器库使用不支持左递归的解析算法。一种解决方案是重写没有左递归的语法，这意味着每个解析器在递归调用自己之前至少需要消耗一些输入。例如，你的语法可以这样写:

def boolExpression: Parser[BoolExpression] = andExpression | boolLiteral
def andExpression: Parser[AndExpression] = (boolLiteral ~ "and" ~ boolExpression) ^^ {
case b1 ~ "and" ~ b2 => AndExpression(b1, b2)
}

但是您也可以使用基于另一种支持左递归的解析算法的解析器组合子库。我只知道Scala有一个:https://github.com/djspiewak/gll-combinators我不知道它在多大程度上可以生产。

//编辑:我想这个可能也支持左递归。再说一次，我不知道它在多大程度上可以投入生产。https://github.com/djspiewak/parseback