今週末から開催される技術書典18で、新刊「LR parser入門」を頒布します。 オフラインでも参加するので6/1(日)は池袋・サンシャインシティにいます。
電子版(PDF)は5/31からこちらで購入できるようになる予定です。
本書の内容
A5で62ページの書籍ということで技術書としては薄め、LR構文解析の本としてはそこそこの内容量になっています1。 「LR parser入門」というタイトルにあるように、一冊まるまるLR構文解析とLR parserに関する書籍です。
目次からわかるように全体は「LR parser概論」と「効率的なLookaheadの計算」の2章からなります。
第1章の「LR parser概論」では主に以下の内容を扱います。
- 言語、文法、オートマトン、parserの関係について説明をする("Language, Grammar, Automaton, Parser")
- 簡単な文法と複雑な文法を例に、それぞれのparserの動きを考察する("LR parserの仕組み")
- 与えられた文法定義からLR parserを構成する("LR parserの構成方法")
- SLR, Canonical LR, LALRといった様々なLR parserの特徴を紹介する("LR parserの種類")
どの内容もいわゆる教科書的な本には書かれている内容です。 しかしそれらの教科書的な本は丁寧な説明をしていますが、全体として技巧的な印象をうけます。 そこで本書ではLR 構文解析および LR parserの動作原理や背後にある考え方をできるだけ説明するように心がけました。 教科書には書かれていない行間を埋める試みをしたといってもいいかもしれません。
第2章ではLALR parserのLookahead集合を効率よく計算するのに不可欠なアルゴリズムを取り上げます。 具体的には「Efficient computation of LALR(1) look-ahead sets」という論文の解説をします。 最近数名の知人が素朴なLALR parser generatorの実装をしたと聞いたので、その次に取り組むことになるであろうLookahead集合の効率のよい計算について、参考になる情報をまとめておこうというのがこの章を書いたモチベーションです。
この論文は目的こそLookahead集合の効率的な計算というニッチな内容ですが、LR parserにおける状態間の依存関係や、LR parserの状態遷移がグラフ構造になっていることなど、LR parserの状態遷移をどのように解析すればよいかという視点を与えてくれる論文でもあります。
最後に
ひょんなことから人生で初めて同人誌を出すことに出すことになりました。 ブースの運営など初めてのことだらけで当日はワタワタしている可能性もありますが、あたたかい目で見守っていただけると幸いです。
では、当日会場でお会いしましょう！
