C#でパーサを作ろうと思ったら酷い目に合った話

こんにちは、skytomoです。
春、ですね。（なんやこいつ）
これは春休みに起こったことです。 春休みに何もせず、ただぼーっと生きてんじゃねえよとチコちゃんに叱られるのは嫌 *1 なので、何かしらプログラミングをしたりします。 長期休暇は、僕を何か作ろう、という気にさせます。いい機会です。

休みのうちの最初はAtCoderでスキルアップしてました。 しかし、途中でロジバンという人工言語が気になりだし、 「そうだ、ロジバンのパーサをC#で書こう」となり、実際にそれに取り組みました。 （ロジバンってなんぞという人は後で説明しますので、ここでは無視してください。） しかし、想像以上にそれは困難を極めました。パーサを作るためにしたことを列挙するとこんな感じです。

1. ロジバンはPEGというもので書かれていることを知る
2. C#でPEGを使ったパーサを生成するライブラリを探す
3. peg-sharpを使ってみる
4. Spracheを使ってみる
5. Antlrを使ってみる
6. Pegasusを使ってみる
7. 再びSpracheを使ってみる
8. 再びPegasusを使ってみる
9. Java Scriptのパーサにデータを渡す

話の前に基礎知識

本題に入る前に次のキーワードの説明をします。

1. パーサ
2. ロジバン
3. PEG

パーサってなに

パーサは、簡単に説明すると、文を解析して構文木を作るための機構です。 例えば1 + 2 × 3という式があります。これは((1) + ((2) × (3)))と同じで、構文木で表すとこんな感じになります。

また、「頭の赤い魚」という文は「(((頭の)(赤い))(魚))」という感じに解析でき、これを構文木で表すとこんな感じになります。

プログラミング言語は必ず構文木が1つに定まりますが、日本語などの自然言語は構文木が1つに定まりません。例えば、「頭が赤い魚を食べる猫」という文は以下の中村明裕さんのツイートのように様々な構文木を作ることができます。

頭が赤い魚を食べる猫（リメイク） pic.twitter.com/VUrw0gOWMn

— 中村明裕 (@nkmr_aki) 2018年8月18日

とはいえ、「頭が赤い魚を食べる猫」という文を見たら、「頭が赤い猫」なんて見たことないので、「頭が赤い魚」と解釈しますよね。また、「頭が猫」という解釈も普通しないので、あのツイートでいうと99%の人が2の構文木を思い浮かべると思います。

しかし、コンピュータは普通とか常識とかは分からない*2ので、 必ず構文木が1つに定まらないといけません。

ロジバンってなに

そこでロジバンです。 ロジバンとは計画的に作られた比較的新しい人工言語です。 ロジバンは機械と人間が融合した文法や単語が定められています。 ですから、ロジバンは構文木は必ず、1通りに定まります。 例えば、先程の「頭が赤い魚を食べる猫」の2番目の構文木と同じ文を作りたいなら、

lo mlatu noi citka lo finpe noi lo stedu cu xunre

というふうに書けば、必ず2番目の構文木と同じ解釈になります。*3

PEGってなに

ロジバンの構文を解析したいなら、Lojban parserというサイトに行けば簡単にパースしてくれます。 さて、そんなロジバンですが、構文（文法）のルールが定められています。そのルールはPEGという形式で書かれています。詳しくはWikipediaとか見ていただければ分かりますが、簡単に言えばBNFの拡張を繰り返した末路がPEGです。

いくらなんでも適当すぎる説明なので、（それにそもそもBNF（バッカス・ナウア記法）すら分からない人もいると思うので、）もう少し具体的に説明します。あ、PEG知ってるよ！という方はこの段落は読み飛ばしても構いません。

例えば「時刻」の文法をPEGで表すと、

Hour ← '0' [0-9] / '1' [0-2]
Minute ← [0-5] [0-9]
Time ← Hour ':' Minute

みたいな感じになります。 例えば、「12:34」は上の文法で受理されます。（文法通りであることを「受理される」といいます。） しかし、「12:345」は受理されません。これは「345」の部分がMinuteの文法に適していないからです。

PEGでは[0-9]で0から9までの数字を表したり、/で選択を表したりすることができます。正規表現でもこのようなことはできますが、PEGは正規表現とは違って、再帰的な文法（括弧の解析など）を解析することができます。

まあ、細かいことはさておき、PEGでロジバンを表現することができます。ここにPEGで書かれたロジバンの文法のURLを貼っておいたので、見たい人は見てください（理解できるとは言っていない。）

それで、PEGで書かれた文法を基に解析をしてくれるプログラム（パーサ）のソースコードを生成するプログラム（パーサジェネレータ）がJavaScriptのライブラリにあり、実際にロジバンの文法はJavaScriptで解析可能です。（先程、紹介したLojban parserはJavaScriptで書かれています。）

しかし、C#にはそのようなパーサはありません。 そこで、僕は「C#でロジバンのパーサを作るぞ！」となったのです。 これが地獄の始まりでした……

ロジバンはPEGというもので書かれていることを知る

ここから本題です。

まずそもそも、僕はPEGを知らなかったです。 yaccというのも知りませんでした。 BNFしか知りませんでした。

「ロジバンはBNFで解析できる」というのをどこかで見たので、BNFで解析しようとしたのですが、BNFで書かれたロジバンはありませんでした。 あとで調べて分かったことですが、BNFには欠点があるため実際には使われることは少ないらしいです。 （これを改良したEBNF（拡張バッカス・ナウア記法）なんていうのがあるらしいですが、それはまた別の話）

yaccはC言語の関数・符号を自動的に生成するコンパイラコンパイラです。 （コンパイラコンパイラとは文字通り、コンパイラを作成するコンパイラのことです。） ロジバンの文法はyaccでも書かれていますが、先程の通りC言語のためのものですので、C#には使えません。

こうして調べていくうちにPEGというものに行き着きました。

C#でPEGを使ったパーサを生成するライブラリを探す

PEGパーサなんてC#のライブラリなら探せば出てくるやろ、と思ったのは間違いでした。

peg-sharpを使ってみる

最初にたどり着いたのはpeg-sharp。 しかし、しっかり動かない…。 しかも、英語も日本語も文書がなさすぎる。

d.hatena.ne.jp

こういうのしか見つからなかった。

Spracheを使ってみる

次に流れ着いたのがSprache。 SpracheはPEGの文法とは違い、C#に直接コードを書き込んでパースするタイプのライブラリでした。 Spracheは日本語でも文書が多くありました。 しかし、うまくいきませんでした。 というかソースコードが大きくなりすぎてうまく作れませんでした。

Pegasusを使ってみる

そこでPegasusです。 PegasusはPEGっぽく書けます。 PegasusはソースコードとPEGっぽい文法のファイルを分割して書きます。

Antlrを使ってみる

しかし、途中でAntlr4のほうがJavaにも汎用できることを知り、Antlrに移行しました。 文書はSpracheより多く存在しました。 でも、作っている途中でAntlr4は左再帰ができないことに気づきました。

再びSpracheを使ってみる

ということで、再びSpracheに帰ってきました。 しかし、よく調べてみるとそもそもSpracheでも左再帰ができないことに気づきました。 そもそも、SpracheはPEGを完全に書き換えないといけないので、疲れます。 やる気を失いました。

再びPegasusを使ってみる

それで再びPegasusを使ってみたのですが、Pegasusも左再帰はできませんでした。 どうにかならないものかと、 Pegasusのリポジトリにあるissueたちを見ていたら、 驚くべきことに、こんなものを見つけました。

github.com

jbovensa 2017年1月30日

私はあなたに送ることができる非常に大きなPEGファイルを使っています。
私が理解している限りでは、それは多くの左再帰を持っています（私はそれを書きませんでした）

ほうほう、大きなPEGファイルね…、僕と同じ問題を抱えている人が世界にはいるんだなあ。 読んで見ると、どうやら、「バージョン3.0では動いたのに4.0で動かないんだけど」という問題のようでした。

otac0n 2017年2月9日

文法ファイルを送ってもらえますか？ご希望の場合は、私の電子メールjohn@gietzen.usに送信できます。ぜひご覧ください。

jbovensa 2017年2月26日

本当にありがとうございます。私は本当にあなたの助けによります。ベンサ

otac0n 2018年4月16日

https://github.com/mhagiwara/camxes.js/blob/master/camxes.js.peg にあるオリジナルのロジバンの文法に基づいて、私がユニットテストを作成したロジバンのパーサーを作成しようとしているのがわかります。

ふむふむ、ん？ロジバン！？

実はissueを書いたjbovensaさんはロジバンのパーサを作ろうとしているのでした。 まさか、世界で僕と全く同じことをしようとする人なんていないと思っていませんでした（笑）。 いや、なんで？って感じです。

結局のこのissueではjbovensaさんが自力で解決しているようでしたが、完成したソースコードはGitHubで公開されていませんでした。 なんだよ。

僕はotac0nさんが作ったPegasus形式のファイルを使って、C#のライブラリを作りました。 これが、CSharp Lojban Project Version 0.0でした。

Java Scriptのパーサにデータを渡す

しかし、otac0nさんが作ったPegasus形式のファイルはうまく作られていませんでした。 otac0nさんは、もともとロジバンに詳しくないただのPegasusの製作者だから、うまく動かなくても文句は全く言えないのですが、とにかくきちんと動作するように僕がどうにかしなければなりません。

それで、最終的にJava Scriptで解析してもらって、そのデータをC#が受けとればよくね？という発想に至りました。 先程、ロジバンでは既にJava Scriptで書かれたパーサが存在していることを書きましたよね。 「こいつにどうにかして渡して、解析結果をどうにかしてこいつから得ればいいぞ…！」 そう思ったのです。

これはうまくいき、結局最終的にはこの方法に落ち着きました。 C#で純粋には書かれていませんが、「まあいいんだよ、とりあえず動けば」という精神にまで疲弊していたので、お咎めはやめてください。 ここに至るまで、1、2週間？くらいはかかったと思います。

ソースコードはGitHubに、ライブラリはNuGetに公開しています。

github.com

www.nuget.org

もう書くのダルくなったんで、これでブログは終わりにします。 またね。

*1:ここでの「春休みに何もしない」というのは、バイトをせず、免許を取らず、資格を取らず、勉強をせず、AtCoderをせず、卒業研究に向けての準備もせず、ただ寝て食って遊ぶかTwitterをするだけの日々のことをさします。そんな、人生の無駄遣いはみなさんもやめましょうね。とはいえ、たまには何も積み重ねず、生産性もなく、思い出に残ることもなく、ただぐずぐずと消滅するだけの日を過ごすのもそれはそれで新鮮な1日かもしれませんけどね。

*2:正直言って常識なんていうのは、アインシュタインが言うように、「十八歳までに身につけた偏見のコレクション」だと思っています。お前が「常識、常識」なんて言っているのは、お前だけの「常識」だったり、お前らだけの「常識」だったりするかもしれません。だから、相手の常識がないと感じたらそれはあなたの常識が相手にとって非常識だったりすると疑ってみましょう。

*3:厳密に言えばロジバンは構文上は必ず一意に定まりますが、意味上は必ずしも一意に定まりません。例えば、merko（アメリカ）とpendo（友達）を連ねた「merko pendo」は構文上は必ず、{merko {pendo}}というふうにmerkoがpendoにかかりますが、意味上は「アメリカ人の友達」なのか「アメリカ的な友達」なのか「アメリカという国と友達」なのかは分かりません。