コンパイラ入門1 変換系と通訳系・後置記法・スタック

コンパイラとは

コンパイラとは、高級プログラム言語で書かれたプログラムを、機械向き言語に変換するためのプログラムです。

高級プログラム言語とは、人間が読みやすいように作られた言語で、BASIC、FORTRAN、COBOL、C言語、C++、Javaなどがあたります。

それに対して機械向き言語(機械語)とは、CPUが理解することのできる数字の並びで書かれた言語で、人間が読み取ることは困難です。

一般的に、ある言語で書かれたプログラムを他の言語に変換するプログラムを変換系と呼び、その元となる言語を原始言語、元のプログラムを原始プログラム、変換後の言語を目的語、変換後のプログラムを目的プログラムと呼びます。

コンパイラは高級プログラム言語を原始言語として、機械語を目的語とする変換系です。翻訳系と呼ばれることもあります。

変換系と通訳系

一旦原始言語にとって都合のいい仮想マシンを考えます。その仮想マシンの機械語に変換して解釈実行するシステムもあり、仮想マシンでの機械語を中間語と呼びます。解釈実行を行うプログラムはインタプリタ、または通訳系と呼ばれます。

仮想マシンの目的プログラムにコンパイルされ、インタプリタで実行されるような方式はコンパイラインタプリタ方式と呼ばれます。この方式では中間語があることによってコンパイラの開発が楽になることです、インタプリタの開発も必要になりますが、コンパイラ開発よりは楽です。ただ、目的プログラムの実行が遅くなってしまうという欠点があります。

コンパイラの他にインタプリタが必要となりますが、原始プログラムを目的プログラムに変換する場合も、何らかの実行時ルーチンが必要となります。このような原始プログラムのコンパイルから実行までに必要な全てのシステムをまとめて言語処理系、または処理系と呼びます。

原始プログラムで前段階の処理のような変換を行う変換系を前処理系と言います。

後置記法

後置記法とは演算子を後ろにおく記法です。普段私たちが使っている「a+b」ような記法は中置記法と呼ばれ、これに対して後置記法は「 ab+」のように演算子が後ろに置かれます。演算子を前に置く記法は前置記法と呼ばれますが、コンパイラで多く用いられるのは後置記法です。

もう少し例を見てみましょう、例えば次のような式があります。

a * b + c * d + e * f

これを後置記法に直すと次のようになります。

ab * cd * + ef * +

かっこでくくるとわかりやすくなります。

((ab*)(cd*)+)(ef*)+

スタック

スタックとは積み重ねという意味で、後に入れたものが先に取り出されます、スタックは入れ子になった括弧構造を解析するのに向いています。例を示します。

((()())(()))

これの括弧の対応を判断するには、括弧を左から調べていき、左括弧の場合はスタックにつみ、右括弧の場合はそれに対応する左括弧をスタックから下ろすということを繰り返せば良いです。

kakko

この括弧構造は木構造と見ることができます。すなわちスタックは木構造を解析するのに適しているということになります。

木構造によって中置記法から後置記法を得ることができます、例えば次の中置記法から後置記法へは次に示す構文木の丸の位置で出力することで変換できます。

a * b + c * d  →  ab * cd * +

中置記法を後置記法に変換するには、スタックも利用できます。これあ中置記法の式も括弧構造をとるからであり、例えば次の式はこのような括弧構造をとります。

a * b + c * d  →  ((a * b) + (c * d))

これは次のような流れで決定できます。

  1. 式の左端には左括弧、右端には右括弧がある
  2. *と+のような演算子が演算数(aなど)を挟んで並んでいる場合は、優先度の高い演算子を囲む括弧が存在する

もし同じ演算子が並ぶ場合は左結合性により、左側の演算子の優先度が高くなります。

中置記法を後置記法に変換する場合は、次のようなアルゴリズムで行います。

  • 演算数を読んだ時はそのまま出力
  • 演算子を読んだらスタックに積む
  • 演算子の右端の演算数を読み終わったらその演算子をスタックから下ろして出力

ここでの右側の演算数とは、一般的には式であることが多いです

a + b * c + d  → ((a + (b * c) + d))

この場合、最初の+の右側の演算数は(b * c)であるから、最初の+を読み終わったことがわかるのは、最初の+より優先度の低い2番目の+を読んだ時となります。

上記のアルゴリズムで考えると、次のようになります。

よって、次のような出力を得ます。

abc * + d +

次の記事はこちら

コンパイラ入門2 コンパイラの例・論理的構造・物理的構造