コンパイラ演習
担当教員
授業の到達目標及びテーマ
本演習では、講義「コンパイラ」で学習した内容の理解を深めるために、コンパイラの基本概念と、コンパイラの各構成要素に関する理論と技術に関する演習問題を解くとともに、簡単な言語のコンパイラの実装を行う。
授業の概要と方法
コンパイラが行う処理は、いくつかのフェーズ(Phase)と呼ばれるプロセスで構成され、各フェーズの実装方法は、オートマトンをはじめとする言語の理論によって裏付けられている。本演習を通して、各フェーズの理論に対する理解を深めるとともに、実際にアルゴリズムをプログラムとして各フェーズの実装を行う。最終的には、これらを踏まえて一つのコンパイラを完成させることが目標である。演習は(A)各フェーズの理論に関する演習、およびプログラミングの演習、(B)コンパイラの作成演習、の2部構成である。プログラミングにはJava言語を用いる。
授業計画
- スタックと後置記法
コンピュータの言語である機械語の構造は、後置記法の形式がその根本にある。中置記法の算術式を後置記法に変換する演習を通して、言語の処理の一端を理解する。
- 後置記法への変換器の作成
中置記法の算術式を後置記法に変換するプログラムの実装を行う。
- 言語の表現法
文脈自由文法の演習を行う。
- 正規表現と有限オートマトン
正規表現を有限オートマトンに変換する演習を行う。
- 字句解析器
実際に、正規表現を定義しその字句を認識する字句解析器を作成する。
- 再帰的下向き構文解析器の作成(1)
LL(1)文法の演習を行う。
- 再帰的下向き構文解析器の作成(2)
LL(1)文法に対する構文解析器の実装を行う。
- コンパイラの作成準備
コンパイラの作成には生成系(コンパイラ・コンパイラ)を用いる。その基本的な使い方を学ぶ。
- コンパイラの作成(1)
以下では、具体的なコンパイラを作成する。典型的なプログラミング言語に含まれる機能をステップに分けて実装する。第9回では算術式のコンパイルを実現する。
- コンパイラの作成(2)
変数機能を実現する。
- コンパイラの作成(3)
記号表を用いた意味解析の実装を行う。
- コンパイラの作成(4)
基本的な制御文(分岐、繰り返し)の実装を行う。
- コンパイラの作成(5)
より複雑な制御文の実装を行う。
- コンパイラの作成(6)
関数呼び出しの実装を行う。
- まとめ
テキスト
講義「コンパイラ」の講義資料、説明資料
参考文献
- 中田育男著「コンパイラ」、オーム社
- 中井央「コンパイラ」コロナ社
評価方法
各回で出題する演習のレポート評価を総合する。本演習は、
A: 各フェーズの理論に関する演習と、各フェーズの実装演習
B: コンパイラの作成演習
の2部構成である。演習A(1から8回)では、各フェーズの理論に関する問題を解く。また、実装演習ではプログラムを作成するレポート課題とする。演習Bは、コンパイラを実際に作成するプログラム課題であり、レポートとして提出する。
情報機器使用
ネットワーク使用あり。オンライン教材を用いることがあるので、コンピュータ持参のこと。