Formal Languages Processing

Course Information

College Tokuyama College Year 2022
Course Title Formal Languages Processing
Course Code 0119 Course Category Specialized / Elective
Class Format Lecture Credits Academic Credit: 2
Department Department of Computer Science and Electronic Engineering Student Grade 5th
Term First Semester Classes per Week 2
Textbook and/or Teaching Materials 湯浅太一:「コンパイラ」,オーム社,2014
Instructor Takayama Yasuhiro

Course Objectives

形式言語の定義,翻訳系の構造(字句解析,構文解析,意味解析,中間語生成,最適化,コード生成)について説明でき,簡単なプログラミング言語の処理系(インタプリタ,コンパイラ)を作成することができる。

Rubric

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
プログラミング言語の言語処理系の構成言語処理系の構成を正しく把握できる言語処理系の構成をほぼ把握できる言語処理系の構成を把握できない
プログラミング言語処理系の基礎理論言語処理系の基礎理論を正しく理解して応用できる言語処理系の基礎理論をほぼ正しく理解できる言語処理系の基礎理論を理解できない
プログラミング言語の言語処理系の構築基本的な言語処理系を作成できる基本的な言語処理系をほぼ作成できる基本的な言語処理系を作成できない

Assigned Department Objectives

到達目標 A 1 See Hide
JABEE d-1 See Hide

Teaching Method

Outline:
プログラミング言語処理系の構造や各種アルゴリズムとその実装のための基本的手法を理解させる。さらに,形式言語の構文解析理論やその適用法について理解させる。
この科目は,企業で実際に言語処理応用システムに関わる実務を担当していた教員が,その経験を生かして,言語処理の基礎と応用について座学と演習形式で授業を行うものである。
Style:
座学の講義を基本に,演習、実習を交えながら進める。また,適宜レポートを課す。簡単なインタプリタ/コンパイラを作成する実習を行う。
事前事後学習として,授業の復習を授業まとめノートの形で作成したり,演習課題のプログラム作成したりを行う(合計約60時間)。
Notice:
数理的な学習内容を含むので,受講者自らが復習を行って手法を確実に身に着けていくことが必須である。
参考図書:中田育男「コンパイラ」(産業図書),佐々正孝「プログラミング言語処理系」(岩波書店),千葉 滋「スクリプト言語の作り方」(技術評論社)
成績評価式:試験点(60点満点) + 課題点(10点満点) + 演習点(30点満点); ここで, 試験点= 0.6×(中間試験点(百点満点)+期末試験点(百点満点)) ÷ 2 とする。ただし,小数点以下は四捨五入して計算する。課題点は授業内容の復習問題や小テストとする。演習点はプログラム作成のレポートとする。

Characteristics of Class / Division in Learning

Active Learning
Aided by ICT
Applicable to Remote Class
Instructor Professionally Experienced

Course Plan

Theme Goals
1st Semester
1st Quarter
1st 言語処理の概要,処理系:言語処理の概要,処理方式などについて学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
言語処理処理系の概要(何か,どのようなものがあるか)を答えることができる。
2nd コンパイラの構造:表記法,コンパイラの論理的な構成,物理的な構成について学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
処理系の構成法を理解し,プログラムや処理系などの表記法を理解して使うことができる。
3rd 文法と言語:形式言語理論(チョムスキー理論)とオートマトン理論の概要を学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
プログラミング言語の形式的な意味を理解できる。
4th コンパイラ言語の構文:BNFによる定義が形式言語のどの範疇に入るのかを示し,BNFを使ってコンパイラ言語の構文が定義されることを学ぶ。
【事前事後学習の内容(5時間)】プログラム作成と予習
BNFによる定義が読め,書くことができる。
5th 字句解析(正規表現と有限オートマトン):字句の構文が正規表現にあたり、正規表現の処理は有限状態オートマトンになること学び,字句解析が有限状態オートマトンの構成に対応することを理解する。
【事前事後学習の内容(4時間)】まとめノート作成と予習
正規表現と有限オートマトンの関係が理解できる.
6th 字句解析モジュールの作成(1):簡単な字句をBNFで定義し、その字句を解析するプログラムを作成する。
【事前事後学習の内容(5時間)】プログラム作成と予習
字句解析のプログラムが設計できる.
7th 構文解析の概要(下向き構文解析,上向き構文解析):構文解析の2つのカテゴリである上向き構文解析と下向き構文解析)について学ぶ。
とオートマトン理論の概要を学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と復習
構文解析の概要と種類について理解できる.
8th 前期中間試験:コンパイラの基本構成,字句解析,構文解析の概要について試験する。 コンパイラの基本構成,字句解析、字句解析の概要について理解できる.
2nd Quarter
9th 構文解析(LL(1)構文解析)(1):下向き構文解析の代表的な文法であるLL(1)文法について特徴について学ぶ。
とオートマトン理論の概要を学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
LL(1)文法の特徴について理解できる.
10th 構文解析(LL(1)構文解析)(2):LL(1)文法の問題点と解決法について学ぶ。
とオートマトン理論の概要を学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
LL(1)文法の問題点について理解できる.
11th 構文解析プログラムの作成:課題・演習を通じて,下向き構文解析(LL(1))のプログラム作成法を体感する。
【事前事後学習の内容(4時間)】プログラム作成と予習
LL(1)構文解析プログラムが設計・実装できる.
12th 構文解析プログラムの生成系について学ぶ。
【事前事後学習の内容(6時間)】プログラム作成と予習
構文解析プログラムの生成系の構成を理解することができる.
13th 意味解析の概要について学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と予習
言語処理における意味解析とは何かについて述べることができる.
14th コード生成および最適化について学ぶ。
【事前事後学習の内容(4時間)】まとめノート作成と復習
コード生成処理の概要と典型的な最適化について述べることができる.
15th 前期末試験 言語処理系の概要,字句解析プログラム,LL(1)構文解析プログラムが理解できたかを確認する.
16th 答案返却など:試験結果と注意点を解説する。
【事前事後学習の内容(4時間)】科目まとめノート作成
言語処理系についての学習内容を振り返り,定着化を図る.

Evaluation Method and Weight (%)

試験課題演習Total
Subtotal601030000100
基礎的能力3010000040
専門的能力3003000060