| 科目コード | HI509 | ||||
| 科目名 | 形式言語とオートマトン(Formal Language and Automata Theory) | 単位数 | 2単位 | ||
| 対象学科 | 人間情報システム工学科 | 対象学年 | 5年 | 開講期間 | 通年 |
| 科目区分 | 専門応用科目 | 必修・選択 | 選択 | 履修/学修 | 学修 |
| 授業形式 | 講義 | 規定授業時数（単位時間） | 60 | ||
| 教員名（所属） | 村上 純（人間情報システム工学科） | 教員室 | 3号棟2階 | ||
| 使用教科書 | 中田 育男「コンパイラ」産業図書 | ||||
| 参考書 | 宮本 衛市「はじめてのコンパイラ」森北出版 大川 知、鈴木 大郎「コンパイラ」近代科学社 山下 義行「コンパイラ入門」サイエンス社 | ||||
| 科目の位置付けと 関連科目 | ４年生までに学んできたプログラミング関係の科目を、さらに深く理解するための科目として位置付けられる。 | ||||
| 科目の概要 | プログラムとはプログラム言語で書かれた命令のことであり、実際にコンピュータに処理を行わせるには、機械語に変換しなければならない。このためのプログラムをコンパイラという。プログラム言語を扱うためには形式的に定義された形式言語と、それと対応関係するオートマトンを学ぶ必要がある。これらの学習を通じて、コンパイラの構成や技法を知り、処理側に立ったよりよいプログラムを書くためには知識を身に付ける。 | ||||
| 授業方針 | 座学を中心に行うが、演習問題やパソコンを用いた演習も行う。 | ||||
授業項目 | 時数 | 達成目標（習得すべき内容） |
| ガイダンス | ||
| コンパイラの概説、文法と言語 | コンパイラの概念、バッカス記法、構文図式、文法と言語の形式的定義、解析木について理解し、説明することができる。 | |
| 字句解析 | 文字読み取り、字句読み取り、正規表現と有限オートマトン、字句読み取り譜の作り方について理解し、説明することができる。 | |
| 字句読み取り譜作成 | 字句読み取り譜が作成できる。 | |
| 構文解析法概説、解析木の形 | 構文解析法概説、四つ組、三つ組、ポーランド記法について理解し、説明することができる。 | |
| 演算子順位法による構文解析 | 演算子順位文法、演算子順位行列による構文解析、演算子順位関数について理解し、説明することができる。 | |
| 演算子順位法による構文解析譜の作成 | 演算子順位法による構文解析譜の作成法が理解でき、説明できる。 | |
| 再帰的下向き構文解析法 | 下向き構文解析法とその問題点、ＬＬ（１）文法、再帰的下向き構文解析譜、文法から構文解析譜への変換について理解でき、説明することができる。 | |
| 構文解析譜の作成 | 演算子順位法あるいは再帰的下向き構文解析法により構文解析譜が作成できる。 | |
| 算術式の目的譜生成 | レジスタが１つの場合と複数個の場合について算術式の目的譜生成のしかたが理解でき、説明しプログラムを作成することができる。 | |
| 論理式の目的譜生成 | 論理式の目的譜生成のしかたが理解でき、説明することができる。 |
ルーブリック | |||
評価項目 | 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 字句解析 | 文法と言語の形式的定義や解析木、正規表現と有限オートマトンについて理解し説明ができ、練習問題を正しく解くことができる。さらに、正確に動作する字句解析のプログラムを作成することができる。 | 文法と言語の形式的定義や解析木、正規表現と有限オートマトンについて理解できて練習問題が解け、字句解析のプログラムを作成することができる。 | 文法と言語の形式的定義や解析木、正規表現と有限オートマトンについて理解できず、練習問題が解けない。また、字句解析のプログラムを作成することができない。 |
| 演算子順位法による構文解析 | 四つ組、三つ組、ポーランド記法などをもとにして、演算子順位法の考え方を理解し説明でき、練習問題を正しく解くことができる。 | 四つ組、三つ組、ポーランド記法などをもとにして、演算子順位法の考え方が理解でき、練習問題を解くことができる。 | 四つ組、三つ組、ポーランド記法などをもとにして、演算子順位法の考え方が理解できず、練習問題を解くことができない。 |
| 再帰的下向き構文解析法 | ＬＬ（１）文法、再帰的下向き構文解析法の考え方を理解し説明でき、練習問題を正しく解くことができる。さらに、演算子順位法か再帰的下向き構文解析法で、正確に動作する構文解析プログラムを作成することができる。 | ＬＬ（１）文法、再帰的下向き構文解析法の考え方が理解でき、練習問題を解くことができる。さらに、演算子順位法か再帰的下向き構文解析法で構文解析プログラムを作成することができる。 | ＬＬ（１）文法、再帰的下向き構文解析法の考え方が理解できず、練習問題を解くことができない。また、演算子順位法か再帰的下向き構文解析法で構文解析プログラムを作成することができない。 |
| 目的プログラムの生成 | 算術式および論理式の目的プログラム生成の考え方を理解し説明でき、練習問題を正しく解くことができる。さらに、正確に動作する算術式および論理式の目的プログラム生成のプログラムを作成することができる。 | 算術式および論理式の目的プログラム生成の考え方が理解でき、練習問題を解くことができる。さらに、算術式の目的プログラム生成のプログラムを作成することができる。 | 算術式および論理式の目的プログラム生成の考え方が理解できず、練習問題を解くことができない。また、算術式の目的プログラム生成のプログラムを作成することができない。 |
| 評価方法及び 総合評価 | 【評価方法】中間試験、定期試験等の筆記試験，レポートで評価する。 【総合評価】定期試験等筆記試験（７０％）、演習レポート評価（３０％）を総合し評価する。６割以上の得点で合格とする。演習レポートの提出期限は課題提示と同時に示し、期限に遅れて提出されたレポートの評価点は０点とする。自学学習用の課題演習レポートはレポート点として評価する。 |
| 学習方法 | プログラム言語のレコード型やポインタ型などについての知識が必要であり、これらを十分に復習して受講することが望ましい。自学学習は講義の復習および演習レポート作成の時間に充てるものとする。 |
| 学生への メッセージ | 教科書に書かれたアルゴリズムを理解することが大事です。よく理解して、できれば最終的に各自でプログラム言語を機械語に変換するコンパイラを作成してください。 |
| 学修単位への対応 | 本科目は９０分の授業に対して放課後・家庭で９０分程度の自学自習が求められます。授業の演習問題やレポート作成の時間などに充てるものとします。 |
| 本校教育目標との対応 | JABEE学習教育目標との対応 | ||||