構文解析はプログラマなら誰しも一度はやったことがあると思います。しかし、構文解析には独自の用語がたくさんあります。
そこで、初心者に向けて用語の解説をしたいと思います。「非終端記号って何?」「トップダウンとボトムアップはどう違うの?」と疑問に思ってる方は必読です。
終端記号と非終端記号
終端記号、非終端記号とは、「置き換えが」終わった記号、終わってない記号のことです。まだ何のことかわかりませんね。wikiの例をみてみましょう。
S→Ax A→a A→b
この3行はそれぞれ「矢印の左側の記号を右側の記号へ置き換える」という構文を表しています。この「記号」たちの種類が「終端記号」「非終端記号」です。
この構文では、SとAは置き換えが起きていますが、aとbは置き換えが起きていません。だから、SとAが非終端記号、aとbが終端記号です。
構文解析の種類
構文解析したい文字列(入力)は終端記号の羅列です。
トップダウン構文解析は、Sという1文字の非終端記号を置き換えていき、入力と同じ形になれるかで正しい構文かを判定します。
たとえば上の例ではS→Ax→axとなるので、axという入力はこの文法において正しい構文です。また、bxもS→Ax→bxとなるので正しいです。
入力を順に非終端記号に置き換えていき、最終的にSになるか調べる方法を「ボトムアップ構文解析」と呼びます。
上の例では、ax→Ax→Sとなるので正しい構文です。
名前の由来
構文解析では通常、「構文木」と呼ばれる木構造のデータを構築していきます。この構文木は葉ノードが終端記号、節ノードが非終端記号となるように構築していきます。「トップダウン」では根ノードから葉ノードへ、「ボトムアップ」では葉ノードから根ノードへ向けて変換を行なっていくので、それぞれこのような名前となっています。
数式を構文解析してみる
数式を構文解析してみます。 以下ME:Multiplicative Expression(掛け算式)、AE: Additive Expression(足し算式)とします。
S→AE …(1)
AE→AE '+' ME | AE '-' ME | ME …(2)
ME→ME '*' primary | ME '/' primary | primary …(3)
primary→'(' AE ')' | Number | '-' primary …(4)
Number→(実数) …(5)
(実数の構文はここに書くには長すぎるので簡潔にしました)
(1)、(2)というのはどの遷移をつかって変換したかを示すために振った番号です。構文自体とは関係ありません。
たとえば 1 + 2は
S→(1) AE→(2) AE '+' ME→(2) ME '+' ME→(3) primary '+' ME→(4) Number '+' ME→(5) 1 '+' ME→(3) 1 '+' primary→(4) 1 '+' Number→(5) 1 '+' 2
と置き換えていくことで得ることができます。
もっと複雑な式も解析できます。が、上の変移をみてわかる通りとても長くなるので割愛します。
