到達目標
この科目ではコンパイラの理論と実際について解説し、コンパイラの開発に必要な知識を習得するとともに、プログラミング言語とプログラムの実行に関するより深い理解を得ることを目的とする。
具体的な達成目標は、
[1] 字句解析の理論的基礎と手法を理解すること
[2] 構文解析の理論的基礎と手法を理解すること
[3] 意味解析とコード生成の手法を理解すること
である。これらの手法を学習することにより、実践的なコンパイラ作成の能力を培い、実践的な問題解決能力を醸成する。また、それらの手法の理論的基礎を学習することにより、プログラミング言語、及び、そのコンパイラを設計する基本的な能力を身につけ、プログラムの実行に関するより深い理解を通して、実践的なプログラミングの能力を高める。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 字句解析の理論的基礎と手法を正確に理解し、字句解析のプログラムを的確に記述できる | 字句解析の理論的基礎と手法を概ね理解し、字句解析のプログラムをおおよそ記述できる | 字句解析の理論的基礎と手法を理解できず、字句解析のプログラムを記述できない |
| 評価項目2 | 構文解析の理論的基礎と手法を正確に理解し、構文解析のプログラムを的確に記述できる | 構文解析の理論的基礎と手法を概ね理解し、構文解析のプログラムをおおよそ記述できる | 構文解析の理論的基礎と手法を理解できず、構文解析のプログラムを記述できない |
| 評価項目3 | 意味解析とコード生成の手法を正確に理解し、意味解析とコード生成のプログラムを的確に記述できる | 意味解析とコード生成の手法を概ね理解し、意味解析とコード生成のプログラムをおおよそ記述できる | 意味解析とコード生成の手法を理解できず、意味解析とコード生成のプログラムを記述できない |
学科の到達目標項目との関係
教育方法等
概要:
我々がプログラムを記述する際、人間にとって可読性の高いプログラミング言語(高級言語)を用いるのが普通である。コンパイラは、そのような高級言語で記述されたプログラムを、CPUが解釈実行できる言語(機械語)に変換するためのソフトウェアである。この科目では、プログラミング言語の構文と意味に関するさまざまな理論と、それらに基づいて開発されてきた、プログラミング言語を機械語に変換するための種々の手法について講義を行う。
授業の進め方・方法:
主にテキストの内容に沿って講義を行うが、必要に応じて配布資料で補う。また、適宜演習課題を課す。第15週には実習を行う。
注意点:
受講に当たっては、マイクロコンピュータ(アセンブリ言語)、プログラミングII、データ構造とアルゴリズム、離散数学(有限オートマトン・形式言語理論)、またはそれらに相当する科目を修得しておくことが望ましい。
合格の対象としない欠席条件(割合) 1/3以上の欠課
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
コンパイラの概要
|
コンパイラ(compiler)の理論的なモデルと一般的なコンパイル(compilation)の過程、また、コンパイラの構造について説明できる。
|
| 2週 |
字句解析 1/3
|
コンパイラの字句解析の理論的基礎として、正規表現(Regular Expression; RE)と有限オートマトン(Finite Automaton; FA)を扱うことができる。
|
| 3週 |
字句解析 2/3
|
正規表現で表わされた字句構造を受理する有限オートマトンを構成することができる。
|
| 4週 |
字句解析 3/3
|
状態遷移表を用いた字句解析プログラムの実際、字句解析プログラムのflexによる自動生成、およびエラー処理について説明できる。
|
| 5週 |
文法(形式言語理論) 1/2
|
形式言語理論、特にプログラミング言語の構文定義で一般的に用いられる文脈自由文法(Context Free Grammar; CFG)を扱うことができる。また、BNF・拡張BNF・構文図式について説明できる。
|
| 6週 |
文法(形式言語理論) 2/2
|
形式言語理論における諸概念: 記号列の導出・最左/最右導出・解析木・文法のあいまい性等について説明できる。
|
| 7週 |
中間試験
授業時間で実施する。 |
|
| 8週 |
構文解析 1/3
|
再帰的下向き構文解析法、特にLL(1)構文解析について説明できる。また、左再帰の問題を解決することができる。
|
| 2ndQ |
| 9週 |
構文解析 2/3
|
LR構文解析について理解し、構文解析プログラムのbisonによる自動生成について説明できる。
|
| 10週 |
構文解析 3/3
|
あいまいな文法への対処法とエラー処理について説明できる。
|
| 11週 |
意味解析 1/2
|
意味解析の概要と言語中の名前とそれが表わすオブジェクトの対応付け(名前の解決)の方法について説明できる。また、スコープと名前空間についても説明できる。
|
| 12週 |
意味解析 2/2
|
前方参照の扱い、型チェック、型変換、およびエラー処理について説明できる。
|
| 13週 |
コード生成 1/2
|
具体的な実行環境のモデルを定義し、関数呼び出しに対応するコードの生成について説明できる。また、局所変数等のために記憶領域を割当てる方法について説明できる。
|
| 14週 |
コード生成 2/2
|
各種の文や式のコードを生成する方法について説明できる。
|
| 15週 |
実習
|
コンピュータとbison・flexを用いて簡単な言語処理系を作成することができる。
|
| 16週 |
期末試験
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前5 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前6 |
| オートマトンの概念について説明できる。 | 4 | 前2 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前2,前3 |
| コンパイラの役割と仕組みについて説明できる。 | 4 | 前1 |
| 分野横断的能力 | 総合的な学習経験と創造的思考力 | 総合的な学習経験と創造的思考力 | 総合的な学習経験と創造的思考力 | 要求に適合したシステム、構成要素、工程等の設計に取り組むことができる。 | 3 | 前2,前3,前4,前8,前9,前10,前11,前12,前13,前14 |
評価割合
| 試験 | 課題 | 発表 | 相互評価 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 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 |