形式言語の定義、翻訳系の構造(字句解析、構文解析、意味解析を理解)を説明でき、簡単なプログラミング言語の処理系(インタプリタ、コンパイラ)を作成することができる。
概要:
プログラミング言語処理系の構造や各種アルゴリズムとその実装のための基本的手法を理解させる。さらに、言語の構文解析理論やその適用法について理解させる。
授業の進め方・方法:
座学の講義を基本に、演習、実習を交えながら進める。また、適宜レポートを課す。最後に、簡単なインタプリタ/コンパイラを作成する実習を行う。
注意点:
数理的な学習内容を含むので、受講者自らが復習を行って手法を確実に身に着けていくことが必須である。
参考図書:中田育男「コンパイラ」(産業図書),佐々正孝「プログラミング言語処理系」(岩波書店),千葉 滋「スクリプト言語の作り方」(技術評論社)
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
言語処理の概要、処理系:言語処理の概要、処理方式などについて学ぶ。 |
言語処理処理系の概要(何か,どのようなものがあるか)を答えることができる。
|
2週 |
コンパイラの構造:表記法、コンパイラの論理的な構成、物理的な構成について学ぶ。 |
処理系の構成法を理解し,プログラムや処理系などの表記法を理解して使えるようになる。
|
3週 |
文法と言語:形式言語理論(チョムスキー理論)とオートマトン理論の概要を学ぶ。 |
プログラミング言語の形式的な意味を理解する。
|
4週 |
コンパイラ言語の構文:BNFによる定義が形式言語のどの範疇に入るのかを示し、これを使ってコンパイラ言語の構文が定義されることを学ぶ。 |
BNFによる定義が読め,書くことができる。
|
5週 |
字句解析(正規表現と有限オートマトン):字句の構文が正規表現にあたり、正規表現の処理は有限状態オートマトンになること学び、字句解析が有限状態オートマトンの構成に対応することを理解する。 |
正規表現と有限オートマトンの関係が理解できる。
|
6週 |
字句解析(有限オートマトンの構成、字句解析器生成系lex):UNIXツールである字句解析器生成系lexを取り上げ、字句解析ルーチンが自動的に生成可能であることを学ぶ。 |
字句解析の自動生成系について理解できる。
|
7週 |
字句解析ルーチンの作成(1):簡単な字句をBNFで定義し、その字句を解析するルーチンを作成する。 |
字句解析ルーチンのプログラムが設計できる。
|
8週 |
字句解析ルーチンの作成(2):字句解析プログラム作成実習の続きを行う。 |
字句解析ルーチンのプログラムが実装できる。
|
2ndQ |
9週 |
前期中間試験:コンパイラの基本構成、字句解析プログラムについて試験する。 |
コンパイラの基本構成、字句解析プログラムについて理解できる。
|
10週 |
構文解析の概要(上向き構文解析、下向き構文解析):構文解析の2つの範疇である上向き構文解析と下向き構文解析)について学ぶ。 |
構文解析の概要と種類について理解できる。
|
11週 |
構文解析(LL(1)構文解析)(1):下向き構文解析の代表的な文法であるLL(1)文法について特徴について学ぶ。 |
LL(1)文法の特徴について理解できる。
|
12週 |
構文解析(LL(1)構文解析)(2):LL(1)文法の問題点と解決法について学ぶ。 |
LL(1)文法の問題点について理解できる。
|
13週 |
構文解析プログラムの作成(1):課題・演習を通じて、下向き構文解析(LL(1))のプログラム作成法を体感する。 |
LL(1)構文解析プログラムが設計できる。
|
14週 |
構文解析プログラムの作成(1):課題・演習を通じて、下向き構文解析(LL(1))のプログラム作成法を完成させる。 |
LL(1)構文解析プログラムが実装できる。
|
15週 |
答案返却など:試験結果と注意点を解説する。 |
言語処理系の概要,字句解析プログラム,LL(1)構文解析プログラムが理解できたかを確認する。
|
16週 |
|
|
後期 |
3rdQ |
1週 |
LR構文解析の概説:上向き構文解析のもう一つの代表例で、かなり強力な構文解析であるLR構文解析について学ぶ。 |
LR構文解析とは何かが理解できる。
|
2週 |
構文解析(SLR(1)構文解析):LR構文解析の中で最も単純な解析法であるSLR(1)構文解析について学ぶ。 |
SLR(1)構文解析とは何かが理解できる。
|
3週 |
構文解析(LR(1)、LALR(1)構文解析):LR(1)構文解析及び解析表を小さくしたLALR(1)構文解析について学ぶ。 |
LALR(1)構文解析とは何かが理解できる。
|
4週 |
構文解析器生成系yaccシステム:LALR(1)構文解析ルーチンを自動生成するUNIXツールyaccについて学ぶ。 |
Yaccシステムの概要と動作が理解できる。
|
5週 |
意味解析(文法の構造):ブロック構造等に関連して意味解析について学ぶ |
ブロック構造のメモリ内での実装について理解できる。
|
6週 |
意味解析(記号表の管理)、 エラー処理、実行時の記憶域の管理):記号表の構造や管理法について学ぶ。また、エラー処理(エラーの発見、エラーからの復帰等を学ぶ。 |
各種データ構造に対する領域の割り当て法や実行時の領域の管理法について理解する。
|
7週 |
構文解析(演算子順位解析):演算子間の優先順位を求める方法をについて、与えられた生成規則から優先順位を求めるための数学的手法を学ぶ。 |
演算子順位解析とは何かが理解できる。
|
8週 |
後期中間試験:上向き構文解析、意味解析等について出題する。 |
上向き構文解析と意味解析について理解できたかを確認する。
|
4thQ |
9週 |
インタープリタの作成(1):簡単な言語のインタプリタを作成する実習を行う。 |
簡単な言語のインタプリタを設計できる。
|
10週 |
インタープリタの作成(2):引き続きインタプリタの実習を行う |
簡単な言語のインタプリタを実装できる。
|
11週 |
意味解析(コード生成):対象マシンの特徴や各制御構造に対するコード生成について学ぶ。 |
コード生成処理の概要について理解できる。
|
12週 |
簡単なコンパイラの作成(1): 簡単なプログラミング言語のコンパイラを作成する実習を行う。 |
簡単なコンパイラのプログラムが設計できる。
|
13週 |
簡単なコンパイラの作成(2):引き続きコンパイラ作成の実習を行う。 |
簡単なコンパイラのプログラムが実装できる。
|
14週 |
簡単なコンパイラの作成(3):コンパイラを完成させる。 |
実装したコンパイラの動作をテストプログラムで確認できる。
|
15週 |
コンパイラ生成系:コンパイラ生成系の内部構成について学ぶ。 |
コンパイラ生成系の内部構成が理解できる。
|
16週 |
答案返却など:コンパイラ作成の演習全体についての解説を行う。 |
言語処理系やコンパイラとは何かを理解し,簡単な処理系を作成することができる。
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | コンピュータシステムにおけるオペレーティングシステムの位置づけを説明できる。 | 3 | |
プロセス管理やスケジューリングなどCPUの仮想化について説明できる。 | 3 | |
形式言語の概念について説明できる。 | 4 | |
オートマトンの概念について説明できる。 | 4 | |
コンパイラの役割と仕組みについて説明できる。 | 4 | |
情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | |
集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | |
ブール代数に関する基本的な概念を説明できる。 | 3 | |
論理代数と述語論理に関する基本的な概念を説明できる。 | 3 | |
離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 3 | |
コンピュータ上での数値の表現方法が誤差に関係することを説明できる。 | 3 | |
コンピュータ上で数値計算を行う際に発生する誤差の影響を説明できる。 | 3 | |
コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。 | 3 | |
情報量の概念・定義を理解し、実際に計算することができる。 | 2 | |
情報源のモデルと情報源符号化について説明できる。 | 2 | |
通信路のモデルと通信路符号化について説明できる。 | 2 | |
その他の学習内容 | 少なくとも一つの具体的なコンピュータシステムについて、起動・終了やファイル操作など、基本的操作が行える。 | 4 | |
少なくとも一つの具体的なオフィススイート等を使って、文書作成や図表作成ができ、報告書やプレゼンテーション資料を作成できる。 | 4 | |
少なくとも一つのメールツールとWebブラウザを使って、メールの送受信とWebブラウジングを行うことができる。 | 4 | |
コンピュータウィルスやフィッシングなど、コンピュータを扱っている際に遭遇しうる代表的な脅威について説明できる。 | 3 | |
コンピュータを扱っている際に遭遇しうる脅威に対する対策例について説明できる。 | 3 | |
メディア情報の主要な表現形式や処理技法について説明できる。 | 3 | |