问题描述
我有以下代码用于逻辑表达式的简单解析器:
I have the following code for simple parser of logical expressions:
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并失败并显示
So, trying to parse a string !a & !b and it fails with
[1.4] failure: string matching regex `\z' expected but `&' found
!a & !b
^
似乎根解析器尝试将整个字符串解析为pattern -> not -> variable，并且在发现!a尚未结束时并没有回溯，因此甚至没有尝试pattern -> and.我认为使用PackratParsers应该可以解决该问题，但是没有实现
It seems that root parser tries to parse a whole string as pattern -> not -> variable and doesn't backtrack when it discovers that !a is not the end yet, so pattern -> and isn't even tried. I thought that using PackratParsers should solve that, but it didn't
我在做什么错了?
推荐答案
我认为一旦成功接受某些解析器，就无法使这些解析器之一回溯.如果替代方法成功，则不会尝试其他替代方法.此行为是解析这些组合器实现的表达式语法的packrat解析方法所固有的(与上下文无关的语法相反，后者的替代顺序无关紧要，回溯行为取决于解析方法).这就是为什么应该首先给出可能与较长输入匹配的替代方案的原因.
I don't think there is any way to make one of these parsers backtrack once it has successfully accepted something. If an alternative succeeds, no other alternative are tried. This behaviour is intrinsic to the packrat parsing method for Parsing Expression Grammars that these combinators implement (as opposed to Context-Free Grammars where the order of alternatives is not relevant and backtracking behaviour depends on the parsing method). That is why the alternatives that may match longer input should be given first.
关于not与and的优先级，标准方法是像在上下文无关文法中一样，在语法规则中对运算符的优先级和关联性进行编码.有关解析的大多数书籍都会描述如何执行此操作.您可以在幻灯片24中的以下注释中看到一个版本: http://www.sci.usq.edu.au/courses/CSC3403/lect/syntax-1up.pdf .
Regarding the precedence of not versus and, the standard approach is to encode the precedence and associativity of operators in the grammar rules as you would for Context-Free Grammars. Most books on parsing will describe how to do this. You can see one version in the following notes starting at slide 24: http://www.sci.usq.edu.au/courses/CSC3403/lect/syntax-1up.pdf.
这篇关于Scala PackratParsers不会回溯吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！