Scalaのパーサーコンビネーターで四則演算をやってみよう

はじめに

こんにちは。meviyのWebシステムを開発している大崎です。
プログラミングをしていて、独自に定義した数式のようなものを読み込ませようとして、正規表現などを駆使して何とか実装した、といった経験はありませんか？
私がScalaの中で面白いと思うものの一つに、パーサーコンビネーターがあります。
パーサーコンビネーターは、簡単に言えば小さなパーサーを組み合わせてより複雑なパーサーを作成するためのライブラリです。これにより、複雑な文法解析をシンプルで直感的な方法で行うことができます。
今回は、Scalaのパーサーコンビネーターを使って、文字列で与えられた四則演算を行うプログラムを作成してみたいと思います。

準備

Scala 2.11以降、標準ライブラリからパーサーコンビネーターが削除されたため、別途依存関係として追加する必要があります。以下のように build.sbt に依存関係を追加しておいてください。

libraryDependencies += "org.scala-lang.modules" %% "scala-parser-combinators" % "2.4.0"

単純加算のコード

まずは、単純な加算を行うパーサーのコードを見てみましょう。

package parser

import scala.util.parsing.combinator._

object SimpleAddParser extends JavaTokenParsers {
  def term: Parser[Int] = wholeNumber ^^ { _.toInt }
  
  def expr: Parser[Int] = term ~ rep("+" ~ term) ^^ {
    // list.map(_._2) で "+" と数字の組み合わせのリストから数字のみを抽出し、sum で合計を計算 それをtと足し合わせる
    case t ~ list => t + list.map(_._2).sum 
  }

  def parse(input: String): ParseResult[Int] = parseAll(expr, input)
}

object SimpleMain extends App {
  println(SimpleAddParser.parse("1"))         // 1
  println(SimpleAddParser.parse("1 + 2"))     // 3
  println(SimpleAddParser.parse("1 + 2 + 3")) // 6
}

コード解説

パーサーの定義

このコードでは、SimpleAddParser オブジェクトに単純な加算式を解析するためのパーサーを定義しています。

term : 整数を解析するパーサー。 2 や 23 といった整数に対応するようなもの
expr : 加算式を表すパーサー。ここでは、term パーサーと複数の "+" ~ term パーサーの組み合わせ。 2 + 23 といった数式に対応するようなもの
parse : 入力文字列を受け取り、expr パーサーで解析するメソッド

全体としては、加算式を解析し、結果を計算して整数として返す定義となっています。

パーサーの組み合わせ

ここで、 ~ や ^^ rep という見慣れない記号・関数が出てきました。
これらは、Scalaのパーサーコンビネーターで使われる記号で、それぞれ以下のような意味を持ちます。

少々語弊はありますが、簡単のために、以下のように解釈していただければと思います。

~ : パーサーを連結する演算子
- p1 ~ p2 は、入力に対して、パーサー p1 の直後にパーサー p2 を適用します。
- 例えば、 "+" ~ term は、 + と整数 term の連結を表しています。
^^ : 左辺のパターンを右辺の関数で変換することを表す演算子
- p ^^ f は、p を関数 f で変換することを定義します。
- 今回であれば、 term の wholeNumber ^^ { _.toInt } は、 wholeNumber という文字列に対して、文字列を整数に変換する関数を対応させています。
rep : パターンが繰り返すことを表す関数
- rep(p) は、 p の繰り返しを表します。
- 今回であれば、例えば 1 + 2 + 3 といった式 expr があった場合、 + 2 + 3が rep("+" ~ term) に対応しています。
- 上記の "+" ~ term は、 + と整数 term で構成されるパターンを表しています。つまり、 + 2 と + 3 です。
- rep はパターンの繰り返しを意味するので、 + 2 と + 3 を連結したもの、つまり + 2 + 3 が rep("+" ~ term) に対応します。
- 繰り返し、と言っていますが、 rep は0回以上の繰り返しを表すため、 term ~ rep("+" ~ term) は term でもあります。
  そのため 1 といった整数1つだけで加算なし、といった式にもマッチすることができます。

四則演算のコード例

次に、ちょっとだけ機能をリッチにした、括弧にも対応した四則演算を扱うパーサーのコード例を見てみましょう。

package parser

import scala.util.parsing.combinator._

object ArithmeticParser extends JavaTokenParsers {
  def expr: Parser[Double] = term ~ rep(("+" | "-") ~ term) ^^ {
    case t ~ list => list.foldLeft(t) {
      case (x, "+" ~ y) => x + y
      case (x, "-" ~ y) => x - y
    }
  }

  def term: Parser[Double] = factor ~ rep(("*" | "/") ~ factor) ^^ {
    case f ~ list => list.foldLeft(f) {
      case (x, "*" ~ y) => x * y
      case (x, "/" ~ y) => x / y
    }
  }

  def factor: Parser[Double] = floatingPointNumber ^^ (_.toDouble) | "(" ~> expr <~ ")"

  def parse(input: String): ParseResult[Double] = parseAll(expr, input)
}

object ArithMain extends App {
  println(ArithmeticParser.parse("1"))                     // 1.0
  println(ArithmeticParser.parse("1 + 2"))                 // 3.0
  println(ArithmeticParser.parse("1 * 2 * 3"))             // 6.0
  println(ArithmeticParser.parse("1 + 2 * 3"))             // 7.0
  println(ArithmeticParser.parse("(1 + 2) * 3"))           // 9.0
  println(ArithmeticParser.parse("(1 + 2) / 3"))           // 1.0
  println(ArithmeticParser.parse("(1 + 2) * (3 - 4) / 2")) // -1.5
}

コード解説

Parserの変更点

今度は factor が増えました。 factor は数値または括弧で囲まれた式を解析するパーサーです。
expr と term も内容が変わっています。減算と乗算と除算に対応するため、expr は加減算式を表すパーサー、 term は乗除算式を表すパーサーとなりました。

また、 term パーサーと expr パーサーの中で、 foldLeft が使われています。これは、リストの要素を左から順に処理していく関数で、これは左から順に数式を計算していくことを示しています。

("+" | "-") や ("*" | "/") は、 + または - 、 * または / のいずれかにマッチすることを示しています。

括弧への対応

括弧に対応するために設けられた factor パーサーですが、 ^^ の右辺に | が使われています。
この | は何を示しているのだろう？と思いませんか？
これは、Scalaのパーサーコンビネーターで、複数のパーサーが適用されうる、という演算子です。

例えば、 p1 | p2 は、パーサー p1 またはパーサー p2 のいずれかにマッチすることを示します。 p1 にマッチしない場合は、p2 にマッチするかどうかを試す、というものです。
もちろん、 p1 にマッチした場合は、p2 は試されませんし、p1 | p2 | p3 といったように、複数のパーサーを指定することもできます。

コード例で説明すると、 floatingPointNumber を toDouble できない場合、 ( と ) で囲まれた式を expr のパーサーでパースする、ということになります。
このとき、 (2 + 3) という式があった場合、 (2 + 3) が factor に該当し、両端の括弧を取り除いた 2 + 3 が expr によってパースされます。

演算子の優先順位

どのようにして四則演算の優先順位を考慮しているのでしょうか？
それは、 parse メソッドで expr パーサーを指定している部分にあります。
def parse(input: String): ParseResult[Double] = parseAll(expr, input) の第一引数に expr が指定されています。これは、加減算の優先順位が最も低く、最後に計算するためです。
次に高い優先度は乗除算であるため、 expr の中で term を、そして乗除算より括弧の中の式を優先するため term の中で factor を指定、というように、優先度が高くなるにつれて深い箇所で指定していきます。
このようにして、パーサーを定義する中で四則演算の優先順位を考慮させることができます。

このような定義をしていくだけで四則演算の式を解析できるなんて、面白いですよね。

まとめ

Scalaのパーサーコンビネーターを使うことで、直感的に文法解析を行うプログラムを作成することができました。
今回は、四則演算の式を解析するパーサーを作成しましたが、他にも様々なパーサーを組み合わせることで、より複雑な文法解析を行うことができます。

題材が四則演算でしたので、計算結果として Double 型の結果を返していますが、こちらはニーズに合わせて任意の型、つまりご自身で定義された木構造・オブジェクトなどのクラスに変換することも可能です。

おわりに

本ブログでは今後もScalaをはじめとする、DTダイナミクスで用いられている技術やプロダクトなどの魅力を発信していきますので、興味を持っていただけると幸いです。

ほかにも、Scalaに関する記事を書いていますので、ぜひご覧ください。