1

私は大学での宿題で、Scala コンビネーターを使用して命題論理を解析するように指示されました。これに数時間取り組んでいて、問題を解決することさえできないので、髪を引き裂こうとしています。最初の段階。

最初の部分は、指定された EBNF 形式に準拠する認識タイプ (タイプは既に個別に提供されています) を構築するレコグナイザーを構築することです。([] は 0 または 1 を意味し、+ は 1 つ以上を意味し、* は 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)
}

構文のより良いアウトラインへのヒントを形成する助けは信じられないほどの助けになるでしょう。これは、命題論理とパーサーに慣れている人にとってはかなり簡単な問題であることは理解していますが、私は何時間も頭を悩ませており、少しずつハッキングすることに近づいています.

編集: 更新指定された構文は 1 つの項目で間違っていたので、微調整したところ、完全に機能するようになりました:

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)}

これは、任意の式を表すためのスーパー クラスであり、引数として 2 つの命題を取るnegtypeであると仮定します。a が何らかの入力を解析し、その結果としてtype の値を返すことを知っておく必要があります。Parser[Proposition]AndParser[T]T

また、共変であるため、任意の命題を解析するために必要な場所をParser使用できます。Parser[And]

命題論理のパーサーについては、この例をご覧ください。

于 2012-04-19T09:26:46.987 に答える