読者です 読者をやめる 読者になる 読者になる

いつ俺〜いつから俺ができないと錯覚していた?〜

学生ブロガー。大学院でプログラミングを専攻している。日本のプログラミング教育に疑念を抱く。

コンパイラの仕組みをサルでもわかるように説明する

プログラミング

f:id:shun_prog0929:20160315002519p:plain

 

みなさん、プログラミング言語を使ったことはありますか?

現在、様々なプログラミング言語が存在し、それらは多様なソフトウェア・アプリケーションの開発に用いられています。

しかし、そんなプログラミング言語がどのようにして動いているのか、知っている人は少ないような気がします。

そこで今回はプログラミング言語が動く仕組み、つまりはコンパイラの仕組みを、わかりやすくざっくりと説明していこうと思います。

 

 

プログラミング言語が動くということ

プログラミング言語が動くためには

僕たちはプログラミング言語を使ってプログラム(ソースコード)を書きますよね。

その書かれたソースコードは、そのままではただの文字の並び(文字列)です。

文字の並びのままでは何がどうなっているのか、コンピュータが理解できません。

そこで、これをコンピュータが理解できる形にしていくわけです。

ですから、「プログラミング言語を動かす」というのは「ソースコードをコンピュータに理解させる」こととほぼ同じ意味になります。

 

動作のイメージ

ここではイメージをわかってもらうために次のような四則演算がどのように動くのかを見ていきたいと思います。

 

1+2+4/2

 

非常に簡単な四足演算であり、人間である僕たちはこの結果が5であることが簡単にわかります。

しかし、コンピュータはこの文字の並びのままでは、計算結果が5になるということがわからないわけです。

そこで、この文字の並びが意味することをコンピュータに理解させていくわけです。

 

ここでコンピュータに理解させなくてはいけないことは次のようなことです。

 

  • 「+」という記号は、左側の計算結果と、右側の計算結果を足す
  • 「/」という記号は、左側の計算結果から右側の計算結果を割る
  • 割り算の方が、足し算よりも先に計算される

 

こんなところですね。

そこで、足し算を見てみると、例えば「1+2」なら次のようなイメージで動きます。

 

f:id:shun_prog0929:20160309144829p:plain

 

  1. 「+」の左側を見にいき、1という値を保存
  2. 「+」の右側を見にいき、2という値を保存
  3.  2つの値を足して、結果を保存

 

このようにすることで、コンピュータは足し算を理解するわけです。

割り算も同じようにします。

 

次に問題になるのは、足し算と割り算があったときに、「割り算を先に計算する」という部分です。

これは、足し算と割り算の計算の順番を意識して、動作を決めておきます

例えば、「2+4/2」を見てみると次のようになります。

 

f:id:shun_prog0929:20160309150621p:plain

 

  1. 「+」の左側を見にいき、2という値を保存(足し算の左側の値)
  2. 「+」の右側を見にいき、「/」の処理へ
  3. 「/」の左側を見にいき、4という値を保存(割り算の左側の値)
  4. 「/」の右側を見にいき、2という値を保存(割り算の右側の値)
  5. 2つの値で割り算を行い、結果を保存(足し算の右側の値)
  6. 2つの値で足し算を行い、結果を保存

 

このようなイメージで処理が行われていきます。

ここでは基本的な四足演算を例に挙げたので、電卓のような感じになっていますが、これに対して色々な機能を足していけばプログラミング言語となるわけです。

少し、イメージが湧いてきたのではないでしょうか。

 

それでは、もう少し詳しく、プログラミング言語が動く工程を見ていくことにしましょう。

 

コンパイラの処理の流れ

全体の流れ

コンパイラは次のような流れで、ソースコードを処理しプログラムを実行します。

 

f:id:shun_prog0929:20160309154854p:plain

 

 少し難しそうな用語が並んでいますが、聞いてしまえば「なんだ、それだけのことか」となりますので安心してください!

一つ一つ見ていきましょう。

 

字句解析

字句解析はプログラミング言語が動く上で、最初に行われるステップです。

ここでは何が行われるのかというと、ただの文字の並びであるソースコードから、意味のある言葉の単位に分割していくんです。

例えば、次のような足し算があったとします。

 

1+2

 

この時、意味のある単位に分割していくので

 

「1」「+」「2」

 

というように分割されます。

このような分割されたものを字句(Token)と呼び、次のステップである構文解析でこれを使って次の処理を行うわけです。

この字句解析を行うプログラムのことを、字句解析器(Lexer)と呼びます。

 

  • ここでのポイント!

字句解析では、ソースコードを意味のある言葉の単位(字句)に分ける

 

構文解析

構文解析は、先ほど作った字句を、意味がわかるように木の形を作っていく工程です。

どのようなことか、例で見ていきましょう。

先ほど字句解析で作られた字句が次にようにあります。

 

「1」「+」「2」

 

これらの字句を見て、足し算の形を表す次のような木を作るんです。

 

f:id:shun_prog0929:20160309165447p:plain

 

なぜこのような木にするかと言えば、機械的に処理しやすいからです。

この形になれば、最初に説明したイメージのように

 

「足し算の記号が来た→左側を計算しにいく→右側を計算しにいく→それらを足す」

 

という自然な流れで処理できますから。

ここで作られた木を構文木(Syntax Tree)と呼びます。

実際のプログラミング言語の中では、意味を理解するのに必要な情報だけを抽出した抽象構文木(AST:Abstract Syntax Tree)がよく使われますね。

また、この構文解析を行うプログラムのことを構文解析器(Parser)と呼びます。

 

構文解析結果の構文木を次の実行コード生成で用いることで、実行できる形式にするわけです。

実は、この構文木を元にしてそのまま実行するものもあるのですが、性能の面でコード生成が行われることが多いです。

 

  • ここでのポイント!

構文解析では、字句を意味がわかる木の形(構文木)にする

 

実行コード生成

実行コード生成は、構文解析の結果である構文木を元に、コンピュータが理解できる言語を作るステップです。

それは機械語であったり、なんらかの中間コード(バイトコード)であったりします。

ここでは、簡単にわかってもらうためにスタックを用いた実行を例に挙げて見ていきます。

この説明のために、スタックについて軽く触れておきますね!

 

【準備】スタックについて

スタックは、コンピュータで使われる構造の一つで、格納していったデータを新しいものから順番に取り出していくものです。

例えば、こんな感じです。

 

f:id:shun_prog0929:20160309180036p:plain

 

このように、底がある穴のようなものをイメージしてもらって、そこにどんどんデータを積み重ねていく

積み重ねていくので、取り出すときは一番上からしか取り出せない

そんなイメージを持ってもらえばいいです。

ここで、スタックにデータを格納することをPUSH、データを取り出すことをPOPと言います。

 

実際の実行コード生成

それでは準備が整ったので、実際の実行コード生成の説明をしますよ!

ここでは先ほどの木を順番に見ながら実行コードを作っていきます。

先ほど作った木を順番に見ていきますね。

 

f:id:shun_prog0929:20160309144829p:plain

 

まず「+」という記号が来たので、左側を見に行きます。

すると、「1」という値があるのがわかります。

このとき、実際に計算をすることを考えると、値を保存しておかなくてはいけません

そこで、「PUSH 1」という命令を作って「1」を保存できるようにします。

同様にして、右側を見ると「2」という値が来ていますから、「PUSH 2」という命令を作ります。

最後にそれらの値を足す「ADD」という命令を作ります。

 

出来上がった実行コードはこんな感じになりますね。

 

1: PUSH 1

2: PUSH 2

3: ADD

 

そしてこのコードをコンピュータが理解し、実行するわけです。

この場合は、

 

1: 「1」をスタックに格納

2: 「2」をスタックに格納

3: スタックから値を2つ取り出し、それらを足して結果をスタックに格納

 

というように実行されるわけです。

 

  • ここでのポイント!

実行コード生成では、構文木を使ってコンピュータが理解できる言語を作る

  

 

このような流れで、プログラミング言語は動いています。

 

まとめ

今回は、コンパイラの仕組みについて、簡単に紹介しました。

僕たちが使っているプログラミング言語も、誰かが動くように作っていて、それがあるからこそソフトやアプリを開発出来ているんですよね。

そんな技術の基盤部分に少し触れてみるのも面白いですね。