言語処理系（１） 金子敬一.

Presentation on theme: "言語処理系（１） 金子敬一."— Presentation transcript:

1 言語処理系（１） 金子敬一

2 １ コンパイラ入門 １．１ コンパイラと翻訳系 １．２ 翻訳系の必要性 １．３ コンパイラの構造 １．４ 字句解析 １．５ 構文解析
１　コンパイラ入門 １．１ 　　　コンパイラと翻訳系 １．２　翻訳系の必要性 １．３　コンパイラの構造 １．４　字句解析 １．５　構文解析 １．６　中間コード生成 １．７　最適化 １．８　コード生成 １．９　記帳 １．１０　誤り処理 １．１１ 　　　コンパイラ作成道具 １．１２ 　　　　始めるにあたって

3 １．１　コンパイラと翻訳系 翻訳系 　　1つのプログラミング言語(原始言語(source language)を別のプログラミング言語(目的言語(object languageあるいはtarget language))に変換するプログラムを一般に翻訳系(translator)とよぶ．

4 １．１　コンパイラと翻訳系 コンパイラ 　　目的言語がアセンブリ言語や機械語であるような翻訳系をコンパイラ(compiler)と呼ぶ．

5 １．１ コンパイラと翻訳系 コンパイルと実行 コンパイルと実行は個別の２段階からなる． コンパイラ 原始 コード 目的 目的コード 入力
１．１　コンパイラと翻訳系 コンパイルと実行 　　コンパイルと実行は個別の２段階からなる． コンパイラ 原始 コード 目的 目的コード 入力 出力

6 １．１ コンパイラと翻訳系 コンパイラの発展 モジュール化手法の開発 技法の開発
１．１　コンパイラと翻訳系 コンパイラの発展 モジュール化手法の開発 技法の開発 道具の開発 コンパイルの過程を系統立てて，モジュール化する方法が分かった 多くの作業に対して系統的な技法が見つかった 有用なソフトウェアツールの開発

7 １．１ コンパイラと翻訳系 他の翻訳系 プログラミング言語を中間コードへ翻訳し， 解釈系(interpreter)で直接実行
１．１　コンパイラと翻訳系 他の翻訳系 中間コード アセンブラ 前処理系 プログラミング言語を中間コードへ翻訳し， 解釈系(interpreter)で直接実行 原始言語がアセンブリ言語で，目的言語が機械語 高水準言語のプログラムを同一の高水準言語の別のプログラムへと翻訳

8 １．２　翻訳系の必要性 機械語 機械語プログラムは0と1の列であり，莫大な労力を必要とする割りに，非常に誤り易いという欠点をも持つ．

9 １．２　翻訳系の必要性 記号アセンブリ言語 命令コードやデータ番地に対して簡略名(mnemonic name)を用いてプログラミングの効率を向上させようとしている． 記号アセンブリ言語は，最も機械語に近い「高水準」言語であり，機械語とほぼ1対1に対応する． しかしながら，計算機がアセンブリ言語を直接実行することはできず，翻訳系であるアセンブラを必要とする．

10 １．２ 翻訳系の必要性 マクロ アセンブリ言語などにあるテキストの置換機能のこと MACRO ADD2 X, Y LOAD Y ADD X
１．２　翻訳系の必要性 マクロ アセンブリ言語などにあるテキストの置換機能のこと MACRO ADD2 X, Y LOAD Y ADD X STORE Y ENDMACRO ADD2 a, b LOAD b ADD a STORE b

11 １．２　翻訳系の必要性 高水準言語 マクロ機能を備えたアセンブリ言語を用いても，プログラマは依然として特定の計算機に依存したコードを生成することしかできない． 複雑な命令やデータ構造の内部表現を常に意識してプログラミングするには，莫大な労力を必要とする． 高水準言語では，AとBを足すにはA＋Bでよい． コンパイラが必要．若干の性能低下．

12 １．３　コンパイラの構造 フェーズ 表管理 字 句 解 析 構 文 解 析 中間コード生成 コードの最適化 コード生成 誤り処理

13 １．３ コンパイラの構造 字句解析系 最初のフェーズを字句解析系(lexical analyzer)と呼ぶ．
１．３　コンパイラの構造 字句解析系 最初のフェーズを字句解析系(lexical analyzer)と呼ぶ． 原始言語の文字を字句(token)と呼ぶ論理的な塊ごとに分離する． 字句にはDOとかIFとかの手掛かり語(keyword)，XやNUMとかいった識別子(identifier)，+や<=といった演算子記号(operator symbol)がある．

14 １．３　コンパイラの構造 構文解析系 構文解析系(syntax analyzer)は，字句解析系から　字句を受けとり，構文単位のまとまりを構成していく． 例えばA+Bを表現している3つの字句は，式(expression)と呼ぶ1つの構文構造へまとめられる． 式はさらに他の構文構造とまとめられて文を形成 構文構造を葉が字句からなる木構造で表現することが多く，この木構造を解析木(parse tree)と呼ぶ．

15 １．３　コンパイラの構造 中間コード生成系 構文解析系の生成した構文構造を用いて，中間コード生成系(intermediate code generator)は，中間コードと呼ぶ一連の簡単な命令列を生成する． 中間コードは，マクロのようなものであり，計算機の詳細とは独立な構造となっている．

16 １．３　コンパイラの構造 コード最適化 最終的な目的プログラムにおいて実行速度の向上や使用する記憶域の抑制などを目指して中間コードを改良するためのフェーズをコード最適化(code optimization)という． 必ずあるとは限らない．

17 １．３　コンパイラの構造 コード生成 最後のフェーズであるコード生成(code generation)では，以下の項目などを決定し目的コードを生成： データ用の記憶位置； 各々のデータをアクセスするためのコード； 計算遂行のためのレジスタ．

18 １．３　コンパイラの構造 表管理 表管理(table management)では，プログラム中で使用される名前を登録し，型などの情報を記憶しておく． 情報保持のデータ構造を記号表(symbol table)．

19 １．３ コンパイラの構造 誤り処理 ソース中に誤りを検出したときに呼び出すフェーズ．
１．３　コンパイラの構造 誤り処理 ソース中に誤りを検出したときに呼び出すフェーズ． できるだけ先のフェーズに進めるように，誤り処理系(error handler)が調整する．

20 １．３ コンパイラの構造 パス いくつかのフェーズをまとめてパス(pass)という． パス間のデータのやり取りは中間ファイルで行う．
１．３　コンパイラの構造 パス いくつかのフェーズをまとめてパス(pass)という． パス間のデータのやり取りは中間ファイルで行う． パス内のフェーズはコルーチンになりうる． 原則は存在しない．

21 １．４ 字句解析 字句解析系 ソースプログラムとコンパイラとのインタフェース
１．４　字句解析 字句解析系 ソースプログラムとコンパイラとのインタフェース 原始プログラムを１文字ずつ読み込み，字句(token)ごとにまとめる．

22 １．４ 字句解析 字句 単一の論理的対象として扱うことのできる文字列 識別子，手掛り語，定数，演算子，区切り記号など．
１．４　字句解析 字句 単一の論理的対象として扱うことのできる文字列 識別子，手掛り語，定数，演算子，区切り記号など． コンパイラ設計者による任意性を持つ．しかし，MAXをMとAXに分けるのは不自然

23 １．４ 字句解析 字句の分類 字句は，型と値からなる対として扱う． 値を持たない型もある． 値を持たないもの： IFや;など
１．４　字句解析 字句の分類 字句は，型と値からなる対として扱う． 値を持たない型もある． 値を持たないもの：　IFや;など 値を持つもの：　識別子，定数，名札など

24 １．４ 字句解析 字句の取出し IF(5.EQ.MAX)GOTO100 原始プログラムを走査し，取り出す．先読みが必要
１．４　字句解析 字句の取出し 原始プログラムを走査し，取り出す．先読みが必要 IF(5.EQ.MAX)GOTO100 5か，5.0か，あるいは5.E-10か？

25 ［if,-] [(,-] [const,341] [eq,-] [id,729] [),-] [goto,-] [label,554]
１．４　字句解析 字句の取出し 原始プログラムを走査し，取り出す．先読みが必要 IF(5.EQ.MAX)GOTO100 ［if,-] [(,-] [const,341] [eq,-] [id,729] [),-] [goto,-] [label,554]

26 １．５　構文解析 構文解析系 字句が原始言語として許されるか検査 字句を以降のフェーズで使用する木構造データに変換

27 １．５　構文解析 検査 プログラミング言語PL/IにおけるA + / Bのような式は，[id,…], [+,-], [/,-], [id,…]のような字句の並びとなる． 演算子が２つ続くことはないので，誤りであることがわかる．

28 １．５ 構文解析 解析木 式A / B * Cの解釈 CやFortran： (A / B) * C APL: A / (B * C) 式 式
１．５　構文解析 解析木 式A / B * Cの解釈 CやFortran： (A / B) * C APL: A / (B * C) 式 式 式 式 式 式 式 式 式 式 A / B * C A / B * C

29 ちょっと休憩 （雑談）

30 タヒチ（フレンチポリネシア） ディペンダブルコンピューティングに関する環太平洋国際会議（ＰＲＤＣ１０） ２日（火）出発，同日タヒチ着
３日（水）～５日（金）会議 ４日（土）ホテルチェックアウト；することなし ５日（日）０：０５位に出る飛行機で出発，６日帰国

31 タヒチ（フレンチポリネシア）

32 タヒチ（フレンチポリネシア）

33 タヒチ（フレンチポリネシア） 感想 食事 フランス料理，ワインなどおいしい 物価
　フランス料理，ワインなどおいしい 物価 　ほとんどのものが輸入であり，観光地であるため，ものの値段が非常に高い 文化 　人は親切で，治安も良い

34 休憩おわり

35 １．６　中間コード生成 中間コード生成系 解析木を中間言語の表現へと変換する

36 １．６ 中間コード生成 ３番地コード 代表的な３番地コード(three-address code)の文は， A := B op C 被演算子
１．６　中間コード生成 ３番地コード 代表的な３番地コード(three-address code)の文は， A := B op C 被演算子 演算子

37 １．６ 中間コード生成 ３番地コード while A>B & A<=2*B-5 do A:=A+B; L1:
１．６　中間コード生成 ３番地コード while A>B & A<=2*B-5 do A:=A+B; L1: if A>B goto L2 goto L3 L2: T1 := 2 * B T2 := T1 – 5 if A <= T2 goto L4 goto L3 L4: A := A + B goto L1 L3:

38 １．７　最適化 最適化フェーズ 中間コードを変換して，より速く，より小さなプログラムを目指す．

39 １．７ 最適化 局所最適化(local optimization) L1: if A > B goto L2 goto L3 L2:
１．７　最適化 局所最適化(local optimization) 局所的なプログラム変換による最適化 L1: if A > B goto L2 goto L3 L2: T1 := 2 * B T2 := T1 – 5 L1: if A <= B goto L3 L2: T1 := 2 * B T2 := T1 - 5

40 １．７ 最適化 共通部分式の削除 A := B + C + D T1 := B + C E := B + C + F A := T1 + D
１．７　最適化 共通部分式の削除 A := B + C + D E := B + C + F ループ最適化 ループ内で不変な計算(loop invariant computation)をループの直前に移動 T1 := B + C A := T1 + D E := T1 + F

41 １．８ コード生成 コード生成系 コード生成系は，中間コードを機械コードへと変換する．
１．８　コード生成 コード生成系 コード生成系は，中間コードを機械コードへと変換する． 機械的で単純な変換は，冗長なデータ転送を多く含む非能率的な目的コードを生成する．

42 １．８ コード生成 レジスタ割当て コード生成系では，レジスタの内容を記憶しておき，不要なデータ転送命令を削除する．
１．８　コード生成 レジスタ割当て コード生成系では，レジスタの内容を記憶しておき，不要なデータ転送命令を削除する． これらのレジスタを効率良く使うために，レジスタ割当て(register allocation)を行う． 一般に最善な割当てを求めることはNP困難な問題⇒発見的な手法を用いる．

43 １．９ 記帳 記号表 原始プログラム中の全データ対象に関する情報を記入
１．９　記帳 記号表 原始プログラム中の全データ対象に関する情報を記入 変数が，整数なのか実数なのか，配列の大きさはいくつか，関数の引数の数はいくつかなど．

44 １．９ 記帳 情報の収集 情報はいくつかのフェーズにまたがる． 字句解析系で，識別子MAXを発見すると，記号表に未記入であれば登録
１．９　記帳 情報の収集 情報はいくつかのフェーズにまたがる． 字句解析系で，識別子MAXを発見すると，記号表に未記入であれば登録 さらに，integer MAXなる宣言を発見すると，記号表にMAXが整数型であることを記入

45 １．９ 記帳 情報の利用 収集した情報は多くのフェーズで利用される． 型誤りの検出や，暗黙の型変換．
１．９　記帳 情報の利用 収集した情報は多くのフェーズで利用される． 型誤りの検出や，暗黙の型変換． 意味解析(semantic analysis)

46 １．１０ 誤り処理 誤りの発生 字句解析系： 原始プログラムの字句の綴り誤り 構文解析系： 入力構造を確定できない構文上の誤り
１．１０　誤り処理 誤りの発生 字句解析系：　原始プログラムの字句の綴り誤り 構文解析系：　入力構造を確定できない構文上の誤り 中間コード生成系：　中間コードを生成できないような不適切な型の被演算子 コード最適化系：　制御の解析の結果，到達不能な文の検出 コード生成系：　目的機械の１語に合わない定数 記帳：　多重宣言された識別子

47 １．１０ 誤り処理 誤りメッセージ 各フェーズは，誤りを見つけたときに誤り処理系に報告する． 誤り処理系は，適切なメッセージを生成する．
１．１０　誤り処理 誤りメッセージ 各フェーズは，誤りを見つけたときに誤り処理系に報告する． 誤り処理系は，適切なメッセージを生成する． 処理の継続を試みる

48 １．１１　コンパイラ作成道具 作成道具 走査系生成系 構文解析系生成系 コンパイラコンパイラ

49 １．１１　コンパイラ作成道具 入力仕様 原始言語の字句および構文構造の記述 原始言語の各構文要素に対して生成すべき出力の記述 目的機械の記述

50 １．１１　コンパイラ作成道具 コンパイラコンパイラの機能 走査系生成系 構文解析系生成系 コード生成機能

51 １．１２ 始めるにあたって 設計上の留意点 原始言語の利用目的…力点はどこか？
１．１２　始めるにあたって 設計上の留意点 原始言語の利用目的…力点はどこか？ コンパイル時間と出力コードの質とのバランス…コンパイル速度の重要性は？ 誤り診断と誤り回復の能力…目的は？ 目的機械の性質と操作環境…コード生成も重要 実現言語 コンパイラの作成環境 変更や修正のしやすさ…改良 コンパイラの生成期間

52 新しい言語Lを，機械語Aを持つ機械MAで使いたい．
１．１２　始めるにあたって ブートストラッピング（最初のコンパイラは？） X　　　Y Z 言語Xから言語Yへの翻訳機能を持ち， 言語Zで記述されたコンパイラ 新しい言語Lを，機械語Aを持つ機械MAで使いたい．

53 さらに言語Lを，機械語Bを持つ機械MBでも使いたい．
１．１２　始めるにあたって L　　　A S L　　　A A S　　　A A ただし，S⊂L さらに言語Lを，機械語Bを持つ機械MBでも使いたい．

54 １．１２　始めるにあたって クロスコンパイラ L　　　B L L　　　B A L　　　A A L　　　B L L　　　B B L　　　B A