山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名 形式言語とコンパイラ
時間割番号 TCS306
担当教員名 鍋島 英知
開講学期・曜日・時限 後期・火・II 単位数 2
<対象学生>
(未登録)
<授業の目的>
記号を扱うコンピュータの論理モデルであるオートマトンと形式言語について学び,その重要な応用であるコンパイラの構成法について学習する.計算の記述とその計算機による実現は情報処理の基礎であり,本科目ではその理論的背景と実践的技術について学ぶ.
<本授業科目による獲得・涵養が特に期待されるコンピテンシー>(能力・資質)
工学部>コンピュータ理工学科向け
記号コンピテンシー(能力・資質) 
CS-A専門6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。6a.解決すべき問題を形式化することができる。
CS-B6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。
<到達目標>  到達目標とは
目標NO説明コンピテンシーとの対応
CS
1字句解析における正規表現と有限オートマトンの関係を理解できる(レベル2)CS-A
2文脈自由文法に基づく構文の定義ができる(レベル2)CS-A
3下向き及び上向き構文解析の方法を理解できる(レベル1)CS-B
4コンパイラコンパイラを用いて字句解析器・構文解析器が実装できる(レベル2)CS-B
5インタプリタの原理を理解できる(レベル2)CS-B
<成績評価の方法>
目標No割合評価の観点
115%レポートおよび中間期の試験により評価する
215%レポートおよび中間期の試験により評価する
310%レポートおよび中間期の試験により評価する
430%レポートおよび最終成果物により評価する
530%レポートおよび最終成果物により評価する
合計100% 
<授業の方法>
・離散数学における集合,グラフ,関係に関する知識を有すること
・計算機アーキテクチャに関する基本的な知識を有すること
・アルゴリズムとデータ構造に関する基本的な知識とプログラミング能力を有すること
<受講に際して・学生へのメッセージ>
(未登録)
<テキスト>
(未登録)
<参考書>
  1. 岩間 一雄, オートマトン・言語と計算理論, コロナ社, ISBN:9784339018219
  2. 中井 央, コンパイラ, コロナ社, ISBN:9784339027082
  3. 岡留 剛, オートマトンと形式言語入門, 森北出版, ISBN:9784627852716
  4. 青木 峰郎, ふつうのコンパイラをつくろう 言語処理系をつくりながら学ぶコンパイルと実行環境の仕組み, ソフトバンククリエイティブ, ISBN:4797337958,
    (JavaCC の解説が詳しい)

  5. 千葉 滋, 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タイトルオブジェクト指向言語への拡張
事前学習
事後学習
事前学習: 事前配布の講義資料を読んでおくこと
事後学習: レポート課題を通して疑問点を解消しておくこと
授業内容クロージャーをベースとしてオブジェクト指向言語への拡張方法を学ぶ
<備考>
・学生の理解度に合わせて,内容を変更する場合がある.