parsing - scala解析器组合器中的回溯？

Question

似乎 scala 的解析器组合器不会回溯。我有一个无法正确解析以下“stmt”的语法（见底部）：

copy in to out .

这应该很容易通过回溯解析：

stmt: (to out(copy in))

还是我错过了什么？

解析器：

type ExprP = Parser[Expr]
type ValueP = Parser[ValExpr]
type CallP = Parser[Call]
type ArgsP = Parser[Seq[Expr]]

val ident     = "[a-zA-Z\\+\\-\\*/%><\\\\\\=]+".r
val sqstart   = "\\["                          .r
val sqend     = "\\]"                          .r
val del       = ","                            .r
val end       = "\\."                          .r

def stmt: ExprP      = expr <~ end
def expr: ExprP      = ucall | call | value
def value: ValueP    = ident ^^ {str => IdentExpr(str)}
def call: CallP      = (args ~ ident ~ expr) ^^ {case args ~ method ~ upon => Call(args, method, upon)}
def ucall: CallP     = (ident ~ expr) ^^ {case method ~ upon => Call(Seq(), method, upon)}
def args: ArgsP      = advargs | smplargs
def smplargs: ArgsP  = expr ^^ {e => Seq(e)}
def advargs: ArgsP   = (sqstart ~> repsep(expr, del) <~ sqend) ^^ {seq => seq}

Answer 1

您想PackratParsers在 2.8 中使用。我认为 packrat 解析器是唯一的回溯解析器。

编辑：截至 2015 年年中，您应该改用fastparse。它不仅速度更快，而且更易于使用（尤其是在通过解析构建数据结构时）。

Answer 2

你的问题不是回溯。中的标准|运算符scala.util.parsing.combinator将进行回溯。您的问题是左递归（expr→ call→ args→ smplargs→ expr）。Packrat 解析可能确实对此有所帮助。