コンパイラの概要

プログラムをするうえで、コンパイラはかかせません。 C言語やFORTRANなどのプログラム言語で書いた プログラムを実行するためには、 まず この コンパイラ に処理してもらわないといけません。 ここでは、コンパイラの 基礎知識を 御紹介します。


コンパイラの技術は、計算機のプログラムを人間に分かりやすい形で書いて、それを machine で 実行できるようにしたいという願いから 1950 年代に生まれま した。現在のソフトウエアのほとんどはこの「分かりやすい形」、つまりプロ グラミング言語で書かれていますので、かかせないものとなっています。 ソフトウエアが計算機で起動するためには、プログラムが計算機自身の言葉、 (これをアセンブリ言語といったり機械語といったりします。)になっていなけ ればいけません。 つまり、コンパイラとは、
プログラミング言語で書かれたプログラムを 計算機自身の言葉で書かれたプログラムに翻訳するソフトウエア、
つまり誤解を恐れずに言いますと、
ソフトウエアのためのソフトウエア
なのです。

コンパイラの仕組み

では、コンパイラの仕組みをご紹介しましょう。
プログラムの解析
字句解析
構文解析
意味解析
コードの最適化
まとめ

プログラムの解析
top

今言いました通り、プログラ ミング言語を機械コードに直すのが仕事ですから、コンパイラはプログラミン グ言語で書かれたプログラムの内容が分からなくてはいけません。この内容を 解析する段階は、字句解析、構文解析、意味解析の3つに分かれます。

字句解析
top

まず、プログラムの文字の並び、文字列を 意味のある単語(これをトー クンと言います。)に分ける処理を行います。これを字句解析と いいます。これは、日常の言葉では、「私は太郎です」を「私」「は」「太郎」 「です」に分けることに対応します。 具体的には、 「x:=y*3+1」というプログラムの文を、
  1. 識別子 x
  2. 代入記号 :=
  3. 識別子 y
  4. 乗算符号
  5. 数 3
  6. 加算符号
  7. 数 1
に分けます。

構文解析
top

次に、トークン間の関係を調べます。これを構文解析といいます。 図を見て下さい。これは「x:=y*3+1」に含まれる単語間の 関係を示しています。これを構文木といいます。 構文木は次のような式としても書くことができます。 「(+ (* y 3) 1)」 この書き方をポーランド記法、といいます。 ちなみに プロセッサコンテストで作るコンパイラは、 このポーランド記法で書くプログラム言語、 スキーム(Scheme)用のものです。 構文解析では、「x=x * 5)」のように 括弧がきちんと対応していない場合など、 文の構造がおかしい場合、チェックします。 「私はです太郎」がおかしいのをチェックすることに対応します。 つまり、普段「文法的におかしい」と思う場所のエラーの対処です。
ではこの構文解析をどうやって自動的に行なうか、ですが、 まず、文法を書いてやることが必要です。 これは日常の言葉で「太郎が走る」を分析する時に 「文→名詞節+動詞節」という文法を考えるのと同じことです。 例えば次のようなものです。
expr-->expropexpr
expr-->(expr)
expr-->-expr
expr-->id
op-->+
op-->-
op-->*
op-->/
ここで、expr,op は プログラム及び その部分です。 例えば、『(y+1)*3』は、1番目の規則で (y+1) 、3 が expr 、「*」が op に分類されます。7番目の規則で「*」という文字がop であることが 正しいということが分かります。同様にして全ての文字が文法にあっている ことを確かめる過程で、同時に木を作っていくわけです。

意味解析
top

最後にプログラムに意味的な誤りがないかチェックします。 これを意味解析といいます。 プログラムでは、変数x が 整数なのか、小数も表せるのか、 あるいは文字なのか、事前に設定することがあります(これを型設定といいます)が、 「xは整数」と最初に宣言しておきながら、「x=1.5」と プログラムすることは、宣言にうそがあったこと になります。 「私は人間です」と言っておきながら、「私の身長は20kmです」 と言うようなものです。 意味的な誤りというのはこういうものです。

中間コードの生成
top

いろいろな計算機、つまり機械コードが違うもの について一つ一つ別々にコンパイラを書くのは 大変だ、という要望に対して答えるのが この中間コード生成です。
中間コードとは、仮想的な計算機の機械コード、 にあたるもので、 簡単に他の計算機の機械コードに変形できる言葉 と考えて下さい。

プロセッサコンテストでは 実装しないグループもあるようです。

コードの最適化

解析のあと、中間コードに直しているか、あるいは構文木の 状態になっていますが、これをただ自動的に機械コードに直しますと、 無駄な操作を行うコードを作ってしまうことがあります。
たとえば、
「x=1;」
「 x=2+y;」
という2つのプログラム文が 連続していた場合、2番目の文でその後のxは全て決まってしまいますから、 始めの「x=1;」は意味がありません。 ですから、この1番目の文「x=1;」に対する機械コードを残しておく 必要がなくなりますので、削除します。
その他、様々な冗長なコードを削除あるいは編集することで 出力する機械コードを短く、つまり結果として実行をspeed upする ことができます。これをコードの最適化といいます。

まとめ
top

以上がコンパイラの仕組みの枠組です。 実例として、プロセッサコンテストでどのような実装が されたかは、こちらのページでご覧下さい。

また、萩谷先生による計算機言語論の virtual 授業では、 さらに詳しい説明がされています。ぜひ御覧下さい!

参考
top

A.V.エイホ、R.セシィ、J.D.ウルマン 共著、
原田賢一訳、
『コンパイラI,II』サイエンス社