構文解析ハンズオン 関西出張版に参加させて頂きました
参加させて頂きました。
目次
良かった点
久しぶりにパーサ系のコード書きました。普段パーサ系のコードを書くことはあまりありませんが、時々必要に迫られるときがあるので定石やいろいろなテクニックや流行とか知っておくというのは大切な気がします。ハンズオンでいろいろ実際に書いてみるというのは自分にはぴったりでした。
苦労した点
Javaのコード書くのが久しぶりすぎてやばかった・・・
事前にJavaでハンズオンをするので環境を用意しておいてくださいと告知があったのですが、環境は構築していましたが、心と体の準備が追い付いていませんでした。
「Javaはもう何年も書いていないけどまぁなんとかなるだろう」と思っていたら、コード書くのと実行するのに戸惑いました。やはり事前に復習をしておけばよかったように思います。
構文解析について思ったこと
パーサを書く場合に気を付けないといけないポイントとして、パースをする際の入出力と内部状態をしっかりと把握しておく必要があると思います。
入出力と状態は、
入力
- 文字列
出力
- 解析結果(AST)
- 解析の成否(正常に解析できたのか、解析できなかったのか)
パーサ内部で保持する状態
- 現在の解析位置
- 入力文字列長
のような構成になります。
再帰下降的にパースする場合、各非終端記号に対応する関数は呼び出し元に
- 解析結果(AST)
- 解析の成否(正常に解析できたのか、解析できなかったのか)
を返す必要があります。
パーサを作る時に話がややこしくなるのは出力が複数存在するというのが１つの要因なのかなと思いました。
例えば戻り値をASTとした場合、解析の成否の情報は戻り値以外の方法で返す必要があります。
例外がサポートされている言語だと例外が１つの選択肢としてありますが、その場合例外クラスの設計をきちんと考えておく必要があります。
NULLやそれに類するものがある言語であれば戻り値のASTがNULLであれば解析異常とするのもありかなと思います。*1
Rubyで式の構文解析をしてみた
復習がてらハンズオンの課題の数式の解析コードを書いてみました。
今後やってみたいこと
パーサジェネレータを書く
パーサ系の実装についてはパーサジェネレータを書いてみたいです。*5
あまり難しくないはずですがBNFパーサを書かないといけないというところでいつも面倒くさくなって挫折してしまいます・・・あと、懇親会でPEGというものを教えてもらったので勉強してみると何か開けてきそうな気がしました。
関数型言語でパーサを書く
勉強会や懇親会でもイミュータブルとかパーサコンビネータの話題が挙がっていましたが、オブジェクト指向言語に囚われずに関数型の頭で何かパーサを書いてみたいです。
その他
ハンズオンの課題でJSONのパーサを書こうというのがありましたが、twitterで最近JSONのパーサに関して面白そうな論文が紹介されていました。
https://www.microsoft.com/en-us/research/publication/mison-fast-json-parser-data-analytics/
ざっと読んでみたところ
- JSONニーズ高まってて大きなデータ扱うことが増えてきたけど、パース遅いので何とかせねば。
- どうやってやるか→投機的解析と並列化で高速化してみた。
- やってみた結果→いい感じ。CSVとかHTMLとかXMLにも適用したい。
といった感じでしょうか。rustのプロジェクトが実装になるのかな。
解析する際にDBのようにインデックスをつけたり、SIMDとビット演算を使った並列化したりするらしい。
大量のデータとか扱う機会があれば、SIMD・GPU・FPGAあたりをデータの解析を目的として勉強してみたいです。
