講義内容詳細：言語理論とコンパイラ

デバイスに最適化/Optimize for device width
画面幅固定(PCサイズ)/Fixed width (PC-size)

小/Small
中/Medium
大/Large
特大/X-large

学部・研究科のディプロマポリシー/
Undergraduate and Graduate Diploma Policy 科目ナンバリングについて/
About Course Numbering

戻る

年度/Academic Year	2023
授業科目名/Course Title (Japanese)	言語理論とコンパイラ
英文科目名/Course Title (English)	Language Theory and Compiler
学期/Semester	前期	単位/Credits	2
教員名/Instructor (Japanese)	DUERST,Martin J.
英文氏名/Instructor (English)	DURST, Martin Jakob

講義概要/Course description

This course will be given in Japanese, with lecture materials in English./この授業は EJ 科目です。
In Information Technology, formal languages such as programming languages fulfill an important role. We study classification, definition, and analysis of formal languages, and the theory, techniques, and tools used in compilers. Understanding how compilers work is core to understanding how programming and computers work. But knowledge gained from this course can not only be applied to compilers, but much more widely to text processing, analysis of program input, and design of data formats.
情報テクノロジーではプログラミング言語などの形式言語が多く使われ、重要な役割を果たしている。形式言語の種類、定義と解析、コンパイラなどに使われる理論、技術とツールを勉強する。コンパイラの理解はプログラミングと計算機の理解に不可欠です。さらに、得た知識はコンパイラだけではなく、文書処理、入力の分析、データ形式の設計など幅広く使える。

達成目標/Course objectives

To understand the relationship between (formal) language theory and its applications (including compilers), and to be able to use the related tools / 言語理論とその応用 (コンパイラなど) の関係を理解し、ツールで応用できること。

学部・研究科のディプロマポリシー（卒業認定・学位授与の方針）に基づき、当該科目を履修することで身につく能力 / Abilities to be acquired by completing the course in accordance with the faculty and graduate school diploma policy (graduation certification and degree conferral)

学部・研究科のディプロマポリシー（卒業認定・学位授与の方針）/ Undergraduate and Graduate Diploma Policy (Graduation Certification and Degree Conferral)

意欲・関心・態度
Motivation, interest, and attitude
知識・技能
Knowledge and skills
思考力・判断力・表現力
Ability to think and judge, and power of expression

授業計画/Lecture plan

授業計画/Class	【一回目の授業のみオンデマンドで実施・first lecture only is on demand】 Overview: Applications of language theory and compilers, overall structure of compilers / 授業の概要: 言語理論とコンパイラの応用分野、コンパイラ全体の仕組み
事前学習/Preparation	Dürst 研究室の Moodle で授業に登録; Enrollment Key については CoursePower を見てください。
事後学習/Reviewing	宿題の提出 (C プログラム断片の字句解析の結果、構文解析の結果、コンパイラの出力)

授業計画/Class	Importance, classification, and definition of formal languages; finite automata / 形式言語の重要性、種類と定義; 有限オートマトン
事前学習/Preparation	復習; 集合についての調査
事後学習/Reviewing	宿題の提出 (クリーン閉包の計算、文法による導出)

授業計画/Class	Deterministic and non-deterministic finite state automata / 決定性有限オートマトンと非決定性有限オートマトン
事前学習/Preparation	復習; 演習用ソフトのインストール
事後学習/Reviewing	宿題の提出 (NFA から DFA への変換)

授業計画/Class	(left and right) linear grammars, regular expressions / (左・右) 線形文法、正規表現
事前学習/Preparation	復習; 演習用ソフトの確認
事後学習/Reviewing	宿題の提出 (線形文法・有限オートマトン・正規表現の変換)

授業計画/Class	Tools for lexical analysis / 字句解析ツール
事前学習/Preparation	復習; 演習用ソフトインストール済みのノートPCの持参
事後学習/Reviewing	字句解析ツールの演習の完成

授業計画/Class	From lexical analysis to parsing / 字句解析から構文解析へ
事前学習/Preparation	復習; 中間テストの準備
事後学習/Reviewing	宿題の提出 (字句解析)

授業計画/Class	Context-free grammars / 文脈自由文法
事前学習/Preparation	復習; 様々なプログラミング言語の文法の調査
事後学習/Reviewing	宿題の提出 (簡単な式のための文法からの導出)

授業計画/Class	Top-down parsing / 下向き構文解析
事前学習/Preparation	復習; 演習用ノートPCの持参
事後学習/Reviewing	宿題 (再帰的下向き構文解析の実装) の提出

授業計画/Class	Use of tools for parsing / 構文解析用のツール
事前学習/Preparation	復習; 上向き構文解析用ツールのインストールの確認; ノートPCの持参
事後学習/Reviewing	宿題 (上向き構文解析ツール、単純編) の提出

授業計画/Class	Principles of bottom-up parsing / 上向き構文解析の原理
事前学習/Preparation	復習; 宿題 (上向き構文解析ツール、単純編) の見直し
事後学習/Reviewing	宿題 (上向き構文解析ツール、応用編) の解決案の考案

授業計画/Class	Error processing, semantic analysis, intermediate representations / 構文解析時のエラー処理、意味解析、中間表現
事前学習/Preparation	復習; 宿題 (上向き構文解析ツール、応用編) についての質問の準備
事後学習/Reviewing	宿題 (上向き構文解析ツール、応用編) の完成と提出

授業計画/Class	Turing Machines / チューリング機械
事前学習/Preparation	復習; チューリング機械についての事前学習
事後学習/Reviewing	宿題 (チューリング機械による計算) の提出

授業計画/Class	Code generation / コード生成
事前学習/Preparation	復習
事後学習/Reviewing	宿題 (if 文などのコード生成) の提出

授業計画/Class	Code optimization / 最適化
事前学習/Preparation	復習; 最適化の方法の考案
事後学習/Reviewing	宿題 (コードの最適化) の提出

授業計画/Class	Executing environment: virtual machines, garbage collection / 実行環境: 仮想計算機、ゴミ集め
事前学習/Preparation	復習; ゴミ集めについての事前学習
事後学習/Reviewing	特になし

授業方法/Method of instruction

区分/Type of Class	対面授業 / Classes in-person
実施形態/Class Method	通常型 / regular
活用される授業方法/Teaching methods used	プレゼンテーション presentation PBL（課題解決型学習） project-based learning 反転授業（知識習得の要素を教室外に済ませ、知識確認等の要素を教室で行う授業形態） reverse teaching(a class style where students educate themselves out of class beforehand, and use the class period to confirm the knowledge one has gained.) ディスカッション、ディベート discussion / debate グループワーク group work 実習、フィールドワーク field work 上記に該当しない none of the above

成績評価方法/Evaluation

100%

授業中のミニテスト、中間テスト、演習課題、期末テストを総合して評価

参考書/Reference books

	コメント Comments
1	一回目の講義でリストを提供

授業関連情報/Class-related information

	件名/Title	内容/Contents	備考/Memo
1	Teacher's email address	duerst@it.aoyama.ac.jp	Please use this address to contact me.
2	Moodle Course	https://moo.sw.it.aoyama.ac.jp/course/view.php?id=62	Please enroll for this course. You can find the enrollment key in CoursePower.

メッセージ/Message

早めに CoursePower で Enrollment Key を入手し、Dürst 研の Moodle (https://moo.sw.it.aoyama.ac.jp/) で授業への登録を行ってください。この授業についての情報はすべて Dürst 研の Moodle で扱っています。CoursePower は極力使いません。