kmizuの日記

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

構文解析歴20年近くになりました

まえがき

 タイトルが一体何言ってるんだお前は、という感じのものなのですが、初めて構文解析器ぽいものを書き始めてから、たぶん20年くらい経ったかなくらいの意味です。私を知っている方はご存知かも知れませんが、修士~博士にかけての私の研究テーマは、Packrat Parser/PEGで、博士論文もそれ関係でした

 で、博士号取った後、査読付き論文は一本も出していないのですが、中田育男先生の、ISO-Rubyパーザの試験実装をお手伝いしたり、なんだかPEGや構文解析に関する論文の査読をしていたら、去年からプログラミング研究会の論文誌編集委員になったりしています。最近、まともに(査読付き)論文書いてない私がこんな立場引き受けていいのかなーと思うものの、構文解析という分野はとてもニッチなので、査読できる人が少ないせいか、構文解析に関する論文は、私に査読の話が来ることがしばしばあります。

 私が型システムが専門とか言ったら、本当の専門の研究者に殴られそうなのでとても言えませんが(とはいえ、勘違いしてる人はいそう)、構文解析に関しては、知り合いのUさんとか複数名の研究者に「水島さんみたいな構文解析屋さん~」って感じで言及されることがしばしばなので、一応そこの専門性はあると言って良いのでしょう。凄く自信がないですが、たぶんそうです。

年表

  • 2000-2001年:

この頃は高校2年生で、記憶が確かなら、初めて数式インタプリタを書いた時期です。私にとっての構文解析元年とでもいいましょうか。要は、1 + (2 *3)とかのカッコ付きの数式をパーズして、解釈して計算するやつですね。今だとこの手のは2時間くらいあればかけるのですが、当時の自分は1週間以上かかった気がします。

確か、初めてJavaCCを使って、ミニ言語を作った記憶があります。関数定義があって、あとは整数とか配列くらいしか扱えないものだった記憶がありますが、一応ミニ言語と言ってよいものだった記憶。

情報特別演習Ⅰというものがあって、要はプチ卒論なのですが、このときに、初めてOnionを作りました。この時はOnionソース→Javaソースへのトレンスレータですが、この頃に、「ある程度複雑な文法」を自分で表現する能力は身につけた気がします。ついでに、コンパイラの授業でtiny-c作れって課題があったのですが、yacc + Cがめんどくさかったので、JavaCCでいいかと教員にたずねて、そのまま提出しました。

情報特別演習Ⅱで、2003年に作ったOnionをバイトコード出力をするようにしたのですが、この時にさらにOnionのパーザをいじくってあれこれしてました。同時期に産業技術総合研究所でバイトをしていて、プログラミング言語関係のプロジェクトをお手伝いしてました(この時はパーザは書かなかったかな)

卒論で、「演算子オーバーロードはマクロとみなすとよい」って主張で、左辺値型とかを型として扱える演算子オーバーロード機構を適当に考えたのですが、その時は具象構文考えるのがめんどくさかったので、Scheme上にその言語を実装しました。ただ、Onionの改良は続けていたので、より複雑なパーザを書くようになっていました。

  • 2006-2007年度: 筑波大学大学院博士前期課程時代。

確か、指導教員のM先生に、「Packrat Parserというのがあるらしいんだけど、論文読んで教えてくれない?」って唆されて、論文読んでゼミで発表したのですが、なんだか面白そうだなーと思ったのがきっかけで、その後Packrat Parsing/PEGの研究を始めるきっかけに。2007年度には、プログラミング研究会でカットに関する論文を発表したりとか、構文解析に関する既存研究をサーベイしたり。この時に、RubyのString Interpolationぽいものは字句解析レスの方が綺麗に書けるとかいう事を気づいたりしました。

  • 2008-2010年度: 筑波大学大学院博士後期課程時代。

D1とかD2の時は、やたらScala関係にのめり込んでいて。その分パーザに関する活動は停滞気味でした。この時にもうちょっと色々論文書いときゃ良かったと今になって思います。D3になって、PASTE'10に論文通したり、プログラミング研究会にまた別のPEG関係の論文通したりとかあったのですが、それD1、D2の時でも頑張ればできたのではと当時の自分にツッコミたい。

ちなみに、研究過程で捨てちゃったアイデアなのですが、カットの自動挿入をするときに、LL(*)ぽい手法でやるのとかは、今思えば突き詰めてやればいい感じの論文になったのではないかと思うことがあります(PEG -> REGEXに保守的に変換してから、DFAを構築して、∩をとるみたいな感じでやって、試験実装もあったのですが、どうにも中途半端なので、途中で捨ててしまった。割とLL(*)とアプローチは近かった記憶)。

幸い(?)PASTE'10の論文は,PEG関係の論文でそこそこ引用されたようで、その後数年間に渡って、時々、PEGやってる人から、私に問い合わせが来たこともあったりしました。というか、去年辺りの論文でも引用されてたりします。非常にニッチな分野ゆえでしょうね……。

  • 2011年度: 社会人1年目時代。

正直、新社会人になってストレスがめっちゃ高かったので、色々それどころじゃなかったですが、構文解析関係の催しは何度か出てた気がします。

  • 2012-2013年度: 社会人2~3年目時代。

実は、PEGに関するサーベイ論文を書いてほしいという依頼が某所から来ていたのですが、当時の自分は体調を崩しがちで、結局書いていた途中の論文は世に出ることがなかったのでした。この時に書いておけば、PEGをもっと布教できたかもしれません。

ただ、中田育男先生から、ISO Rubyの試験パーザーを書いているのだけど、色々わからないから教えて欲しいって話がメールで突如来たので、「あの中田先生から……」とビビったのを覚えています。で、ヒアドキュメントとか配列リテラルとか、めっちゃややこしいところの実装は私が代わりに書いてメールで送ったり説明した記憶があります。この時に、「あー、やっぱRubyの文法はウルトラ複雑だ」と再認識しました。

  • 2014年度~2018年度: 社会人4年目以降。

時々、国内の論文(英語のも含む)の査読を引き受けるようになったりしたのですが、前職のときも(今もですが)、割と査読のために学会出席するのも仕事(ということにしてもらえた)だったので、ちょくちょく出ていました。さすがに何を査読したのかとかは言えないですが、PEGに関する研究は未だに続いているんだなーとか実感してました。あとは、思いつきのMacro PEGをSwoPP 2016で発表したり(Macro PEG自体は思いつきにせよ、割と面白いと思っているので、査読通せる程度の論文書こうかなーと未だに思っているのですが、書けていません)。

  • 2019年度:

確か、この年の頭に、プログラミング研究会の編集委員(任期4年)に推薦されたのですが、今考えても、なんで推薦されたのかと不思議に思います。査読をちょくちょく引き受けたのが評価されたんでしょうか。正直、編集委員と言っても、年1回の開催以外は責任持つ必要あまりないので気楽なものですが、今までよりは責任が必要な立場になった気がします。

あと、構文解析の分野でとある知見がたまって来ていたので、論文を書こうと重い腰をあげたのですが、結局、色々別件で忙しくなったので、棚上げに。

  • 2020年度:

転職先(現職)の会社も、割と裁量が効くのですが、研修とか、色々教育方面で責任持たないとって仕事が増えて、それに忙殺されてました。ようやく、最近、その辺の作業負荷が下がったので、そろそろPEGに限らずですが、構文解析関係で持ってるネタでどっかの論文誌/国際会議に投稿しようかと思っています。

感想

びっくりする程、論文書いてませんね、正直。人生は短いので、明日からでもとりあえず、論文書いていこうというのが思ったことです。国内では、一部ですが、学会運営側の立場でもあるので、こういうのは不謹慎なのですが、国際会議のオンライン開催が増えれば、もうちょい気楽に国際会議に論文投稿できるのに、と思うことも(国内ならともかく、国際会議は旅費の面からちょっと会社に出してもらうのが厳しい)。

あと、細かすぎて書ききれてませんが、社会人になってからも、ほぼ毎年、なんか新しい言語の構文解析器は書いています。特に、PEGで割と大きな文法を記述するのにかなり慣れたので、yaccとかのLALRよりも、JavaCCとかのLLよりも、PEGの方がよっぽど早くパーザ書けるようになりました。