インタプリタの仕組みをインタプリタ開発者が解説
目次
インタプリタの仕組みとは？
インタプリタ（Interpreter）の仕組みはどのようなものでしょうか？
インタプリタは↓のような仕組みで動作するソフトウェアです。
字句解析
構文解析
構文木実行
この記事では「インタプリタとはなんなのか？」というところからはじめ、インタプリタの具体的な仕組みについて解説します。
記事の執筆者は2015年頃からインタプリタを開発しています。
インタプリタの仕組みは、作っていない人からするとすごく未知的で得体のしれないものですが、その仕組みは意外と単純なものです。
インタプリタは3つの工程に分かれていて、それぞれを個別に作ればインタプリタはできてしまいます。
インタプリタを作るということは自分のプログラミング言語を作るということです。
ぜひみなさんも自分のインタプリタを作り、言語の制約のない自由な世界を覗いてみてください。
| （^ _ ^） | インタプリタは自由の象徴 |
インタプリタとは？
そもそもインタプリタとはなんなのでしょうか？
この記事をご覧の皆さんは、すでにインタプリタの仕組みについて知りたいわけなので、この説明は今さら不要かもしれません。
インタプリタとは、プログラマーなどの開発者がプログラミング言語で書いたソースコードを、解析「しながら」実行するソフトウェアのことです。
「解析しながら」というところがミソです。
一度、すべてのソースコードを解析してから実行するのではなく、解析が進んだら解析した分をそのつど実行していくのがインタプリタの特徴です。
インタプリタとはソフトウェアなのでその正体はバイナリファイルです。
これはコンパイラ系のC/C++などの速度が速い言語で制作されていることが多いです。
C/C++などで書かれたインタプリタのソースコードを、コンパイルしてバイナリにしたのがインタプリタです。
そしてそのインタプリタに、インタプリタが対応しているプログラミング言語を入力として渡すと、インタプリタはそのソースコードを解釈しながら、パソコンに命令を出していきます。
動的型付けなどのインタプリタはメモリを多く消費します。
これはオブジェクトを動的なメモリの確保で生成しているためです。
動的型付けではすべての変数がなんらかのオブジェクトとして表現されます。
それらのオブジェクトはガベージコレクションというメモリのマネージャーでメモリが管理されます。
各オブジェクトは参照カウントというカウント変数を持っていて、それが0にならない限りメモリは開放されません。
これはインタプリタの機能の一部ですが、このようにインタプリタは内部ではずいぶんと「贅沢」な処理をやっています。
この結果、インタプリタで実行されるプログラムは、コンパイルされたプログラムに比べると非常に動作が遅くなるのが特徴です。
たとえばRuby, Python, PHPといった有名なインタプリタ系言語は速度の面において、コンパイラ系の言語……たとえばC/C++, Rustなどには遠く及びません。
しかしインタプリタ系言語は非常に柔軟な記述が可能で、生産性も高く、現代の贅沢なプログラミングが当たり前になった時代ではなくてはならない存在です。
インタプリタとコンパイラの違い
プログラミング言語には大きく分けて「インタプリタ系の言語」と「コンパイラ系の言語」があります。
インタプリタ系の言語はさきほどの解説の通りですが、コンパイラ系の言語との違いはなんでしょうか？
コンパイラはソースコードをバイナリファイルに変換するソフトウェアです。
バイナリファイルとは機械語（マシン語）で書かれたファイルのことです。
CPUは基本的にこのマシン語しか理解できません。
いっぽうインタプリタは、ソースコードをバイナリファイルには変換せずにそのまま解釈して実行していきます。
コンパイラ系の言語 ... ソースコードがバイナリファイルに変換される
インタプリタ系の言語 ... ソースコードがそのまま解釈されて実行される
このようにインタプリタ系の言語はソースコードをバイナリに変換しません。
ソースコードを解釈し、パソコンに命令をするのはインタプリタ自身の仕事です。
プログラムはバイナリファイルとして生成したほうが動作が早くなります。
なぜならバイナリファイルはCPUが直接理解できるからです。
しかしインタプリタはバイナリを生成せず、解釈しながら実行していくので、どうしてもバイナリファイルの実行に比べると動作が遅くなります。
速度の面ではインタプリタはコンパイラに比べるとデメリットしかないように感じますが、メリットももちろんあります。
それはインタプリタ系の言語がコンパイラ系の言語に比べると高度に抽象化されているという点です。
この一例がRubyやPythonなどが採用している「動的型付け」という機能です。
このような動的型付けを採用しているインタプリタ系の言語では「型」について意識する必要が無く、また制約もゆるいです。
そのためコンパイラ系の言語と比較すると自由な記述が可能です。
また、ガベージコレクションなども実装されていることが多いため、メモリを自分で解放する必要もありません。
このようにインタプリタ系の言語はコンパイラ系の言語と比べると抽象化が進んでいることが多く、そのぶん生産性は上がります。
これはインタプリタがコンパイラ型言語で制作されているためです。
インタプリタはコンパイラ型言語の資産を流用できるので、そのぶん抽象化が上がります。
＊注: 「型」があったほうが生産性が上がるという意見もあります。
＊注: Go言語など、ガベージコレクションを実装しているコンパイラ型言語もあります。
インタプリタの大まかな実行の流れ
それではインタプリタの実際の仕組みについて見てみたいと思います。
インタプリタがソースコードを読み込みんで実際にパソコンに命令を出すまでには、↓の工程を経るのが一般的です。
字句解析
構文解析
構文木実行
インタプリタの持っている機能によってはこれ以上の工程に分かれることがありますが、基本的な工程は↑の3つだけです。
つまり、この3つの工程を実装できればインタプリタは実装できることになります。
ちなみに難易度は上から順に上がっていきます。
| （^ _ ^） | ダンジョンみたいだな |
| （・ v ・） | インタプリタ・ダンジョン |
字句解析
まず、もっとも基本となるのがこの「字句解析」の工程です。
字句解析のおもな目的は、ソースコードを解析して、その内容を意味のある「トークン列」に変換することです。
インタプリタにとって意味のある字句を「トークン」と言い、その列をトークン列と言います。
また、ソースコードをトークン列に変換するオブジェクトのことを「字句解析器」と言います。
これは「Tokenizer（トーカナイザー）」とか「Lexer（レクサー）」と名付けられることが多いです。
たとえばインタプリタで「def」という単語が予約語だったとします。
このdefは関数を定義したりするときに使われる単語です。
すると字句解析器は、ソースコードを解析して、このdefという単語と他の単語を別々に分解します。
defという単語は個別のトークンとして保存され、トークン列に加えられます。
もっと具体的に見てみましょう。
たとえば私の開発している「Pad」では↓のようなソースコードを
{@ a = 1 @}
↓のようなトークン列に変換します。
['{@', 'a', '=', '1', '@}']
実際にはトークン列内のトークンは文字列ではなく、オブジェクトです。
しかしイメージ的には↑のイメージと同じです。
このように字句解析器は、ソースコード内の単語、字句を「意味のあるトークン」に変換する役割を持っています。
なぜ「意味のあるトークン」に変換するのかと言うと、これは後の工程である構文解析のためです。
たとえば↑の場合、aと=と1という字句があります。
これは元のソースコードでは変数aへの整数1の代入です。
インタプリタはこの代入文を解釈するとき、それぞれを個別の情報として扱います。
aは変数の識別子、=は演算子、1は整数と言った具合にです。
そのためこの字句解析が重要になってきます。
字句解析は料理で言うところの「下ごしらえ」みたいなものです。
包丁で食材を刻んでいくように、字句解析器はソースコードを刻んで行くわけですね。
構文解析
字句解析の次に行うのが「構文解析」です。
構文解析の主な目的は、字句解析で作ったトークン列を解析して、「構文木」を構築することです。
この構文解析を行うオブジェクトを「構文解析器」などと言います。
これは「Parser（パーサー）」とか「Compiler（コンパイラー）」とか呼ばれることが多いです。
プログラミング言語の構文木は特に「抽象構文木（AST）」と呼ばれます。
なぜ構文木を作る必要があるのでしょうか？
インタプリタはプログラミング言語を解釈しますが、その解釈はつまりプログラミング言語の「文法」の解釈になります。
この文法を解釈する方法はいろいろありますが、その1つが構文木を作る方法です。
構文木とはデータ構造で言うところのツリー構造で表現されます。
たとえば先ほどのa = 1という代入文の構文を考えてみます。
このa = 1という構文はたとえば↓のようなツリーで表現されます。
= / \ a 1
では↑のツリーを疑似コードにしてみましょう。
struct Assign:
lhs = Variable() // 左側の子供
rhs = Integer() // 右側の子供
end
↑のAssignという構造が=のことで、Variableというのがaです。
そしてIntegerは1ですね。
lhsというのはleft hand sideの略で、左手側だよという意味です。
rhsはright hand sideの略で、右手側だよという意味になります。
実際のプログラムでは↑の疑似コードのようなコードでツリー構造が表現されます。
↑のAssignというオブジェクトはまた別のオブジェクトの子供になったりします。
BNFを作る
構文木解析で重要になるのが「BNF」という文書です。
BNFとは「Backus-Naur form（バッカス・ナウア記法）」の頭文字です。
これは構文規則が書かれた、いわばプログラミング言語の「設計書」みたいなものです。
構文解析器の開発では先にこのBNFを作ります。
そしてBNFを見ながら実装を進めます。
BNFに間違いがあったらBNFを修正し、実装を修正します。
言語制作で一番重要なものかもしれません。
これの質が良いと言語の質が良くなり、これの質が悪いと言語の質も悪くなります。
それほど制作するプログラミング言語の品質に直結するものです。
ただBNFを使わないで言語を実装するスーパーな人もいるらしいので世の中は広いと言えます。
BNFは内容的にはただのテキストファイルです。
PadのBNFの一部を見てみます。
...
asscalc: expr [ augassign expr ]*
expr: term [ add_sub_op term ]*
term: negative [ mul_div_op negative ]*
...
↑のようにBNFでは左側に文法の要素を書き、コロンをはさんだ右側にその要素の構成を書きます。
（↑の記法は正規のBNFではなく、独自拡張したものです）
要素: 構成
↑の例ではexprの要素を見てみましょう。
exprはPadにおける「足し算と引き算」を表す要素です。
その構成は↓のようになっています。
expr: term [ add_sub_op term ]*
これは「足し算と引き算」では最初にtermという要素があって、その次にadd_sub_opという要素とtermという要素が複数続くという意味になります。
[ ]*の部分は繰り返しを表しているわけですね。
ではtermという要素はどうなっているのでしょうか？ これは先ほどのサンプルに書かれています。
term: negative [ mul_div_op negative ]*
↑のようにtermという要素もexprと似たような構成になっています。
termは「掛け算と割り算」を表す要素です。
このようにどんどんと要素が繋がっていきますが、これが結果的にツリー構造になります。
そしてtermなどの要素は最終的に変数aや整数1に、add_sub_opの要素は+や-になるわけです。
構文木実行
構文木を構築したら、その構文木を実行します。
これを行うオブジェクトは特に慣例はありませんが「Executor（エグゼキューター）」などと呼ばれます。
Padでは「Traverser（トラバーサー）」という名前を使っています。
構文木を構築できたらすでに構文が出来上がっています
あとはこの構文にしたがってパソコンに命令を出していくだけです。
出していくだけなんですが、3つの工程では一番難易度が高い工程です。
言語が動的型付けなどをサポートしている場合は、この工程で変数などのオブジェクトが作られたり代入されたりします。
構文木の根っこのことを「ルート」と言います。
また、構文木に繋がっているオブジェクトのことを「ノード」と言います。
構文木実行器は構文木をルートからたどり、つぎつぎにノードを読み込んでいきます。
そして文脈を解釈して、その文脈で表現したい処理を実際に実行していきます。
たとえばa = 1という式では、左側の変数aに右側の整数1を代入するという処理です。
やってることはそれほど複雑なことではありませんが、変数やスコープ、コンテキストなど、言語の機能によっていろいろなケースを想定する必要があるので、難しい実装になっていきます。
これをいかにスッキリとシンプルに実装できるかが言語実装者の腕の見せ所のような気がします。
インタプリタを作るにはどうしたらいいか？
いきなりインタプリタを作るといっても、なかなかハードルが高いものです。
なにか手頃な、練習になる題材のソフトウェアはないでしょうか？
あります。それは「電卓です」
電卓からはじめる
電卓は数式を解釈して、その結果を表示するソフトウェアです。
インタプリタの開発の練習の題材にする場合は、その数式の解釈を↑のような工程で実装するといいでしょう。
四則演算などの数式を解釈し、結果を出せるようになれば、それはもうほぼほぼインタプリタです。
あとはその電卓を拡張して、if文を付けたり、for文を付けたりすればプログラミング言語になります。
このように電卓と言うのは意外かもしれませんが、インタプリタに近しい存在です。
身近過ぎるソフトウェアですが、意外に高度な概念で作られているんですね。
| （^ _ ^） | 電卓は心の師 |
おわりに
この記事ではインタプリタの仕組みについて解説しました。
最初はわけわかんないと思いますが、電卓を自分で実装できると「こういうことか～」とわかると思います。
| （^ _ ^） | またね |