言語処理系

科目基礎情報

学校 鹿児島工業高等専門学校 開講年度 2019
授業科目 言語処理系
科目番号 0057 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 2
開設学科 情報工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 なし
担当教員 堂込 一秀

到達目標

本科目の受講生の目標は、学習を通して形式文法を理解し、形式文法で構造が定義されたテキストファイルの解析技術を身に付けることである。より具体的には、コンパイラを構成する字句解析器、構文解析器およびコード生成器の機能を知り、その一部を作れるようになることが求められる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
文法が表す言語を示せる生成規則で記述された形式言語が、どの文法レベルに属すか判定できるある文字列が与えられた生成規則で導出可能か判定できる 自然言語で書かれた文法規則から生成規則を記述できるある文字列が与えられた生成規則で導出可能か判定できない
正規表現から最簡形決定性有限オートマトンへ変換できるプログラム言語における字句解析プログラムを作成できる正規表現から最簡略形決定性有限オートマトンへ変換できる正規表現から決定性有限オートマトンを作成できない
上向き構文解析と下向き構文解析の動作を追跡できる与えられた簡易言語のLL構文解析のプログラムをC言語等で部分的に作成できるある文法がLL(1)文法か判定できる。 Action 表、Goto表を用いてLR構文解析の動作を理解できる。First集合、Follow集合、Director集合を求めることができず、LL(1)文法であるか判定できない Action 表、Goto 表を用いたLR構文解析を理解できない
記号表に登録される内容を示せる与えられた簡易言語の記号表をC言語等で作成でき、コンパイルエラーを出力できる意味解析でどのようなエラーを判定できるか理解できる 記号表への登録、参照方法を理解できる記号表に何が登録されるか理解できない 意味解析で何が行われるかを理解できない
式,制御文,関数に対するコード生成手法を示せる与えられた簡易言語に対応するC言語で書かれたコンパイラの動作を完全に理解できる式、制御文に対応するアセンブリ言語を生成できる  コールスタックの動作および変数、実引数、仮引数の参照方法を理解できる式、制御文のコード生成手法を理解できない コールスタックを用いたアセンブリ言語の動作を理解できない
最適化の役割とその動作を示せるアセンブリ言語を手作業で最適化できる最適化の役割や種類を理解できる最適化の役割や種類を理解できない

学科の到達目標項目との関係

教育方法等

概要:
ソフトウェア技術者は言語処理系の内部構造を理解することが不可欠である。本科目の受講生の目標は、学習を通して形式文法を理解し、形式文法で構造が定義されたテキストファイルの解析技術を身に付けることである。より具体的には、コンパイラを構成する字句解析器、構文解析器およびコード生成器の機能を知り、その一部を作れるようになることが求められる。特に、字句解析器と構文解析器については、与えられた入力に対する動作を追跡できるようになることが求められる。
授業の進め方・方法:
授業は講義形式で行う。授業資料は事前に配布するので、予習を行い、授業中に予習では分らなかったことを確実に理解すること。授業中、説明で理解できないことに関して積極的な質問を歓迎する。
注意点:
コンパイラの理論は集合の記法を用いて記述されることが多いので、読解できるようになっておくこと。

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 概論 プログラム開発環境の構成要素とその役割を示せる
2週 概論 コンパイラの構成要素とその役割を示せる
3週 文法の記述法 言語を数学的に理解するために必要な数学を示せる
4週 文法の記述法 言語を構成するものを示せる
5週 文法の記述法 生成規則を理解し、ある言語を生成文法示せる
6週 文法の記述法 正規文法と文脈自由文法の違いを示せる
7週 文法の記述法 ある文法をBNF記法および構文図式で示せる
8週 字句解析 字句解析の詳細を示せる
2ndQ
9週 字句解析 状態遷移図を理解し、ある文字列をオートマトンの状態遷移図が受理できるか追うことができる
10週 字句解析 DFA, NFA, ε-NFAを理解し、ある正規表現をε-NFAに変換できる
11週 字句解析 e-NFAからDFAを作成できる
12週 字句解析 DFAから最簡形DFAへ変換できる
13週 字句解析 正規表現から最簡形DFAへ変換できる
14週 字句解析 実際の字句解析器で行われていることを示せる
15週 試験答案の返却・解説 試験において間違えた部分を自分の課題として把握する
16週
後期
3rdQ
1週 構文解析 数式の後置表現を理解し、中置表現を後置表現に変換できる
2週 構文解析 構文解析の種類を理解し、下向き構文解析の問題を示せる
3週 構文解析 ある文法がLL(1)文法であるための条件を示せる
4週 構文解析 First集合、Follow集合、Director集合を求めることができる
5週 構文解析 文法に従って下向き構文解析器の作成方法を理解する
6週 構文解析 与えられた文法がLL(1)文法であるか示せる
7週 構文解析 LR構文解析器の動作を理解し、action表、goto表を追うことができる
8週 意味解析 構文解析と意味解析での解析の違いを示せる
4thQ
9週 意味解析 記号表で管理すべき項目を示せる
10週 コード生成 コード生成手法の概略を示せる
11週 コード生成 式,制御文に対するコード生成手法を示せる
12週 コード生成 関数に対するコード生成手法を示せる
13週 コード生成 統合した最終的なコンパイラの動作を示せる
14週 最適化 最適化の役割とその動作を示せる
15週 試験答案の返却・解説 試験において間違えた部分を自分の課題として把握する
16週

評価割合

試験宿題等態度合計
総合評価割合60400100
専門的能力60400~-40100