コンパイラ
担当教員
授業の到達目標及びテーマ
コンパイラは、計算機科学の分野でもっとも重要なソフトウェアの一つである。本講義では、コンパイラの基本概念について説明するとともに、コンパイラの各構成要素における理論と技法について説明する。また、簡単な言語を例題として、コンパイラの全体像を理解を深める。
授業の概要と方法
コンパイル処理は、いくつかのフェーズ(Phase)と呼ばれるプロセスで構成される。各フェーズの実装方法は、オートマトンをはじめとする言語の理論によって裏付けられている。講義前半(第1～8回)では、各フェーズに対して、(1)フェーズを裏付ける理論の学習、(2)理論に対するプロセスの実装方法(アルゴリズム)の学習、というステップで理解を深めていく。講義後半では、前半で学んだそれぞれのフェーズを統合することで、一つのコンパイラを構成できることを学ぶ。
授業計画
- コンパイラの概要(1)
プログラミング言語およびその処理系の役割について学ぶ。また、算術演算式を逆ポーランド記法(後置記法)に翻訳(コンパイル)することを学び、コンパイルのプロセスの直感的な理解を目標とする。
- コンパイラの概要(2)
コンパイラの各フェーズの詳細を述べるとともに、それらをどのように統合して全体像とするのかを示す。
- 文法と言語
言語の文法を定義する1手法である文脈自由文法について学ぶ。
- 正規表現と有限オートマトン
字句の定義は正規表現で定義され、その認識機は有限オートマトンとして定式化(公式化)できる。
- 字句解析器
第4回の内容に基づいて、字句解析フェーズの実装法の詳細を学ぶ。
- 再帰的下向き構文解析(1)
言語の文法は文脈自由文法で定義されるが、構文解析向けにより実用的な文法であるLL(1)文法について学ぶ。
- 再帰的下向き構文解析(2)
第6回の内容に基づいて、LL(1)文法に対する構文解析フェーズの実装法の詳細を学ぶ。
- 意味解析
プログラミング言語の意味とは何かについて説明する。また、意味解析で重要な記号表について学ぶ。
- バーチャルマシン(1)
- バーチャルマシン(2)
バーチャルマシン(仮想機械)は、CPUを抽象化した仮想的なアーキテクチャであり、言語処理系を実装する一つの手段でもある。第11回以降で用いるコンパイラの目的機械も一つの仮想機械を用いる。
- コンパイラの例(コード生成)(その1)
- コンパイラの例(コード生成)(その2)
- コンパイラの例(コード生成)(その3)
- コンパイラの例(コード生成)(その4)
簡単なプログラミング言語を題材として、これを第9,10回で紹介する仮想機械のマシン語にコンパイルするコンパイラを示す。簡単な、式や変数の機能から始め(その1、その2で扱う)、if文、繰り返し文をはじめとする制御構造(その3)を加え、最終的には関数呼び出しの機能(その4)の実現を目指す。
- 定期試験
テキスト
授業内で適宜配布する資料
参考文献
- 中田育男著「コンパイラ」、オーム社
- 中井央「コンパイラ」コロナ社
評価方法
定期試験により評価する。次に挙げる点を主に評価する: コンパイラの各フェーズ(字句解析、構文解析、意味解析)の理論や実装方法を理解しているかどうか、プログラミング言語の様々な言語機能がどのように目的言語のコードにコンパイルされるかを理解しているかどうか。
情報機器使用
ネットワーク使用あり。オンライン教材を用いることがあるのでコンピュータ持参のこと。