Scala でお手軽言語解析~カレンダーDSLの計算~

これは、[FOLIO Advent Calendar 2023](https://adventar.org/calendars/8882)の23日目の記事です。

---

弊社に入社してはや2週間と少しが経ち、Scalaのキャッチアップに勤しんでいる充実した年末を過ごしています、こんにちは、RikiyaOta です。[^1]

さて、今回は以下の記事で説明されている「複数の営業日カレンダーを扱う日付モデル」の構文解析・計算を行うような簡単なスクリプトを Scala で書いてみたいと思います。

https://zenn.dev/zahn/articles/948fc5b66648a3

コードは以下にて公開しております🙏

https://github.com/RikiyaOta/biz-calendar-calculator

※本コードは個人の学習を目的としており、業務利用等はしておりません。

# 扱う日付モデル

モデルの詳細な説明は先ほどの記事に譲ります。
とてもわかりやすい説明なので、ぜひご覧ください🎉

> ```text
> binop    ::= '+'
>            | '-'
> castop   ::= '_'
>            | '^'
> cal      ::= 'jp'
>            | 'us'
>            | 'c'
>            | 'jp & us'
>            | 'jp | us'
> expression
>          ::= ( ( "T" | expression ) cast_op ) cal
>            | ( "(" expression ")" )
>            | expression binop num
> ```           

引用：https://zenn.dev/zahn/articles/948fc5b66648a3#ebnf%E8%A1%A8%E8%A8%98

# Scala CLI について

具体的な実装に入る前に、今回利用した Scala CLI について簡単に説明したいと思います

https://scala-cli.virtuslab.org/

Scala CLI は、小規模な学習用のプログラムやスクリプト、あるいはプロトライピングなどのライトな用途で Scala を書きたい場合にぴったりのツールです🥳

例えば`hello.sc`ファイルを用意して以下のように実行するだけで Scala のコードを動作させることができます：

```terminal
$ scala-cli hello.sc
```

このお手軽さも魅力的なのですが、もう1つ魅力的なのが、実行可能なバイナリに簡単にパッケージングができるという点です⚡️

https://scala-cli.virtuslab.org/docs/commands/package

出力形式も色々な種類が対応されており、OS ネイティブな実行ファイルも出力できます。
作成したプログラムをバイナリとして配布することも簡単にできそうです😯

---

それでは、日付モデルの簡単な計算プログラムを実装してみましょう！

# EBNF の"微調整"

ある意味ここが一番注意が必要なところだと思います。

今回の記事では、Lexer/Parser をゼロから実装するのではなく、scala-parser-combinators というパーサーコンビネーターをお手軽に使えるライブラリを使ってみます。

https://github.com/scala/scala-parser-combinators

ただし、scala-parser-combinators は『トップダウン構文解析』と呼ばれる戦略で解析していく実装になっています。

この種のパーサーを扱う際には、対象の構文に『左再帰』という構造が含まれていないかを気にする必要があります。[^3]

https://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0

そこで、今回パースしたい日付モデルの EBNF から左再帰を除去する必要があります。
後の実装のしやすさも少し意識して、以下のようなものを再定義してみました：

```text
binop    ::= '+'
           | '-'
           
castop   ::= '_'
           | '^'
           
cal      ::= 'jp'
           | 'us'
           | 'c'
           | 'jp & us'
           | 'jp | us'
           
term       ::= "T" | "(" expression ")"

castterm   ::= term castop cal

expression ::= castterm [ binop num ]
```

左再帰の問題を解消したので、あとは scala-parser-combinators で用意された演算子・クラスを使って上の EBNF を表現することで、簡易的な計算機を実装することができます。[^5]

# 実装の方針

やることは大きく分けて2つだけ：

- [scala-parser-combinators](https://github.com/scala/scala-parser-combinators)の構文を使って EBNF の記述を表現する
- 日付モデルの中で定義されている５種類のカレンダー（`c`, `jp`, `us`, `jp&us`, `jp|us`）に対応するクラスとそれらの演算`_`,`^`,`+`,`-`を実装する

それでは見ていきましょう💫

## ステップ1: EBNF の記述を表現する

少し scala-parser-combinator 特有の`~`,`~>`,`^^`といった構文がありますが、一旦ざっと眺めてみてください。

```scala:BizCalendarDslCalculator.scala
//> using dep org.scala-lang.modules::scala-parser-combinators:2.3.0

import scala.util.parsing.combinator._
import java.time.LocalDate
import CalendarType._

class BizCalendarDslCalculator(targetDate: LocalDate) extends JavaTokenParsers {
  private def binOp = "+" | "-"
  private def castOp = "_" | "^"
  private def cal = ("jp" | "us" | "c" | "jp&us" | "jp|us") ^^ {t =>
    t match {
      case "c" => C
      case "jp" => Jp
      case "us" => Us
      case "jp&us" => JpAndUs
      case "jp|us" => JpOrUs
    }
  }
  private def num = "(0|[1-9][0-9]*)".r ^^ { s => s.toInt }

  private def initTerm: Parser[BizCalendar] = "T" ^^ { t => CommonCalendar(targetDate) }
  private def term: Parser[BizCalendar] = initTerm | "(" ~> expression <~ ")"
  private def castTerm = term ~ castOp ~ cal ^^ { t =>
    t match {
      case bizCalendar ~ "_" ~ calendar => bizCalendar __ calendar
      case bizCalendar ~ "^" ~ calendar => bizCalendar ^  calendar
    }
  }
  private def expression: Parser[BizCalendar] = castTerm ~ opt(binOp ~ num) ^^ { t =>
    t match {
      case bizCalendar ~ None => bizCalendar
      case bizCalendar ~ Some(binOpNum) => {
        binOpNum match {
          case "+" ~ n => bizCalendar + n
          case "-" ~ n => bizCalendar - n
        }
      }
    }
  }

  def parse(input: String) = parseAll(expression, input)
}
```

先ほど定義し直した EBNF を`expression`, `castTerm`, `term`で表現しています（実装の都合上、term のなかに initTerm を入れています）

```scala
  private def initTerm: Parser[BizCalendar] = "T" ^^ { t => CommonCalendar(targetDate) }
  private def term: Parser[BizCalendar] = initTerm | "(" ~> expression <~ ")"
  private def castTerm = term ~ castOp ~ cal ^^ { t =>
  private def expression: Parser[BizCalendar] = castTerm ~ opt(binOp ~ num) ^^ { t =>
```

`~`はパーサーの連結です。EBNF で単に並べているような書き方に相当します。

`~>`も`~`と同じようなパーサーの連結なのですが、パースした結果の左側を捨ててしまう点だけ`~`と異なります。逆に`<~`は右側を捨てます。今回の実装では、`"("`と`")"`はパースしてしまえば計算には不要なのでこのような実装としています。

`^^`は、パースした結果を受け取って何か処理を行うことができるパーサーコンビネータです。
今回の実装では、パースした結果を`BizCalendar`クラスのインスタンスに適宜変換したり、`BizCalendar`クラスのメソッド（演算子）を使った計算をする方針としました。例えば上記のコードだと、以下の部分がわかりやすいかと思います

```scala
  private def castTerm = term ~ castOp ~ cal ^^ { t =>
    t match {
      case bizCalendar ~ "_" ~ calendar => bizCalendar __ calendar
      case bizCalendar ~ "^" ~ calendar => bizCalendar ^  calendar
    }
  }
```

このパターンでは、例えば`T_jp`というような式にマッチするので、後で定義する`BizCalendar`クラスの演算子`__`を使って日付の計算をしています。

他には以下のパターンを見てみると、

```scala
  private def expression: Parser[BizCalendar] = castTerm ~ opt(binOp ~ num) ^^ { t =>
    t match {
      case bizCalendar ~ None => bizCalendar
      case bizCalendar ~ Some(binOpNum) => {
        binOpNum match {
          case "+" ~ n => bizCalendar + n
          case "-" ~ n => bizCalendar - n
        }
      }
    }
```

こちらは例えば`T_jp+1`にマッチし、`BizCalendar`の演算子`__`と`+`を続けて実行する形にしています。

EBNF で定義されている演算子をそのまま`BizCalendar`の演算子に対応づけている様子がわかるかなと思います。

---

この時点ではまだ`BizCalendar`など、定義していないクラスがあり面食らうところがあるかもしれませんが、EBNF に近い見た目で実装をすることができました🎉

## ステップ2: カレンダークラスと演算を実装する

ステップ2ではステップ1で定義していなかった`BizCalendar`クラスやその演算子たちという、よりプリミティブなものを実装します💪

といっても、そこまで複雑なことはしたくないので、割と愚直にやりました。

コードの詳細は長くなるので、以下の GitHub リポジトリでご確認ください💦

https://github.com/RikiyaOta/biz-calendar-calculator

やっていることは極々単純です！

[BizCalendar.scala](https://github.com/RikiyaOta/biz-calendar-calculator/blob/v0.0.0/BizCalendar.scala)でカレンダークラスと演算を定義しているのが一番大事なところかと思います。

また、[DateHelper.scala](https://github.com/RikiyaOta/biz-calendar-calculator/blob/v0.0.0/DateHelper.scala)では日本と米国の祝日をテキストファイルから読み取ることで閉場日を判定するような仕組みにしました。もちろんDBでも良いですが、祝日を登録しておけばちゃんと計算に反映されるという点で要件を満たそうとしています。

# 簡単な動作確認

それでは、簡単な動作確認をしてみましょう。
例として、[冒頭の記事](https://zenn.dev/zahn/articles/948fc5b66648a3)で最後に出題されている式を計算してみましょう！

なお、2020年12月26,27日は土曜・日曜であり、12月25日は米国閉場日という問題設定なので、`holidays/us_holidays.txt`には`2020-12-25`だけ書き込んでおきます。

先にパッケージングをしておきます。

```terminal
$ scala-cli --power package .
Wrote /Users/rikiyaota/biz-calendar-calculator/main, run it with
  ./main
```

それでは、計算を実行してみましょう⚡️

```terminal
$ ./main '((T_c+1)^jp+1)_us-1' '2020-12-26'
[1.20] parsed: UsBizCalendar(2020-12-24)
```

正答の通りに出力されました🎉
もう少し理解を深めるため、1つずつ計算を実行してみても良いかもしれません。

```terminal
$ ./main 'T_c' '2020-12-26'
[1.4] parsed: CommonCalendar(2020-12-26)

$ ./main 'T_c+1' '2020-12-26'
[1.6] parsed: CommonCalendar(2020-12-27)

$ ./main '(T_c+1)^jp' '2020-12-26'
[1.11] parsed: JpBizCalendar(2020-12-25)

$ ./main '(T_c+1)^jp+1' '2020-12-26'
[1.13] parsed: JpBizCalendar(2020-12-28)

$ ./main '((T_c+1)^jp+1)_us' '2020-12-26'
[1.18] parsed: UsBizCalendar(2020-12-28)

$ ./main '((T_c+1)^jp+1)_us-1' '2020-12-26'
[1.20] parsed: UsBizCalendar(2020-12-24)
```


# 最後に

いかがだったでしょうか？

筆者は EBNF のようなメタ言語をパースするプログラムを真面目に考えるのが初めての経験でしたが、ScalaCLI と scala-parser-combinators のおかげでかなり手軽に実装できたと振り返っています（エラーハンドリングちゃんとしてないからってのもありますが、今回の本筋に関わらないことはやりたくなかっただけです）。

来年はもう少しまとまった量の記事を書きたいなと思います🙇🙇🙇

# 参考資料

- https://ja.wikipedia.org/wiki/LL%E6%B3%95
- https://www.scala-lang.org/api/2.12.8/scala-parser-combinators/scala/util/parsing/combinator/RegexParsers.html
- https://www.scala-lang.org/api/2.12.8/scala-parser-combinators/scala/util/parsing/combinator/JavaTokenParsers.html
- https://docs.scala-lang.org/tour/operators.html
- https://tamura70.gitlab.io/lect-prolang/scala/scala-parser.html
- https://www.hpcs.cs.tsukuba.ac.jp/~msato/lecture-note/comp-lecture/note4.html
- https://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0

[^1]: Scala もそうですがドメインのこともよくわからない中、メンターをはじめチームの皆さんがサポートしてくださり、とても前向きに取り組めています😊
[^3]: 最初何も考えずに実装したところ、パーサーが無限に再帰するような挙動に遭遇しました。タメになる。
[^5]: 厳密に言うと、元の定義では表現できていた式が表現できなくなっています。詳細は[こちらの記事](https://curelemonade2.hatenablog.com/entry/2022/12/11/000101)をぜひご参照ください。