斯卡拉PackratParsers不会回溯，因为它应该？(Scala PackratParsers

我有一个逻辑表达式解析器简单下面的代码：

import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.PackratParsers


object Parsers extends RegexParsers with PackratParsers

// Entities definition
sealed trait LogicalUnit
case class Variable(name: String) extends LogicalUnit
case class Not(arg: LogicalUnit) extends LogicalUnit
case class And(arg1: LogicalUnit, arg2: LogicalUnit) extends LogicalUnit


import Parsers._

// In order of descending priority
lazy val pattern: PackratParser[LogicalUnit] =
  ((variable) | (not) | (and))

lazy val variable: PackratParser[Variable] =
  "[a-zA-Z]".r ^^ { n => Variable(n) }

lazy val not: PackratParser[Not] =
  ("!" ~> pattern) ^^ { x => Not(x) }

lazy val and: PackratParser[And] =
  ((pattern <~ "&") ~ pattern) ^^ { case a ~ b => And(a, b) }


// Execution
println(Parsers.parseAll(pattern, "!a & !b"))

因此，试图解析字符串!a & !b ，它失败

[1.4] failure: string matching regex `\z' expected but `&' found

!a & !b
   ^

看来，根解析器试图解析整个字符串的pattern -> not -> variable ，当它发现不走回头路!a还没有结束呢，所以pattern -> and甚至没试过。 我认为使用PackratParsers要解决这个问题，但是事实并非如此

我究竟做错了什么？

Answer 1:

我不认为有什么办法让这些解析器之一走回头路一旦成功接受一些东西。 如果替代成功，没有其他办法都试过了。 这种行为是内在的解析表达式语法，这些组合子实现（而不是上下文无关文法，如果替代的顺序是不相关的和回溯行为取决于解析法）packrat解析方法。 这就是为什么，可能不再匹配输入的替代品，应先给予。

对于不与优先级和标准的做法是运营商的优先级和结合编码的语法规则，你会为上下文无关文法。 在解析大多数书籍将介绍如何做到这一点。 ：您可以在开始幻灯片24以下注意事项见一个版本http://www.sci.usq.edu.au/courses/CSC3403/lect/syntax-1up.pdf 。

Answer 2:

我不知道具体原因，但每当我遇到了这样的问题，解析器，我把解析的可能性顺序从最复杂，最简单的。

在你的情况下，将

lazy val pattern: PackratParser[LogicalUnit] = ((and) | (not) | (variable))这使得您的示例解析。

结果然而Not(And(Variable(a),Not(Variable(b))))可能不是你想要的是什么。

其原因是， a & !b是一个有效的模式，所以!a & !b可以从开始解析not 。

要改变这种状况，您能介绍括号。 这是一个简单的可能性：

lazy val not: PackratParser[Not] =
  ("!" ~> term) ^^ { x => Not(x) }

lazy val term: PackratParser[LogicalUnit] = 
  variable | "(" ~> and <~ ")" 

现在的结果是And(Not(Variable(a)),Not(Variable(b)))

文章来源: Scala PackratParsers does not backtrack as it should?