PPT

平成19年度卒業研究
PASCALコンパイラについて
福永研究室
山川武志
畑中陽介
佐藤遼
目次



コンパイラとは？
開発の背景
開発フロー






字句解析
構文解析
型検査
中間コード
コード生成
実行とまとめ
開発の背景（１）



以前、当研究室ではSRC（SRC2）と呼ばれるCPUを製作し
た。SRC2は基本演算の他にFPU（浮動小数点計算機構）を
搭載した汎用型CPUである。
SRC2を使ってハードウェア上でのアプリケーションを開発
するにはアセンブリ言語でプログラミングする必要があっ
た。
SRC2を利用しやすくするため、Pascalのコードをアセンブ
リコードに変換するコンパイラ作成を行った。
プログラミング例

アセンブリ
Loop:
.start
la
r2
la
r3
la
r4
add r1
sub r2
brnz r4
st
r1
stop

10
1
Loop
r1
r2
r2
r3
r2
100
Pascal
progarm sum
var i, total : integer;
begin
total := 0;
for i:=1 to 10 do
total = total+i
end.
コンパイラとは・・・？

ある言語で書かれたプログラムをそれと「等価な」別の言
語のプログラムに「翻訳」すること。
例） Cコンパイラや電卓 etc…
私たちの作ったコンパイラ
Pascal → アセンブリ言語（SRC2対応の）
コンパイラの位置づけ
原始プログラム（入力）
前処理系
コンパイラ
アセンブラ
機械コード
コンパイラの概要（１）


解析部
入力エラーの指摘
生成部・合成部
目的コード生成とコードの最適化
コンパイラの概要（２）






字句解析
構文解析
意味解析（型検査など）
中間コード生成
コード最適化
コード生成
解析部
生成部
仕様・特徴



Pascalコンパイラ
1パス（アセンブラコードの出力まで）
中間コードを作った
開発フロー

コンパイラの開発は以下のようなフローを
経て行った。





字句解析
構文解析
型検査
中間コード生成
目的コード生成
字句解析



ソースコードをトークン（意味を持つ最小の
単位）に分ける。
空白、タブ、改行コードを取り除く。
識別子（名前）を記号表に登録する。
字句解析
program call (input, output);
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:=1 to 10 do
begin
read (m);
writeln(cube(m))
end
end.
program call ( input , output
) ; var i , m , : integer ;
function cube := p * p * p
end ; begin for i := 1 to
10 do begin read ( m ) ;
cube ; writeln ( cube ( m
) ) end end .
字句解析
記号表
token
:
call
id(名前)
i
id(名前)
m
id(名前)
cube
id(名前)
p
id(名前)
:
type
value
・・
字句解析
字句解析の実現には有限オートマトンがよく利用
される。
Pascalの字句解析用に作成した有限オートマトンで
array[1..15] of integer が解析される様子を見る。

array[1..15] of integer
字句解析

「 a 」を読むことで図のように状態が
遷移する。
array[1..15] of integer
字句解析

「◎」の状態は受理状態を表すが、
遷移できなくなるまで読み込みを続ける。
array[1..15] of integer
字句解析

以降の文字は図のように解析され、
array[1..15] of integer
字句解析

『array』の後の『 [ 』を読み込んだ段階で、
遷移できないため、文字列「array」が確定
される。
array[1..15] of integer
字句解析

次は『 [ 』から解析を始める。
array[1..15] of integer
字句解析

しかしその次が『 1 』となり、次の遷移先が
無いため、『 [ 』だけで確定される。
array[1..15] of integer
字句解析

次は数字の『1』から解析を始める。
array[1..15] of integer
字句解析

次は数字の『1』から解析を始める。
array[1..15] of integer
字句解析

次は数字の『1』から解析を始める。
array[1..15] of integer
字句解析

次の『.』を見て図のように遷移するが、
array[1..15] of integer
字句解析

次の『.』を見て図のように遷移するが、
array[1..15] of integer
字句解析

その次の『.』では遷移先が無いため、直前の受
理状態までの文字列（数字の『1』）を確定し、そ
の直後の文字から再び解析する。
array[1..15] of integer
字句解析

数字『１』の直後の『.』から解析を始める。
array[1..15] of integer
字句解析

数字『１』の直後の『.』から解析を始める。
array[1..15] of integer
字句解析

数字『１』の直後の『.』から解析を始める。
array[1..15] of integer
字句解析

二つ目の『.』で図のように遷移。
array[1..15] of integer
字句解析

二つ目の『.』で図のように遷移。
array[1..15] of integer
字句解析

次の数字の『1』で遷移先が無いため『..』を
確定する。以下同じように解析し、
array [ 1 .. 15 ] of integer となる。
array[1..15] of integer
字句解析

字句解析では、Pascalで使うことのない
記号が現れてしまっているときエラーとし
て検出できる。
例）￥＄あ etc・・
構文解析


字句解析で分割されたプログラム文が、
Pascalの構文規則に従っているか
チェックする。
もし、従っていない場合はその箇所を
エラーとして検出する。
構文解析

『プログラム』は『プログラム頭部』『;』『ブロック』
『.』から成る。
プログラム＝プログラム頭部 ; ブロック .
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
構文解析
プログラム頭部＝
program 名前 [プログラムパラメタ並び]
（[ ]はあってもなくてもよい）
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
構文解析
プログラムパラメタ並び
＝ ( 名前並び )
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
構文解析
名前並び＝名前｛ , 名前｝
｛｝は０回以上の繰り返し
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
構文解析
ブロック＝ラベル宣言部定数宣言部
変数宣言部手続き宣言部
実行部
変数宣言部
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
実行部
begin read (m) ; writeln(cube(m)) end
end .
手続き・
関数宣言部
構文解析

構文解析は非終端記号（構文規則
の左辺）を関数とすることで実現した。
構文解析
変数宣言部＝
[ var 変数宣言 ; { 変数宣言 ; } ]
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
変数宣言部()｛
if(token == “var” ){
match();
変数宣言();
if(token != “ ; ” ){
error();
}
if(token == “var”){
変数宣言();
}
}
}
構文解析
変数宣言＝
名前並び：型
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
i,m,がそれぞれ変数名であり
integer型を持つという情報を
記号表に保存する。
変数宣言(){
名前並び();
if(token != “:”){
error();
}
match();
型();
}
構文解析
変数宣言部＝
[ var 変数宣言 ; { 変数宣言 ; } ]
program call (input, output) ;
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i:= 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end .
変数宣言部()｛
if(token == “var” ){
match();
変数宣言();
if(token != “ ; ” ){
error();
}
if(token == “var”){
変数宣言();
}
}
}
構文解析


構文解析が終了した時点での記号表は右図のよ
うになる。
各宣言のトークン、それぞれの型などが決定でき
ているのがわかる。
型検査

記号表の型情報をもとに、変数などが正し
く使われているか検査するフェーズ。
型検査
program call (input, output);
引数の数と型
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i := 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end.
戻り値の型
型検査
program call (input, output);
引数の数と型
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i := 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end.
戻り値の型
型検査
program call (input, output);
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i := 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end.
型検査
program call (input, output);
引数の数と型
var i, m : integer;
function cube (p : integer) : integer;
begin cube := p*p*p end;
begin for i := 1 to 10 do
begin read (m) ; writeln(cube(m)) end
end.
型検査

各変数の型以外にも、
if文やwhile文などの
条件部がboolean型
かどうか、代入文の
左辺と右辺の整合性
などの検査も行う。
例）
左辺と右辺の
整合性
・if x < y then z:=x else z:=y
・while i <> 1 do begin i := i-1
論理式(boolean型)
でなくてはならない
コード生成


解析部（字句解析、構文解析、型検査）に
よってプログラムが言語の通り書かれてい
るかどうかチェックできた。
生成部では、解析部で作られた記号表を
参照しながら、コードを生成していく。
中間コード

SRC2では（一般のCPUでも）二項演算しか許され
ないが、通常プログラミング言語では自由な演算
が可能になっている。
i := 2 * 3 + 8 div 5
二項演算以外の自由な演算が可能

そのため、プログラム上の計算を全て二項演算
のみに直すことでプログラムを単純にする作業を
施す。それによって作成されるコードを「中間コー
ド」という。
三番地コード


中間表現には、三番地コードと呼ぶ表現を
用いるのが一般的。
三番地コードでは、各文が、演算数に二つ
の番地、結果に一つの番地、合わせて三
つの番地を用いる。
三番地コードの実現


三番地コードの実現に、四つ組という、四
つの欄を持つレコード構造を用いる。
四つ組には、一つの演算子の欄「op」と、
二つの演算数の欄「arg1」「arg2」と、結果
の欄[result]がある。
中間コード
i := 2 * 3 + 8 div 5
t0 := 2
t1 := 3
t2 := t0 * t1
ｔ3 := 8
t4 := 5
ｔ5 := t3 div t4
t6 := t2 + t5
i := t6
二項演算のみで
計算を定義する。
→中間コード
四つ組

先ほどの中間コードを、四つ組を用いて表現する
と、以下のようになる。
i := 2 * 3 + 8 div 5
中間コード

中間コードを生成することで、様々なCPUで動作するコン
パイラを容易に作成することができる。
CPUそれぞれのコ
ンパイラを作成しな
くてはならない。
中間コード

中間コードを生成することで、様々なCPUで動作するコン
パイラを容易に作成することができる。
中間コードまで
各CPUへの変
を作成しておく
換が容易にで
ことで、
きるようになる
コード生成

中間コードで表され
たプログラムを、実
際に使用するCPU
のアセンブリ言語に
変換していく。
コード生成の例

例
掛け算の場合
番地
op
2
*
L-2:
ld
ld
mul
st
arg1 arg2 result
T-0
r1
r2
r3
r3
T-1
T-2
T-0
T-1
r1
T-2
(2*3)
r2
実行

エラトステネスのふるい（素数を見つけるア
ルゴリズム）
考察


今回SRC2用のPASCALコンパイラを開発したこと
で、今までよりもSRC2を容易に扱うことができる
ようになった。
今後はハードウェア上でのアプリケーション開発
などを可能にしたということは、今回の研究で得
た大きな財産であろう。

Download Report