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