形式言語の定義、翻訳系の構造(字句解析、構文解析、意味解析を理解)を説明でき、簡単なプログラミング言語の処理系(インタプリタ、コンパイラ)を作成することができる。
概要:
プログラミング言語処理系の構造や各種アルゴリズムとその実装のための基本的手法を理解させる。さらに、言語の構文解析理論やその適用法について理解させる。
この科目は,企業で実際に言語処理応用システムに関わる実務を担当していた教員が,その経験を生かして、言語処理の基礎と応用について座学と演習形式で授業を行うものである。
授業の進め方・方法:
座学の講義を基本に、演習、実習を交えながら進める。また、適宜レポートを課す。最後に、簡単なインタプリタ/コンパイラを作成する実習を行う。
事前事後学習として、授業の復習を授業まとめノートの形で作成したり、演習課題のプログラム作成したり(合計約60時間)を行う。
注意点:
数理的な学習内容を含むので、受講者自らが復習を行って手法を確実に身に着けていくことが必須である。
参考図書:中田育男「コンパイラ」(産業図書),佐々正孝「プログラミング言語処理系」(岩波書店),千葉 滋「スクリプト言語の作り方」(技術評論社)
成績評価式:試験点(60点満点) + 課題点(10点満点) + 演習点(30点満点); ここで, 試験点= 0.6×(中間試験点(百点満点)+期末試験点(百点満点)) ÷ 2 とする。ただし,小数点以下は四捨五入して計算する。
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
言語処理の概要、処理系:言語処理の概要、処理方式などについて学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
言語処理処理系の概要(何か,どのようなものがあるか)を答えることができる。
|
2週 |
コンパイラの構造:表記法、コンパイラの論理的な構成、物理的な構成について学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
処理系の構成法を理解し,プログラムや処理系などの表記法を理解して使うことができる。
|
3週 |
文法と言語:形式言語理論(チョムスキー理論)とオートマトン理論の概要を学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
プログラミング言語の形式的な意味を理解できる。
|
4週 |
コンパイラ言語の構文:BNFによる定義が形式言語のどの範疇に入るのかを示し、これを使ってコンパイラ言語の構文が定義されることを学ぶ。 【事前事後学習の内容(5時間)】プログラム作成と予習 |
BNFによる定義が読め,書くことができる。
|
5週 |
字句解析(正規表現と有限オートマトン):字句の構文が正規表現にあたり、正規表現の処理は有限状態オートマトンになること学び、字句解析が有限状態オートマトンの構成に対応することを理解する。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
正規表現と有限オートマトンの関係が理解できる.
|
6週 |
字句解析ルーチンの作成(1):簡単な字句をBNFで定義し、その字句を解析するルーチンを作成する。 【事前事後学習の内容(5時間)】プログラム作成と予習 |
字句解析ルーチンのプログラムが設計できる.
|
7週 |
構文解析の概要(上向き構文解析、下向き構文解析):構文解析の2つの範疇である上向き構文解析と下向き構文解析)について学ぶ。 とオートマトン理論の概要を学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と復習 |
構文解析の概要と種類について理解できる.
|
8週 |
前期中間試験:コンパイラの基本構成、字句解析、構文解析の概要について試験する。 |
コンパイラの基本構成、字句解析、字句解析の概要について理解できる.
|
2ndQ |
9週 |
構文解析(LL(1)構文解析)(1):下向き構文解析の代表的な文法であるLL(1)文法について特徴について学ぶ。 とオートマトン理論の概要を学ぶ。と予習 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
LL(1)文法の特徴について理解できる.
|
10週 |
構文解析(LL(1)構文解析)(2):LL(1)文法の問題点と解決法について学ぶ。 とオートマトン理論の概要を学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
LL(1)文法の問題点について理解できる.
|
11週 |
構文解析プログラムの作成:課題・演習を通じて、下向き構文解析(LL(1))のプログラム作成法を体感する。 【事前事後学習の内容(4時間)】プログラム作成と予習 |
LL(1)構文解析プログラムが設計・実装できる.
|
12週 |
構文解析プログラムの生成系について学ぶ。 【事前事後学習の内容(6時間)】プログラム作成と予習 |
構文解析プログラムの生成系の構成を理解することができる.
|
13週 |
意味解析の概要について学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と予習 |
言語処理における意味解析とは何かについて述べることができる.
|
14週 |
コード生成および最適化について学ぶ。 【事前事後学習の内容(4時間)】まとめノート作成と復習 |
コード生成処理の概要と典型的な最適化について述べることができる.
|
15週 |
前期末試験 |
言語処理系の概要,字句解析プログラム,LL(1)構文解析プログラムが理解できたかを確認する.
|
16週 |
答案返却など:試験結果と注意点を解説する。 【事前事後学習の内容(4時間)】科目まとめノート作成 |
言語処理系についての学習内容を振り返り,定着化を図る.
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | コンピュータシステムにおけるオペレーティングシステムの位置づけを説明できる。 | 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 | |