言語プロセッサ2015 Language Processors 2015

言語プロセッサ2015 Language Processors 2015
平成27年9月28日（月）～平成28年1月20日（木）東京工科大学コンピュータサイエンス学部亀田弘之 url: kameken.clique.jp/Lectures/Lectures2015/Compiler2015/

まずはイントロから… なぜ言語プロセッサを学ぶのか？（Why do we study a course 言語プロセッサ ?）
Copyright© School of Computer Science, Tokyo University of Technology

複雑だなぁセキュリティネットワーククラウドコンピューティングモバイル

Divide and Conquer （困難は分割し、しかる後に統合せよ！）

出力 (Output) 処理入力 (Input)

コンピュータの階層化モデル Examples Application Software Operating System
Instr. Set Architecture Micro Architecture Logic Module Digital Circuit Analog Circuit Devices (elements) Physics (Electron etc.) Program Device Driver Instruction set & Register Data Bus, Controller Adder, Register AND Gate, OR Gate Amplifier, Filter Diode, Transistor Electron, Photon Copyright© School of Computer Science, Tokyo University of Technology

? 高水準言語ー＞論理回路 main( ){ int a; a = 1; printf(“%d”,a); } 高水準言語
高水準言語ー＞論理回路 main( ){ int a; a = 1; printf(“%d”,a); } ? 高水準言語論理回路 Copyright© School of Computer Science, Tokyo University of Technology

言語プロセッサとは高水準言語によるプログラム（処理手順の記述,命令群）－＞論理回路制御指令群（注）・命令：command
　　（処理手順の記述,命令群）　　－＞　論理回路制御指令群（注）・命令：command 　　　・指令：instruction Copyright© School of Computer Science, Tokyo University of Technology

.def ___main; .scl 2; .type 32; .endef .text .globl _main
$ cat p01.s .file "p01.c" .def ___main; scl 2; type 32; .endef .text .globl _main .def _main; .scl 2; type 32; .endef _main: pushl %ebp movl %esp, %ebp subl $8, %esp andl $-16, %esp movl $0, %eax movl %eax, -4(%ebp) movl -4(%ebp), %eax call __alloca call ___main leave ret Copyright© School of Computer Science, Tokyo University of Technology

main(){ int a; a = 20; a = a + 30; a = 100 - a; a = a*7; }

.def ___main; .scl 2; .type 32; .endef .text .globl _main
$ cat p01.s .file "p01.c" .def ___main; scl 2; type 32; .endef .text .globl _main .def _main; .scl 2; type 32; .endef _main: pushl %ebp movl %esp, %ebp subl $8, %esp andl $-16, %esp movl $0, %eax movl %eax, -8(%ebp) movl -8(%ebp), %eax call __alloca call ___main movl $20, -4(%ebp) leal -4(%ebp), %eax addl $30, (%eax) movl $100, %eax subl -4(%ebp), %eax movl %eax, -4(%ebp) movl -4(%ebp), %edx movl %edx, %eax sall $3, %eax subl %edx, %eax leave ret Copyright© School of Computer Science, Tokyo University of Technology

$ gcc -S filename.c $ ls $ cat filename.s

コンパイラの処理工程概要ソース言語読み込み字句解析構文解析中間語生成コード生成目的言語

言語プロセッサの種類インタープリタ（interpreter）コンパイラ (compiler)

数式の例 A = B*3.14 + C/A Area = 2*3.14*R*R

数式の解析 kingaku = teika + teika * shouhizei

数式の解析読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析＝ kingaku teika + shouhizei * Copyright© School of Computer Science, Tokyo University of Technology

分析合成ソース言語読み込み字句解析構文解析中間語生成コード生成目的言語

数式の解析読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析＝ kingaku teika + shouhizei * Copyright© School of Computer Science, Tokyo University of Technology

数式の解析読み込み（文字列として）読み込み “kingaku = teika + teika * shouhizei”
要素(token)の切り出し　字句解析 “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析　構文解析＝ kingaku teika + shouhizei * Copyright© School of Computer Science, Tokyo University of Technology

数式の解析読み込み字句解析構文解析ファイルからの入力技法有限オートマトンの理論正規文法正規表現スタックオートマトン理論
文脈自由文法 Copyright© School of Computer Science, Tokyo University of Technology

学んで得られるもの言語理論とオートマトンプログラミング技法抽象的・論理的な思考への慣れソフトウェア分野における基本的概念
正規表現 etc. プログラミング言語へのより深い理解プログラミング技法プログラミング力（知識）アップ洗練されたアルゴリズムの理解　　などなど Copyright© School of Computer Science, Tokyo University of Technology

言語プロセッサ関連は、コンピュータサイエンスの英知が集積されている！
この授業を取った人は先見の明がある！ Copyright© School of Computer Science, Tokyo University of Technology

授業概要人間はより複雑で高度な処理手順（プログラム）を記述するために、C言語やJava言語などの高級言語を考え出したが、それらの言語で記述されるプログラムは実際には、より低水準な機械語に翻訳し直さなければコンピュータは直接理解し実行することはできない。このような翻訳処理を行うプログラムは、一般に“言語プロセッサ”と呼ばれている。本講義では言語プロセッサのうち特にコンパイラを取り上げ、これに関する原理と設計方法について講義する。また部分的ではあるが実際に簡易コンパイラを作成する。このことによって、コンパイラについて深い理解を得るとともに、自力でコンパイラを設計するための基礎的な設計・プログラミング技術をもあわせて修得することを目指す。具体的な学習目標は、1) 言語プロセッサの処理の流れ、2)語彙解析の役割と仕組みそれぞれを自分の言葉で説明できること、3)正規表現を利用した語彙解析プログラムの動作を理解できること、4)構文解析の役割と仕組みを理解できること、5)Flex、Bison、Antlrを使った言語プロセッサ作成手順を説明できること、である。学生諸君が本授業を履修することにより、プログラミング言語に関する造詣を深めることを期待する。 Copyright© School of Computer Science, Tokyo University of Technology

到達目標コンパイラやインタプリターの処理の流れを理解し、説明できる。字句解析の原理、基本的処理を理解する。
構文解析の原理、基本的処理を理解する。中間言語表現を理解する。最適化処理の概要と処理内容を知り、説明できる。 Flex,Bisonを用いて簡単な言語処理プロセッサを自作できる。 AntlrWorksなど、他のコンパーラーコンパーラーの存在について知る。 Copyright© School of Computer Science, Tokyo University of Technology

言語プロセッサ2015 東京工科大学CS学部 (担当亀田弘之)
コード生成の概要原始プログラム目的コード字句解析構文解析意味解析中間コード生成コード生成最適化中間コード中間コード言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

もう一度具体例で確認 program daikei(input,output); var abc,xyz,t:integer; begin write('abc xyz = '); read(abc,xyz); abc := xyz + abc * 123; writeln('result = ',abc) end. 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

abc := xyz + abc * 123; （読み込み）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

abc := xyz + abc *123；トークンへの分解（字句解析）（変数１，　abc ）（代入記号，　:= ）（変数２，　xyz ）（加算記号，　＋）（変数１， abc ）（乗算記号，　＊）（定数１，　123 ）（文区切り記号，　；）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

abc := xyz + abc * 123 （構文解析）代入記号変数１加算記号変数２乗算記号変数１定数１言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

コード生成の概要原始プログラム目的コード字句解析構文解析意味解析中間コード生成コード生成最適化中間コード中間コード言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

意味解析名前の宣言と使用との対応付け例： int x, y; float z; x = z * y; 整数型 = 浮動小数点型　＊　整数型言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

意味解析例： int x, y; float z; x = z * y; 整数型 = 浮動小数点型　＊　整数型整数型 = 浮動小数点型＊浮動小数点型整数型 = 浮動小数点型整数型 = 整数型言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

変数等の宣言された情報を参照する必要がある。＝＞　記号表を用意しよう！・名前 (spell) ・型 (int, float, …, struct char *, etc.) ・記憶域 (static, auto, …) ・その他 (const, etc.) 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

変数の場合（例）型大きさ（バイト数）有効範囲通常変数/仮引数宣言の有無（暗黙宣言が許されている言語）実行時に割り当てられるアドレス　など言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

関数名・手続き名（例）仮引数の個数および仮引数の型戻り値の型（関数の場合）有効範囲コードの先頭番地（entry point）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

定数名（例）型定数の内部表現アドレス言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

型名（例）型の種別(int, float, array, structure, etc.) 型の種別ごとの情報（arrayならば、添字の範囲、要素の型など）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

記号表に対する操作登録参照更新削除＝＞表探索問題(Table Search Problem) 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

記号表の操作は速くなければならない＝＞どうすればいいのか？＝＞　これ以降の議論は、　　「データ構造とアルゴリズム」や　　「計算可能性と計算量」など　　の授業で学んでください。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

探索アルゴリズム線形探索法（改良版には番兵法）２分探索法ハッシュ法（ハッシング法）２分最適木法 B木法 etc. 自分で作るときには、まず「線形探索」でOK。その後、例えばhashing法にしてみよう。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

中間言語原始プログラムの構文解析結果は、「解析木」である。実際には、解析木とは異なる内部表現を使うことも多い。＝＞これを「中間言語」と呼ぶ。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

中間言語とはコンパイラは、原始プログラムを目的プログラムに変換する途中段階で、中間的なプログラムを作る場合がある。これを「中間コード」あるいは、「中間言語プログラム」といい、これを記述する言語を「中間言語」という。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

中間言語構文木後置記法（Polish notation）三つ組四つ組言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

１．構文木（いままで幾つか例を見てきましたので省略）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

２．後置記法前置記法(prefix notation) 中置記法(infix notation) 後置記法(postfix notation) 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

２．後置記法前置記法(prefix notation) + X Y 中置記法(infix notation) X + Y 後置記法(postfix notation) X Y + 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

練習問題言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

後置記法の長短長所：括弧が不要コード生成がし易いスタックを利用すると、インタープリタが容易に実現可能（教科書pp.15-19参照のこと）短所：四つ組（後述）と比べ表現に融通性欠如そのため、最適化に不向き言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

3.三つ組形式：番号　（演算子，被演算子１，被演算子２）例：７．（＋，X，１５）（意味）　⑦　←　X＋１５二番地命令/コードともいう言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例 A = 10 * B ー C / D => （＊，１０，B）（ / ，C，D）（ー，①，②）（＝，③，A）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

４．四つ組形式：（演算子，被演算子１，被演算子２，結果の変数）例：（＋，X，１５，ｔ）（意味）　ｔ ← X+15 三番地命令/コードともいう言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例 A = 10 * B ー C / D => １．（＊，１０，B，ｔ１）２．（ / ，C，D，ｔ２）３．（ー，ｔ１，ｔ２，A）
１と２の順序を入れ替えても、結果は変わらない！最適な計算順序がある？言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例２：X=(A+B-C)/(A+B) 練習問題（まずは自分でやってみよう）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例２：X=(A+B-C)/(A+B) （＋，A，B，ｔ１）（ー，ｔ１，C，ｔ２）（＋，A，B，ｔ３）（ / ，ｔ２，ｔ３，X）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例２：X=(A+B-C)/(A+B) （＋，A，B，ｔ１）（ー，ｔ１，C，ｔ２）（＋，A，B，ｔ３）（ / ，ｔ２，ｔ３，X）ｔ１とｔ３は実は同じもの！最適化しよう！言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

例２：X=(A+B-C)/(A+B) （＋，A，B，ｔ１）（ー，ｔ１，C，ｔ２）（ / ，ｔ２，ｔ１，X）（最適化された!）言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

練習問題今日の練習問題式 x + y * ( z – w ) を構文木後置記法三つ組　の列四つ組　の列　として表せ。出席用紙に答案を書いてください。最後に、提出してもらいます。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

コードの最適化コンパイル過程において、生成するコードを改良することを「コード最適化」という。では、「改良」とはどうすること？言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

最適化の内容（例）コードを小さくする実行時の効率をよくする実行時の使用メモリを小さくする一般には、２が重要視される。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

コード最適化の手法共通部分の削除複写伝播不要コードの削除ループ不変量の抽出とコード移動演算子の強さの軽減　などなど言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

１．共通部分の削除 A=B/(C+D)-(C+D); ( +, C, D, t1 ) ( /, B, t1, t2 ) ( +, C, D, t3) ( -, t2, t3, A) 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

１．共通部分の削除 A=B/(C+D)-(C+D); ( +, C, D, t1 ) ( /, B, t1, t2 ) ( +, C, D, t3 ) ( -, t2, t3, A ) ( +, C, D, t1 ) ( /, B, t1, t2 ) ( -, t2, t1, A ) 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

２．複写伝播 X = Y; Z = X + 1; W = X; X = Y; Z = Y + 1; W = Y; Yだけ。Xなし。言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

３．不要コードの削除 X = Y; Z = Y + 1; W = Y; Z = Y + 1; W = Y; 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

４．ループ不変量の抽出とコード移動 for ( i=0; i<100; i++ ) x[ i ] = 10 * a[ j ] + y[ i ]; w = 10*a[ j ]; for( i = 0; i < 100; i++ ) x[ i ] = w + y[ i ] 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

５．演算子の強さの軽減 Y = A*２ Y = A + A 言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

コード生成の概要（再）原始プログラム目的コード字句解析構文解析意味解析中間コード生成コード生成最適化中間コード中間コード言語プロセッサ2015 東京工科大学CS学部 (担当　亀田弘之)

言語プロセッサ2015 Language Processors 2015

Similar presentations

Presentation on theme: "言語プロセッサ2015 Language Processors 2015"— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

言語プロセッサ2015 Language Processors 2015

Similar presentations

Presentation on theme: "言語プロセッサ2015 Language Processors 2015"— Presentation transcript:

Similar presentations

About project

フィードバック