yaccで作成した構文解析ソフトを加工して「骨組み(スケルトン)に肉付け」する形でコンパイラを作っていく。
例えば、文法の一部の、
行 = 行番号 + 命令群
命令群 = 命令 + 「：」 + 命令群 または 命令群 = 命令
と言う部分について、
構文を定義したyaccソースコード部分に追加で、その構文に対してどのような処理をするのかを書くことが出来る。
しかし、解釈した構文の処理は、コンパイラが出力すべき命令語の順番になっていない。
上記の例の場合には大きく順番が狂うことはないが、数式の処理の部分だと演算子の優先順位や括弧の処理で大きく順番が狂う。
これを解決するには”構文木”という二分木のツリー構造を使う。
「行 = 行番号 + 命令群」の場合、
ツリーの根元が「行」で、ツリーの左下に「行番号」、ツリーの右下に「命令群」を格納する。
「命令群 = 命令 + : + 命令群」の場合、
ツリーの根元が「命令群」で、ツリーの左下に「命令」、ツリーの右下に次の「命令群」を格納する。
そして、
行 ---+--- 行番号
|
+--- 命令群 ---+--- 命令
|
+--- 次の命令群 ---+--- 命令(2)
|
+--- (以下省略)
というようにツリー構造を作成していく。処理を進めるたびにツリー構造が伸びていき、ソースコード全部を構文解析ソフトが処理し終えると、1つの大きなツリー構造ができあがる。
このツリー構造に対して、根元から左方優先探査をすれば、コンパイラが出力すべき処理の順番に結果を得ることができる。(そういう仕組みでyaccが作られている。)
上記の場合、
1番目 行
2番目 行番号
3番目 命令群
4番目 命令
5番目 次の命令群
6番目 命令(2)
7番目 (以下省略)
という順になる。
この順序で、コンパイルしてコード生成して行けば良い。
例えば、
1番目 行 に対して、特に出力は無し
2番目 行番号 に対して、ジャンプ命令用にラベルを出力(数値の妥当性もチェックする)
3番目 命令群 に対して、特に出力は無し
4番目 命令 に対して、コード出力
5番目 次の命令群 に対して、特に出力は無し
6番目 命令(2) に対して、コード出力
7番目 (以下省略)
というようになる。
実際には「命令」と「命令(2)」の部分は、もっと細かいツリーになっている。
最終的に何処まで細かく落とし込むかというと、アセンブリ言語の命令語に近いところまで細かくする。
アセンブリ言語の命令というのは、
代入 レジスタ, 数値
加算 レジスタ, 数値
ジャンプ アドレス値
のような単純処理の命令である。
—
続く。