平成 19 年度卒業研究 PASCAL コンパイラについ て 福永研究室 山川 武志 畑中 陽介 佐藤 遼.

Presentation on theme: "平成 19 年度卒業研究 PASCAL コンパイラについ て 福永研究室 山川 武志 畑中 陽介 佐藤 遼."— Presentation transcript:

1 平成 19 年度卒業研究 PASCAL コンパイラについ て 福永研究室 山川 武志 畑中 陽介 佐藤 遼

2 目次 コンパイラとは？ 開発の背景 開発フロー 字句解析 構文解析 型検査 中間コード コード生成 実行とまとめ

3 開発の背景（１） 以前、当研究室では SRC （ SRC2 ）と呼ばれる CPU を 製作した。 SRC2 は基本演算の他に FPU （ 浮動小数点計 算機構 ）を搭載した汎用型 CPU である。 SRC2 を使ってハードウェア上でのアプリケーション を開発するにはアセンブリ言語でプログラミングす る必要があった。 SRC2 を利用しやすくするため、 Pascal のコードをア センブリコードに変換するコンパイラ作成を行った。

4 プログラミング例 アセンブリ.start la r2 10 la r3 1 la r4 Loop Loop:add r1 r1 r2 sub r2 r2 r3 brnz r4 r2 st r1 100 stop Pascal progarm sum vari, total : integer; begin total := 0; for i:=1 to 10 do total = total+i end.

5 コンパイラとは・・・？ ある言語で書かれたプログラムをそれと「等価な」 別の言語のプログラムに「翻訳」すること。 例） C コンパイラや電卓 etc… 私たちの作ったコンパイラ Pascal → アセンブリ言語（ SRC2 対応の ）

6 コンパイラの位置づけ 原始プログラム（入力） アセンブラ 機械コード 前処理系 コンパイラ

7 コンパイラの概要（１） 解析部 入力エラーの指摘 生成部・合成部 目的コード生成とコードの最適化

8 コンパイラの概要（２） 字句解析 構文解析 意味解析（型検査など） 中間コード生成 コード最適化 コード生成 解析部 生成部

9 仕様・特徴 Pascal コンパイラ 1 パス（アセンブラコードの出力まで） 中間コードを作った

10 開発フロー コンパイラの開発は以下のようなフ ローを経て行った。 字句解析 構文解析 型検査 中間コード生成 目的コード生成

11 字句解析 ソースコードをトークン（意味を持つ 最小の単位）に分ける。 空白、タブ、改行コードを取り除く。 識別子（名前）を記号表に登録する。

12 字句解析 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. tokentypevalue ・・ : call id( 名前 ) i m cube id( 名前 ) p : 字句解析 記号表

13 字句解析 字句解析の実現には有限オートマトンがよく 利用される。 Pascal の字句解析用に作成した有限オートマト ンで array[1..15] of integer が解析される様子を見る。 array[1..15] of integer

14 字句解析 「 a 」を読むことで図のように 状態が遷移する。 array[1..15] of integer

15 字句解析 「◎」の状態は受理状態を表すが、 遷移できなくなるまで読み込みを続け る。 array[1..15] of integer

16 字句解析 以降の文字は図のように解析され、 array[1..15] of integer

17 字句解析 『 array 』の後の『 [ 』を読み込んだ段 階で、遷移できないため、文字列 「 array 」が確定される。 array[1..15] of integer

18 字句解析 次は『 [ 』から解析を始める。 array[1..15] of integer

19 字句解析 しかしその次が『 1 』となり、次の遷 移先が無いため、『 [ 』だけで確定さ れる。 array[1..15] of integer

20 字句解析 次は数字の『 1 』から解析を始める。 array[1..15] of integer

21 字句解析 次は数字の『 1 』から解析を始める。 array[1..15] of integer

22 字句解析 次は数字の『 1 』から解析を始める。 array[1..15] of integer

23 字句解析 次の『. 』を見て図のように遷移するが、 array[1..15] of integer

24 字句解析 次の『. 』を見て図のように遷移するが、 array[1..15] of integer

25 字句解析 その次の『. 』では遷移先が無いため、直前の 受理状態までの文字列（数字の『 1 』）を確 定し、その直後の文字から再び解析する。 array[1..15] of integer

26 字句解析 数字『１』の直後の『. 』から解析を始 める。 array[1..15] of integer

27 字句解析 数字『１』の直後の『. 』から解析を始 める。 array[1..15] of integer

28 字句解析 数字『１』の直後の『. 』から解析を始 める。 array[1..15] of integer

29 字句解析 二つ目の『. 』で図のように遷移。 array[1..15] of integer

30 字句解析 二つ目の『. 』で図のように遷移。 array[1..15] of integer

31 字句解析 次の数字の『 1 』で遷移先が無いため 『.. 』を確定する。以下同じように解析 し、 array [ 1.. 15 ] of integer となる。 array[1..15] of integer

32 字句解析 字句解析では、 Pascal で使うことのな い記号が現れてしまっているときエ ラーとして検出できる。 例） ￥ ＄ あ etc ・・

33 構文解析 字句解析で分割されたプログラム文 が、 Pascal の構文規則に従っている かチェックする。 もし、従っていない場合はその箇所 をエラーとして検出する。

34 構文解析 『プログラム』 は 『プログラム頭部』『 ; 』 『ブロック』『. 』から成る。 プログラム ＝ プログラム頭部 ; ブロック. 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.

35 構文解析 プログラム頭部 ＝ 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.

36 構文解析 プログラムパラメタ並び ＝ ( 名前並び ) 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.

37 構文解析 名前並び ＝ 名前 ｛, 名前 ｝ ｛ ｝は０回以上の繰り 返し 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.

38 構文解析 ブロック ＝ ラベル宣言部 定数宣言部 変数宣言部 手続き宣言部 実行部 変数宣言部 手続き・ 関数宣言部 実行部 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.

39 構文解析 構文解析は非終端記号（構文規則 の左辺）を関数とすることで実現 した。

40 構文解析 変数宣言部 ＝ [ 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 ” ){ 変数宣言 (); }

41 構文解析 変数宣言 ＝ 名前並び ： 型 i,m, がそれぞれ変数名であり integer 型を持つという情報 を記号表に保存する。 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 != “ : ” ){ error(); } match(); 型 (); }

42 構文解析 変数宣言部 ＝ [ 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 ” ){ 変数宣言 (); }

43 構文解析 構文解析が終了した時点での記号表は右図のよ うになる。 各宣言のトークン、それぞれの型などが決定で きているのがわかる。

44 型検査 記号表の型情報をもとに、変数などが 正しく使われているか検査するフェー ズ。

45 型検査 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. 引数の数と型 戻り値の 型

46 型検査 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. 引数の数と型 戻り値の 型

47 型検査 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.

48 型検査 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. 引数の数と型

49 型検査 各変数の型以外に も、 if 文や while 文な どの条件部が boolean 型かどうか、 代入文の左辺と右 辺の整合性などの 検査も行う。 例） ・ if x < y then z:=x else z:=y ・ while i <> 1 do begin i := i- 1 論理式 (boolean 型 ) でなくてはならな い 左辺と右辺の 整合性

50 コード生成 解析部（字句解析、構文解析、型検 査）によってプログラムが言語の通り 書かれているかどうかチェックできた。 生成部では、解析部で作られた記号表 を参照しながら、コードを生成してい く。

51 中間コード SRC2 では（一般の CPU でも）二項演算しか許 されないが、通常プログラミング言語では自 由な演算が可能になっている。 そのため、プログラム上の計算を全て二項演 算のみに直すことでプログラムを単純にする 作業を施す。それによって作成されるコード を「中間コード」という。 i := 2 * 3 + 8 div 5 二項演算以外の自由な演算が可能

52 三番地コード 中間表現には、三番地コードと呼ぶ表 現を用いるのが一般的。 三番地コードでは、各文が、演算数に 二つの番地、結果に一つの番地、合わ せて三つの番地を用いる。

53 三番地コードの実現 三番地コードの実現に、四つ組という、 四つの欄を持つレコード構造を用いる。 四つ組には、一つの演算子の欄「 op 」 と、二つの演算数の欄「 arg1 」 「 arg2 」と、結果の欄 [result] がある。

54 中間コード i := 2 * 3 + 8 div 5 t 0 := 2 t 1 := 3 t 2 := t 0 * t 1 ｔ 3 := 8 t 4 := 5 ｔ 5 := t 3 div t 4 t 6 := t 2 + t 5 i := t 6 二項演算のみで 計算を定義する。 → 中間コード

55 四つ組 先ほどの中間コードを、四つ組を用いて表現 すると、以下のようになる。 i := 2 * 3 + 8 div 5

56 中間コード 中間コードを生成することで、様々な CPU で動作す るコンパイラを容易に作成することができる。 CPU それぞれのコ ンパイラを作成し なくてはならない。

57 中間コード 中間コードを生成することで、様々な CPU で動作す るコンパイラを容易に作成することができる。 中間コードま でを作成して おくことで、 各 CPU への変 換が容易にで きるようにな る

58 コード生成 中間コードで表さ れたプログラムを、 実際に使用する CPU のアセンブリ 言語に変換してい く。

59 コード生成の例 例 掛け算の場合 番地 op arg1 arg2 result 2 * T-0 T-1 T-2 (2*3) L-2: ldr1T-0 ldr2T-1 mulr3r1r2 str3T-2

60 実行 エラトステネスのふるい（素数を見つ けるアルゴリズム）

61 考察 今回 SRC2 用の PASCAL コンパイラを開発した ことで、今までよりも SRC2 を容易に扱うこと ができるようになった。 今後はハードウェア上でのアプリケーション 開発などを可能にしたということは、今回の 研究で得た大きな財産であろう。