構文解析ハンズオン 関西出張版に参加させて頂きました

lang-impl.connpass.com

参加させて頂きました。

目次

良かった点

久しぶりにパーサ系のコード書きました。普段パーサ系のコードを書くことはあまりありませんが、時々必要に迫られるときがあるので定石やいろいろなテクニックや流行とか知っておくというのは大切な気がします。ハンズオンでいろいろ実際に書いてみるというのは自分にはぴったりでした。

あと、普段は再帰を使ってコードを書く機会が少ないので再帰を使うちょうどよい練習になりました。

苦労した点

Javaのコード書くのが久しぶりすぎてやばかった・・・
事前にJavaでハンズオンをするので環境を用意しておいてくださいと告知があったのですが、環境は構築していましたが、心と体の準備が追い付いていませんでした。
「Javaはもう何年も書いていないけどまぁなんとかなるだろう」と思っていたら、コード書くのと実行するのに戸惑いました。やはり事前に復習をしておけばよかったように思います。

構文解析について思ったこと

パーサを書く場合に気を付けないといけないポイントとして、パースをする際の入出力と内部状態をしっかりと把握しておく必要があると思います。
入出力と状態は、

入力

• 文字列

出力

• 解析結果(AST)
• 解析の成否(正常に解析できたのか、解析できなかったのか)

パーサ内部で保持する状態

• 現在の解析位置
• 入力文字列長

のような構成になります。

再帰下降的にパースする場合、各非終端記号に対応する関数は呼び出し元に

• 解析結果(AST)
• 解析の成否(正常に解析できたのか、解析できなかったのか)

を返す必要があります。

パーサを作る時に話がややこしくなるのは出力が複数存在するというのが１つの要因なのかなと思いました。
例えば戻り値をASTとした場合、解析の成否の情報は戻り値以外の方法で返す必要があります。

例外がサポートされている言語だと例外が１つの選択肢としてありますが、その場合例外クラスの設計をきちんと考えておく必要があります。
NULLやそれに類するものがある言語であれば戻り値のASTがNULLであれば解析異常とするのもありかなと思います。*1

Rubyで式の構文解析をしてみた

復習がてらハンズオンの課題の数式の解析コードを書いてみました。

gist.github.com

書いてみて気づいたこと

上記コードを書いていて気づいたのですが、入力が不正な場合の異常系に対応できていません。
非終端記号に対応する各関数は、解析異常時はnilを返すというポリシーで実装してみたのですが、再帰下降型で書くと想定していない文字が出てきたときに関数レベルではエラーハンドリングができないです。やはり字句解析フェーズがないというのはつらい気がする。
この辺は好みだと思いますが、個人的には先に入力を全てレキサーにかけるのが好きです。*2

再帰か状態遷移か

再帰を使わず状態遷移で書けば、適切に入力を弾けるので、仕様が小さくて手書きでパーサを書くのであれば状態遷移の方がいいようにも思いました。*3

再帰を使うメリットは何か考えてみたのですが、コードが短くなるというのはあるかも知れません。あと仕様が大きくなると状態遷移を考えるのがかえって面倒になる気がする。デバッグは状態遷移の方が断然しやすい気がしました。*4

今後やってみたいこと

パーサジェネレータを書く

パーサ系の実装についてはパーサジェネレータを書いてみたいです。*5
あまり難しくないはずですがBNFパーサを書かないといけないというところでいつも面倒くさくなって挫折してしまいます・・・あと、懇親会でPEGというものを教えてもらったので勉強してみると何か開けてきそうな気がしました。

関数型言語でパーサを書く

勉強会や懇親会でもイミュータブルとかパーサコンビネータの話題が挙がっていましたが、オブジェクト指向言語に囚われずに関数型の頭で何かパーサを書いてみたいです。

その他

ハンズオンの課題でJSONのパーサを書こうというのがありましたが、twitterで最近JSONのパーサに関して面白そうな論文が紹介されていました。

https://www.microsoft.com/en-us/research/publication/mison-fast-json-parser-data-analytics/

ざっと読んでみたところ

1. JSONニーズ高まってて大きなデータ扱うことが増えてきたけど、パース遅いので何とかせねば。
2. どうやってやるか→投機的解析と並列化で高速化してみた。
3. やってみた結果→いい感じ。CSVとかHTMLとかXMLにも適用したい。

といった感じでしょうか。rustのプロジェクトが実装になるのかな。

github.com

解析する際にDBのようにインデックスをつけたり、SIMDとビット演算を使った並列化したりするらしい。
大量のデータとか扱う機会があれば、SIMD・GPU・FPGAあたりをデータの解析を目的として勉強してみたいです。

感想

勉強会も懇親会も色々と勉強になることが多かったです。

参加して思ったのは、構文解析を短い時間で「理解する、誰かに教える」というのは結構難しいのではないかと思いました。勉強会への参加だけでなく予習とか復習が欠かせない気がします。
あと、勉強会だと主催者の方や周りの詳しい方に質問できるので、やはりこういった場があるのはいいなぁと感じます。

kmizu様、チューターの皆様、いろいろ教えてくださった参加者の皆様、会場を使わせて頂いたはてな様、ありがとうございました。

*1:もしかしたら複数のオブジェクトを返せる言語(goとか!?)というのはパーサを書くのに向いているのかもしれない。Rubyでも複数返せるけど、そういう場合はなぜかHashを使いたくなる

*2:パーサに渡った時点で不正な文字が登場しないことが保証されるので

*3:組込だとスタックサイズの見積りの事情により再帰が使えない場合がある

*4:再帰のパースをデバッグする場合はログをしっかりと入れておかないとデバッグが難しいです

*5:せっかく勉強会に参加して気持ちが高ぶったので