Copyright 守屋悦朗 2005 アセンブラとコンパイラ インタプリタ ここでは 人間にとってより分かりやすい言語 ( アセンブラ語や BASIC, FORTRAN, C, Pascal などの汎用プログラミング言語 ) で書かれたプログラムを コンピュータのハードウエアが直接理解して実行できるプログラム (= 機械語 ) に翻訳するプログラムについて考える アセンブラ語のプログラムを機械語に翻訳するプログラムがアセンブラであり 汎用言語で書かれたプログラムを機械語に翻訳するプログラムがコンパイラ ( 翻訳系 ) である コンパイラは実行前に前もって翻訳をすませるのに対し 実行時にプログラムを 1 行 1 行逐一通訳するようなプログラムをインタープリタ ( 通訳系 ) という 1. アセンブラ すでに見たように 機械語でプログラムを組むのはきわめて大変である そこで 機械語命令を 8 ビットの 2 進数 ( 命令コード ) で書いたり 命令の対象になるデータの格納されている場所 ( 主記憶装置上のアドレス ) を 16 ビットの 2 進数で書いたりする代わりに 命令に決まった名前 ( ニモニック ) を付けておき また アドレスにも自由に名前 ( ラベル ) を付けることができるようにしたものがアセンブラ言語 ( アセンブラ語 ) である アセンブラ言語は こういった名前付けなどがうまくできるようにする命令 (DS 命令や DC 命令 ) を備えていると同時に そのようなアセンブラ言語で書かれたプログラムを機械語に翻訳する作業 ( この作業は アセンブラと呼ばれるプログラムが行う ) がきちんとできるようにするためにアセンブラへ情報 ( プログラムの始まり 終わり 実行開始位置など ) を伝えるための命令 ( アセンブラ制御命令 ) も持っている さらに マクロ機能のような高級な機能を持っていることもある このようなアセンブラ言語は人間にとっては機械語でプログラムを書くよりはるかに簡単になるが コンピュータのハードウエアはアセンブラ言語で書かれたプログラムを直接理解することができないので機械語に翻訳してあげる必要が生じる これを行うプログラムがアセンブラ (assembler) であり その作業をアセンブル作業とかアセンブリング (assembling) という 人間 アセンブラ語 プログラム アセンブラ 機械語プログラム コンピュータ ソースプログラム 目的プログラム 翻訳前のプログラムを原始プログラム ( ソースプログラム ソースコード source
program, source code) といい 翻訳した結果を目的プログラム ( オブジェクトコード 目的コード object code) という 目的コードは そのまま主記憶装置へロードしてすぐさま実行できる形の場合と そうでない場合とがある 前者の場合 目的コード内のすべてのアドレスが絶対番地 ( 主記憶装置の各語 ( ワードマシンの場合 ) あるいは各バイト ( バイトマシンの場合 ) に付けられたアドレスのこと absolute address) になっていなければならない 後者の場合 各プログラム単位 (program unit, サブルーティン単位 ) の目的コード内のアドレスは そのプログラム単位の先頭から何語目か ( 何バイト目か ) という値 ( 相対番地という relative address) になっている ( 注 ) 前者のようにそのまま主記憶装置へロードしてすぐさま実行できる形の目的コードを実行形式 ( ロードモジュール (load module)) という これに対し 後者のような目的コードは 先頭番地を変えるだけで主記憶装置のどこにでもロードして実行することができるので 再配置可能型 (relocatable) であるという 再配置可能型プログラム (1つ以上のプログラム単位の集まり ) は実行直前に各プログラム単位の先頭番地を決めて実行形式に変換され ( この作業を行うプログラムをリンカー (linker) とかリンケージエディタ ( 連係編集プログラム linkage editor) という ) 主記憶装置にロードされる( この作業を行うプログラムをローダー (loader) という ) リンカーの部分まで含めてアセンブラということもある ソースコード 1 再配置可能コード 1 プログラム単位 1... アセンブラ... リンカー実行形式 ソースコード k 再配置可能コード k プログラム単位 k 名前表とロケーションカウンタアセンブラが上のように機械語への翻訳を行うためには プログラム内に現れる記号番地 ( 上の例では EXMPL, BGN, DONE, A, B, MAX) の相対番地 ( プログラムの先頭から数えて何語 ( バイト ) 目か ) を知る必要ある 次の例を考えよう 左側にアセンブラ言語のプログラムを 右側にそれを機械語に翻訳したもの ( この場合 再配置可能型コード ) を示した 話を簡単にするために 2パスのアセンブラを考える kパスアセンブラ (k-pass seembler) とは 目的コードを生成するまでにソースコードをk 回見るタイプのものである
アセンブラ語プログラム 機械語コード (relocatable code) EXPL START BGN 相対番地 (LC) コード BGN LD GR1,A 0000 10 10 000B LD GR2,B 0002 10 20 000C SUBA GR1,GR2 0004 21 12 JPL DONE 0005 65 00 0008 LD GR1,GR2 0007 10 12 DONE ST GR1,MAX 0008 11 10 000D RET 000A 81 00 A DC 12 000B 000C B DC 34 000C 0022 MAX DS 1 000D 0000 END 2パスアセンブラの場合 1パスめで アセンブラは機械語コードの命令コード部分をはじめ アンダーラインした以外の部分を決定することができる 同時に 各命令が何語使う命令であるかも知ることができる アンダーラインした部分は 記号番地に対応するアドレス ( 相対番地 ) であるが それはその記号番地が命令のラベル部に出現するまで判明しない そこで ロケーションカウンター (location counter)lc を用意し これにはプログラムの先頭からの語数 (= 相対番地 ) をカウントする また 名前表 (name table 記号表 symbol table ということもある ) を用意し 記号番地が初めて出現すると名前表に登録し その記号番地が命令のラベル部に現れたときに そのときの LC の値をアドレスとして対応させる 上例の場合 次のようになる : A A B A B LC=0 LC=0 LC=2 LC=5
DONE A B DONE 8 MAX A 11 B DONE 8 MAX A 11 B 12 DONE 8 MAX A 11 B 12 DONE 8 MAX 13 LC=8 LC=11 LC=12 LC=13 2パスめでは 名前表に従って機械語コードのアドレス部を埋めることができ 機械語コードは確定する 1パスアセンブラの場合 1パスめでは アドレスが義の命令語のアドレス部から名前表の対応する所へのポインタ ( 上例の矢印の向きを逆にしたようなもの ) を埋め込んでおく パスの最後ですべての記号番地のアドレスが確定したら ポインタをたどって未確定の命令のアドレス部にその確定値を書き込む 2. コンパイラ アセンブラといえども 人間にとってはまだ使いにくい アセンブラは機械語とほぼ 1 対 1 対応なので それぞれのマシンに依存した仕様になってしまい コンピュータごとに別々のアセンブラを覚えなければならないという難点もある そこで 人間の使う言語 ( 自然言語 ) により近い言語を使ってプログラムを書くことができるようにすると 今度はそのような言語で書かれたプログラムを機械語に翻訳するプ
ログラムが必要になる 自然言語に近いプログラミング言語で 特定用途に限定せずどんな目的のプログラムでも書けるようにデザインされたものを汎用プログラミング言語 (general purpose programming language) とか高級言語 (high-level language) とかコンパイラ言語といい そのような言語で書かれたプログラムを機械語に翻訳するプログラムをコンパイラ (compiler) という 人間 高級言語の プログラム コンパイラ 機械語プログラム コンピュータ ソースプログラム 目的プログラム 高級言語 (C++ 言語 ) 中間コード 機械語コード main( ) { int x, y, z; // 変数宣言 LD GR1,C001 100100A0 cin >> x; cin >> y; MULA GR1,V001 280100A3 if (y>x) { MULA GR1,V001 280100A3 z=x; x=y; y=z; ST GR1,W001 110100A6 } LD GR1,C002 100100A1 cout << 3*x*x+2*y+1; MULA GR1,V002 280100A4 // 特に意味はない出力 ADDA GR1,W001 200100A6 } ADDA GR1,C003 200100A2 ST GR1,W001 110100A6 C001 DC 3 0003 C002 DC 2 0002 C003 DC 1 0001 V001 DS 1 0000 V002 DS 1 0000 V003 DS 1 0000 W001 DS 1 0000 この例で分かるように 高級言語ごとに異なるコンパイラが必要になる (C 言語には C 言語用のコンパイラが BASIC には BASIC 用のコンパイラが というように ) 機械語への翻訳は実行前に行われる
機械語へ直接翻訳するのではなく 一旦 アセンブラレベルの中間言語へ翻訳する方式もある 高級言語のプログラムのたった1 行も機械語に翻訳すると何十行にもなるほど 翻訳作業は大変である * プログラムという 文字列 の中で 変数 配列名 関数名 キーワードなど各種の名前の区別 四則 比較 代入など各種演算を表す文字列の判別 等々 この作業を字句解析とか語彙解析という * 文 ( ステートメント ) の判別と それぞれの文に対応する機械語コードへの変換 これを行うためには 文がどのような構造を持っており したがってどのようなコードを生成すべきであるかを解析しなければならない この作業を構文解析という コンパイル開始 構文解析部 字句解析部 コード生成部 コンパイル修了 字句解析字句解析 (lexical nalysis) は コンパイラがまず最初に行う作業である 高級言語で書かれたソースプログラムを文字列として読み その中の部分文字列を種別に分類する 種別には 定数 ( 整数定数 実数定数 文字定数 文字列 ) 変数名 配列名 関数名 キーワード 演算子 ( 代入 比較 四則 論理など ) 区切り記号( 空白文字 タブ 改行 ) 注釈などがある 注釈は読み捨てられるが その他は種別ごとに管理する ( 名前は名前表 定数は定数表に登録される ) このような種別分けされたものをトークン(token) という 例えば 上例の C++のプログラムは次のようなトークンの列に分解される : main ( ) { int x, y, z ; 関数名左 ( 右 ) 左 { キーワード名前コンマ名前コンマ名前セミコロン cin >> x ; cin >> y ; if 名前演算子名前セミコロン名前演算子名前セミコロンキーワード ( y > x ) { z = x ; 左 ( 名前比較演算子名前右 ) 左 { 名前代入演算子名前セミコロン x = y ; y = z ; } 名前代入演算子名前セミコロン名前代入演算子名前セミコロン右 } cout << 3 * x * x + 名前 演算子整数定数乗法演算子名前乗法演算子名前加法演算子
2 * y + 1 ; } 整数定数乗法演算子名前加法演算子整数定数セミコロン右 } 構文解析字句解析して得られたトークンの列は 高級言語の文法に照らしてどのような構造 ( 意味 ) をもっているかを分析する この作業を構文解析 (syntax analysis) という 例えば 3*x*x+2*y+1 は算術式であるが 算術式 とは何か ( 算術式の外見的な形 = 構文 ( シンタックス syntax)) が高級言語の文法できちんと定義されている必要がある そのような文法の厳密な定義法としては例えばバッカス記法 (BNF: Backus Naur form) などがある 例えば 算術式 の構文はバッカス記法を使って < 算術式 >::=< 算術式 >< 加法演算子 >< 項 > < 項 > < 項 >::=< 項 >< 乗法演算子 >< 因子 > < 因子 > < 因子 >::=<1 次子 > < 因子 > <1 次子 > <1 次子 >::=-<1 次子 > (< 算術式 >) < 変数 > < 定数 > < 変数 >::=x y z < 定数 >::=< 整数定数 > < 整数定数 >::=0 1 2 < 乗法演算子 >::=* / < 加法演算子 >::=+ - と定義される ( これが 算術式の 文法 である ) 例えば 1 行目は次のように読む : 算術式とは 算術式の直後に+を書いてその後ろに項を書いたものであるか または 算術式の直後に-を書いてその後ろに項を書いたものであるか または 単独の項だけである 上記の算術式は この文法的には次ページに示したような構造をしている ( 一意的に定まる ) 構文解析結果をこの木構造(tree structure) で表したものを構文解析木 (parse tree) と呼ぶ このような構文解析のアルゴリズムはいろいろ知られているが この講義の範囲を超えているのでここでは述べない コード生成構文解析が終わると その情報をもとにコードの生成 (code generation) を行う コードの生成法もいろいろあるが ここでは詳細は述べない 実際には 構文解析と同時に中間コードを生成してしまうアルゴリズムもある 中間コードから機械語への変換は一般にやさしくなるような中間コードが用いられる
3 * x * x + 2 * y + 1 整数定数乗法演算子変数乗法演算子変数加法演算子整数定数乗法演算子変数加法演算子整数定数 定数定数定数 1 次子 1 次子 1 次子 1 次子 1 次子 1 次子 因子因子因子因子因子因子 項項項 項 項 項 算術式 算術式 3*x*x+2*y+1 の構文解析木 算術式 中間言語このような構文木も一種の中間言語 (intermediate language) といえる その他の中間言語として 数式のための逆ポーランド記法 (reverse Polish notation) 3つ組コード 4つ組コードなどがある 逆ポーランド記法は後置記法 (postfix notation) とも呼ばれ 数式における演算子をオペランドの後ろに書く書き方である 例えば a+b*(c-d)/e は abcd-e/* と書く 普通の数式の書き方は 演算子をオペランドの間に書く書き方で中置記法 (infix notation) とも呼ばれる これらに対し 演算子をオペランドの前に書く記法を前置記法 (prefix notation) とかポーランド記法 (Polish notation) という 前置記法 -*ab+c/de 中置き法 a*b-(c+d/e) 後置記法 ab*cde/+-
前置記法や後置記法では括弧が要らない これらの記法は 構文解析木をたどる方法と密 接に関係しているが それについてはここでは述べない 3つ組コード (triple code, 二番地命令 two-address code ともいう ) や4つ組コードはよく使われるもので 3つ組コードは次の形の命令を使って記述する : 番号.( 演算子 第一オペランド 第二オペランド ) 例えば 5. (+, x, 100) は ( 変数 5) x + 100 を意味する ( 変数?) は作業用変数を表す 例えば z=123*x+(y-z) は次のような3つ組コードに変換される : 1. (*, 123, x) 2. (-, y, z) 3. (+, 1, 2) 4. (=, 3, z) 4つ組コード (quadruple code, 三番地命令 three-address code ともいう ) は ( 演算子 第一オペランド 第二オペランド 結果の変数 ) の形の命令を用いて記述する 例えば 上例は次のようになる : (*, 123, x, w1) (-, y, z, w2) (+, w1, w2, z) 最適化目的コードをできるだけ効率が良いものにすることをコードの最適化 ( code optimization) といい コンパイラの重要な仕事の一つである 現在のコンパイラはこの最適化機能を必ず備えているため プログラマが考える以上に効率の良い機械語プログラムが生成される 最適化は中間コードに対して行われる場合と 機械語コードに対して行われる場合がある 実行速度の向上に貢献する場合と 記憶容量の縮小に貢献する場合がある : 共通の部分式の除去 不要コードの除去 少ない回数のループの展開 ループ普遍量の抽出とコード移動 演算子の強さの軽減
3. インタプリタ パソコン初期の BASIC 言語にはコンパイラがなく インタープリタ方式で実行された インタープリタ (interpreter) 解釈実行系とか通訳系とも呼ばれ 高級言語で書かれたプログラムを先頭から1 行ずつ順にその意味を解釈しながら実行していくプログラムである ソースプログラムの形のままで解釈実行することもあるが 構文解析木や中間言語などに変換しておいてそれを解釈実行する方式のものもある ここでは 数式 ( 算術式 ) を逆ポーランド記法に翻訳しておいてから それを解釈実行するインタープリタを例として考える すでに見たように 数式 (a+b)*(c-d) は逆ポーランド記法で ab+cd-* と表される これを解釈実行するのに スタックを用いる : 演算子が出現すると スタックのトップとセカンドをオペランドとしてその演算を適用して 結果をスタックにプ ッシュする a d b c c c-d a a+b a+b a+b a+b (a+b)*(c-d) 参考書 : 疋田輝夫 石畑清 コンパイラの理論と実現 共立出版 1988. 疋田輝夫 コンパイラ 昭晃堂 1985. 守屋悦朗 コンピュータサイエンスのための離散数学 2 章 サイエンス社 1991.
始め 問題 / 仕事... 解決策を検討する 解法 / 作業手順... アルゴリズムを考える algorithm... コーディング ( プログラムを書く ) coding プログラム ( 机上 )... プログラミング言語で記述 Pascal,C,FORTRAN など... 入力 ( エディタを使う ) editor デバッグ ソースプログラム source program debugging ( 原始プログラム ) 人間にしかわからない文字の列 エラーが ある場合... コンパイラによって機械語に翻訳 compiling プログラムを修正する 目的コード object program 未確定部分を含む機械語コード library ライブラリや 他の目的 コード... リンカによって他のプログラムと結合編集する linkage editing 実行可能プログラム executable program 機械語で記述された命令の列 ( コンピュータが理解できる 0,1 の列 ) データ... 実行 execution (run) 実行結果... 結果が ok なら終了終り