コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。
計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2*3″は、”1,2,+,3,*” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。
字句解析と構文解析
このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化、コード生成などが行われる。
C言語であれば、コンパイル前後には以下の処理が行われる。
- プリプロセッサ処理
↓(#の無いCコード) - コンパイル処理
- 字句解析
- 構文解析
- コード生成
↓(中間コード)
- リンク処理 ← ライブラリ
↓ - 機械語
字句解析と正規表現
字句(トークン)の切り出しでは、正規表現なども用いられる。
簡単な正規表現 . 任意の文字 * 直前の0回以上の繰り返し + 直前の1回以上の繰り返し [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。 (a|b|c) 丸カッコの|区切りのうちのどれか。 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*
構文解析の方法
構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は？ という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、
などが用いられる。
再帰下降パーサ
簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。
加減,乗除の式のバッカス記法(BNF)
exp_加減 ::= exp_乗除 '+' exp_乗除
| exp_乗除 '-' exp_乗除
| exp_乗除
;
exp_乗除 ::= DIGIT '*' exp_乗除
| DIGIT '/' exp_乗除
| DIGIT
;
DIGIT ::= [0-9]
;
練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、 (2) 式を読みやすくする空白を処理できるように してみよう。