Course Objectives
この科目ではコンパイラの理論と実際について解説し、コンパイラの開発に必要な知識を習得するとともに、プログラミング言語とプログラムの実行に関するより深い理解を得ることを目的とする。
具体的な達成目標は、
[1] 字句解析の理論的基礎と手法を理解すること
[2] 構文解析の理論的基礎と手法を理解すること
[3] 意味解析とコード生成の手法を理解すること
である。これらの手法を学習することにより、実践的なコンパイラ作成の能力を培い、実践的な問題解決能力を醸成する。また、それらの手法の理論的基礎を学習することにより、プログラミング言語、及び、そのコンパイラを柔軟に設計する基本的な能力を身につけ、プログラムの実行に関するより深い理解を通して、実践的なプログラミングの能力を高める。
Rubric
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | 字句解析の理論的基礎と手法を理解し、的確に字句解析をすることができる | 字句解析の理論的基礎と手法を理解し、字句解析をすることができる | 字句解析の理論的基礎と手法を理解できず、字句解析をすることができない |
評価項目2 | 構文解析の理論的基礎と手法を理解し、的確に構文解析をすることができる | 構文解析の理論的基礎と手法を理解し、構文解析をすることができる | 構文解析の理論的基礎と手法を理解できず、構文解析をすることができない |
評価項目3 | 意味解析とコード生成の手法を理解し、的確に意味解析とコード生成をすることができる | 意味解析とコード生成の手法を理解し、意味解析とコード生成をすることができる | 意味解析とコード生成の手法を理解できず、意味解析とコード生成をすることができない |
Assigned Department Objectives
学習・教育到達度目標 (F)
See
Hide
学習・教育到達度目標 (G)
See
Hide
学習・教育到達度目標 (H)
See
Hide
Teaching Method
Outline:
我々がプログラムを記述する際、人間にとって可読性の高いプログラミング言語(高級言語)を用いるのが普通である。コンパイラは、そのような高級言語で記述されたプログラムを、CPUが解釈実行できる言語(機械語)に変換するためのプログラムである。この科目では、これまでに発達してきたプログラミング言語の構文と意味に関するさまざまな理論と、それらに基づいて開発されてきた、プログラミング言語を機械語に変換するための種々の手法について講義を行う。
Style:
講義。15週で実習を行う。
Notice:
受講に当たっては、マイクロコンピュータ(アセンブリ言語)、プログラミングII、データ構造とアルゴリズム、離散数学(有限オートマトン・形式言語理論)、またはそれらに相当する科目を修得しておくことが望ましい。
合格の対象としない欠席条件(割合) 1/3以上の欠課
Course Plan
|
|
|
Theme |
Goals |
1st Semester |
1st Quarter |
1st |
コンパイラの概要
|
コンパイラ(compiler)の理論的なモデルと一般的なコンパイル(compilation)の過程、また、コンパイラの構造について説明できる。
|
2nd |
字句解析 1/3
|
コンパイラの字句解析の理論的基礎として、正規表現(Regular Expression; RE)と有限オートマトン(Finite Automaton; FA)を扱うことができる。
|
3rd |
字句解析 2/3
|
正規表現で表わされた字句構造を受理する有限オートマトンを構成することができる。
|
4th |
字句解析 3/3
|
状態遷移表を用いた字句解析プログラムの実際、字句解析プログラムのlexによる自動生成、およびエラー処理について説明できる。
|
5th |
文法(形式言語理論) 1/2
|
形式言語理論、特にプログラミング言語の構文定義で一般的に用いられる文脈自由文法(Context Free Grammar; CFG)を扱うことができる。また、BNF・拡張BNF・構文図式について説明できる。
|
6th |
文法(形式言語理論) 2/2
|
形式言語理論における諸概念: 記号列の導出・最左/最右導出・解析木・文法のあいまい性等について説明できる。
|
7th |
構文解析 1/3
|
再帰的下向き構文解析法、特にLL(1)構文解析について説明できる。また、左再帰の問題を解決することができる。
|
8th |
中間試験
|
|
2nd Quarter |
9th |
構文解析 2/3
|
LR構文解析について理解し、構文解析プログラムのyaccによる自動生成について説明できる。
|
10th |
構文解析 3/3
|
あいまいな文法への対処法とエラー処理について説明できる。
|
11th |
意味解析 1/2
|
意味解析の概要と言語中の名前とそれが表わすオブジェクトの対応付け(名前の解決)の方法について説明できる。また、スコープと名前空間についても説明できる。
|
12th |
意味解析 2/2
|
前方参照の扱い、型チェック、型変換、およびエラー処理について説明できる。
|
13th |
コード生成 1/2
|
具体的な実行環境のモデルを定義し、関数呼び出しに対応するコードの生成について説明できる。また、局所変数等のために記憶領域を割当てる方法について説明できる。
|
14th |
コード生成 2/2
|
各種の文や式のコードを生成する方法について説明できる。
|
15th |
実習
|
コンピュータとyacc・lexを用いて簡単な言語処理系を作成することができる。
|
16th |
期末試験
|
|
Evaluation Method and Weight (%)
| 試験 | 課題 | 発表 | 相互評価 | ポートフォリオ | その他 | Total |
Subtotal | 80 | 20 | 0 | 0 | 0 | 0 | 100 |
基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
専門的能力 | 80 | 20 | 0 | 0 | 0 | 0 | 100 |
分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |