C言語完全に理解したい２ または小学校におけるポーランド記法の是非
お約束
C言語なんもわからん≒C言語のコンパイラ書ける
C言語完全に理解≒ズルすればC言語のコンパイラ書ける
構文解析
プログラミング言語の処理系というのはいってしまえば構文解析器、横文字で言えばパーサーだ。構文解析器というのはって…なるともう僕には手に負えないので浅い理解でいうならば文章の構造を解析するものである。解析結果は構文木という木構造に保存される。自然言語ならいざ知らず、よく書かれたプログラムは仕様上、解析するにあたりなんのあいまいさも残さない。というか曖昧だったらコンパイラがエラーを吐く。*** is ambiguousとかね。
簡単な例
プログラム言語でもなんでもないもので申し訳ないのだが、
40 - 32 / 2
という式をどう解釈するだろうか？計算の順序によって4、4!の2種類の答えが出てきてしまうが算数的には24のみが答えだ。もっともこれは記法の問題であって、演算子を後ろに持ってくる記法
(40 (32 2 /) -) = (40 16 -) = 24
だったらもはや間違うはずがない。まあ別に
40 - (32 / 2) = 40 - 16 = 24
と解釈しても間違いようがないのだが。重要なのは数式をどのように還元していくかということだ。自然言語に主語とか述語があるように、そして主語とか述語が最終的に単語に分解されるように、数式も要素に分解して正しく構造を解釈しなければいけない。四則演算と単なる数の範囲ならば、因子と演算子に分解すればよろしい。
ステップ１ 多項式を単項式に分解する
足し算、引き算を含む多項式を単項式の足し算、引き算に分解する
ステップ２ 単項式を因子に分解する
足し算、引き算を含まない単項式(a * b とか)は因子の掛け算に割り算分解できる
ステップ３ 因子を解釈する
因子とは12とかの数字だったり、多項式をカッコで囲ったものである。多項式が出たらやり直し、全部数になったら無事終わり。
とこのように品詞分解をするように丁寧にやっていけばルール通り解釈できて、演算子を後ろに持ってくる記法に変換することもできる。
ちなみに演算子を前に持っていくこともできる。
(- 40 (/ 32 2)) = - 40 16 = 24
最初に出てきた構文木というのは(40 (32 2 /) -)とか(- 40 (/ 32 2))みたいなものが典型的なものである。えっ、どこが木？
バッカス・ナウア記法
こういうルールのある言語を体系的に記述できるのがバッカス・ナウア記法(BNF)である。BNF風に多項式を記述すると
FORMULA ::= TERM *( '+' TERM | '-' TERM)
TERM ::= FACTOR *( '*' FACTOR | '/' FACTOR)
FACTOR ::= NUMBER | '(' FORMULA ')'
ルールは他のところを参照してほしいのだが、この記法にしたがってFORMULAを展開していくと、四則演算とNUMBERだけの式に展開できるのがわかるだろうか。次回はこの記法とboost::spirit::qiについて書く予定。
参考資料