構文解析ってなんだろう

　そもそも構文解析ってなんでしょうか？もしかしたら抹茶味かもしれない・・・という冗談はさておき、プログラムを実行する時にかなり重要な役割を果たしています。よく考えると、高水準言語のプログラムというものは本来ただの文字が連続しただけの存在であるはずなのに、コンピューターがこれは「if文」だとか、「for文」だとか認識して、レジスタやメモリが頑張って演算してくれるのはすごいことだと思いませんか？。メモ帳ソフトウェアに「printf("hello world\n");」と記述したものであっても、拡張子を.cとかにして、gccコンパイラに渡してあげたら、動作が同等なものを機械語として出力し、hello worldを標準出力することだって出来るわけです。つまり、メモ帳ソフトウェアに書いただけのものなのに、コンピューターに命令をすることが出来るわけです！。これを支えているのが、コンパイラに組み込まれている仕組みなのです。その中で、先ほども述べた、ただの連続したテキストに対して、コンピューターがこれは「if文」だとか、「for文」だとか認識できるようにしてあげるのが、構文解析だということです。

　ざっくりと構文解析の重要性について書きましたが、では実際に構文解析をしたい！となった時に何をすればいいのでしょうか。一番簡単な方法は「yacc(yet another compiler compiler)」などの構文解析のためのパーサージェネレータを使ってしまうということです。パーサージェネレータを使えば、この後出てくるようなクロージャー展開などの恐ろしい処理を自力で実装する必要はないですし、各々のプロジェクトにおいて構文解析の開発自体はあまり重要視しない場合は、パーサージェネレータを使ってしまうのが良い選択肢と言えます。反対に、構文解析そのものを実装してみたい！というならば、楽しい楽しい構文解析処理の実装の世界に足を踏み入れ、どんどん沼にはまっていくことも良いかもしれません。（ただし、泥沼にははまらないように気をつけてください）!

LR構文解析

　LR構文解析ってなんでしょうか。本来は木構造などアルゴリズムとデータ構造に関する話を厳密に行わないといけないのですが、今回は省くとして、簡単に言えば「各構文が終了したタイミングで○○構文だ」と解析していく方式です。LL(k)文法が定義文法の最初のk個のみを見て文法を予測しつつ決定しなければならないのに対して、LR(k)文法は文法が確定するまで、つまり予測なしに構文解析を行うことができます。このため、一般的に強力な構文解析とされています。

　LR構文解析において、先読みをしないLR構文解析のことをLR(0)文法と呼びます。この手の○○法において(LL文法とか)、かっこの中に入る数字(kであらわされる)は先読みの個数のことを言います。

　このLR(0)文法も十分強力なのですが、それでも弱点があり、構文解析表において還元が衝突してしまうということが一部文法において起きてしまいます。すなわちLR(0)文法ではないということになり、LR(0)文法では解析不可能となってしまいます。このため、より強力な構文解析が必要になりますね。

　その手法としてSLR構文解析とか、LALR構文解析などが存在しますが、私は今回（何を思ったのか）、最強の構文解析手法であるLR(1)文法を採用することにしました。つまり、一つだけ先読みをするということです（ただしこの最強の構文解析手法でもC++言語だけは構文解析ができないようです。恐るべしC++)
、、、と言ってもLR(1)文法がLR(0)文法に破壊的な変更がなされているわけではありません。大まかにいえば、LR(0)文法にクロージャー展開処理で先読み記号を追加するということと、決定性有限オートマトンから構文解析表を作成する過程で、還元処理を追加する根拠を先読み記号に変えているという工夫がなされています。あとは、LR(1)文法は作成した構文解析表がかなり巨大になってしまう問題があります。だいたい3~5個のBNF構文を定義しただけで、出力される構文解析表はかなり大きいものになってしまうということを覚えています。（そのための対策としてあるのが、実はLALR構文解析なのです。こういった経緯から、多くのプログラミング言語がLALR構文解析を採用することになっています）

LR(0)文法の概要

アイテム集合の構築、クロージャー展開

　LR(0)文法においてもLR(1)文法においても、アイテム集合という存在はかなり重要な存在になっています。アイテム集合の後に作成するDFA・決定性有限オートマトンの構築にも直結するものです
アイテム集合は、簡単に言えば「定義された文法の状態遷移をまとめたもの」なんですが、アイテム集合の構築がかなり厄介です。構築には再帰的な処理を組み合わせなければなりません。深さ優先探索によく似た処理になるのですが、適切にアルゴリズムを実装する力が必須です。先読み記号といった処理を追加しようとすれば、まあまあの地獄を見ます。適切に収束させるアルゴリズムを構築しないと、無限の計算時間がかかるアルゴリズムが完成してしまいます！

ここで、次の文法よりアイテム集合を構築してみましょう。

E→E+B
E→E＊B
E→B
B→Num

　BNFっぽい記法だな、と思われるかもしれませんが、実際BNF記法とかなり酷似しています。EとBは非末端記号,Numは末端記号です。0,1,2,3・・・のように具体的な数字を用いずにNumとして定義するのは、LR構文解析表が巨大になりやすいという性質を回避するためです。

　LR(0)文法におけるアイテム集合の展開とその過程でのクロージャー展開と呼ばれる処理は図解した方が理解しやすいかもしれませんから、構築する過程の簡単な説明画像を掲載しておきます。クロージャー展開は、図において、黄色文法から緑色文法を追加する処理のことを指します。お堅く言えば、[X→a・YB]という状況があるとき、[Y→・y]という文法を、集合が収束するまで追加しなければならないということです。次の図表において、Sは開始記号です。

DFA・決定性有限オートマトン

　「オートマトン」という言葉、なんとなくかっこいいですよね。実際、計算機科学においてはかっこいい存在、つまり重要な存在になっています。状態による遷移を結構簡単に表現することができます。コンパイラにも欠かせないものとなっています。（いわゆる高水準プログラミング言語は、文字列のつながりの関係性に注目、つまり形式文法の解釈をしなければならないという性質があるからかもしれません）。アイテム集合を求められていれば、比較的容易に変換することができます。実際、私が実装に苦戦したのはDFAの構築よりアイテム集合の構築でした。

これを表に書き起こすというアイデアは、今後の構文解析において良いアイデアとも言えます

　ここで構築した表は、この後、シフト項や還元項といった情報を追加して、実際に構文解析を行えるように加工していくこととなります。

まとめ

　LR構文解析表を作成する準備として、アイテム集合をクロージャー展開を用いて作成した後、決定性有限オートマトンの構築が必要ということです。

参考文献

コンパイラ入門 -構文解析の原理とlex yacc C言語による実装-

山下義行 , サイエンス社 , 2008年

LR構文解析への入門 ~DFAの構築~