コンパイラ資料 1章　概要 2016.4.5更新

本講義のねらい プログラミング言語の設計実装 ソフトウエア設計全般のための基礎技術 理論と実践の連携

文献 本資料 教科書 参考書 URL: http://thales.philos.k.hosei.ac.jp/compiler.html Modern Compiler Implementation in ML Modern Compiler Implementation in C Modern Compiler Implementation in Java(2nd ed.) (A.W.Appel, Cambridge Univ. Press) 参考書 コンパイラ ― 原理・技法・ツール （第2版） （エイホ,セシィ,ウルマン,ラム, サイエンス社）

コンパイラの構造 原始プログラム 字句解析(Lexical Analysis) 解析 記号表管理 構文解析(Syntactical Analysis) 意味解析(Semantic Analysis) 記号表管理 生成 中間コード レジスタ割り当て・最適化 コード生成 誤り処理 目的プログラム

各部の役割 解析：プログラムの意味を調べる 生成 記号表管理：変数名（識別子）の管理 誤り処理：各フェーズで誤り検出しながら処理を継続 字句解析：「字面」の解析。字句の認識 構文解析：文法にしたがって構文木をつくる 意味解析：各要素の意味と型の整合性 生成 中間コード生成：抽象機械に対するコード レジスタ割り当て：対象機械のレジスタ利用コード 最適化：意味上の無駄を省いて高速化する コード生成：目的コードを生成する 記号表管理：変数名（識別子）の管理 誤り処理：各フェーズで誤り検出しながら処理を継続

授業の進め方 概ね前ページのモジュールごとに講義 講義に沿って各モジュールを作成 （可能なら）講義（４限）と演習（５限）は通し授業とする （宿題の一部解答） 講義 （コードの雛形配布） 課題プログラム（授業時間内） 解答・解説 宿題プログラム （可能なら）講義（４限）と演習（５限）は通し授業とする

プログラミング言語 kitty Cに似た構文 静的スコープルール 代入文, If文, while文, print文 関数定義/関数呼び出し 基本型(int, bool)のみ 算術・論理演算、結果の印字

kittyプログラムの例 int fact(int n) { int x, y; if(n=0) x:=1; else x:=fact(n-1)*n; return x; } int main() int x; x:=fact(11); print x; return 0; kittyプログラムの例

授業で製作するkittyコンパイラ x86アセンブリ(MASM版,32bit)を生成 リンカ, アセンブラは含まない(授業ではMSリンカ・アセンブラで実行ファイル作成) 構文・型検査でエラー報告

//プログラム名：学ぶこと (導入構文要素) １章 hello： 開発環境の使い方 count： 入力記号列、語の切り出し countalpha: 文字種の区別 ２章 iddfa ： 英数字受理オートマトン (id) inr： 字句解析 　　　 (num, rel) ddinr： 要求駆動型字句解析 lexer： 字句解析完全版 ３章 literal： 構文解析,属性 (関係式) ifprint ： 構文解析 　 (if文、print文) exppp： 再帰下降解析 　 (数式) expast： 抽象構文木生成 　 astpp: 抽象構文木の利用 clause ： 構文要素の追加　　　(論理式) ４章 calc： 評価器　　　　　　(ブロック) varcalc ：　記号表 (宣言文、代入文) scopecalc： スコープ interpreter： インタプリタ print_visitor: visitorパターン ５章 blood: 型の表現　 stmtype:　 文の型検査 typecheck_visitor：　型検査完全版 ６章 translate_visitor：中間コード生成 ７章 callprint: ライブラリ呼び出し　　 tv：実行環境 (関数定義・呼出, return文) ８章 def_use: レジスタ利用調査　 liveness: 生存解析 ralloc：　簡易版レジスタ割り当て spill: レジスタあふれ対策 emit: コード生成 9章 control_flow：　制御フローグラフ・大域版 liveness:生存解析・大域版 interference: 干渉グラフ １０章 color：　レジスタ割り当て・大域版 １１章 kittyc: 全体の組み立て

開発言語・環境 開発言語: C++ 推奨開発環境・ツール プラットフォーム: WindowsXP以降(x86) 開発ツール：Visual Studio 2010 VS 2012使用も推奨

演習の手順 スライド内で提示された課題プログラムを授業内作成 （場合により）授業内で解答・解説。 課題に関して不明な点を質問して解決。 のこった課題＝宿題プログラムを次回までに作成 （次の授業）宿題プログラムに関する質問

質問について 質問は講義中・演習中問わず、随時OK ほかに、月曜5限（オフィスアワー）S413 など

課題 hello ”Hello World!”を印字するプログラムを作成せよ。

課題 count 標準入力の非空白文字列の数をカウントするプログラムを作れ。 作成したプログラムが正常に動かない入力はあるか？ ヒント：バッファサイズを考慮せよ。 hello! This is a sample input file. It’s April 11th today. Unixでは Ctrl-Z Ctrl-D Enter 11

課題　countalpha　 標準入力から英字列（英字だけからなる非空白文字列）の数をカウントするプログラムを書け。

C++のヒント std:cin 標準入力 >>演算子 非空白文字列を右被演算数に格納　 値は、条件式ではEOFを読んだときfalse 厳密には、戻り値（左被演算数への参照）がbool型に型変換されたときの値は読み込み成功時以外でfalse 英字：　文字（char型）の値がa...zまたはA...Zの範囲か否か調べよ。