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

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

Copyright© 2015 School of Computer Science, Tokyo University of Technology

（参考）これからはIoTの時代 IoT Japan 2014 （10月15日～17日開催）http://itpro.nikkeibp.co.jp/expo/2014/iot/ IoTの概要図 （出典）http://tocos-wireless.com/jp/tech/Internet_of_Things.html Copyright© 2015 School of Computer Science, Tokyo University of Technology

情報システム Copyright© 2015 School of Computer Science, Tokyo University of Technology

Copyright© 2015 School of Computer Science, Tokyo University of Technology

複雑だなぁ セキュリティ ネットワーク クラウドコンピューティング モバイル Copyright© 2015 School of Computer Science, Tokyo University of Technology

Divide and Conquer （困難は分割し、しかる後に統合せよ！） Copyright© 2015 School of Computer Science, Tokyo University of Technology

何が基本なのかなぁ？ Copyright© 2015 School of Computer Science, Tokyo University of Technology

ディスプレイ 本体 キーボード Copyright© 2015 School of Computer Science, Tokyo University of Technology

出力 (Output) 処理 入力 (Input) Copyright© 2015 School of Computer Science, Tokyo University of Technology

本体内部が大切！ Copyright© 2015 School of Computer Science, Tokyo University of Technology

Copyright© 2015 School of Computer Science, Tokyo University of Technology

コンピュータの階層化モデル 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© 2015 School of Computer Science, Tokyo University of Technology

Copyright© 2015 School of Computer Science, Tokyo University of Technology

Copyright© 2015 School of Computer Science, Tokyo University of Technology

Copyright© 2015 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© 2015 School of Computer Science, Tokyo University of Technology

論理回路 Copyright© 2015 School of Computer Science, Tokyo University of Technology

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

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

Ｃ言語・Java言語 アセンブリ言語 Copyright© 2015 School of Computer Science, Tokyo University of Technology

main(){ } Copyright© 2015 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© 2015 School of Computer Science, Tokyo University of Technology

main(){ int a; a = 20; a = a + 30; a = 100 - a; a = a*7; } Copyright© 2015 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, -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© 2015 School of Computer Science, Tokyo University of Technology

$ gcc -S filename.c $ ls $ cat filename.s Copyright© 2015 School of Computer Science, Tokyo University of Technology

コンパイラの処理工程概要 ソース言語 読み込み 字句解析 構文解析 中間語生成 コード生成 目的言語 Copyright© 2015 School of Computer Science, Tokyo University of Technology

言語プロセッサの種類 インタープリタ （interpreter） コンパイラ (compiler) Copyright© 2015 School of Computer Science, Tokyo University of Technology

コンパイラとは Compilerとは、high level languageで記述されたプログラム（例えば、C言語のプログラム）を、機械向き言語（例えば、機械語）のプログラムに変換する（翻訳する）ためのプログラムのこと。 Copyright© 2015 School of Computer Science, Tokyo University of Technology

数式の例 A = B*3.14 + C/A Area = 2*3.14*R*R Copyright© 2015 School of Computer Science, Tokyo University of Technology

数式の解析 kingaku = teika + teika * shouhizei Copyright© 2015 School of Computer Science, Tokyo University of Technology

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

分析 合成 ソース言語 読み込み 字句解析 構文解析 中間語生成 コード生成 目的言語 Copyright© 2015 School of Computer Science, Tokyo University of Technology

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

言語プロセッサ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学部 (担当　亀田弘之)

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

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

言語プロセッサ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学部 (担当　亀田弘之)

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

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