1

我已经为大学的一项作业设置了一项家庭作业任务，使用 Scala 组合器来解析命题逻辑，我正要撕毁我的头发，因为我已经为此工作了几个小时，甚至无法通过第一阶段。

最初的部分是构建一个识别器，它构建符合给定 EBNF 形式的识别类型（类型已经单独提供）。（[] 表示 0 或一，+ 表示一或多个，* 表示零或多个）

prop  ::=  equiv

equiv ::=  impl biArrow impl
                                   p <=> q   becomes  Equivalent (P, Q)
                                   p <+> q   becomes  Not (Equivalent (P, Q))
impl  ::=  disj [impls]
impls ::=  (rightArrow disj)+
                                   p => q    becomes  Implies (P, Q)
        |  (leftArrow disj)+
                                   p => q    becomes  Implies (Q, P)
disj ::=  conj (disjOp conj)*
                                   p | q    becomes  Or (P, Q)
conj ::=  neg (conjOp neg)
                                   p & q    becomes  And (P, Q)
neg  ::=  negs | pos
negs ::=  negOp neg
                                   ~ p      becomes  Not (P)
pos  ::=  ident | "(" prop ")"
                                   ident   becomes  Literal (true, ident)

我们在组合器中给出的 scala 代码提供了一个错误的 prop 定义。我已经开始像这样填写类来匹配上面的代码，但是即使我实现它，我也没有捕捉到正确的错误，我认为实际上我不明白你如何指定捕捉一个值解析器

trait PropRecognizer extends RegexParsers {

  val ident = """[a-zA-Z]\w*""".r

  val biArrow = "<=>" | "<+>"
  val rightArrow = "=>"
  val leftArrow = "<="
  val disjOp = "|"
  val conjOp = "&"
  val negOp = "~"
  lazy val pos = ident | "("~prop~")"
  lazy val negs: Parser[Any] = negOp~neg
  lazy val neg = negs | pos
  lazy val conj = neg~(conjOp~neg).* | neg
  lazy val disj = conj~(disjOp~conj).* | conj
  lazy val impls = (rightArrow~disj).+ | (leftArrow~disj).+ | disj
  lazy val impl = disj~impls.? | impls
  lazy val equiv = impl~biArrow~impl | impl
  lazy val prop: Parser[Any] = rep(equiv)
}

任何帮助，形成更好的语法概述的提示都会有难以置信的帮助，我一直在阅读文档，但似乎仍然无法在我的脑海中点击它。我知道这对于那些习惯于命题逻辑和解析器的人来说是一个相当容易的问题，但我已经摸索了好几个小时了，而且我已经快要一点一点地破解它了。

编辑：更新一个项目给出的语法是错误的，所以我对其进行了调整，现在可以完美运行：

lazy val prop: Parser[Any] = rep(equiv)
lazy val equiv: Parser[Any] = impl~(biArrow~impl).?
  lazy val impl = disj~impls.?
  lazy val impls: Parser[Any] = (rightArrow~disj).+ | (leftArrow~disj).+
  lazy val disj = conj~(disjOp~conj).*
  lazy val conj: Parser[Any] = neg~(conjOp~neg).* 
  lazy val neg: Parser[Any] = negs | pos
  lazy val negs: Parser[Any] = negOp~neg 
  lazy val pos = ident | "("~prop~")"
4

1 回答 1

3

您需要使用^^运算符/方法将解析的表达式转换为表示类。例如：

lazy val conj: Parser[And] = neg~conjOp~neg ^^ {case p1~_~p2 => And(p1,p2)}

这假设neg是 类型Parser[Proposition]，它是表示任何公式的超类，并And接受两个命题作为参数。您需要知道 aParser[T]将解析一些输入并返回一个类型的值T作为其结果。

也是Parser协变的，因此您可以Parser[And]在需要解析任何命题的地方使用。

看一下这个命题逻辑解析器的例子。

于 2012-04-19T09:26:46.987 回答