kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

「構文解析ハンズオン」を開催しました(2017/07/01)

今まで、あまり見たことがない(一般エンジニア向け)勉強会で、かつ、これを学ぶことは実用上とても意味があるテーマの一つに「構文解析」があります*1

たとえば、Webアプリケーションにおいて、ユーザの入力に大して何らかの構文的制約をつけてバリデーションをする機会は多いですが、正規表現による簡単なチェック(あるいは、滅茶苦茶複雑な正規表現を作って色々な入力のバリエーションに対応する)や、よくわからない緩いバリデーションで済まされることは多いように感じます(自分の開発経験というより、Webアプリケーションのフォームのバリデーションの仕方などを見ての感想です)。

正規表現によるバリデーションで十分なことも多いので、それをむやみに否定するものではありませんが、入力が(原理的に)正規表現でバリデーションできない場合や、可能だが正規表現が爆発するケースだと、正規表現が不適当なこともしばしばです。

個人的には(文脈自由な)構文解析ができる技能があれば、もっと精度の高いバリデーションができるのに、と思っていたこともあり、構文解析の基本を学ぶ勉強会を開催してみることにしたのでした。

構文解析ハンズオン - connpass

というわけで、昨日に開催したのが、↑の勉強会です。ハンズオン形式で、1桁整数の構文解析JSON構文解析を学ぶ、というものです。

大学における構文解析の授業では、手書き構文解析の方法として、LL(1)のようなものを再帰下降パーザで模倣することが非常に一般的ですが、昨日の勉強会では、時間的制約( 全部で6時間程度しかない)や、自分のPEG推しという趣味もあって、PEGベースの再帰下降パーザを学んでもらう構成にしました。

参加者層は本当に構文解析初学者が多いので、PEGという言葉をだすと混乱するだろうと思われたため、そういう言葉を出さずに、PEG的な発想をそのまま教えるというアプローチを取りました。結果としては、短い時間でJSONのような再帰的構造を持つ言語の構文解析までたどりついてもらうには、それなりに有効なアプローチだったと思います。

反省点については

  • 資料を準備する時間が十分でなかったため、当日、大量のアドリブを入れて説明をする必要があった
  • 自分の構文解析器をテストするように、用意したプログラムを修正してもらうというやり方は遠回り過ぎた
  • 参加者層に対する要求である「Javaが普通に書ける」が曖昧過ぎて、参加条件を満たさない方も参加してしまった
    • それらの方に対する苦情というより、それだとハンズオンで構文解析を学んでもらうことが難しいので、結果的に申し訳ないことになってしまったなという意図です
  • 資料の細かいミスが結構あった
  • , etc.

と色々あるのですが、構文解析の基本をおさえてもらうという目的はある程度達成できたかなと思っています。

興味深かった(一部の方の)反応として、わかったか自信がないけど、心を無にすれば書けたという趣旨の発言が見られたことです。BNFからPEGベース手書きパーザへの(ほぼ)機械的な変換方法を提示するというやり方だったからだと思うのですが、PEGベースのパーザの単純さ、理解の容易さがそれに貢献したのではないかなと思います。

構文解析をテーマにした勉強会については、当分はしないと思いますが、その他の、「(情報系の)学部だと普通にならうけど、自習がやや難しい」系のテーマについて、積極的に教える機会を作っていきたいなと思っています。

*1:自然言語構文解析を主に指します