授業科目名	形式言語とコンパイラ
時間割番号	TCS306
担当教員名	鍋島　英知
開講学期・曜日・時限	後期・火・II	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
記号を扱うコンピュータの論理モデルであるオートマトンと形式言語について学び，その重要な応用であるコンパイラの構成法について学習する．計算の記述とその計算機による実現は情報処理の基礎であり，本科目ではその理論的背景と実践的技術について学ぶ．
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部(～2023年度入学生)>コンピュータ理工学科向け 記号 コンピテンシー（能力・資質）   CS-A 専門 6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。 6a.解決すべき問題を形式化することができる。 ○ CS-B 6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。 ◎
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 CS 1 字句解析における正規表現と有限オートマトンの関係を理解できる（レベル２） CS-A 2 文脈自由文法に基づく構文の定義ができる（レベル２） CS-A 3 下向き及び上向き構文解析の方法を理解できる（レベル１） CS-B 4 コンパイラコンパイラを用いて字句解析器・構文解析器が実装できる（レベル２） CS-B 5 インタプリタの原理を理解できる（レベル２） CS-B
＜成績評価の方法＞
目標No 割合 評価の観点 1 15% レポートおよび中間期の試験により評価する 2 15% レポートおよび中間期の試験により評価する 3 10% レポートおよび中間期の試験により評価する 4 30% レポートおよび最終成果物により評価する 5 30% レポートおよび最終成果物により評価する 合計 100%
＜授業の方法＞
前半は座学を基本とし，字句解析・構文解析の背景にあるオートマトンと形式言語の理論を学ぶ．また理解を深めるため講義時間中に取り組む演習問題と，講義後に取り組むレポート課題を課す． 後半は演習を基本とし，インタプリタ型プログラミング言語の開発を通して，プログラミング言語の構成法について学ぶ．また理解を深めるために講義後に取り組むレポート課題を課す．
＜受講に際して・学生へのメッセージ＞
・離散数学における集合，グラフ，関係に関する知識を有すること． ・計算機アーキテクチャに関する基本的な知識を有すること． ・アルゴリズムとデータ構造に関する基本的な知識とプログラミング能力を有すること．
＜テキスト＞
(未登録)
＜参考書＞
岩間 一雄, オートマトン・言語と計算理論, コロナ社, ISBN:9784339018219 中井 央, コンパイラ, コロナ社, ISBN:9784339027082 岡留 剛, オートマトンと形式言語入門, 森北出版, ISBN:9784627852716 青木 峰郎, ふつうのコンパイラをつくろう 言語処理系をつくりながら学ぶコンパイルと実行環境の仕組み, ソフトバンククリエイティブ, ISBN:4797337958, (JavaCC の解説が詳しい) 千葉 滋, 2週間でできる! スクリプト言語の作り方, 技術評論社, ISBN:4774149748
＜授業計画の概要＞
1 タイトル コンパイラの概要，形式言語 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 言語処理系とその構造，形式言語の定義を学ぶ 2 タイトル 字句解析: 正規表現と有限オートマトン (DFA, NFA) 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 正規表現，決定性有限オートマトン(DFA)，非決定性有限オートマトン(NFA)について学ぶ 3 タイトル 字句解析: ε-NFA, DFA と NFA の等価性 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 ε動作付非決定性有限オートマトン(ε-NFA)，DFA と NFA の等価性について学ぶ 4 タイトル 字句解析: NFAとε-NFA の等価性，正規表現とε-NFA の等価性 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 NFAとε-NFAの等価性，正規表現とε-NFAの等価性について学ぶ 5 タイトル 構文解析: 文脈自由文法 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 文脈自由文法について学ぶ 6 タイトル 構文解析: 下向き構文解析 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 下向き構文解析について学ぶ 7 タイトル 構文解析: 上向き構文解析 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 上向き構文解析について学ぶ 8 タイトル 中間評価（総括とまとめ） 事前学習 事後学習 事前学習: 過去の試験問題を公開するのでそれに各自取り組み，解けるようになっておくこと 授業内容 講義前半の内容を総括し，その理解度を試験により評価する 9 タイトル コンパイラコンパイラ演習 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 JavaCC を利用した電卓プログラムの開発を通して括弧付き四則演算の処理を学ぶ 10 タイトル 変数の実現 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 変数テーブルと変数への代入，値参照のための構文を実現する 11 タイトル 構文木の構築 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 ソースから構文木を生成して評価する手法を学ぶ 12 タイトル 制御構文の実装 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 制御構文として if, while 文の実現方法を学ぶ 13 タイトル 関数の実装 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 文字列，画面出力，関数の実現方法を学ぶ 14 タイトル クロージャの実装 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 クロージャーの実現方法を学ぶ 15 タイトル オブジェクト指向言語への拡張 事前学習 事後学習 事前学習: 事前配布の講義資料を読んでおくこと 事後学習: レポート課題を通して疑問点を解消しておくこと 授業内容 クロージャーをベースとしてオブジェクト指向言語への拡張方法を学ぶ 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜前年度授業に対する改善要望等への対応＞
中間評価結果を早めに学生に連絡する
＜備考＞
・学生の理解度に合わせて，内容を変更する場合がある．