プログラム言語を扱うためには形式的に定義された形式言語と、それと対応関係するオートマトンを学ぶ必要がある。これらを学習し、実際のコンパイラにおける次の各部のアルゴリズムを理解するとともに、簡単な処理のプログラムが作成できる。
1.字句解析
2.演算子順位法による構文解析
3.再帰的下向き構文解析法
4.目的プログラムの生成
概要:
プログラムとはプログラム言語で書かれた命令のことであり、実際にコンピュータに処理を行わせるには、機械語に変換しなければならない。このためのプログラムをコンパイラという。プログラム言語を扱うためには形式的に定義された形式言語と、それと対応関係するオートマトンを学ぶ必要がある。これらの学習を通じて、コンパイラの構成や技法を知り、処理側に立ったよりよいプログラムを書くためには知識を身に付ける。
授業の進め方・方法:
本科目は、4年生までに学んできたプログラミング関係の科目を、さらに深く理解するための科目として位置付けられるものである。講義は座学を中心に行うが、演習問題やパソコンを用いた演習も適宜行い、演習のレポートは評価に取り入れる。総合点は6割以上の得点で合格とし、演習レポートは課題提示時に示された期限に遅れて提出された場合は評価点を0点とする。自学学習用に与えられた課題の演習レポートはレポート点として評価する。
注意点:
本科目ではプログラム言語のレコード型やポインタ型などについての知識が必要であり、これらを十分に復習して受講することが望ましい。教科書に書かれたアルゴリズムを理解することが大事であるから、よく理解して、できれば最終的に各自でプログラム言語を機械語に変換するコンパイラを作成できるようになってほしい。
規定授業時数は60時間である。本科目はレポート課題作成等のため放課後・家庭で60時間の自学自習が求められる。
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
ガイダンス コンパイラの概説 |
本科目の概要、授業の流れ等について大まかに理解する。記述言語やコンパイラの構造、処理の概要について理解し、説明できる。
|
2週 |
文法と言語 |
バッカス記法、構文図式、文法と言語の形式的定義、解析木について理解し、練習問題を解くことができる。
|
3週 |
字句解析1(文字読み取りと字句読み取り) |
文字読み取りと字句読み取りのアルゴリズムを理解し、説明することができる。
|
4週 |
字句解析2(正規表現) |
正規表現について理解し、練習問題を解くことができる。
|
5週 |
字句解析3(有限オートマトン) |
非決定性有限オートマトン、決定性有限オートマトンについて理解し、練習問題を解くことができる。
|
6週 |
字句解析4(有限オートマトン演習) |
指定された処理を行う有限オートマトンを構成し、それからプログラムにすることができる。
|
7週 |
字句読み取りプログラム作成1(仕様作成、プログラム設計) |
字句読み取りの処理について、仕様を作成し、プログラムの設計を行うことができる。
|
8週 |
前期中間試験 |
|
2ndQ |
9週 |
字句読み取りプログラム作成2(プログラム作成、評価) |
字句読み取りのプログラムを作成し、実行、評価を行うことができる。
|
10週 |
構文解析の基礎 |
四つ組み、三つ組み、ポーランド記法について理解し、練習問題を解くことができる。
|
11週 |
演算子順位法による構文解析1(演算子順位文法) |
演算子順位文法と演算子順位行列について理解し、練習問題を解くことができる。
|
12週 |
演算子順位法による構文解析2(演算子順位行列による構文解析) |
演算子順位行列による構文解析手法について理解し、練習問題を解くことができる。
|
13週 |
演算子順位法による構文解析3(演算子順位関数) |
演算子順位関数について理解し、練習問題を解くことができる。
|
14週 |
演算子順位法による構文解析プログラム作成1(仕様作成、プログラム設計) |
演算子順位法による構文解析処理について、仕様を作成し、プログラムの設計を行うことができる。
|
15週 |
前期定期試験 |
|
16週 |
答案返却 演算子順位法による構文解析プログラム作成2(プログラム作成、評価) |
演算子順位法による構文解析処理について、プログラムを作成し、実行、評価を行うことができる。
|
後期 |
3rdQ |
1週 |
再帰的下向き構文解析法1(下向き構文解析法) |
下向き構文解析法について、その問題点も含めて理解し、練習問題を解くことができる。
|
2週 |
再帰的下向き構文解析法2(LL(1)文法) |
LL(1)文法について理解し、与えられた問題について、FirstとFollowおよびDirectorを求め、LL(1)文法かどうか判断することがる。
|
3週 |
再帰的下向き構文解析法4(再帰的下向き構文解析プログラム) |
再帰的下向き構文解析プログラムのアルゴリズムを理解し、与えられた課題についてトレースを行うことができる。
|
4週 |
再帰的下向き構文解析法による構文解析プログラム作成1(文法から構文解析プログラムへの変換) |
与えられた文法から構文解析プログラムへ変換する手法について理解し、実際にプログラムのコーディングを行うことができる。
|
5週 |
再帰的下向き構文解析法による構文解析プログラム作成2(プログラム作成、評価) |
再帰的下向き構文解析プログラムを作成し、実行、評価を行うことができる。
|
6週 |
算術式の目的プログラム生成法1(演算レジスタが1個の場合) |
演算レジスタが1個の場合の算術式の目的プログラム作成アルゴリズムを理解し、練習問題を解くことができる。
|
7週 |
算術式の目的プログラム生成法2(演算レジスタが複数個の場合) |
演算レジスタが複数個の場合の算術式の目的プログラム作成アルゴリズムを理解し、練習問題を解くことができる。
|
8週 |
後期中間試験 |
|
4thQ |
9週 |
答案返却 論理式の目的プログラム生成法1(解析木から目的プログラムへ) |
論理式の目的プログラム作成について、解析木から目的プログラムを作成するアルゴリズムを理解し、練習問題を解くことができる。
|
10週 |
論理式の目的プログラム生成法2(原始プログラムから目的プログラムへ1) |
論理式の目的プログラム作成について、原始プログラムから目的プログラムを作成するアルゴリズムを理解し、練習問題を解くことができる。
|
11週 |
論理式の目的プログラム生成法2(原始プログラムから目的プログラムへ2) |
論理式の目的プログラム作成について、原始プログラムから目的プログラムを作成するアルゴリズムの改良版を理解し、練習問題を解くことができる。
|
12週 |
論理式の目的プログラム作成1(仕様作成、プログラム設計) |
論理式の目的プログラム作成について、その仕様を作成し、プログラムの設計を行うことができる。
|
13週 |
論理式の目的プログラム作成2(プログラム作成、評価) |
論理式の目的プログラム作成について、実際にプログラムを作成し、実行、評価を行うことができる。
|
14週 |
目的プログラムの最適化 |
目的プログラムの最適化に関する種々の手法について理解し、説明することができる。
|
15週 |
後期定期試験 |
|
16週 |
答案返却 |
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 代入や演算子の概念を理解し、式を記述できる。 | 3 | |
プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | |
与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 1 | |
ソフトウェア | アルゴリズムの概念を説明できる。 | 2 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 2 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 2 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 3 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 2 | |
システムプログラム | 形式言語の概念について説明できる。 | 2 | |
オートマトンの概念について説明できる。 | 2 | |
コンパイラの役割と仕組みについて説明できる。 | 2 | |