科 目 | システムプログラム ( System Programs ) | |||
---|---|---|---|---|
担当教員 | 長野 勝利 | |||
対象学年等 | 電子工学科・5年・後期・選択・1単位 ( 学修単位I ) | |||
学習・教育 目標 |
工学系複合プログラム | JABEE基準1(1) | ||
A4-4(100%) | (d)1,(d)2-a,(d)2-d,(g) | |||
授業の概要 と方針 |
コンピュータのプログラムは通常,高級言語によって記述され,コンパイラによって機械語プログラムに翻訳された上で実行される。 ここではこのコンピュータの使用に不可欠なコンパイラのしくみについて学習する。構文解析など重要な事柄については,理論とともにシステム実現のためのアルゴリズムについても考察する。 | |||
到 達 目 標 |
1 | 【A4-4】 コンピュータとコンパイラについて理解できる。 | 2 | 【A4-4】 プログラミング言語について構文の側面から理解できる。 | 3 | 【A4-4】 形式言語理論における構文解析について理解できる。 | 4 | 【A4-4】 中間言語の各種の形態について理解する。 | 5 | 【A4-4】 実行時のデータの構成について理解する。 | 6 | 【A4-4】 コード最適化の手法について理解する。 | 7 | 8 | 9 | 10 |
評 価 方 法 と 基 準 |
到 達 目 標 毎 |
1 | コンパイラとは何か,コンパイルはどのような過程を経て行なわれるのか等が理解できているか定期試験で評価する。 | |
2 | 形式言語理論,あいまいな文法,正規表現と有限オートマトン等について理解できているか定期試験で評価する。 | |||
3 | LL解析,LR解析のアルゴリズム及びLL解析表,LR解析表作成の算法について理解できているか演習及び定期試験で評価する。 | |||
4 | 式の記法,三つ組,四つ組等について理解できているか定期試験で評価する。 | |||
5 | 記号表のデータ構造,探索法,データの内部表現,再帰呼出しとスタックについて等が理解できているか定期試験で評価する。 | |||
6 | 中間言語プログラムに対して行なう機械独立なコード最適化の手法等について理解できているか定期試験で評価する。 | |||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
総 合 評 価 |
成績は,試験70% 演習30% として評価する. | |||
テキスト | 「コンパイラの理論と実現」:疋田輝雄,石畑清(共立出版) |
|||
参考書 | 「プログラミング言語処理系」:佐々正孝(岩波書店) 「コンパイラI II」:A.V.エイホ他著,原田賢一訳(サイエンス社) |
|||
関連科目 | ソフトウェア工学 | |||
履修上の 注意事項 |
授業はほぼテキストの内容にそって進めるが,手法の前提となる理論や誘導等について適宜補足して行うので必ずノートをとること。 |
週 | 上段:テーマ/下段:内容(目標、準備など) |
---|---|
1 | コンピュータと言語処理 |
コンパイラとは何か。何を対象とするのか。コンパイルはどのような過程を経て行なわれるのか。 コンパイラの他にどのような言語処理の方式があるのか。等について理解する。 | |
2 | プログラミング言語 |
プログラミング言語について復習する。言語には構文と意味の2つの側面がある。構文について形式言語理論について概説する。 | |
3 | プログラムの構文 |
プログラミング言語の各レベルの構成要素について,コンパイラの観点から整理をし理解する。 | |
4 | 字句解析と正規表現 |
コンパイラが行なう最初の作業は字句解析である。字句は自然言語の単語にあたる。字句解析は,文字の列としての原始プログラムを字句の列に区切り,字句を内部表現に変換する。 | |
5 | 正規表現と有限オートマトン |
字句解析の理論として正規表現と有限オートマトンについて理解する。非決定性有限オートマトンの動作は非決定的で取扱いに不便であるので決定性有限オートマトンを定義する。 | |
6 | 構文解析 |
構文解析は,入力として字句の列を受け取り,これに対応する解析木を構成する。方法は大別して下降型解析と上昇型解析とがある。ここでは,下降型解析として再帰下降解析とLL解析,上昇型解析としてLR解析について学習する。 | |
7 | LL解析 |
コンパイラをPascalやC等の再帰呼出しを許す言語で記述する場合は再帰下降解析でよいがそうでないときは困る。LL解析は再帰下降解析と本質的には同じで,再帰呼出しの代わりにスタックを用いるものである。LL解析のアルゴリズム,LL解析表作成の算法について理解する。 | |
8 | LR解析 |
LR解析の特徴は適用できる文法の範囲が広いことで,記号列を左から右へ一度だけ見て解析する方法としては最も広い範囲の言語,いわゆる決定性言語を解析することができる。LR解析のアルゴリズム,LR解析表作成の算法について理解する。 | |
9 | 中間言語 |
原始プログラムから構文解析の結果として解析木にあたるものが作られるが,実際の内部表現では解析木と異なる表現をとることが多い。これを中間言語という。中間言語の各種の形態について理解する。 | |
10 | 実行時のデータの構成 |
目的プログラムは,命令コード部分と,その操作の対象となるデータ部分とからなる。ここでは,データ部分について,目的プログラムの実行時にどのような構成をとればよいかについて学習する。 | |
11 | 仮想機械と機械語 |
一般に機械語プログラムはデータ部分と命令部分からなる。機械命令語は操作の指定部とオペランドの指定部からなる。コード生成の観点から仮想機械語と機械語について考察する。 | |
12 | インタプリタ |
インタプリタは原始プログラムをそのまま解釈して実行する。インタプリタの構造は原始言語に依存し,統一的な説明は難しいが,ここでは式と仮想機械コードのインタプリタについて学習する。 | |
13 | コード最適化 |
コード最適化とは,効率等をよくするため目的プログラムを改良することである。中間言語プログラムに対して行なう機械独立なコード最適化の手法について理解する。 | |
14 | コード生成 |
コード生成とは,構文木などの中間コードから,記号表内の情報を用いながら最終的な機械語コードを生成する,コンパイラにおいて重要な段階である。原始言語の各言語要素ごとにコード生成の実際について学習する。 | |
15 | コンパイラの移植 |
コンパイラを他機種のコンピュータに移植する方法や既存のコンパイラを利用してコンパイラを作成する方法について学習する。 | |
備 考 |
中間試験は実施しない.定期試験を実施する. |