EBNFからFIRST集合を求めるプログラム Rustで書いてみた

ナマステ
コンパイラ自作の副産物として，EBNFからFIRST集合を求めるプログラムをRustで書いてみたのでその記録を残す．
ここでは各種用語の解説はしない

またこの記事中の引用形式では，下部に示した参考書籍からの引用を示しているものとする．

ソースコードは以下にある．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs

アルゴリズム

以下のアルゴリズムに従ってプログラムを構成した．

(0) FIRST($\alpha$)を空集合に初期化する．
以下のステップを，もう付け加えるものがなくなるまで繰り返す．
(1) $\alpha$が空系列($\epsilon$): FIRST($\alpha$)に$\epsilon$を付け加える．
(2) $\alpha$が終端記号a 1文字: FIRST($\alpha$)にaを付け加える．
(3) $\alpha$が非終端記号A 1文字: Aを左辺に持つすべての生成規則A ::= $\beta$に対して，FIRST($\beta$)を求め，その要素をFIRST($\alpha$)に付け加える．
(4) $\alpha$が長さ2以上の系列($\alpha = X\beta$)とする
(4-1) FIRST(X)が$\epsilon$を含まない: FIRST(X)の要素をFIRST($\alpha$)に付け加える．
(4-2) FIRST(X)が$\epsilon$を含む: FIRST(X) - {$\epsilon$}とFIRST($\beta$)の要素をFIRST($\alpha$)に付け加える．
(5) $\alpha$が $\beta | \gamma$: FIRST($\beta$)とFIRST($\gamma$)の要素をFIRST($\alpha$)に付け加える．
(6) $\alpha$が{$\beta$}: FIRST($\beta$)の要素と$\epsilon$をFIRST($\alpha$)に付け加える．
(7) $\alpha$が[$\beta$]: FIRST($\beta$)の要素と$\epsilon$をFIRST($\alpha$)に付け加える．
(8) $\alpha$が($\beta$): FIRST($\beta$)の要素をFIRST($\alpha$)に付け加える．

文中で出てくる記法の解説を軽く示す

• $\beta | \gamma$: $\beta$または$\gamma$
• {$\beta$}: $\beta$の0回以上の繰り返し
• [$\beta$]: $\beta$の0回または1回の出現

プログラム

基本的には条件分岐して再帰すればよさそうだ．
記号は1記号1文字列として文字列配列で表現する．
今回はひとまず簡単に動けばいい．ので，生成規則については記号の間には必ず空白を入れるという前提で，空白で分割して文字列配列にした．またハードコーディングしている．

それぞれのステップは以下のように実装した．

(1) $\alpha$が空系列($\epsilon$): FIRST($\alpha$)に$\epsilon$を付け加える．

配列の長さが1で，かつその要素が"$\epsilon$"の場合という条件でよさそうだ．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L212-L215

(2) $\alpha$が終端記号a 1文字: FIRST($\alpha$)にaを付け加える．

配列の長さが1で，かつその要素が終端記号の場合という条件でよさそうだ．
今回は，終端記号は大文字アルファベットを含まないかつ( ) [ ] { } |という制御用の記号ではない文字列とした．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L216-L219

(3) $\alpha$が非終端記号A 1文字: Aを左辺に持つすべての生成規則A ::= $\beta$に対して，FIRST($\beta$)を求め，その要素をFIRST($\alpha$)に付け加える．

配列の長さが1で，かつその要素が非終端記号の場合という条件でよさそうだ．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L220-L231

生成規則はそれぞれの生成規則を配列としてまとめ，グローバル変数に保持している．
再帰を使うときにどこからでも気軽に読み取りたいためである．環境をキャプチャできるクロージャが使えれば良かったのだが，Rustのクロージャは再帰できないためグローバル変数に保持した．

(4) $\alpha$が長さ2以上の系列($\alpha = X\beta$)とする

一番めんどうだった．( ) [ ] { } |といった制御用の記号をカウントし，すべてのカウントが0の時なら2つの系列として分割できそうだ．
{ a }のような形だった場合はカウントは0になるが2つの系列に分割できないので，こういったケースは考慮する必要があるだろう．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L292-L339

(4-1) FIRST(X)が$\epsilon$を含まない: FIRST(X)の要素をFIRST($\alpha$)に付け加える．
(4-2) FIRST(X)が$\epsilon$を含む: FIRST(X) - {$\epsilon$}とFIRST($\beta$)の要素をFIRST($\alpha$)に付け加える．

XについてFIRST集合を求め，集合の要素に$\epsilon$が含まれているかどうかで条件分岐するだけである．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L232-L246

(5) $\alpha$が $\beta | \gamma$: FIRST($\beta$)とFIRST($\gamma$)の要素をFIRST($\alpha$)に付け加える．

ステップ4と同じように，( ) [ ] { } |といった制御用の記号をカウントする．すべてのカウントが0の時に|が来たらそこで分割する．
a | b | cといった3つ以上の選択のケースも考えられる．が，aとb | cという2つの系列に分割さえできればあとは再帰的に解決できる．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L341-L389

https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L247-L253

(6) $\alpha$が{$\beta$}: FIRST($\beta$)の要素と$\epsilon$をFIRST($\alpha$)に付け加える．

配列の先頭と末尾を見ればよい．
https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L391-L401

https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L254-L259

(7) $\alpha$が[$\beta$]: FIRST($\beta$)の要素と$\epsilon$をFIRST($\alpha$)に付け加える．
(8) $\alpha$が($\beta$): FIRST($\beta$)の要素をFIRST($\alpha$)に付け加える．

(6)と同じように配列の先頭と末尾を見ればよい．
コードの掲示は省略する．

効率化

FIRST集合を求める中で，何度も同じFIRST集合を求めることがある．
なので，一度求めたFIRST集合はキャッシュしておくことで効率化できる．
lazyLockとMutexを使用して可変なグローバル変数にキャッシュした．

https://github.com/neruneruna7/compiler_MPPL/blob/master/src/bin/first.rs#L28-L30

さて，どのくらい効率化できるのだろうか？
以下の簡単な文法について試してみた

文法G8' (書籍にある文法G8を少し変更したもの)
E ::= T { ( + | - ) T }
T ::= { ( * | / ) F }
F ::= '(' E ')' | i | n

コード中，自分が定義した関数についての総呼び出し回数を計測した．

• キャッシュなし: 74809回
• キャッシュあり: 321回

かなり効率化できていることがわかる．
生成規則3つ程度なのに，74809回も関数を呼び出しているのはなんというか，こう，ヤバい．

しかし，実のところ実行時間については体感できるほどの差はなかった．
ではなぜ効率化したのか？ デバッガを使用する際の時間に大きく影響したからである．
FireDbgというタイムトラベルデバッガを使用していたが，それを使用した際のおおよその実行時間は以下の通りである．

• キャッシュなし: 約18分
• キャッシュあり: 約6秒

デバッガ使用時に18分もかかるのはちょっとしんどかったので，効率化した．

使ってみたい人へ

Rust環境があればコードのコピペだけで実行できるはずである．
実行に際しての注意点がある．OnceLockを使用してグローバル変数に文法を保持している都合，1回のプログラム実行（関数呼び出しではない）で，2種類の文法についてFIRST集合を求めることができない．
例：文法G1と文法G2を，FIRST集合を求める関数を2回呼んでそれぞれ求めようとしてもうまくいかない．どちらか片方の結果が2回出力されることになる．

また，生成規則を書く際には以下のことに留意してほしい

• 記号に大文字アルファベットを含んでいるものは，非終端記号として扱われる
• 記号は1文字でなくてもよいが，記号の間には空白を入れること
  • a Bもalphabet BlockもOK
• 終端記号として(,),[, ], {, }, |は単体では使用できない.が，'('のようにシングルクォートなど何かしら終端記号として扱われるもので囲むことで終端記号として扱うことができる．

おわりに

なんだかんだで，こういったキラキラしてたり流行ったりはしてないけどIT技術の基礎として存在しているものを作ってみるのは楽しいですね．

同じように自作コンパイラを作ってみたり学んでみたりしている人の参考になればうれしいです．

このプログラムについて，いくつかテストを書いたり実行結果を確認したりしていますが，誤りがあるかもしれません．
もし誤りを見つけた場合は，教えていただけると幸いです．

参考

• コンパイラ 第2版 著 辻野嘉宏 出版 オーム社 ISBN978-4-274-22472-0 C3055