代写 C compiler 研究プロジェクト演習 マニュアル

研究プロジェクト演習 マニュアル
コンパイラと仮想スタックマシンの製作
⃝c 福本 聡

1. コンパイラの試作
現在の計算機のほとんどすべてが，プログラム記憶方式 (1)−(4) で実現されています.これは，
計算機内部に記憶されたプログラムの命令に従って順番に演算操作を実行する方式です.この方 式の概念が提案された当初は，計算機がプログラムを直接解釈して実行することを前提としてい ました.そのため，記憶されるプログラムは，マシン語やアセンブリ言語などの低水準な言語で 記述されていたわけです.その後，さまざまな情報処理の問題を効率的に計算機で扱えるよう， FORTRAN や C や PASCAL など，いわゆる高水準言語が設計され，使用されるようになりま した.これらの言語は抽象性が高く，マシン語などと比較すれば人間にとって遥かに理解しやす いのが特徴です.そのため，プログラムの開発期間の短縮や，誤りの回避に大きな成果をあげて きました.しかし，それらの言語には，“高水準” であるがゆえに，計算機で直接解釈するのが困 難であるという特徴もあります.つまり，高水準言語で書かれたプログラムを実行するには，いっ たん，上記のような低水準言語で記述されたプログラムに変換する必要があるわけです.その変 換を実行するのが，コンパイラ (Compiler) と呼ばれるプログラムです (3),(4).
この実験では，コンパイラの機能や実現手法について学ぶため，簡単なプログラミング言語に 対するコンパイラを試作することにします.図 1 は，実験で対象とするシステムの構成を表して います.一般に，高水準言語で記述されたプログラムをコンパイル(翻訳)して低水準言語プロ グラムへ変換するとき，前者をソースプログラム(原始プログラム)，後者をオブジェクトプログ ラム(目的プログラム)と呼びます.ここでは，ソースプログラムは実験用に考えられたパスカ ル風言語 “Mini-Mini-Pascal” を用いて記述され，オブジェクトプログラムは実験用の仮想スタッ クマシンで直接実行可能なアセンブリコードで記述されるものとします (3)−(5).実験ではそれら の仲立ちをするコンパイラを作ることになります.
以下では，まず，想定するスタックマシンの原理とアーキテクチャについて述べます.続いて， ソースプログラミング言語である “Mini-Mini-Pascal” の仕様について説明します.そして，それ らのためのコンパイラの構成と手法について述べていくことにします.
読み込み
書き出し
ソース プログラム
オブジェクト プログラム
試作する コンパイラ
パスカル風言語 : Mini-Mini-Pascal で記述
図 1: システムの構成.
1
仮想アーキテクチャ (スタックマシン)

1.1 スタックとポーランド記法 この節では，スタック機構とポーランド記法の概念に基づくスタックマシン (4),(5) の演算動作
について説明します.
スタック (Stack) とは，荷物などの “積み重ね” を意味する言葉です.ここでは，計算機の記
憶機構のひとつをいいますが，その構造は本来の言葉のイメージに関係しています.つまり，ス タックは，図 2 (a) のようにデータを積み重ねて格納する構造を持っているのです.新たにデー タを格納するときは必ずいちばん上に積み重ね，逆に，格納されているデータを取り出すときも いちばん上のデータから順に取り出します.この場合，スタックポインタ (SP) は，常にいちばん 上のデータの 1 つ上の領域，すなわち，次にくるであろうデータの格納領域を指しています.ス タックにデータを格納する操作を “プッシュダウン” と呼び(図 2 (b))，データを取り出す操作 を “ポップアップ” と呼びます(図 2 (c)).プッシュダウンによりスタックポインタは 1 つ上に あがり，ポップアップによりスタックポインタは 1 つ下に降りることに注意してください.
プッシュダウン
(Push Down)
ポップアップ
(Pop Up)
7
7
12
5
スタック ポインタ SP
SP
12
5
12
5
(a)
(b)
(c)
図 2: スタック機構.
このスタック機構，一見，何の役にも立ちそうもないと思われるかもしれません.しかし，使
い方によってはたいへん役に立ちます.この実験で想定するスタックマシンはその良い例となる
わけですが，そのはなしのまえに，まず，準備としてポーランド記法について述べましょう.
いま，次のような算術式の書き換えを考えます.
X+Y → (X,Y)+ → XY+ (1) いちばん左の式は，通常の算術式の表現です.被演算子 X と Y のあいだに演算子 + が置かれて
2
SP

います.これで X と Y の加法を表しているわけです.この算術式の両側に括弧を付けて，演算 子の代わりに “, ” でふたつの被演算子を句切り，演算子を右括弧の後に置けば上式の中央の表現 に書き換えられます.さらに，この表現から括弧と “,” を取り除けばいちばん右の表現となりま す.この演算子を後ろに置く記法をいちばん左の記法に対するポーランド記法と呼びます.まっ たく同様にして，減法，乗法，除法についても
X−Y → (X,Y)− → XY− (2) X∗Y → (X,Y)∗ → XY∗ (3) X/Y → (X,Y)/ → XY/ (4)
のようにポーランド記法で書き換えることができます.この表現をもう少し複雑な算術式に適用
してみましょう.例えば，算術式
A + (B − C) ∗ D (5)
を考えます.我々は，既に，このような算術式の演算には優先順位があることを知っています.そ れは，はじめに括弧でくくられた B − C を演算し，次にその結果と D の乗算を実行し，最後に その結果と A との加算を実行するという演算順序です.この順序を守りながら，式に含まれるす べての演算の演算子を後置する記法について述べます.まず，この算術式の最も大局的な演算は 何かを考えます.あきらかに A と (B − C) ∗ D との加算ということになります.そこで，その 演算について上述のように
→ (A, (B−C)∗D)+ (6) と書き換えます.ここでの非演算子のひとつ (B − C) ∗ D も大局的に見れば B − C と D との乗
法ですから，次にこれを
→ (A, ((B − C), D)∗)+ (7) と書き換えます.さらに，その演算の非演算子のひとつである B − C も同様に
→ (A, ((B, C)−, D)∗)+ (8) と書き換えます.ここで括弧と “,” をはずして
→ ABC−D∗+ (9)
のように得られるのが原式 (5) に対するポーランド記法です.この算術式の表現で，前述の演算 順序どおりの評価を実行できます.式は左から順に見ていきます.演算子を見たとき，その前の ふたつの非演算子について対応する演算を実行し，その結果を次の演算についての非演算子の値 と見なします.同様の手続きをいちばん右の演算子まで実行します.実際，式 (9) を左から見て いけば，はじめの演算子は − で，その前の非演算子 B と C とで減算を実行することになり，次 に見る演算子 ∗ にはその前の BC− の結果と非演算子 D とが対応し，最後の演算子 + には非演 算子 A と BC − D∗ の結果とが対応するので，式 (5) とまったく同じ順序で評価できることが判 ります.
3

6
8
6
5
6
3
8
6
3
8
6
ABC–D*+ ABC–D*+ ABC–D*+
(a) (b) (c)
*
ABC–D*+ ABC–D*+
(f) (g) (h)
–
ABC–D*+
(d) (e)
+
ABC–D*+
(i) (j)
10
5
6
10
5
6
50
6
50
6
56
図 3: ポーランド記法とスタックによる算術式の評価.
さて，このポーランド記法の主な利点は何かといえば，括弧を一切使わずにもとの算術式と同
じ演算順序を表現できることです.つまり，非演算子と演算子だけのならびによってすべての演
算順序を正しく記述できるのです.しかもその結果，式の値の評価では，先に表れた演算を後回
しにしたりすることなく，ただ現れる演算を順番に実行すれば良いのです.ポーランド記法で記
述された算術式は，この性質と前述のスタック機構とを組み合せることによって極めて合理的に
評価できます.
図 3 は， A = 6, B = 8, C = 3, D = 10 のとき，式 (9) の値がスタックを用いて評価される様 子を (a) から (j) の順に示しています.算術式の下の矢印は，そのとき注目する非演算子または 演算子を指しています.(a) ではまず，式の左端の非演算子 A の値を評価して，スタックに 6 を プッシュダウンしています.次に (b) では，非演算子 B の値を評価して，スタックに 8 をプッ シュダウンしています.同様に，(c) では非演算子 C の値 3 をプッシュダウンしています.(d) では，はじめて演算子 − が現れ，その左のふたつの非演算子 B と C の値，すなわちスタックの 上から 2 つ目の値といちばん上の値とで減算を実行しています.(e) は，その結果をふたつの非
4

演算子の値の替わりにプッシュダウンしたことを示しています.次に (f) では非演算子 D の値を 評価して， 10 をプッシュダウンしています.(g) では第 2 の演算子 ∗ が現れたため，その前の 非演算子である BC− の値と D の値，すなわちスタックの上から 2 つ目の値といちばん上の値 とで乗算を実行しています.(h) はその結果をプッシュダウンしたことを示しています.そして， (i) では最後の演算子 + が現れ，その前の非演算子である A の値と BC − D∗ の値，すなわちス タックの上から 2 つ目の値といちばん上の値とで加算を実行しています.(j) は，式 (9) を評価 した結果の値 56 をプッシュダウンしたことを示しています.
この実験で想定するスタックマシンの演算動作の原理は，以上のようなスタック機構とポーラ
ンド記法の概念に基づくものとします.なお，後に述べるように，通常の算術式表現をポーラン
ド記法で書き換える手続き自体もまた，スタックの概念によって実現されます.
1.2 仮想スタックマシン
想定するスタックマシンのアーキテクチャ(1),(5) について具体的に述べましょう.
図 4 は，スタックマシンの構成を示しています.オブジェクトコード記憶領域には，命令コー
ド(アセンブリコード)のならびでできたオブジェクトプログラムが記憶されます.記憶領域に は番地が付いていて 0 番地から順にコードを格納していきます.そして，実行すべきコードの番
番地
0 PC 1 プログラム 2
カウンタ 3 ·
· · · · · ·
番地
0 1 2 3 · · · ·
23 24 25
キーボード
ディスプレイ
オブジェクトコード コード 記憶領域
スタック構造 変数用メモリ のレジスタ メモリ
仮想アーキテクチャ
(スタックマシン)
SP
スタック ポインタ
図 4: スタックマシンのアーキテクチャ.
地を指定するために，プログラムカウンタと呼ぶレジスタにその番地を格納しています.ただし， 図では，矢印によってプログラムカウンタの指定するコード番地を表しています.プログラムの 実行は，0 番地の命令コードから始まり，飛び越し命令がない限り番地の順に進んでいきます.プ ログラムカウンタが命令コードのない番地を指定したとき，プログラムの実行は終了します.ス タック構造のレジスタは，演算対象となる数値や結果の記憶などに使われます.以下では，これ を単にスタックと呼ぶことにします.また，このスタックためのスタックポインタも別のレジス
5

命令語
Get Put L oad
L oad C onstant S tore
Add
S ubtract Multiply Divide
E qual Greater than Less than
Conditional Jump Unconditional Jump
命令コード
GET X PUT X LOD X
LDC I
STR X
表 1: スタックマシンで実行する命令コード. 内 容
メモリの X 番地領域へキーボードから数値を入力する. メモリの X 番地領域の数値をディスプレイへ出力する. メモリの X 番地領域の数値をスタックへプッシュダウンす る.(その結果 SP ← SP + 1.)
定数 I をスタックへプッシュダウンする.(その結果 SP ← SP + 1.)
スタックから数値をポップアップし，メモリの X 番地領域へ
格納する.(その結果 SP ← SP– 1.)
ADD スタックから続けて 2 つの数値をポップアップして，後か SUB ら取り出した数値に対して先に取り出した数値を演算操作
ポインタの指す場所へ 1 を格納し，そうでなければ 0 を格 納する.
スタックポインタの指す場所の値が 0 ならプログラムカウン タの指定するコード番地の値を K にする. プログラムカウンタの指定するコード番地の値を K にする.
し，結果の数値をスタックにプッシュダウンする.(その
ML T
DIV 結果，命令実行前に対してSP←SP–1.)
EQL スタックから続けて 2 つの数値をポップアップして(その GRT 結果，S P ← S P – 2. )，後から取り出した数値と先に取り LES 出した数値とを比較し，命令語の関係どおりならスタック
CJP K
UJP K
タで実現します.変数用メモリには 26 個の整数値の格納領域があり，各領域には 0 から 25 まで の番地が付いています.このメモリの各領域にはキーボードから数値を入力することができ，逆 に，記憶されている数値はディスプレイで表示することができます.以下，メモリと言えばこの 変数用メモリを指すものとします.
次に，スタックマシンが実行する 14 個の命令コードの内容をまとめて表 1 に示します.これ らのうち，命令 EQL, GRT, LES の演算を実行したときだけは，結果の 1 か 0 かをスタックポイ ンタが直接指すことに注意してください.そしてこの値は，命令 CJP の条件判定フラグとしてだ け使われ，その後のポップアップ操作では無視され，プッシュダウン操作時に新しい数値で上書 きされます.
それではここで，スタックやメモリの状態変化を確認しながら，簡単なオブジェクトプログラ ムについてのスタックマシンの動作を見てみましょう.図 5, 6 は，キーボードから数値を入力 し，これに数値 10 を加えた結果をディスプレイに表示するというプログラムの実行例を示して います.
(a) は，プログラムカウンタの指定した破線矢印の命令 GET 0 を実行した直後の状態です.実 行の結果，プログラムカウンタの指定するコード番地が 1 に変わったことを実線矢印で表してい ます.以下，(b) から (f) でも同様の矢印の使い方をするものとします.ここで実行された命令
6

オブジェクトプログラム スタック メモリ
実行番地
0
1 PC 2 3 4 5
0 1 2
PC 3 4 5
0 1 2 3
PC 4 5
番地 キーボード
20
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
0 1 2 · ·
SP · 25
GET 0
LOD 0
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
0
20
20
SP
1 2 · · · 25
0 1 2 · · · 25
LOD 0
LDC 10
20
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
SP
10
20
LDC 10
ADD
図 5: オブジェクトプログラム実行例.
7

オブジェクトプログラム スタック
メモリ
実行番地
番地
0 1 2 · · · 25
0 1 2 · · · 25
0 1 2 · ·
20
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
30
PC
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
SP
ADD
STR 0
30
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
PC
SP
STR 0
PUT 0
ディスプレイ
30
30
GET 0 LOD 0 LDC 10 ADD STR 0 PUT 0
PC
SP · 25
PUT 0
図 6: オブジェクトプログラム実行例(続き).
8

GET 0 は，メモリの 0 番地領域へキーボードから数値を入力するという命令で，この場合，数値 20 が入力されたわけです.
次に (b) は，命令 LOD 0 を実行した直後の状態を表しています. LOD 0 は，メモリの 0 番地 領域の数値をスタックへプッシュダウンするという命令です.その実行の結果，スタックポイン タが 1 つ上に移動しますが，移動前のポインタを破線で，移動後のポインタを実線で表していま す.以下，(c) から (e) でも同様に表すものとします.
(c) は，整定数 10 をスタックへプッシュダウンする命令 LDC 10 を実行した直後の状態です. プログラムカウンタとスタックポインタがひとつずつ推移しています.
(d) は，命令 ADD を実行した直後の状態を表しています.ADD は，スタックから数値を 2 つポッ プアップし，後から取り出した数値へ先に取りだし数値を加え，結果をスタックにプッシュダウ ンするという命令です.この場合，結果の数値 30 がスタックに入っています.スタックポインタ は，2 つの数値がポップアップされた時点では 2 つ下へ推移しますが，加算結果がプッシュダウ ンされたときに 1 つ上に推移するため，結局，命令実行前と比較して 1 つ下へ推移します.
(e) は，スタックから数値をポップアップし，メモリの 0 番地へ格納することを意味する命令 STR 0 を実行した直後の状態です.
(f) は，メモリの 0 番地の数値をディスプレイから表示する命令 PUT 0 を実行した直後の状態 です.この場合，数値 30 が表示されています.そして，この時点でプログラムカウンタは命令 コードのない番地を指定しているので，オブジェクトプログラムの実行は終了ということになり ます.
1.3 ソースプログラミング言語 Mini-Mini-Pascal この節では，この実験のために設計されたソースプログラミング言語 Mini-Mini-Pascal につい
て述べます. 細かな内容を説明する前に，まず，言語の大まかなイメージを掴むため，Mini-Mini-Pascal で
記述したソースプログラム例を以下に示します.
READ(L);
A:= 0; K:= 1;
WHILE K < L+1 DO A:= A+K; K:= K+1 ENDWHILE; WRITE(A). 見てのとおりのパスカル風言語 (6),(7) です.READ 文はキーボードから変数へ数値を読み込む入 力文で，英字や数字を “:=” で結んだ文は，標準パスカル (6) と同様に代入文を表します.WHILE 文は，“WHILE” と “DO” にはさまれた関係式が成り立つあいだ “DO” と “ENDWHILE” には さまれた文を繰り返し実行する制御文です.また，WRITE 文は変数の値をディスプレイから表 示する出力文です.これらから，例文は，キーボードから整数値を入力し，1 から その値までの すべての整数の和を求めて，結果をディスプレイに出力するプログラムであることが判ります. それでは，Mini-Mini-Pascal の仕様を具体的に述べていきましょう.標準パスカルと較べると かなり簡単で，その分使用できる機能は少なくなっています.まず，使用する文字は以下のもの 9 だけです. 数字: 0123456789 の計 10 個; 英字: ABC ··· Z の計 26 個(大文字のみ); 特殊文字: 空白 ( ) ∗ + − . / : ; < = > の計 13 個.
また，予約語は，
READ, WRITE, WHILE, DO, ENDWHILE
の 5 個だけとします.変数名は大文字の英字 1 字だけ，したがって，26 個しか使用できません. データ型は −32768 から +32767 までの整数型だけです.言語の文法は，図 7, 8 の構文図 (5),(6) で記述されます.これらから判るように，Mini-Mini-Pascal には標準パスカルにあるような定義 部や宣言部はありません.プログラムは，単文または複文からなり，必ず終端記号 “.” で終了し ます.複文構成の場合は，文と文のあいだを “;” で区切ります.また，READ 文と WRITE 文 の引数は変数名 1 個だけです.なお，構文図には表されていませんが，プログラム中の任意の場 所に任意の数の空白または改行コードを入れることができます.
プログラム (program) 文.
;文
READ ( 変数名 ) WRITE ( 変数名 )
変数名 : = 単純式 関係式 DO 文
;
図 7: 構文図.
1.4 Mini-Mini-Pascal コンパイラ
以下では，前節の Mini-Mini-Pascal で記述したソースプログラムを，前々節のスタックマシン
で実行可能なオブジェクトプログラムに変換する Mini-Mini-Pascal コンパイラについて考えてい きます.まず，この節では，問題のコンパイラの機能を具体的な実行例を用いて示します.
図 9 は，ソースプログラム SAMPLE1.PAS をコンパイルしてオブジェクトプログラム SAMPLE1.OBJ を生成した例です.オブジェクトプログラムの方は，すでに図 5, 6 の実行例で見たものと同じで
文 (statement)
WHI L E
E NDWHI L E
10

関係式 (relational expression)
< 単純式 = >
単純式 (simple expression) +
単純式
+ –
項
–
項 (term)
因子
因子 (factor)
項
* 因子 /
変数名 符号なし定数
( 単純式 )
符号なし定数 (unsigned constant) 数字
図 8: 構文図(続き).
11

す.これは，キーボードから数値を入力して，その値に整定数 10 を加え，結果をディスプレイか ら表示するプログラムの例でした.SAMPLE1.PAS は，それとまったく等価な機能を持つ高水準言 語プログラムです.オブジェクトプログラムの命令コード GET 0 の内容は，キーボードから数値 を入力してメモリの 0 番地領域へ格納するというものでした.ソースプログラムでこれに対応す るのが，READ(A) という文です.Mini-Mini-Pascal では，変数名は A から Z までの英字の大文 字 26 個しか使用できませんでしたが，これにスタックマシンのメモリ番地 0 から 25 までの領 域が割り当てられています.そのため，変数名 A はメモリの 0 番地領域に自動的に対応します. また，ソースプログラムの代入文 A:= A+10 には，ポーランド記法の概念に基づいて，オブジェ クトプログラムのコード番地 1 から 4 までの 4 個の命令コードが対応します(図にはコード番 地は記されていませんが，先頭の命令を 0 番地として順に数えるものとします).
次に，もうひとつのコンパイラ実行例，図 10 を見てみましょう.ソースプログラム SAMPLE2.PAS は，前節で示した例文と同じものです.これをコンパイルして得られるオブジェクトプログラム が SAMPLE2.OBJ です.ふたつのプログラムを比較すれば，同じ内容を記述するのにも，高水準 言語の方がはるかに容易であることが解ります.実行例 1 と同様に，変数名 A, K, L は，メモ リ番地 0, 10, 11 にそれぞれ対応します.WHILE 文に相当する制御は，コード番地 5 から 9 の 関係式についての命令とコード番地 10 の CJP 20 およびコード番地 19 の UJP 5 で実現されま す(スタックマシンの命令コード表参照).
ソースプログラム
SAMPLE1.PAS
READ(A); A:= A+10; WRITE(A).
オブジェクトプログラム
SAMPLE1.OBJ
GET 0
LOD 0
LDC 10
ADD
STR 0
PUT 0
図 9: コンパイラ実行例 1. 12

ソースプログラム
SAMPLE2.PAS
READ(L);
A:= 0; K:= 1; WHILE K < L+1 DO A:= A+K; K:= K+1 ENDWHILE; WRITE(A). オブジェクトプログラム SAMPLE2.OBJ GET 11 LDC 0 STR 0 LDC 1 STR 10 LOD 10 LOD 11 LDC 1 ADD LES CJP 20 LOD 0 LOD 10 ADD STR 0 LOD 10 LDC 1 ADD STR 10 UJP 5 PUT 0 図 10: コンパイラ実行例 2. 1.5 コンパイラの設計方針 この節では，実験で試作する Mini-Mini-Pascal コンパイラの構成 (3)−(5) について述べ，設計 方針をまとめます. 図 11 はコンパイラの実行過程 (3) の概略を示したものです.(a) は，通常のコンパイラの基本 的な処理フェーズ (3) を表し，(b) は，この実験で作るコンパイラについて表しています. (a) では，まずはじめのフェーズで，ソースプログラムを読み込んで字句解析 (lexical analyze) を実行します.字句 (token) とは，論理的にひとまとまりとなっている文字列のことをいい，予 約語，変数名，数値および特殊文字がそれに当ります.そして字句解析は，単なる文字列のなら びであるソースプログラムを字句ごとに分離する操作を意味します.次の構文解析のフェーズで は，字句を手掛かりにして，ソースプログラムの構文構造を特定します.さらに，次のコード生 成フェーズでは，それらの構文構造に対応して，計算機で実行可能なオブジェクトコードの列を 作り出します.実際に実用的と言えるような言語のコンパイラを設計する場合，意味解析やコー ド最適化と呼ばれるフェーズ (3) がコード生成の前で重要となりますが，ここでは，コンパイラの 基本的な処理だけに着目しました. 上記の各フェーズでは，ソースプログラムで指定された名前(変数名や関数名)の型などについ ての一貫した情報の記録が必要です.その機能は，記号表管理の部分で実現されます.また，ソー スプログラムに文法上の誤りがある場合には誤り処理のブロックが呼び出されます.この処理で 13 ソースプログラム 字句解析 コード生成 オブジェクトプログラム (a) コンパイラの基本的な 処理フェーズ ソースプログラム 記 号 表 管 理 誤 り 処 理 字句解析 構文解析 コード生成 構文解析 図 11: コンパイラの実行過程. は，単にプログラマに誤りの通知をするだけでなく，できるだけ詳しい誤り診断情報を提供し，可 能ならば，誤りが検出されたフェーズへ制御を返して処理を継続させることが望まれます. 次に，図 11 (b) に注目しましょう.ここでは，字句解析，構文解析，コード生成といった処理 は，(a) のような明確なフェーズに分かれていません.Mini-Mini-Pascal コンパイラでは，ソー スプログラムの先頭の字句を手掛かりに構文解析を開始し，構文解析手続きの必要に応じて順次 字句を取りだしていきます.そして，構造が特定された構文については，そのつど対応するオブ ジェクトコードを生成しながら構文解析が進んでいきます.このようなコンパイラは，再帰降下 型構文解析法 (3) と呼ばれる手法によって実現できます.これは，言語の文法を規定する構文図を 参照しながらソースプログラムの構文の記述を調べるもので，構文図の各要素に対応して，それ ぞれに再帰的手続きを用意します.したがって，原則的に再帰呼びだしが使用できる言語でコン パイラを記述する必要があります. ところで，ここで試作するコンパイラには記号表は必要ありません.すでに述べたように，Mini- Mini-Pascal という言語では，使用できる変数名 A から Z の 26 個はスタックマシンのメモリ 番地に自動的に割り付けられますし，関数や手続きなどの名前の使用も許されていないからです. また，簡単のために，誤り処理はおこなわないものとします.余裕がある場合にはおこなっても 構いませんが，それでも，整数値の許容範囲オーバの通知と文法誤りの存在通知だけとし，コン パイル処理への復帰はおこなわないものとします. 14 オブジェクトプログラム (b) Mini-Mini-Pascal コンパイラ の処理 誤 り 処 理 1.6 課題 1. 上記のコンパイラを作成してください.プログラミング言語には，再帰呼び出しを使用でき る言語であれば何を使用しても構いません. 2. 生成したオブジェクトプログラムを実行する仮想スタックマシンを作成してください. 3. 作成したコンパイラの改良を試みてください. 参考文献 (1) 斎藤 忠男，大森健児:現代計算機アーキテクチャ，オーム社，1994. (2) 樹下 行三:コンピュータ工学，昭晃堂，1993. (3) A. V. Aho, J. D. Ullman / 土居 範久 訳:コンパイラ，培風館，1986. (4) 伊藤 貴康:ソフトウェア工学基礎論，丸善，1981. (5) 池田 克夫 編:情報工学実験，オーム社，1993. (6) たとえば，K. Jensen, N. Wirth / 原田賢一 訳:PASCAL，培風館，1981. (7) たとえば，玉井 浩:TURBO Pascal プログラミング，サイエンス社，1987. 15