Microsoft PowerPoint - Compiler01note.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Compiler01note.pptx"

よしたかののした
4 years ago
Views:

1 第 1 回の概要 38 号館 4 階 N-411 内線 5459 takasi-i@info.kindai.ac.jp 本科目の内容 (compiler) とは何かの構成の作成方法字句解析構文解析制約検査コード生成最適化情報システムプロジェクト I と連携成績について課題レポート (30%) 中間試験 (30%) 期末試験 (40%) 無届欠席禁止やむを得ず欠席した場合は翌週までに欠席届を提出すること無届欠席が複数回ある場合は試験の点数に関わりなく不受となる昨年度の受講状況学年コース受講者数合格不可不受合格率 3 システム % 4 システムメディア % 4 メディア % 全出席し全レポートを〆切までに提出して不可になった受講生はいない導入 Javaプログラムの実行 Hello. public class Hello { public static void main (tring args[]) { ystem.out.print( Hello! World! n ); Cプログラムの実行 Hello.c #include <stdio.h> int main () { printf ( Hello! World! n"); 機械語 (machine language) 1,0 の並び計算機で実行可能レジスタ, ビット操作が必要ハードウェアに依存 $ c Hello. $ Hello Hello! World! これは? 実行 $ gcc -o Hello Hello.c $ Hello Hello! World! プログラムの作成が困難プログラムの理解が困難プログラムのデバグが困難実行の前にコンパイル (compile) を行う人間が機械語を直接操作するのは効率が悪い 1

2 アセンブリ言語 (assembly language) 機械語命令を簡略名で記述レジスタ, ビット操作が必要ハードウェア依存番地レジスタ等に名前実行は機械語変換が必要機械語よりはプログラムの作成理解デバグが容易しかしまだ人間がアセンブリ言語を直接操作するのは効率が悪い A DC 5 B DC 10 TART D GR0, A ADD GR0, B T GR0, A 高水準言語 (high level language) 命令が基本的に英語ハードウェアに依存しない変数名メソッド名等を付けられるメソッド関数等を定義できる C, Java 等人間にとって理解し易いしかし計算機はそのままでは高水準言語を理解できない public class ample { public static void main (tring args[]) { int n; int a[n] = new int[8]; for (int i=0; i<n; ++i) { a[i] = i*2; int x, y, z; if (x == 1) { ystem.out. print (y) : else { プログラミング言語の翻訳プログラミング言語は文法が明確計算機で翻訳可能高水準言語のプログラム翻訳自然言語は文法に曖昧性計算機での翻訳は難しい低水準言語のプログラムプログラミング言語の文法 < 文 > ::= <if 文 > <while 文 > <for 文 > < 式文 > { < 文の並び > ; ( 空文 ) 文として定義されているもの以外はエラープログラミング言語の文法 <if 文 > ::= if ( < 式 > ) < 文 > または if ( < 式 > ) < 文 > else < 文 > < 式 > ::= < 項 > + < 項 > < 項 > ::= < 因子 > * < 因子 > < 因子 > ::= < 整数 > < 変数 > ( < 式 > ) 全て厳密に定義されている (compiler) (source program) を (object program) に変換 ( 翻訳 ) するプログラム (source program) 入力 (compiler) 出力 (object program) 2

3 (source program) (source program) 高水準言語 (high level language) で記述人間がエディタで作成そのままでは実行不可 C, Java 等 public class ample { public static void main (tring args[]) { int n; int a[n] = new int[8]; for (int i=0; i<n; ++i) { a[i] = i*2; int x, y, z; if (x == 1) { ystem.out.print (y) : else { (object program) (object program) 低水準言語 (low level language) で記述 ( 高水準言語を出力するもある ) 高水準言語からが変換実行可能なプログラムもある機械語, アセンブリ言語 0 PUHI 0 1 POP 5 2 PUH 5 3 PUH 1 4 COP 5 BGE 20 6 JUP 11 7 PUHI 5 8 PUH 5 9 INC と Hello. c public class Hello { public static void main (tring args[]) { ystem.out.print( Hello! World! n ) 人間が読み書き可能 Hello.class ハコセ???2???????????<init>?()V?Code? inenumbertable?main?([/lang/tring;)v? ourcefile? Hello.?????? Hello! World!????Hello?/lang/Object?/lang/ystem?out?/io/Printtream;?/io/Printtream? println?(/lang/tring;)v?!????????????????????* キ? ア???????????????????%????? イ? カ? ア??????????????????? 人間には理解不能実行形式プログラム (executable program) 実行形式プログラム (executable program) 実行可能なプログラム機械語で記述高水準言語からが変換 Hello.c gcc Hello 実行形式 $ gcc -o Hello Hello.c ファイル名を入力すれば $ Hello 実行可能 Hello! World! ( 注意 ) ファイル名入力で実行できるもの全てが実行形式プログラムではないライブラリ (library) 多くのプログラムに共通して使われる機能入出力関数, 数学関数 ( 三角, 指数対数等 ) 等ライブラリ (library) 多くのプログラムに共通して使われる機能 = プログラムごとに作成するのは無駄プログラム 1 入出力関数ライブラリ (library) を用いるプログラム 2 プログラム 3 入出力関数個別に入出力関数作るのは無駄予め作成しておけばいいプログラム 1 プログラム 2 プログラム 3 ライブラリ入出力関数数学関数結合 3

4 コンパイルシステム例プリプロセッサアセンブラ分割コンパイル (separate compile) 分割コンパイル (separate compile) をクラスメソッドごとに分割各クラスごとにコンパイルする入出力部の関数計算部の時間計測部のライブラリ入出力部の関数計算部の時間計測部の結合リンカ (linker) 分割コンパイルの問題点複数のファイルを別々にコンパイル他のファイルのサイズ番地が分からないファイル 1 ファイル 2 ジャンプ番地を後から決定できるようにする再配置可能プログラム (relocatable program) 飛び先の番地は? 再配置可能プログラム (relocatable program) 再配置可能プログラムプログラム先頭を 0 番地として相対的に記述他のプログラムと結合時に番地を再計算 0 OAD OAD 1: 2 ADD 3 BEQ 10 4 INPUT 5 TORE 1002 : 先頭を 0 番地とした番地他のプログラムの番地には仮のラベル分割コンパイル 1 (source) 再配置可能プログラム 1 (relocatable) 実行形式プログラム (executable) 2 (source) 再配置可能プログラム 2 (relocatable) リンカプリプロセッサ (preprocessor) プリプロセッサが高水準言語のの前処理として行う ( 高水準言語 ) プリプロセッサ ( 高水準言語 ) ライブラリリンカ4

5 インタプリタ (interpreter) 高水準言語低水準言語インタプリタ (interpreter) 高水準言語インタプリタ実行実行高水準言語を解釈して処理 BAIC, perl, ruby 等とインタプリタ一旦コンパイルすれば高速で実行可能 ( インタプリタの数十 ~ 数百倍 ) 繰り返し実行するときに有効インタプリタコンパイルすることなく実行可能 1 回だけ実行するときに有効作成実行を繰り返すときに有効処理とインタプリタインタプリタ低水準言語に変換そのまま実行プログラム作成 + 実行コンパイルが必要そのまま実行可能実行速度速遅処理系の多機種への移植難易作成し易さ難易 Java の場合 Java $ c Hello. $ Hello Hello! World! c Java byte code インタプリタ Java byte code は中間コード (intermidiate code) 実行形式ではないインタプリタを使用 + インタプリタの記述言語 (source program) を (object program) に変換 ( 翻訳 ) するプログラムもプログラムその言語は? 高水準言語? 低水準言語? T 図式原始言語を目的言語 T に変換する言語で記述された原始言語目的言語 T 図式 T 記述言語 5

6 T 図式 ( 言語 ) ( 言語 ) ( 言語 T) T 図式例 : Java を JBC(Java byte code) に変換する機械語で記述された c f T f T Hello. Java Java Hello. class c JBC JBC T 図式 ( インタプリタの場合 ) f ( 言語 ) インタプリタ ( 言語 ) T 図式 (Java の場合 ) Java c Java byte code インタプリタ f Hello. Java Java Hello. class c JBC JBC JBC の作成機械語のみ実行可能計算機計算機上で動く高水準言語のが欲しい必要なしかし機械語でプログラムは難しい既存の高水準言語を利用の作成計算機上で動く高水準言語のが欲しい計算機上で動く高水準言語 T のを利用 T T 作成する既存の目的のの作成は高水準言語で行える 6

7 の作成計算機上で動く高水準言語のが欲しいの作成新しい計算機 N 既存の計算機 N 計算機上で動く高水準言語 T のを利用ではTのはどうやって作る? 上で動く既存の高水準言語が無い場合は? 別の計算機 N 上で動くを利用 N 作成する N 既存の N 目的のクロスコンパイル (cross compile) 情報システムプロジェクト I の場合原始言語 : k19 言語 (C 風言語 ) 目的言語 : V(Virtual tack achine) アセンブラ言語記述言語 : Java k19 Kc. V k19 Java Java 作成する sort.k c k19 既存の Kc.classV V JBC JBC JBC 既存のインタプリタ sort.asm V vsm 授業で配布するインタプリタの構造字句解析系構文解析系制約検査系中間コード生成系最適化系目的コード生成系字句解析系 (lexical analyzer, scanner) 字句解析系空白コメントを読み飛ばす単語 (token) に区切るマイクロ構文エラーを検出 if (ans >= 123 ) /* ans の値で分岐 */ ( 改行 ) ( 空白 )output ( 1 ) ; 予約語 if 左括弧 ( 変数 ans 不等号 >= 整数 123 右括弧 ) 予約語 output : 構文解析系 (syntax analizer, parser) 構文解析系構文解析木を作成 if (ans > 123 ) output ( 1 ) ; 変数 if 文 if ( 式 ) 文式 > 式 ans 123 出力文整数 output ( 式 ) ; 文字 1 7

8 制約検査系 (constraint checker) 制約検査系変数の未定義二重定義型の不一致などを検査変数 x は未定義変数 i は配列ではない代入の左辺が変数ではない int i, j; x = 0; i[10] = 5; 0 = 10; 中間コード生成系 (semantics analyzer, intermediate code generator) 意味解析系単純な命令の列 ( 中間コード ) を生成する中間コード (intermediate code) ハードウェアには依存しない 3 番地コード (three address code) が多用される A := B op C if (a>0) b:=2*a+b; if (a 0) goto : t := 2 * a b := t + b : 中間コードを用いる利点中間コードはハードに依存しない異なるハードで共通で使用可能中間コード中間コード中間コード中間コード N 計算機用計算機 N 用最適化系 (optimizer) 最適化系中間コードを改良実行速度を速くメモリ使用領域を小さく if (a 0) goto : t := 2 * a b := t + b : if (a 0) goto : t := a + a b := t + b : 掛け算より足し算の方が速い目的コード生成系 (object code generator) 目的コード生成系変数の記憶位置決定レジスタの割付 D GR1, a EA GR1, 0, GR1 if (a 0) goto : t := a + a b := t + b : JI : JZE : ADD GR1, a ADD GR1, b T : GR1, b 表管理 (table manegement, bookkeeping) 表管理中の変数, 関数等の名前, 型情報等を記憶 int i, j; char ch; int a[10]; 変数名型サイズ番地 i int 1 0 j int 1 1 ch char 1 2 a int[] 10 3~12 8

9 管理表の構成誤り処理 (error handling) 誤り処理が言語の制約を満たしていない場合にエラーメッセージを出す int あ, い, う ; if () output (1); 5 = a; 1 行目で字句解析エラー : 変数名に日本語は使えません 2 行目で構文解析エラー : if 文の条件式がありません 3 行目で制約検査エラー : 代入の左辺が変数ではありません字句解析構文解析制約検査中間コード生成最適化目的コード生成字句解析誤り処理構文解析誤り処理制約検査誤り処理 ( 情報システムプロジェクトIの場合 ) K18 言語字句解析字句解析誤り処理構文解析構文解析誤り処理制約検査制約検査誤り処理中間コード生成最適化目的コード生成 Vアセンブラ言語管表理の構成処理の流れ ( 情報システムプロジェクト I の場合 ) output (ab); 字句解析系 output ( 変数名 ) ; 構文解析系マイクロ構文の文法に従い解析マクロ構文の文法に従い解析 <output_statement> ::= output ( <exp> ) ; コード生成系 1. PUH ab 2. OUTPUT V アセンブラの文法に従い生成スタックマシン (stack machine) スタックマシン (stack machine) スタックマシン Instruction Iseg[] : アセンブラプログラムを格納 int Dseg[] : 実行中の変数値を格納 int tack[] : スタック ( 作業場所 ) int Program Counter : 現在の Iseg の実行位置 int tack Top : 現在のスタックの操作位置 Program Counter 3 Iseg 0 PUHI 0 1 PUHI 3 2 AGN 3 PUHI 7 4 AGN 5 ADD 6 OUTPUT 7 HAT Dseg tack tack Top 1 9

10 Iseg と Program Counter V の動作 1. Iseg の PC 番地の命令を実行 2. PC := PC+1 or ジャンプ命令で指定した先 Program Counter 34 Iseg 0 PUHI 0 1 PUHI 3 2 AGN 3 PUHI 7 4 AGN 5 ADD Dseg 実行中の変数値を格納 int i, j, x=2, y=3; char c = a ; int a[5]; Dseg 0 0 i 1 0 j 2 2 x 3 3 y 4 a c 5 0 a[0] 6 0 a[1] 7 0 a[2] 8 0 a[3] 9 0 a[4] tack tack 作業場所, 処理中のデータの一時置き場 ast In First Out tack tack Top 1 最後に入れたデータの位置初期値 = -1 ( スタック内にデータ無し ) プログラムの構造 ( 字句解析系構文解析系 ) Filecanner. ファイル探査部 char nextchar(); //1 文字読み込む k 言語 exicalanalyzer. 字句解析部 Kc. 構文解析部 char Token Token nexttoken(); void parse<a>(); // トークンを切り出す // 非終端記号 <A> を // 解析をする Token. トークン定義部 boolean checkymbol(ymbol); // トークンを識別する ymbol. トークン名列挙部プログラムの構造 ( コード生成系 ) Kc. 構文解析部 void parse<a>(); // 非終端記号 <A> を // 解析をする VarTable. 変数表格納部 boolean registernewvariable(); // 変数を加える boolean exist(); // 変数の存在判定 boolean checktype(type); // 型識別 PseudoIseg. 命令表格納部 int appendcode(); // 命令を加える void replacecode(); // 命令を変更する void dump2file(); // 命令を出力する Var. 変数部 Type. 型名列挙部 Instruction. 命令部 Operetor. 命令名列挙部 V アセンブラ宿題言語理論とオートマトンの復習をする有限オートマトン正則表現正則文法 BNF 記法, EBNF 記法 10

Microsoft Word - Javacc.docx

Microsoft Word - Javacc.docx JavaCC 実習レポート課題について以下の実習のためにコンパイラのページ http://www.info.kindai.ac.jp/compiler/ から javacc.zip をダウンロードしてください javacc.zip は以下のファイルから成ります javacc/ sample0.k, sample1.k, samplell2.k : k 言語の例プログラム sample0.asm,