言語処理系

科目基礎情報

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

目的・到達目標

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

ルーブリック

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

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

教育方法等

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

授業の属性・履修上の区分

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 概論 プログラム開発環境の構成要素とその役割を示せる。
2週 概論 コンパイラの構成要素とその役割を示せる。
3週 文法の記述法 集合論の概略を示せる。
4週 文法の記述法 記号および記号列の集合と演算について示せる。
5週 文法の記述法 文法を数学的に記述する方法を示せる。
6週 文法の記述法 文法を生成規則、BNF、拡張BNF、および構文図式で示せる。
7週 文法の記述法 与えられた文法と終端記号列に対する導出過程と還元過程を示せる。
8週 演習 ここまでの学習内容に関わる質問に解答できる。
2ndQ
9週 字句解析 有限オートマトンの状態遷移図と受理する言語との関係を示せる。
10週 字句解析 与えられた正規表現からNFAを作れる。
11週 字句解析 NFAからDFAを作れる。
12週 字句解析 DFAから最簡形DFAを作れる。
13週 字句解析 字句解析器を実際に作るときの配慮事項を示せる。
14週 演習 ここまでの学習内容に関わる質問に解答できる。
15週 試験答案の返却・解説 試験において間違えた部分を自分の課題として把握する。
16週
後期
3rdQ
1週 構文解析 下向き構文解析法と上向き構文解析法の特徴を示せる。
下向き構文解析に不都合な左再帰性を除去できる。
2週 構文解析 与えられた文法に対するFirst集合を決定できる。
3週 構文解析 与えられた文法に対するFollow集合とDirector集合を決定できる。
与えられた文法がLL(1)文法であるかどうかを判定できる。
4週 構文解析 与えられた文法に対する下向き構文解析器のプログラムを作れる。
5週 構文解析 与えられた終端記号列に対する下向き構文解析器の動作をトレースできる。
6週 構文解析 上向き構文解析器の特徴と基本的な動作を示せる。
7週 構文解析 与えられた終端記号列に対する上向き構文解析器の動作をトレースできる。
8週 演習 ここまでの学習内容に関わる質問に解答できる。
4thQ
9週 意味解析 構文解析と意味解析の役割分担を示せる。
10週 コード生成 式に対するコード生成手法を示せる。
11週 コード生成 制御文に対するコード生成手法を示せる。
12週 コード生成 関数に対するコード生成手法を示せる。
13週 最適化 最適化の具体例を示せる。
14週 演習 ここまでの学習内容に関わる質問に解答できる。
15週 試験答案の返却・解説 試験において間違えた部分を自分の課題として把握する。
16週

評価割合

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