§§§コンパイラに関する実験§§§ 情報工学科 1031060322 松本亮介 1、プログラムと各部の説明 作成したコンパイラのプログラムの説明を行う。 最初に作成したコンパイラのプログラムを記述しておく。 プログラムソース'compiler.c'ここから↓ ------------------------------------------------------------------------------------------------------------- /*-------------------------------------------------------------------------------------------- 四則演算を解析するコンパイラ ---------------------------------------------------------------------------------------------- 作成者:松本亮介(Ryousuke Matsumoto) 作成日:2006.01.31 ---------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------- ファイル名: compiler.c ---------------------------------------------------------------------------------------------*/ #include #include #include #define MAXLENG 128 #define MAXLENGS 256 /* ------------サブルーチンここから--------------- */ int lexical_analysis(void);/* 字句解析関数 */ int syntactic_analysis_1(void);/* 構文解析関数1 */ void syntactic_analysis_2(void);/* 構文解析関数2 */ void syntactic_analysis_3(void);/* 構文解析関数3 */ void syntactic_analysis_4(void);/* 構文解析関数4 */ int code_generation(void);/* コード生成関数 */ /* ----------------------------------------------- */ /* ---------グローバル宣言--------- */ FILE *fp,*fp2; /* ----------字句解析の字句と種類を格納する構造体ここから-------- */ struct character{ char jiku[MAXLENG]; int result; }lexical_result[MAXLENG],syntactic_result[MAXLENG]; /* ---------字句解析の字句と種類を格納する構造体ここまで--------- */ int i=0,j=0,n,o; int num,gyou_kaihi; int stack[MAXLENGS]; char op,*temp[MAXLENGS]; /* -------------------------------- */ /* ---------------------------------------メインルーチンここから----------------------------------------- */ int main(int argc,char *argv[]){ int ni; if((fp=fopen(argv[1],"r"))==NULL){ printf("Cannot Open File.\n"); exit(1); } fp2=fopen("compiler_data.txt","w"); ni=1; do{ while(op!=';'){ gyou_kaihi=ni; fprintf(fp2,"【%d-gyoume】\n",ni); ni++; fprintf(fp2,"【motono-siki】\n"); lexical_analysis();/* 字句解析関数呼び出し */ fprintf(fp2,"\n"); syntactic_analysis_1();/* 構文解析関数呼び出し */ code_generation();/* コード生成関数呼び出し */ } op=getc(fp); }while(op!=EOF); printf("\nIt succeeded in making 'compiler_data.txt'.\n"); return 0; } /* ------------------------------------------メインルーチンここまで--------------------------------------- */ /* -------------------------------------サブルーチン(字句解析)ここから---------------------------------- */ /* --------------------------------- ・構造体のresultに字句の種類を格納 ・構造体のjikuに字句を格納 --------------------------------- */ int lexical_analysis(){ int d,h,li,li2; d=0,h=0; for(li=0;libcc32 compiler.c Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland compiler.c: Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland C:\Documents and Settings\i865gpen4\デスクトップ\提出レポ(3回後期)\コンパイ ラ動作試験>dir C:\Documents and Settings\i865gpen4\デスクトップ\提出レポ(3回後期)\コンパ イラ動作試験 のディレクトリ 2006/01/29 01:26 . 2006/01/29 01:26 .. 2006/01/29 01:19 13,890 compiler.c 2006/01/29 01:26 62,976 compiler.exe 2006/01/29 01:26 9,329 compiler.obj 2006/01/29 01:26 393,216 compiler.tds 2006/01/28 23:32 39 siki_1.txt 2006/01/28 23:41 27 siki_2.txt 2006/01/29 00:10 126 siki_3.txt 7 個のファイル 479,603 バイト 2 個のディレクトリ 29,980,884,992 バイトの空き領域 C:\Documents and Settings\i865gpen4\デスクトップ\提出レポ(3回後期)\コンパイ ラ動作試験>compiler siki_1.txt It succeeded in making 'compiler_data.txt'. C:\Documents and Settings\i865gpen4\デスクトップ\提出レポ(3回後期)\コンパイ ラ動作試験>dir C:\Documents and Settings\i865gpen4\デスクトップ\提出レポ(3回後期)\コンパ イラ動作試験 のディレクトリ 2006/01/29 01:27 . 2006/01/29 01:27 .. 2006/01/29 01:19 13,890 compiler.c 2006/01/29 01:26 62,976 compiler.exe 2006/01/29 01:26 9,329 compiler.obj 2006/01/29 01:26 393,216 compiler.tds 2006/01/29 01:27 986 compiler_data.txt 2006/01/28 23:32 39 siki_1.txt 2006/01/28 23:41 27 siki_2.txt 2006/01/29 00:10 126 siki_3.txt 8 個のファイル 480,589 バイト 2 個のディレクトリ 29,980,880,896 バイトの空き領域 ---------------------------------------------------------------------------- ↑ここまで 3、動作例とその説明 (1)、siki_1.txt x := 3; y := 5; z := x * y - (y - x); この対象言語は先生にもらった資料に記述されているもので、まずはこれをコンパイルにより解析してみる。 今回作ったコンパイラは、同じつづりのものを同じ字句として解析することができないため、同じであってもそれぞれ前から読んでいき、順次別の字句とアドレスを設定していっている。 以下の例では、 z := x * y - (y - x); のxとyは、それぞれ式の中に2回づつ使われているが、今回のプログラムでは前から順に以下のようにアドレスを設定しているのがわかる。 kigou1 kigou2 address z i1.3 004128DC x i2.3 00412960 y i3.3 004129E4 y i4.3 00412B70 x i5.3 00412BF4 このように、したことでメモリをムダに使ってる感が否めないが、計算の結果は同様のものが得られるためによしとした。 しかし、字句解析としてはこれは不十分な場所だといえる。 時間があれば、これも同じつづりのものは同じ字句・同じアドレスとして設定するようにしたい。 また、資料の4.2.3の課題3-1の問題も1行目と2行目のコード生成を見る限りでは、クリアしていることが分かる。 とりあえず、出力されたテキストファイルのコンパイラのデータの説明を個別にしておく。 (@)【1-gyoume】 読み込んだ対象言語のテキストファイルの1行目を示している。 つまり、この動作結果の場合は1行目の解析は 'x := 3;' の解析を示している。 (A)【motono-siki】 読み込んだ対象言語を字句解析により解析し、その解析した字句で元の対象言語を書き直したものになっている。 1行目の解析を例にあげると、 x → i1.1 3 → num1.1 と字句解析し、対象言語を解析した字句と置き換えて i1.1 := num1.1 と表現している。 (B)【gyakupooranndokihou-siki】 字句解析した対象言語を、構文解析により逆ポーランド記法で表したものに書き換えている。 1行目の解析を例にあげると、元の対象言語が以下なので、 i1.1 := num1.1 これを逆ポーランド記法で書き換える事で、以下のように表現される。 i1.1 num1.1 := (C)【kigouhyou/teisuuhyou】 ここで、字句解析によって解析された識別子と定数の表を表示している。 1行目の例では、上記で説明した通り、 x → i1.1 3 → num1.1 と字句が表現し直されているので、以下のような記号表と定数表が表示されている。 【kigouhyou/teisuuhyou】 kigou1 kigou2 address x i1.1 004128DA teisu1 teisu2 address 3 num1.1 00412960 ここで、 kigou1 → 元の対象言語におけるつづり kigou2 → 字句解析によって表現し直された字句 adress → 字句解析によって設定された字句が格納されているメモリ上のアドレス(パソコン環境によって当然変わる) となっている。 (D)【code-generation】 コード生成の結果が表示されている。 コードはアセンブリ言語で表現されており、アドレスは記号表・定数表で設定されているメモリ上のアドレスに対応している。 1行目のコード生成を例にあげると、コードが、 LOAD 00412960 STORE 004128DA となっていて、アドレスと字句の対応が、 kigou1 kigou2 address x i1.1 004128DA teisu1 teisu2 address 3 num1.1 00412960 となっているので、 まず、'LOAD 00412960'により、ACCにアドレス'00412960'上のデータ、記号表より'3'が置かれる。 次に、'STORE 004128DA'により、ACC上のデータつまりは、'LOAD 00412960'によって読み込まれた'3'が、アドレス'004128DA'のメモリに読み込まれる。 このときアドレス'004128DA'は、'x'が置かれているために、'x := 3;'という意味になり、マシンが'x := 3;'という対象言語をアセンブリ言語により理解したことになる。 ここで、個別に各コードの説明をしておく。 命令コード 意味 LOAD M (M) → ACC STORE M (ACC) → M ADD M (ACC) + (M) → ACC SUB M (ACC) - (M) → ACC MUL M (ACC) * (M) → ACC DIV M (ACC) / (M) → ACC ※()はそのアドレス上に置かれているデータの事を示している。 【siki_1.txt】の動作結果をみると、上記に説明した内容を表現できているようだ。 ↓【siki_1.txt】の動作結果ここから --------------------------------------------------- 【1-gyoume】 【motono-siki】 i1.1 := num1 【gyakupooranndokihou-siki】 i1.1 num1.1 := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address x i1.1 004128DA teisu1 teisu2 address 3 num1.1 00412960 【code-generation】 LOAD 00412960 STORE 004128DA 【2-gyoume】 【motono-siki】 i1.2 := num1.2 【gyakupooranndokihou-siki】 i1.2 num1.2 := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address y i1.2 004128DB teisu1 teisu2 address 5 num1.2 00412963 【code-generation】 LOAD 00412963 STORE 004128DB 【3-gyoume】 【motono-siki】 i1.3 := i2.3 * i3.3 - (i4.3 - i5.3) 【gyakupooranndokihou-siki】 i1.3 i2.3 i3.3 * i4.3 i5.3 - - := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address z i1.3 004128DC x i2.3 00412960 y i3.3 004129E4 y i4.3 00412B70 x i5.3 00412BF4 teisu1 teisu2 address 【code-generation】 LOAD 00412960 MUL 004129E4 STORE 00412D71 LOAD 00412B70 SUB 00412BF4 STORE 00412D72 LOAD 00412D71 SUB 00412D72 STORE 004128DC --------------------------------------------------- ↑【siki_1.txt】の動作結果ここまで。 --------------------------------------------------- (2)、siki_2.txt abc := e3 * 256 - abc / e3; これは、指導書に書かれている例の対象言語である。 相変わらず同じつづりのものを同じ識別子・定数として表現はできていないが、それ以外の問題はないと思われる。 一時的にデータを置いて置くアドレス(以下の例でいうと'00412BEE'や'00412BED'など)も、記号表と定数表で設定されている字句のアドレスと重複されることなく設定されているのがわかる。 ↓【siki_2.txt】の動作結果ここから --------------------------------------------------- 【1-gyoume】 【motono-siki】 i1.1 := i2.1 * num1.1 - i3.1 / i4.1 【gyakupooranndokihou-siki】 i1.1 i2.1 num1.1 * i3.1 i4.1 / - := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.1 004128DA e3 i2.1 0041295E abc i3.1 00412AEA e3 i4.1 00412B6E teisu1 teisu2 address 256 num1.1 004129E4 【code-generation】 LOAD 0041295E MUL 004129E4 STORE 00412BED LOAD 00412AEA DIV 00412B6E STORE 00412BEE LOAD 00412BED SUB 00412BEE STORE 004128DA --------------------------------------------------- ↑【siki_2.txt】の動作結果ここまで。 --------------------------------------------------- (3)、siki_3.txt abc := def * 256 - e8; abc := def * 256 - (e8 + 512); abc := def * 256 + (e8 + 512); abc := def * 256 / (e8 + 512); abc := def * 256 * (e8 + 512); 【siki_3.txt】では、スタック上のACCの位置によるコード生成の場合分けを全てふまえたような対象言語を設定して、全ての場合において、正確にコード生成ができているかを調べてみた。 指導書における、表4の命令コード生成表を参考にした。 1行目は命令コード生成表の1、2、5の命令を使って生成している。生成されたコードをみると正確に生成されている。 2行目は命令コード生成表の1、4、5の命令を使って生成している。生成されたコードをみると正確に生成されている。 3行目は命令コード生成表の1、3、5の命令を使って生成している。生成されたコードをみると正確に生成されている。 4行目は命令コード生成表の1、4、5の命令を使って生成している。生成されたコードをみると正確に生成されている。 5行目は命令コード生成表の1、3、5の命令を使って生成している。生成されたコードをみると正確に生成されている。 ↓【siki_3.txt】の動作結果ここから --------------------------------------------------- 【1-gyoume】 【motono-siki】 i1.1 := i2.1 * num1.1 - i3.1 【gyakupooranndokihou-siki】 i1.1 i2.1 num1.1 * i3.1 - := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.1 00412906 def i2.1 0041298A e8 i3.1 00412B16 teisu1 teisu2 address 256 num1.1 00412A10 【code-generation】 LOAD 0041298A MUL 00412A10 SUB 00412B16 STORE 00412906 【2-gyoume】 【motono-siki】 i1.2 := i2.2 * num1.2 - (i3.2 + num2.2) 【gyakupooranndokihou-siki】 i1.2 i2.2 num1.2 * i3.2 num2.2 + - := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.2 00412907 def i2.2 0041298B e8 i3.2 00412B9B teisu1 teisu2 address 256 num1.2 00412A13 512 num2.2 00412C23 【code-generation】 LOAD 0041298B MUL 00412A13 STORE 00412D1D LOAD 00412B9B ADD 00412C23 STORE 00412D1E LOAD 00412D1D SUB 00412D1E STORE 00412907 【3-gyoume】 【motono-siki】 i1.3 := i2.3 * num1.3 + (i3.3 + num2.3) 【gyakupooranndokihou-siki】 i1.3 i2.3 num1.3 * i3.3 num2.3 + + := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.3 00412908 def i2.3 0041298C e8 i3.3 00412B9C teisu1 teisu2 address 256 num1.3 00412A16 512 num2.3 00412C26 【code-generation】 LOAD 0041298C MUL 00412A16 STORE 00412D9D LOAD 00412B9C ADD 00412C26 ADD 00412D9D STORE 00412908 【4-gyoume】 【motono-siki】 i1.4 := i2.4 * num1.4 / (i3.4 + num2.4) 【gyakupooranndokihou-siki】 i1.4 i2.4 num1.4 * i3.4 num2.4 + / := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.4 00412909 def i2.4 0041298D e8 i3.4 00412B9D teisu1 teisu2 address 256 num1.4 00412A19 512 num2.4 00412C29 【code-generation】 LOAD 0041298D MUL 00412A19 STORE 00412E1D LOAD 00412B9D ADD 00412C29 STORE 00412E1E LOAD 00412E1D DIV 00412E1E STORE 00412909 【5-gyoume】 【motono-siki】 i1.5 := i2.5 * num1.5 * (i3.5 + num2.5) 【gyakupooranndokihou-siki】 i1.5 i2.5 num1.5 * i3.5 num2.5 + * := 【kigouhyou/teisuuhyou】 kigou1 kigou2 address abc i1.5 0041290A def i2.5 0041298E e8 i3.5 00412B9E teisu1 teisu2 address 256 num1.5 00412A1C 512 num2.5 00412C2C 【code-generation】 LOAD 0041298E MUL 00412A1C STORE 00412E9D LOAD 00412B9E ADD 00412C2C MUL 00412E9D STORE 0041290A --------------------------------------------------- ↑【siki_3.txt】の動作結果ここまで。 (4)、エラー表示・不完全な部分。 ・対象言語に式の終わりを表す記号';'がないと、無限ループになってしまう。 ・(()のような対象言語の場合でも、(()→()と判断し解析してしまう。 ・':'の次に'='がこなかったとき字句解析エラーを表示する。 ・逆ポーランド記法において、最初に識別子か定数がこなかった場合、コード生成エラーを表示する。 4、コンパイラ検討 (1)、字句解析による誤り処理。 字句解析における誤り処理としては、読み込む文字が未知の場合におこることがある。 処理できる言語において、定義していない字句を読み込んでしまった場合、この字句解析は適したトークンを返せない。 (2)、コンパイラに用いられるほかの構文解析法について。 作成したコンパイラのプログラムでは、LL(1)文法において、下向き構文解析を再帰的に用いるものであった。その他には次のような構文解析がある。 (@)、シフト還元構文解析 入力文字を先頭からスタックに読み込んでいき、構文解析表を参考にして、順次文法規則で還元していく、上向き構文解析。特徴は最右導出の逆順で解析する手法である。最右導出とは、常に最も右の非終端記号を生成規則によって書き換えることが出来る。 (A)、LR構文解析 シフト還元構文解析のうちで最も一般的で、効率がよいものである。解析できる文法もLL(1)文法よりも多く、決定性構文解析のうちでは最も広い範囲を解析することが可能。左から右に解析して分かる最も早い段階で構文誤りを検出できる。LR構文解析では、ある時点まで読んで分かる複数の可能性を状態として覚えておく。 (B)、SLR(1)構文解析 LR構文解析の中で最も単純で、還元のために先読み記号の決め方はfollowを用いる。構文解析表は、LR(0)集成を用いる。 (C)、正準LR(1)構文解析 SLR(1)構文解析に対し、正準LR(1)集成から構文解析表を作る。SLR(1)より状態を細分化することにより衝突を回避する。それによって、状態数は多くなる。一つ先の先読み記号を持つために、SLR(1)より多くの情報を保持する事が出来る。 (D)、LALR(1)構文解析 これは、正準LR(1)の状態数をへらしたものである。解析できる文法は正準LR(1)と等しい。 現在、実用化されているコンパイラのほとんどがこれらのLR構文解析であるようだ。 (3)、意味解析と最適化 (@)、意味解析 意味解析とは、プログラムソースに出てきた1つの意味が、そのプログラムを通して、一貫しているかどうかの意味規則の対応を取ることである。 例えば、C言語において、intで宣言した変数は、そのプログラムでは終始intとしてしか使えない、こういった変数や、定数などの情報を管理するために記号表を作る。 また、これ以外に、変数のスコープの管理も意味解析に含まれる。ブロックが入れ子になったとき、深いブロックにある変数は、そのブロックより浅いブロックからは範囲外である。スコープ管理も記号表にブロックレベルの欄を作ることによって、制御する事が出来る。 コンパイラの扱える文法が複雑になったり、プログラムソースが長くなるにつれて、意味解析での記号表は膨大な大きさになる。そのために、記号表の検索方法として、線形検索や2分法、ハッシュ法など、工夫されるのが一般的である。 (A)最適化 最適化とは、プログラムの実行時間を短くする目的で、定数同士の掛け算や、同じ計算の省略、実行前からの害損の条件分岐など、コンパイル時に簡略することで、実行効率をあげることである。中間コードの形としては、三番地コードや四つ組などが有名である。コンパイラによっては、何度も最適化し、中間コードを生成するものもあるが、一般的に最適化はコンパイラの要であるために、そう方法については、非公開なこともある。 (4)、条件文、繰り返し文に対するコード生成 2重のif文 if(e1){ if(e2)s1 else s2 } に対して、以下のようなコード生成が得られる。 --------------------------------------- e1を計算し、結果が偽ならL1へ移動する。 e2を計算し、結果が偽ならL2へ移動する。 S1の実行 jmp L3 L2:s2の実行 L3: L1: --------------------------------------- L1とL3はそれぞれ、外側の内側のif文のコードの終わりを表すラベルである。これらは同じ場所を表すので、一方のラベルだけを使い、以下のようにするほうが、より簡潔のなる。 --------------------------------------- e1を計算し、結果が偽ならL1へ移動する。 e2を計算し、結果が偽ならL2へ移動する。 S1の実行 jmp L1 L2:s2の実行 L1: --------------------------------------- (5)、字句解析器生成系と構文解析器生成系 (@)、字句解析器生成系 字句解析器生成系とは、文法ファイルに世紀表現で、処理対象の字句の定義を書いておく事で、自動的に字句解析プログラムを生成してくれるツールのことを言う。 有名なのが、lexとよばれ、yacc(次に説明する構文解析器生成系のツール)で生成する構文解析プログラムが呼び出す字句解析プログラムをlexが自動生成する。文法ファイルの記述は、正規表現で字句を記述する。 (A)、構文解析器生成系 構文解析器生成系とは、字句解析器生成系と同様に、記号列だけを見て会席できるように言語を設計し、自動的に構文木をつくるツールのことである。最も有名なものとして、yaccというのがある。yaccは、文法ファイルという自分の扱いたい文法を記述したファイルを、yaccにに入力することで、自動的にC言語のソースコードを生成してくれる。yaccでは、上向き構文解析で奇異席するので、今回の実験のLL(1)文法ではエラーが発生するために使えない。文法ファイルは、3つの部分からなっており、ヘッダ、規則部、ユーザー定義部である。最も重要な部分は規則部で、ここにBNFで対象言語を書くと、後は自動で解析してくれる。 5、実験に対する感想や独自の考察 今回は前期よりもさらに膨大なプログラムを作らなければならないため、よりプログラミングに対する深い理解をしなけらばならなかった。 最初はできるか不安だったが、やってるうちに楽しくなり、なんとかここまで作ることができた。 このプログラム作成のおかげで、C言語に対する深い関心を持てたと思う。