3

Scala パーサー コンビネーター ライブラリを学んでいます。いくつかの算術式を抽象的な構文ツリーで解析する実用的なパーサーを実験しました。だから私が電話するとき

phrase(expr)(tokens)

私のパーサーはすべての入力を解析し、評価を提供します。しかし、どうすれば段階的な評価を行うことができますか?

言う

3 + 4 * 7

それは印刷します

3 + 28

それから

31

別の行で。

私はAPIをスキャンしましたが、そこにあるドキュメントはあまり役に立ちません...助けてくれてありがとう。

4

2 に答える 2

5

これは、あなたがやろうとしていることの本当に簡単な実装です:

まず、式の階層を定義します。これを特定の問題に合わせて調整する必要があります。

trait Expr {
  def eval: Int
}
case class IntLeaf(n: Int) extends Expr {
  def eval = n
  override def toString = "%d".format(n)
}
case class Sum(a: Expr, b: Expr) extends Expr {
  def eval = a.eval + b.eval
  override def toString = "(%s + %s)".format(a, b)
}

そして、一番下の枝だけを組み合わせる機能。

def combineLeaves(e: Expr): Expr = {
  e match {
    case IntLeaf(n) => IntLeaf(n)
    case Sum(IntLeaf(a), IntLeaf(b)) => IntLeaf(a + b)
    case Sum(a, b) => Sum(combineLeaves(a), combineLeaves(b))
  }
}

次に、ツリーを一度に 1 レベルずつ結合し、その都度印刷する関数。

def printEval(e: Expr) {
  println(e)
  e match {
    case IntLeaf(n) =>
    case _ => printEval(combineLeaves(e))
  }
}

さて、パーサー。繰り返しますが、これをデータに合わせて調整する必要があります。

object ArithmeticParser extends RegexParsers {
  private def int: Parser[IntLeaf] = regex(new Regex("""\d+""")).map(s => IntLeaf(s.toInt))
  private def sum: Parser[Sum] = ("(" ~> expr ~ "+" ~ expr <~ ")").map { case (a ~ _ ~ b) => Sum(a, b) }
  private def expr = int | sum
  def parse(str: String): ParseResult[Expr] = parseAll(expr, str)
  def apply(str: String): Expr = ArithmeticParser.parse(str) match {
    case ArithmeticParser.Success(result: Expr, _) => result
    case _ => sys.error("Could not parse the input string: " + str)
  }

}

そして、これを使用する方法は次のとおりです。

scala> printEval(ArithmeticParser("((1 + 7) + ((3 + 9) + 5))"))
((1 + 7) + ((3 + 9) + 5))
(8 + (12 + 5))
(8 + 17)
25
于 2012-09-24T21:02:27.600 に答える
2

パーサー コンビネータは、評価を行いません。パーサー コンビネータを使用して、入力文字列を解析し、それを表すデータ構造を構築します。評価は、何らかの方法でデータ構造を処理し、必要な単純化を実行するもう 1 つのステップです。したがって、式3+4*7を使用すると、解析フェーズで次の抽象構文ツリーを構築できます。

   +
  / \
 3 *   
    / \
   4 7

次に、評価段階で、再帰的にツリーをたどり、葉以外のノードごとに、その左右のサブツリーの評価結果にノード操作を適用します。

ドキュメンテーションが役に立たない場合は、 Programming in Scalaのパーサー コンビネーターの章を参照してください。初版は無料で入手できます。

また、最近、Scala のパーサー コンビネーターに関するブログ投稿を書きました。そこでは、あなたのシナリオにいくぶん似たシナリオについて説明しています。

于 2012-09-24T20:44:05.057 に答える