コンパイラ 2012年10月4日 酒居敬一＠Ａ４６８([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html 1 コンパイラの構成と プログラム言語の形式的な記述 式(Expression)と文(Statement) 算術式の中置期法と後置記法 コンパイラの論理的な構成 コンパイラの物理的な構成 プログラム言語の形式的な記述方法 2 バッカス記法 構文図式（→次回） 式(Expression)と文(Statement) 式はそれ自体が値を持つもの。 一般的には値・変数・演算子・関数を組み合わせたもの。 式として認識される範囲は言語仕様に依存する。 文は手続きを表すことが多い。 改行文字まででひとつの文とする言語 区切り文字で区切る言語 Pascalは、';'が区切り文字になっている。 区切りが特に無い言語 3 特別な記号で区切ったり、次行と結合したりもできる。 文脈依存文法。 Ｃは、';'が式を文とする記号。 算術式の中置期法と後置記法 四則演算では演算には優先順位がある。 乗除算は加減算に優先する、括弧はそれらより優先する。 通常の式では変数と変数の間に演算子がある。 中に演算子を置くので中置記法という。 学群実験の経験より、計算機は優先順位など知らない。 機械語として書かれた順に処理するだけ。 通常の式を機械語に変換するに先立って、書き換える。 4 そのひとつが後置記法。 演算子を被演算対象の後に置く。 後置記法の例 中置記法のＡ＋Ｂ＊Ｃ－Ｄは、ＡＢＣ＊＋Ｄ－という後置記法になる。 1. 2. 3. 優先順位に基づき（（Ａ＋（Ｂ＊Ｃ））－Ｄ）というように解釈する。 演算対象を読んだらそのまま出力する 演算子を読んだら、それより優先度の高い演算子があれば スタックから取り出し順に出力しておいて、スタックに積む。 式を読み終わったら全部順に取り出し出力する。 入力 （ （ 出力 Ａ ＋ （ Ｂ ＊ Ｃ ） ） Ａ Ｂ Ｃ ＊ ＋ ー Ｄ Ｄ ＊ ＊ （ スタック 5 （ （ （ ＋ ＋ ＋ ＋ ＋ ＋ （ （ （ （ （ （ （ （ （ （ （ （ （ （ （ （ （ ー ー （ （ （ ） ー コンパイラの場合 後置記法の式を機械語（中間語）に変換する。 ＡＢＣ＊＋Ｄ－の場合 1. 2. 3. mul B,C, W1 add A,W1, W2 sub W2,D,W3 変数または定数を入力したらスタックに積む。 演算子を入力したらスタックから右辺・左辺を取り出し出力 最後にスタックに残ったものが式の答え 入力 Ａ Ｂ Ｃ ＊ ＋ Ｄ ー Ｃ スタック Ａ 出力 6 Ｂ Ｂ Ｗ１ Ａ Ａ Ａ ＊，Ｂ，Ｃ Ｗ１ Ｄ Ｗ２ ＋，Ａ，Ｗ１ Ｗ２ Ｗ２ Ｗ３ ー，Ｗ２，Ｄ Ｗ３ コンパイラの論理的な構成 コンパイラは図のように各フェーズに分かれて処理する。 字句解析 構文解析 意味解析 最適化とコード生成 その過程で中間情報として名前表や中間語を保持する。 ソース プログラム 字句 解析 構文 解析 意味 解析 最適化 中間情報（中間語、名前表） 7 コード 生成 目的 プログラム 字句解析 ソースプログラムを字句と呼ばれる基本要素に分解する。 ｉｎｔ ａ，ｂ，ｃ，ｄ；の例 予約語 ｉｎｔ 名前 ａ 記号コンマ 記号コンマ 名前 ｄ 記号セミコロン 記号コンマ 名前 ｃ ａ＝ｂ＋ｃ＊ｄ；の例 名前 ａ 記号等号 記号セミコロン 8 名前 ｂ 名前 ｂ 記号加算 名前 ｃ 記号乗算 名前 ｄ 構文解析 分解された字句の並びが、構文規則に合うかどうか調べる。 関数名、変数名といった名前は名前表に登録される。 名前 ａ 名前 ｂ 名前 ｃ 名前 ｄ 記号乗算 記号加算 記号等号 エントリ番号 名前 データ型 番地 領域長 １ ａ ｉｎｔ １２ ４ ２ ｂ ｉｎｔ １６ ４ ３ ｃ ｉｎｔ ２０ ４ ４ ｄ ｉｎｔ ２４ ４ ５ ＄ｗｋ１ ｉｎｔ ２８ ４ ６ ＄ｗｋ２ ｉｎｔ ３２ ４ 9 意味解析 式は複数の演算に分解される。 式の場合、例えば、変数の型や型変換の可否を調べる。 最初の例にあったように、４つ組の中間語出力を生成 する際に ＄ｗｋ１や＄ｗｋ２といった一時記憶を使う。 10 乗算 名前表 ＃３ 名前表 ＃４ 名前表 ＃５ 加算 名前表 ＃２ 名前表 ＃５ 名前表 ＃６ 代入 名前表 ＃１ 名前表 ＃６ 最適化 例えば、最適化前のフェーズの中間語表現 加算 名前表 ＃２ 名前表 ＃５ 代入 名前表 ＃１ 名前表 ＃６ 代入はデータを移動するだけなので、加算命令の結果の 行き先に指定すれば代入が不要になる（無用命令削除）。 加算 名前表 ＃６ 名前表 ＃２ 名前表 ＃５ 名前表 ＃１ 他に、共通部分式の括り出し、定数伝播、演算強度の 低減、ループ内不変式のループ外への括り出し、 などを行う。 11 コード生成 中間語として表されたプログラムを機械語に変換する。 コード生成するために、より前の段階で中間語生成に 制約を設けている。 この段階の中間語はプロセッサに依存しない仮想機械 の命令で、それを変換する。 演算命令にメモリオペランドの使えるアーキテクチャ Ｒｅｇ＃１，Ａｄｄｒ＃２０ Ｒｅｇ＃１，Ａｄｄｒ＃２４ Ｒｅｇ＃１，Ａｄｄｒ＃１６ Ｒｅｇ＃１，Ａｄｄｒ＃１２ 演算命令にメモリオペランドの使えないアーキテクチャ 12 Ｌｏａｄ Ｍｕｌｔｉｐｌｙ Ａｄｄ Ｓｔｏｒｅ Ｌｏａｄ Ｌｏａｄ Ｍｕｌｔｉｐｌｙ Ｌｏａｄ Ａｄｄ Ｓｔｏｒｅ Ｒｅｇ＃１，Ａｄｄｒ＃２０ Ｒｅｇ＃２，Ａｄｄｒ＃２４ Ｒｅｇ＃１，Ｒｅｇ＃２，Ｒｅｇ＃１ Ｒｅｇ＃２，Ａｄｄｒ＃１６ Ｒｅｇ＃１，Ｒｅｇ＃２，Ｒｅｇ＃１ Ｒｅｇ＃１，Ａｄｄｒ＃１２ かなり違うので前段階で 制約として違いを盛り込む。 コンパイラの物理的な構成 パスとは、コンパイラ内部で中間語を順次出力する段階。 プログラムとして分離しているかどうかではない。 ワンパスコンパイラの例 最適化しないことが多い。 字句 解析 ソース プログラム 構文 解析 目的 プログラム 意味 解析 13 コード 生成 普通のコンパイラ 最適化のパスがコード生成前にある。 商用コンパイラではもっとパス数が多い。 ３パスコンパイラの例 パス１ パス２ パス３ 最適化 コード 生成 字句 解析 構文 解析 ソース プログラム 意味 解析 目的 プログラム 中間語 14 中間語 プログラム言語の形式的な記述方法 プログラミング言語の文法、つまり、生成規則。 プログラムを書くとは、文法に基づいてソースプログラムを 生成すること。だから、生成規則と呼んでいる。 コンパイラではソースプログラムが生成規則から生成されうる 文であるかどうかを判断し、目的プログラムを出力する。 生成規則に則らない記述はエラーとなる。 生成規則を意図的にゆるめている（シンタックスシュガー）場合もある。 生成規則が厳密であること。 もちろん、意図されないものはコンパイラの欠陥。 そのために、形式的な記述法が必要。 ソースプログラムが書きやすいこと。 15 素で書きやすいこと。シンタックスシュガーは必要悪。 バッカス記法(Backus Naur Form, BNF) ＜＞で囲まれたものを構文要素と呼ぶ。 例では字句を定義しているが、字句解析済みの場合もある。 Javaのように名前に日本語文字集合が使える場合は、 こんなに単純に記述できない。ＡＳＣＩＩ文字集合なら簡単。 →の左側の要素は右側で構成される。 ｜は「または」を意味する。 ＜数字＞→０｜１｜２｜３｜４｜５｜６｜７｜８｜９ ＜英字＞→ａ｜ｂ｜ｃ｜ｄ｜ｅ｜ｆ｜ｇ｜ｈ｜ｉ｜ｊ｜ｋ｜ｌ｜ｍ｜ｎ｜ｏ｜ｐ｜ｑ｜ｒ｜ｓ｜ｔ｜ｕ｜ｖ｜ｗ｜ｘ｜ｙ｜ｚ ｜Ａ｜Ｂ｜Ｃ｜Ｄ｜Ｅ｜Ｆ｜Ｇ｜Ｈ｜Ｉ｜Ｊ｜Ｋ｜Ｌ｜Ｍ｜Ｎ｜Ｏ｜Ｐ｜Ｑ｜Ｒ｜Ｓ｜Ｔ｜Ｕ｜Ｖ｜Ｗ｜Ｘ｜Ｙ｜Ｚ ＜名前＞→＜英字＞｜＜名前＞＜英字＞｜＜名前＞＜数字＞ 16 %token int_const char_const float_const id string enumeration_const %% translation_unit : external_decl | translation_unit external_decl ; external_decl : function_definition | decl ; function_definition : decl_specs declarator decl_list compound_stat | declarator decl_list compound_stat | decl_specs declarator compound_stat | declarator compound_stat ; decl : decl_specs init_declarator_list ';' | decl_specs ';' ; decl_list : decl | decl_list decl ; decl_specs : storage_class_spec decl_specs | storage_class_spec | type_spec decl_specs | type_spec | type_qualifier decl_specs | type_qualifier ; storage_class_spec : 'auto' | 'register' | 'static' | 'extern' | 'typedef' ; type_spec : 'void' | 'char' | 'short' | 'int' | 'long' | 'float' | 'double' | 'signed' | 'unsigned' | struct_or_union_spec | enum_spec | typedef_name 17 ; type_qualifier : 'const' | 'volatile'出典：http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf 拡張ＢＮＦ ｛｝：｛｝の中の要素を０個以上並べたもの。 []：[]の中の要素を０または１個書いたもの。 これを使うとこのように＜名前＞を書き直せる。 ＜名前＞→＜英字＞｛＜英字＞｜＜数字＞｝ ＢＮＦで使う記号 ＜＞｛｝[]｜→ はメタ記号と呼ぶ。 ＜＞で囲んだ構文要素を非終端記号 ＜＞で囲まないものを終端記号と呼ぶ。 18 プログラマがソースプログラムに書けるのは終端記号だけ。 構文解析に先立って字句解析があるときは、終端記号の 一部は字句としてまとめられている。
© Copyright 2024 ExpyDoc
