本科 | 選択・必修 | 開設時期 | 単位数 | 授業形態 | 担 当 | |||
情報電子 | 選択 | 5年 | 2 | 講義 | 高山泰博 | |||
【授業の概要】 プログラミング言語処理系の構造や各種アルゴリズムとその実装のための基本的手法を理解させる。さらに、言語の構文解析理論やその適用法について理解させる。 | ||||||||
【授業の進め方】 座学の講義を基本に、演習、実習を交えながら進める。また、適宜レポートを課す。最後に、簡単なインタプリタ/コンパイラを作成する実習を行う。数理的な学習内容を含むので、受講者自らが復習を行って手法を確実に身に着けていくことが必須である。 | ||||||||
【授業計画】 | 【授業項目】 | 【内 容】 | ||||||
1 回 | 言語処理の概要、処理系、表記法 | 言語処理の概要、処理方式などについて学ぶ。また、プログラムや処理系などの表記法を導入し、処理系の構成法などを学ぶ。 | ||||||
2 回 | コンパイラの構造 | コンパイラの論理的な構成、物理的な構成について学ぶ。 | ||||||
3 回 | 文法と言語 | 形式言語理論(チョムスキー理論)とオートマトン理論の概要を学び、プログラミング言語の意味を理解する。 | ||||||
4 回 | コンパイラ言語の構文 | BNFによる定義が形式言語のどの範疇に入るのかを示し、これを使ってコンパイラ言語の構文が定義されることを学ぶ。 | ||||||
5 回 | 字句解析(正規表現と有限オートマトン) | 字句の構文が正規表現にあたり、正規表現の処理は有限状態オートマトンになること学び、字句解析が有限状態オートマトンの構成に対応することを理解する。 | ||||||
6 回 | 字句解析(有限オートマトンの構成、字句解析器生成系lex) | UNIXツールである字句解析器生成系lexを取り上げ、字句解析ルーチンが自動的に生成可能であることを学ぶ。 | ||||||
7 回 | 字句解析ルーチンの作成(1) | 簡単な字句をBNFで定義し、その字句を解析するルーチンを作成する実習を行う。 | ||||||
8 回 | 字句解析ルーチンの作成(2) | 字句解析プログラム作成実習の続きを行う。 | ||||||
9 回 | 前期中間試験 | コンパイラの基本構成、字句解析プログラムについて試験する。 | ||||||
10 回 | 構文解析の概要(上向き構文解析、下向き構文解) | 構文解析の2つの範疇である上向き構文解析と下向き構文解析)について学ぶ。 | ||||||
11 回 | 構文解析(LL(1)構文解析)(1) | 下向き構文解析の代表的な文法であるLL(1)文法について特徴について学ぶ。 | ||||||
12 回 | 構文解析(LL(1)構文解析)(2) | LL(1)文法の問題点と解決法について学ぶ。 | ||||||
13 回 | 構文解析プログラムの作成 | 課題・演習を通じて、下向き構文解析(LL(1))のプログラム作成法を体感する。 | ||||||
14 回 | 構文解析(演算子順位解析) | 演算子間の優先順位を求める方法を述べ、与えられた生成規則から優先順位を求めるための数学的手法を学ぶ。 | ||||||
期末試験 | ||||||||
15 回 | 答案返却など | 試験結果と注意点を解説する。 | ||||||
16 回 | LR構文解析の概説 | 上向き構文解析のもう一つの代表例で、かなり強力な構文解析であるLR構文解析について学ぶ。 | ||||||
17 回 | 構文解析(SLR(1)構文解析) | LR構文解析の中で最も単純な解析法であるSLR(1)構文解析について学ぶ。 | ||||||
18 回 | 構文解析(LR(1)、LALR(1)構文解析) | LR(1)構文解析及び解析表を小さくしたLALR(1)構文解析について学ぶ | ||||||
19 回 | 構文解析器生成系yaccシステム | LALR(1)構文解析ルーチンを自動生成するUNIXツールyaccについて学ぶ。 | ||||||
20 回 | 意味解析(文法の構造) | ブロック構造等に関連して意味解析について学ぶ。 | ||||||
21 回 | 意味解析(記号表の管理)、 エラー処理 |
記号表の構造や管理法について学ぶ。また、エラー処理(エラーの発見、エラーからの復帰等)について学ぶ。 | ||||||
22 回 | 意味解析(実行時の記憶域の管理) | 各種データ構造に対する領域の割り当て法や実行時の領域の管理法について学ぶ。 | ||||||
23 回 | 後期中間試験 | 上向き構文解析、意味解析等について出題する。 | ||||||
24 回 | インタープリタの作成(1) | 簡単な言語のインタプリタを作成する実習を行う。 | ||||||
25 回 | インタープリタの作成(2) | 引き続きインタプリタの実習を行う | ||||||
26 回 | 意味解析(コード生成) | 対象マシンの特徴、及び各制御構造に対するコード生成について学ぶ。 | ||||||
27 回 | 簡単なコンパイラの作成(1) | 簡単なプログラミング言語のコンパイラを作成する実習を行う。 | ||||||
28 回 | 簡単なコンパイラの作成(2) | 引き続きコンパイラ作成の実習を行う。 | ||||||
29 回 | コンパイラ生成系 | コンパイラ生成系の内部構成について学ぶ。 | ||||||
期末試験 | 後期末試験は実施せず(演習レポート作成に充てる)。 |
|||||||
30 回 | 答案返却など | コンパイラ作成の演習全体についての解説を行う。 | ||||||
【到達目標】 | 形式言語の定義、翻訳系の構造(字句解析、構文解析、意味解析を理解)を説明でき、簡単なプログラミング言語の処理系(インタプリタ、コンパイラ)を作成することができる。 | 【徳山高専学習・教育目標】 | A1 | 【JABEE基準】 | 1(2)d-1,2.1(1)A | |||
【評価法】 | 定期試験(60%)、演習レポート(30%)、課題レポート(10%)によって総合評価をする。 | |||||||
【テキスト】 | 教科書:湯浅太一「コンパイラ」(オーム社) 参考図書:中田育男「コンパイラ」(産業図書) 佐々正孝「プログラミング言語処理系」(岩波書店) 参考図書:千葉 滋「スクリプト言語の作り方」(技術評論社) | |||||||
【関連科目】 | プログラミング言語(2年)、情報数学(3年)、アルゴリズムとデータ構造(3年) |