到達目標
形式文法で構造が定義されたテキストファイルの解析技術を身に付ける。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
形式文法が生成する形式言語を示せる。 | 与えられた文法が生成する終端記号列の集合の階層関係を示せる。 | 与えられた文法が生成する終端記号列の集合を示せる。 | 与えられた文法が生成する終端記号列の集合を示せない。 |
正規表現から最簡形決定性有限オートマトンへ変換できる。 | 与えられた正規表現が生成する終端記号列の集合を受理する最簡形決定性有限オートマトンを構成できる。 | 与えられた正規表現が生成する終端記号列の集合を受理する決定性有限オートマトンを構成できる。 | 与えられた正規表現が生成する終端記号列の集合を受理する決定性有限オートマトンを構成できない。 |
学科の到達目標項目との関係
教育方法等
概要:
形式言語理論とオートマトン理論は形式的に構造が定義されたテキストファイルを解析するための理論的根拠を示している。より具体的には、コンパイラを構成する字句解析器や構文解析器を文法に基づいて実装するために用いられる。
授業の進め方・方法:
授業はスライド資料を用いた講義形式で行う。授業資料は事前に配布する。授業では予習で分らなかったことを中心に理解を深めること。
注意点:
形式言語理論とオートマトン理論は情報工学の基礎となる数学的な理論である。集合の記法を用いて記述されることが多いので事前に慣れておくこと。本講義は、後期の「言語処理系」の準備となる講義である。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
概論 |
プログラム開発環境の構成要素とその役割を示せる。
|
2週 |
概論 |
コンパイラの構成要素とその役割を示せる。
|
3週 |
文法の記述法 |
集合論の概略、記号および記号列の集合と演算について示せる。
|
4週 |
文法の記述法 |
文法を数学的に記述する方法を示せる。
|
5週 |
文法の記述法 |
文法を生成規則、BNF、拡張BNF、および構文図式で示せる。
|
6週 |
文法の記述法 |
与えられた文法と終端記号列に対する導出過程と還元過程を示せる。
|
7週 |
演習 |
ここまでの学習内容に関わる質問に解答できる。
|
8週 |
中間試験 |
試験において間違えた部分を自分の課題として把握する(非評価項目)。
|
2ndQ |
9週 |
字句解析 |
有限オートマトンの状態遷移図と受理する言語との関係を示せる。
|
10週 |
字句解析 |
与えられた正規表現からNFAを作れる。
|
11週 |
字句解析 |
NFAからDFAを作れる。
|
12週 |
字句解析 |
DFAから最簡形DFAを作れる。
|
13週 |
字句解析 |
字句解析器を実際に作るときの配慮事項を示せる。
|
14週 |
演習 |
ここまでの学習内容に関わる質問に解答できる。
|
15週 |
試験答案の返却・解説 |
試験において間違えた部分を自分の課題として把握する(非評価項目)。
|
16週 |
|
|
評価割合
| 試験 | 課題 | 態度 | 合計 |
総合評価割合 | 60 | 40 | 0 | 100 |
専門的能力 | 60 | 40 | 0 | 100 |