LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Rikiya_Ota(Rikiya Ota)

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

Last updated at Posted at 2023-12-22

これは、FOLIO Advent Calendar 2023の23日目の記事です。

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

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

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

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

扱う日付モデル

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

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 について簡単に説明したいと思います

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

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

$ scala-cli hello.sc

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

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

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

EBNF の"微調整"

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

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

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

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

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

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 を表現することで、簡易的な計算機を実装することができます。3

実装の方針

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

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

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

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

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

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 を入れています）

  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クラスのメソッド（演算子）を使った計算をする方針としました。例えば上記のコードだと、以下の部分がわかりやすいかと思います

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

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

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

  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 リポジトリでご確認ください💦

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

BizCalendar.scalaでカレンダークラスと演算を定義しているのが一番大事なところかと思います。

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

簡単な動作確認

それでは、簡単な動作確認をしてみましょう。
例として、冒頭の記事で最後に出題されている式を計算してみましょう！

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

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

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

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

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

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

$ ./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 のおかげでかなり手軽に実装できたと振り返っています（エラーハンドリングちゃんとしてないからってのもありますが、今回の本筋に関わらないことはやりたくなかっただけです）。

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

参考資料

  1. Scala もそうですがドメインのこともよくわからない中、メンターをはじめチームの皆さんがサポートしてくださり、とても前向きに取り組めています😊 ↩

  2. 最初何も考えずに実装したところ、パーサーが無限に再帰するような挙動に遭遇しました。タメになる。 ↩

  3. 厳密に言うと、元の定義では表現できていた式が表現できなくなっています。詳細はこちらの記事をぜひご参照ください。 ↩

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?