コンパイラ 2011年10月6日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html

コンパイラの構成と プログラム言語の形式的な記述 コンパイラの構成と プログラム言語の形式的な記述 式(Expression)と文(Statement) 算術式の中置期法と後置記法 コンパイラの論理的な構成 コンパイラの物理的な構成 プログラム言語の形式的な記述方法 バッカス記法 構文図式（→次回）

式(Expression)と文(Statement) 式はそれ自体が値を持つもの。 一般的には値・変数・演算子・関数を組み合わせたもの。 式として認識される範囲は言語仕様に依存する。 文は手続きを表すことが多い。 改行文字まででひとつの文とする言語 特別な記号で区切ったり、次行と結合したりもできる。 文脈依存文法。 区切り文字で区切る言語 Pascalは、';'が区切り文字になっている。 区切りが特に無い言語 Ｃは、';'が式を文とする記号。

算術式の中置期法と後置記法 四則演算では演算には優先順位がある。 通常の式では変数と変数の間に演算子がある。 乗除算は加減算に優先する、括弧はそれらより優先する。 通常の式では変数と変数の間に演算子がある。 中に演算子を置くので中置記法という。 学群実験の経験より、計算機は優先順位など知らない。 機械語として書かれた順に処理するだけ。 通常の式を機械語に変換するに先立って、書き換える。 そのひとつが後置記法。 演算子を被演算対象の後に置く。

後置記法の例 中置記法のＡ＋Ｂ＊Ｃ－Ｄは、ＡＢＣ＊＋Ｄ－という後置記法になる。 優先順位に基づき（（Ａ＋（Ｂ＊Ｃ））－Ｄ）というように解釈する。 演算対象を読んだらそのまま出力する 演算子を読んだら、それより優先度の高い演算子があれば スタックから取り出し順に出力しておいて、スタックに積む。 式を読み終わったら全部順に取り出し出力する。 入力 Ａ Ｂ Ｄ Ｃ ＋ ー ＊ （ ） 出力 スタック

コンパイラの場合 後置記法の式を機械語（中間語）に変換する。 ＡＢＣ＊＋Ｄ－の場合 変数または定数を入力したらスタックに積む。 mul B,C, W1 add A,W1, W2 sub W2,D,W3 変数または定数を入力したらスタックに積む。 演算子を入力したらスタックから右辺・左辺を取り出し出力 最後にスタックに残ったものが式の答え 入力 Ａ Ｂ Ｃ ＊ ＋ Ｄ ー スタック Ｃ Ｂ Ｂ Ｗ１ Ｄ Ａ Ａ Ａ Ａ Ｗ２ Ｗ２ Ｗ３ 出力 ＊，Ｂ，Ｃ Ｗ１ ＋，Ａ，Ｗ１ Ｗ２ ー，Ｗ２，Ｄ Ｗ３

コンパイラの論理的な構成 コンパイラは図のように各フェーズに分かれて処理する。 その過程で中間情報として名前表や中間語を保持する。 字句解析 構文解析 意味解析 最適化とコード生成 その過程で中間情報として名前表や中間語を保持する。 ソース プログラム 目的 中間情報（中間語、名前表） 字句 解析 コード 生成 構文 意味 最適化

字句解析 ソースプログラムを字句と呼ばれる基本要素に分解する。 ｉｎｔ ａ，ｂ，ｃ，ｄ；の例 ａ＝ｂ＋ｃ＊ｄ；の例 予約語 ｉｎｔ ｉｎｔ　ａ，ｂ，ｃ，ｄ；の例 ａ＝ｂ＋ｃ＊ｄ；の例 予約語　ｉｎｔ 記号セミコロン 記号コンマ 名前　ａ 名前　ｂ 名前　ｃ 名前　ｄ 名前　ａ 名前　ｂ 名前　ｃ 名前　ｄ 記号乗算 記号加算 記号等号 記号セミコロン

構文解析 分解された字句の並びが、構文規則に合うかどうか調べる。 関数名、変数名といった名前は名前表に登録される。 名前 ａ 名前 ｂ 名前　ａ 名前　ｂ 名前　ｃ 名前　ｄ 記号乗算 記号加算 記号等号 エントリ番号 名前 データ型 番地 領域長 １ ａ ｉｎｔ １２ ４ ２ ｂ １６ ３ ｃ ２０ ｄ ２４ ５ ＄ｗｋ１ ２８ ６ ＄ｗｋ２ ３２

意味解析 式は複数の演算に分解される。 式の場合、例えば、変数の型や型変換の可否を調べる。 最初の例にあったように、４つ組の中間語出力を生成 する際に ＄ｗｋ１や＄ｗｋ２といった一時記憶を使う。 乗算 名前表　＃３ 名前表　＃４ 名前表　＃５ 加算 名前表　＃２ 名前表　＃６ 名前表　＃５ 名前表　＃１ 代入 名前表　＃６

最適化 例えば、最適化前のフェーズの中間語表現 代入はデータを移動するだけなので、加算命令の結果の 行き先に指定すれば代入が不要になる（無用命令削除）。 他に、共通部分式の括り出し、定数伝播、演算強度の 低減、ループ内不変式のループ外への括り出し、 などを行う。 加算 名前表　＃２ 名前表　＃６ 名前表　＃５ 名前表　＃１ 代入 名前表　＃６ 加算 名前表　＃２ 名前表　＃１ 名前表　＃５

コード生成 中間語として表されたプログラムを機械語に変換する。 この段階の中間語はプロセッサに依存しない仮想機械 の命令で、それを変換する。 コード生成するために、より前の段階で中間語生成に 制約を設けている。 この段階の中間語はプロセッサに依存しない仮想機械 の命令で、それを変換する。 演算命令にメモリオペランドの使えるアーキテクチャ Ｌｏａｄ　　　Ｒｅｇ＃１，Ａｄｄｒ＃２０ Ｍｕｌｔｉｐｌｙ　Ｒｅｇ＃１，Ａｄｄｒ＃２４ Ａｄｄ　　　　Ｒｅｇ＃１，Ａｄｄｒ＃１６ Ｓｔｏｒｅ　　　Ｒｅｇ＃１，Ａｄｄｒ＃１２ 演算命令にメモリオペランドの使えないアーキテクチャ Ｌｏａｄ　　　Ｒｅｇ＃２，Ａｄｄｒ＃２４ Ｍｕｌｔｉｐｌｙ　Ｒｅｇ＃１，Ｒｅｇ＃２，Ｒｅｇ＃１ Ｌｏａｄ　　　Ｒｅｇ＃２，Ａｄｄｒ＃１６ Ａｄｄ　　　　Ｒｅｇ＃１，Ｒｅｇ＃２，Ｒｅｇ＃１ かなり違うので前段階で 制約として違いを盛り込む。

コンパイラの物理的な構成 パスとは、コンパイラ内部で中間語を順次出力する段階。 ワンパスコンパイラの例 プログラムとして分離しているかどうかではない。 ワンパスコンパイラの例 最適化しないことが多い。 ソース プログラム 目的 字句 解析 コード 生成 構文 意味 ひどいクロスコンパイラがあったなぁ～

普通のコンパイラ 最適化のパスがコード生成前にある。 ３パスコンパイラの例 商用コンパイラではもっとパス数が多い。 パス３ パス２ パス１ ソース プログラム 目的 字句 解析 コード 生成 構文 意味 最適化 中間語

プログラム言語の形式的な記述方法 プログラミング言語の文法、つまり、生成規則。 生成規則が厳密であること。 プログラムを書くとは、文法に基づいてソースプログラムを 生成すること。だから、生成規則と呼んでいる。 コンパイラではソースプログラムが生成規則から生成されうる 文であるかどうかを判断し、目的プログラムを出力する。 生成規則に則らない記述はエラーとなる。 生成規則を意図的にゆるめている（シンタックスシュガー）場合もある。 もちろん、意図されないものはコンパイラの欠陥。 生成規則が厳密であること。 そのために、形式的な記述法が必要。 ソースプログラムが書きやすいこと。 素で書きやすいこと。シンタックスシュガーは必要悪。

バッカス記法(Backus Naur Form, BNF) ＜＞で囲まれたものを構文要素と呼ぶ。 例では字句を定義しているが、字句解析済みの場合もある。 Javaのように名前に日本語文字集合が使える場合は、 こんなに単純に記述できない。ＡＳＣＩＩ文字集合なら簡単。 →の左側の要素は右側で構成される。 ｜は「または」を意味する。 ＜数字＞→０｜１｜２｜３｜４｜５｜６｜７｜８｜９ ＜英字＞→ａ｜ｂ｜ｃ｜ｄ｜ｅ｜ｆ｜ｇ｜ｈ｜ｉ｜ｊ｜ｋ｜ｌ｜ｍ｜ｎ｜ｏ｜ｐ｜ｑ｜ｒ｜ｓ｜ｔ｜ｕ｜ｖ｜ｗ｜ｘ｜ｙ｜ｚ 　　　　　　｜Ａ｜Ｂ｜Ｃ｜Ｄ｜Ｅ｜Ｆ｜Ｇ｜Ｈ｜Ｉ｜Ｊ｜Ｋ｜Ｌ｜Ｍ｜Ｎ｜Ｏ｜Ｐ｜Ｑ｜Ｒ｜Ｓ｜Ｔ｜Ｕ｜Ｖ｜Ｗ｜Ｘ｜Ｙ｜Ｚ ＜名前＞→＜英字＞｜＜名前＞＜英字＞｜＜名前＞＜数字＞

%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 type_qualifier : 'const' | 'volatile' struct_or_union_spec : struct_or_union id '{' struct_decl_list '}' | struct_or_union '{' struct_decl_list '}' | struct_or_union id struct_or_union : 'struct' | 'union' struct_decl_list : struct_decl | struct_decl_list struct_decl init_declarator_list : init_declarator | init_declarator_list ',' init_declarator init_declarator : declarator | declarator '=' initializer struct_decl : spec_qualifier_list struct_declarator_list ';' spec_qualifier_list : type_spec spec_qualifier_list | type_qualifier spec_qualifier_list struct_declarator_list : struct_declarator | struct_declarator_list ',' struct_declarator struct_declarator : declarator | declarator ':' const_exp | ':' const_exp enum_spec : 'enum' id '{' enumerator_list '}' | 'enum' '{' enumerator_list '}' | 'enum' id enumerator_list : enumerator | enumerator_list ',' enumerator enumerator : id | id '=' const_exp declarator : pointer direct_declarator | direct_declarator direct_declarator : id | '(' declarator ')' | direct_declarator '[' const_exp ']' | direct_declarator '[' ']' | direct_declarator '(' param_type_list ')' | direct_declarator '(' id_list ')' | direct_declarator '(' ')' pointer : '*' type_qualifier_list | '*' | '*' type_qualifier_list pointer | '*' pointer type_qualifier_list : type_qualifier | type_qualifier_list type_qualifier param_type_list : param_list | param_list ',' '...' param_list : param_decl | param_list ',' param_decl param_decl : decl_specs declarator | decl_specs abstract_declarator | decl_specs id_list : id | id_list ',' id initializer : assignment_exp | '{' initializer_list '}' | '{' initializer_list ',' '}' initializer_list : initializer | initializer_list ',' initializer type_name : spec_qualifier_list abstract_declarator | spec_qualifier_list abstract_declarator : pointer | pointer direct_abstract_declarator | direct_abstract_declarator direct_abstract_declarator: '(' abstract_declarator ')' | direct_abstract_declarator '[' const_exp ']' | '[' const_exp ']' | direct_abstract_declarator '[' ']' | '[' ']' | direct_abstract_declarator '(' param_type_list ')' | '(' param_type_list ')' | direct_abstract_declarator '(' ')' | '(' ')' typedef_name : id stat : labeled_stat | exp_stat | compound_stat | selection_stat | iteration_stat | jump_stat labeled_stat : id ':' stat | 'case' const_exp ':' stat | 'default' ':' stat exp_stat : exp ';' | ';' compound_stat : '{' decl_list stat_list '}' | '{' stat_list '}' | '{' decl_list '}' | '{' '}' stat_list : stat | stat_list stat selection_stat : 'if' '(' exp ')' stat | 'if' '(' exp ')' stat 'else' stat | 'switch' '(' exp ')' stat iteration_stat : 'while' '(' exp ')' stat | 'do' stat 'while' '(' exp ')' ';' | 'for' '(' exp ';' exp ';' exp ')' stat | 'for' '(' exp ';' exp ';' ')' stat | 'for' '(' exp ';' ';' exp ')' stat | 'for' '(' exp ';' ';' ')' stat | 'for' '(' ';' exp ';' exp ')' stat | 'for' '(' ';' exp ';' ')' stat | 'for' '(' ';' ';' exp ')' stat | 'for' '(' ';' ';' ')' stat jump_stat : 'goto' id ';' | 'continue' ';' | 'break' ';' | 'return' exp ';' | 'return' ';' exp : assignment_exp | exp ',' assignment_exp assignment_exp : conditional_exp | unary_exp assignment_operator assignment_exp assignment_operator : '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<=' | '>>=' | '&=' | '^=' | '|=' conditional_exp : logical_or_exp | logical_or_exp '?' exp ':' conditional_exp const_exp : conditional_exp logical_or_exp : logical_and_exp | logical_or_exp '||' logical_and_exp logical_and_exp : inclusive_or_exp | logical_and_exp '&&' inclusive_or_exp inclusive_or_exp : exclusive_or_exp | inclusive_or_exp '|' exclusive_or_exp exclusive_or_exp : and_exp | exclusive_or_exp '^' and_exp and_exp : equality_exp | and_exp '&' equality_exp equality_exp : relational_exp | equality_exp '==' relational_exp | equality_exp '!=' relational_exp relational_exp : shift_expression | relational_exp '<' shift_expression | relational_exp '>' shift_expression | relational_exp '<=' shift_expression | relational_exp '>=' shift_expression shift_expression : additive_exp | shift_expression '<<' additive_exp | shift_expression '>>' additive_exp additive_exp : mult_exp | additive_exp '+' mult_exp | additive_exp '-' mult_exp mult_exp : cast_exp | mult_exp '*' cast_exp | mult_exp '/' cast_exp | mult_exp '%' cast_exp cast_exp : unary_exp | '(' type_name ')' cast_exp unary_exp : postfix_exp | '++' unary_exp | '--' unary_exp | unary_operator cast_exp | 'sizeof' unary_exp | 'sizeof' '(' type_name ')' unary_operator : '&' | '*' | '+' | '-' | '~' | '!' postfix_exp : primary_exp | postfix_exp '[' exp ']' | postfix_exp '(' argument_exp_list ')' | postfix_exp '(' ')' | postfix_exp '.' id | postfix_exp '->' id | postfix_exp '++' | postfix_exp '--' primary_exp : id | const | string | '(' exp ')' argument_exp_list : assignment_exp | argument_exp_list ',' assignment_exp const : int_const | char_const | float_const | enumeration_const 出典：http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf

拡張ＢＮＦ ｛｝：｛｝の中の要素を０個以上並べたもの。 []：[]の中の要素を０または１個書いたもの。 これを使うとこのように＜名前＞を書き直せる。 ＜名前＞→＜英字＞｛＜英字＞｜＜数字＞｝ ＢＮＦで使う記号　＜＞｛｝[]｜→　はメタ記号と呼ぶ。 ＜＞で囲んだ構文要素を非終端記号 ＜＞で囲まないものを終端記号と呼ぶ。 プログラマがソースプログラムに書けるのは終端記号だけ。 構文解析に先立って字句解析があるときは、終端記号の 一部は字句としてまとめられている。