コンパイラの基礎原理 III

コンパイラの基本原理 III
–C 言語による仮想マシンの構築–
目的
1
コンピュータは，人間と違い文字を読んでプログラムを理解するわけではなく，最もコンピュータよりの処理を
記述する言葉は番号（数字）を用いて記述される．これが機械語である．本実験では，仮想的なコンピュータを
自ら設計し，そのコンピュータが理解できる機械語をデザインする．そして，アセンブリ言語をその機械語に翻
訳するアセンブラを作成し，コンパイラの実験を通して作成した字句解析ルーチンおよび構文解析ルーチンと合
わせて，数式を機械語に変換し計算を実行することで仮想マシンの概念について理解する．
原理
2
2.1
仮想マシン
仮想マシンは，近年では，Java 言語の実行環境などとして有名である．古くは，PASCAL や LISP などの言語
で記述されたプログラムを，特定の CPU や環境に依存せずに実行するために用いられた．このような実際のコ
ンピュータ上に作られた架空のアーキテクチャのコンピュータを仮想マシン (Virtual Machine) と呼ぶ．
仮想マシンを用いれば，実際に用いるコンピュータのアーキテクチャが様々でも，同じ実行コードを用いるこ
とができ，各アーキテクチャ毎にコンパイラを作らなくてもよい．
2.2
仮想マシンの命令セット
多くのコンピュータは，機械語を記述する数字の区切りとして byte（バイト）を用いる．1 byte は 8 bit なの
で 28 = 256 通り，例えば， {0, 1, . . . , 255} の数字が扱える．本実験で用いる仮想マシンの数字の区切りも byte
を採用することにする．
先の実験はで，PRINT，SET，ADD，MUL などのニーモニックを扱った．それ以外にも， R0, R1, R2, ... な
どのレジスタもあった．これらを番号で表さなければならない．また，レジスタに代入される数値それ自身も番
号として表さなければならない．そこで機械語が，表 1 ようないくつかのパターンで表されると仮定する．
コード形式
表 1: 機械語のコード形式
対応する機械語の系列パターン
単項演算型
(オペコード, レジスタ番号)
２項演算型
(オペコード, レジスタ番号 1, レジスタ番号 2)
(オペコード, レジスタ番号, ak−1 , ak−2 , . . . , a1 , a0 )
代入型
ここで，オペコードとはニーモニックの番号のことである．また，代入型の a0 , a1 , . . . , ak−1 は，符号無し整
数nを
n = ak−1 × 256k−1 + ak−2 × 256k−2 + · · · + a1 × 256 + a0
と表した場合の係数である．なお，この例のように，ak−1 , ak−2 , . . . , a1 , a0 と上の桁が前にくるように並べる形
式を big-endian，同じ数値を a0 , a1 , . . . , ak−1 , ak のように下の桁が前にくるように並べる形式を little-endian と
呼ぶ．
1
例えば表 2 のように，PRINT のオペコードが 10 であり，R0 のレジスタ番号が 0 であるとするなら PRINT
R0 は単項演算型を用いて (10, 0) と表される．また，ADD のオペコードを 20，R1, R2 のレジスタ番号をそれ
ぞれ 1, 2 とするなら，ADD R1, R2 は 2 項演算型を用いて (20, 1, 2) と表すことができる．さらに，SET のオペ
コードが 30 であり，この仮想マシンが扱える符号無し整数が 0 から 215 − 1 = 32767 であるとすると，この整数
は 16 bit = 2 byte で表すことがき，SET R0, 123 は代入型を用いて (30, 0, 0, 123) と表すことができる．また，
SET R0, 256 は同様に (30, 0, 1, 0) と表すことができる．
表 2: アセンブリ言語と機械語との対応例
アセンブリ言語機械語の型機械語
PRINT R0
ADD R1, R2
単項演算型
SET R0, 123
SET R0, 256
代入型
2 項演算型
代入型
(10, 0)
(20, 1, 2)
(30, 0, 0, 123)
(30, 0, 1, 0)
上記のような取り決めを，全てのニーモニック，レジスタ，数値に対して決定することで，仮想マシンの命令
セットがデザインできる．
2.3
仮想マシンの実装
ここでは，整数の加算と符号反転および表示をサポートした仮想マシンを実際に C 言語を用いて実装する．取
り扱う数値は，0 から 215 − 1 の範囲の整数で，big-endian を用いることとし，命令セットを表 3 および表 4 で
与える．
表 3: オペコード表
ニーモニックオペコードコード形式
表 4: レジスタ番号表
レジスタ番号レジスタ
番号
PRINT
10
単項演算型
R0
0
R5
5
NEG
ADD
11
20
単項演算型
2 項演算型
R1
R2
1
2
R6
R7
6
7
SET
30
代入型
R3
R4
3
4
R8
R9
8
9
標準入力から機械語を読み込んで実行する仮想マシンの， C 言語による実装は以下のようになる．
予習問題
次のプログラムの動作について説明せよ．
2
#include <stdio.h>
#include <stdlib.h>
/*** 各機械語のオペコード ***/
#define op_PRINT 10
#define op_NEG
11
#define op_ADD
20
#define op_SET
30
int main()
{
int
int
int
int
op;
x, y;
n;
R[10];
/*
/*
/*
/*
オペコード用変数 */
レジスタ番号用変数 */
数値用作業変数 */
レジスタ用配列 */
while (op = getchar(), op != EOF) {
switch (op) {
case op_PRINT: /* レジスタの表示 */
x = getchar(); /* レジスタ番号の読み込み */
printf("%d\n", R[x]);
break;
case op_NEG: /* 符号反転 */
x = getchar(); /* レジスタ番号の読み込み */
R[x] = -R[x];
break;
case op_ADD: /* 加算 */
x = getchar(); /* x のレジスタ番号の読み込み */
y = getchar(); /* y のレジスタ番号の読み込み */
R[x] = R[x] + R[y];
break;
case op_SET: /* レジスタへの整数代入 */
x = getchar();
/* レジスタ番号の読み込み */
n = getchar();
/* 整数の上の桁読み込み */
n = n * 256 + getchar(); /* 整数の下の桁読み込み */
R[x] = n;
break;
default: /* 予定外のコードを読み込んだらエラー終了 */
fprintf(stderr, "error: bad op-code\n");
exit(1);
}
}
return 0;
}
2.4
実数（倍精度浮動小数点数）の表現
上記の仮想マシンでは，数値として 2 byte の符号無し整数を取り扱っているため，実数（倍精度浮動小数点数）
を取り扱えない．実数の表現には，整数とは異る込み入った問題が存在するため，本実験では，fread, fwrite を用
いて，C 言語における内部形式（IEEE 754）を利用する．このため，本実験の仮想マシンの倍精度浮動小数点数
の扱いは，内部形式に依存することになり，全ての環境で同じ実行結果を得ることはできない．
予習問題
IEEE 754 規格の概要を説明せよ．
3
3
実験
実数の四則演算が可能な仮想マシンを以下の手順で C 言語により実装せよ．
1. 実数の四則演算が可能な仮想マシンの命令セットをデザインする．
2. 実数の四則演算をアセンブリコードに変換するコンパイラ eucom を以下の手順で作成する（eucom.l およ
び eucom.y は「コンパイラの基本原理 II」で作成したコンパイラを用いること）．
%flex eucom.l
%bison eucom.y
%gcc eucom.tab.c -ll -o eucom
3. 実数の四則演算が可能なアセンブリ言語を機械語に変換するアセンブラを以下の手順で作成する．ただし，
実数は 8 byte の系列で表現できると仮定し，その出力には fwrite を用いる．参考として，加算と符号反転
および表示をサポートしたアセンブラ (euasm.l, euasm.y) を付録に示す．
%flex euasm.l
%bison euasm.y
%gcc euasm.tab.c -ll -o euasm
4. 実数の四則演算が可能な仮想マシンを C 言語により実装せよ．ただし，実数の入力には fread を用いる．参
考として，加算と符号反転および表示をサポートした実装 (euvm.c) を付録に示す．euvm.c をコンパイルす
ると仮想マシンが作成される．
%gcc euvm.c -o euvm
5. 作成したコンパイラとアセンブラにより数式を機械語に翻訳し，仮想マシンで実行した結果を記録せよ．
%echo "1.0 + 0.23" | ./eucom | ./euasm > executable
%./euvm < executable
4
課題
1. コンパイラの最適化について調べよ．
2. コンパイラとインタプリタの違いを調べ，利点欠点についてまとめよ．
4
A
A.1
サンプルプログラム
C 言語による仮想計算機の実装
[euvm.c]
#include <stdio.h>
#include <stdlib.h>
/*** 各機械語のオペコード ***/
#define op_PRINT 10
#define op_NEG
11
#define op_ADD
20
#define op_SET
30
typedef double num_t;
#define print(reg) printf("%f\n", reg)
int main()
{
int op;
int x, y;
num_t n;
/* 数値用作業変数 */
num_t R[10]; /* レジスタ用配列 */
while (op = getchar(), op != EOF) {
switch (op) {
case op_PRINT: /* レジスタの表示 */
x = getchar();
print(R[x]);
break;
case op_NEG: /* 符号反転 */
x = getchar();
R[x] = -R[x];
break;
case op_ADD: /* 加算 */
x = getchar(); y = getchar();
R[x] = R[x] + R[y];
break;
case op_SET: /* レジスタへの数値代入 */
x = getchar();
fread(&n, sizeof(n), 1, stdin);
/* 数値の内部形式入力 */
R[x] = n;
break;
default: /* 予定外のコードを読み込んだらエラー終了 */
fprintf(stderr, "error: bad op-code(%d)\n", op);
exit(1);
}
}
return 0;
}
5
アセンブラ
A.2
[euasm.l]
%{
#include <stdlib.h>
#define to_reg(str) ( str[1] - ’0’ ) /* レジスタ番号への変換 */
#define to_num(str) ( atof(str) )
/* 倍精度浮動小数点数への変換 */
%}
register
number
operator
R[0-9]
"0"|[1-9][0-9]*|[0-9]+"."[0-9]*
[",""\n"]
print
neg
add
set
PRINT
NEG
ADD
SET
%%
{register}
{number}
{operator}
{ yylval.reg = to_reg(yytext); return REGISTER; }
{ yylval.val = to_num(yytext); return NUMBER; }
{ return yytext[0]; }
{print}
{neg}
{add}
{set}
{
{
{
{
[" ""\t"]+
.
%%
/* skip */
{ printf("error: ’%c’\n", yytext[0]); exit(1); }
return
return
return
return
PRINT; }
NEG; }
ADD; }
SET; }
[euasm.y]
%{
#include <stdio.h>
#include <stdlib.h>
typedef enum { R0, R1, R2, R3, R4, R5, R6, R7, R8, R9 } reg_id;
typedef double num_t; /* レジスタの値は倍精度浮動小数点数 */
/***
void
void
void
void
%}
仮想マシンのコード生成関数 ***/
vm_PRINT(reg_id Rx);
vm_NEG(reg_id Rx);
vm_ADD(reg_id Rx, reg_id Ry);
vm_SET(reg_id Rx, num_t n);
%union { reg_id reg; num_t val; }
%token <reg> REGISTER
%token <val> NUMBER
%token
PRINT NEG ADD SET
%start script
%%
script: line;
script: script ’\n’ line;
line: /* empty */;
6
line:
line:
line:
line:
%%
PRINT REGISTER
{
NEG REGISTER
{
ADD REGISTER ’,’ REGISTER {
SET REGISTER ’,’ NUMBER
{
vm_PRINT($2); };
vm_NEG($2); };
vm_ADD($2, $4); };
vm_SET($2, $4); };
#include "lex.yy.c"
int yyerror(const char *s) { printf("%s\n", s); exit(1); }
int main() { return yyparse(); }
/*** 各機械語のオペコード ***/
#define op_PRINT 10
#define op_NEG
11
#define op_ADD
20
#define op_SET
30
void vm_PRINT(reg_id Rx)
{
putchar(op_PRINT); /* PRINT のオペコード出力 */
putchar(Rx);
/* レジスタ番号を出力 */
}
void vm_NEG(reg_id Rx)
{
putchar(op_NEG); /* NEG のオペコード出力 */
putchar(Rx);
/* x のレジスタ番号を出力 */
}
void vm_ADD(reg_id Rx, reg_id Ry)
{
putchar(op_ADD); /* ADD のオペコード出力 */
putchar(Rx);
/* Rx のレジスタ番号を出力 */
putchar(Ry);
/* Ry のレジスタ番号を出力 */
}
void vm_SET(reg_id Rx, num_t n)
{
putchar(op_SET);
/* SET のオペコードを出力 */
putchar(Rx);
/* レジスタ番号を出力 */
fwrite(&n, sizeof(n), 1, stdout); /* 数値の内部形式出力 */
}
7

Download Report