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

字句解析(Lexical Analysis) 文字や文字の並びを、意味の有る字句として認識する。 自然言語では単語に分解することに相当する。 文法に基づき、予約語・識別子・演算子などに分解する。 識別子が関数名なのか変数名なのかは区別しない。 あくまで、単語に分解するだけである。 分解されたものは、文法上の構成単位である。 構文解析器の要求により動作する。 字句の要求に対する、字句への分解と字句の出力。 ソースプログラムからの文字の読み取り。 ファイルからのソースプログラムの読み込み。 読み込んだソースプログラムのバッファリング。

[条件式] 式 == != > < >= <= [加減演算子] [乗除演算子] + - ＊ / 要素型 void [数字]と[英字]は非終端記号なので、 本来はそれらも終端記号に至るまでの 定義が必要。しかし、省略されている。 前回のＢＮＦの例でも省略されている。 [返戻型] 数字 英字 [識別子] [整数] 数字 int [要素型]

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

有限オートマトン 名前などの字句は正規表現で定義できる。 つまり、正規言語で表せる。 入力の文字列が正規言語に含まれるかどうか？ 名前などの字句は正規表現で定義できる。 つまり、正規言語で表せる。 入力の文字列が正規言語に含まれるかどうか？ それを判定する仮想機械を有限状態オートマトンと呼んでいる。 開始状態から出発し、文字列を１文字ずつ読んでいきながら、 状態遷移関数によって状態を変化させていく。 最終的に最終状態に到達すれば、受理された、ということになる。

非決定性有限オートマトン(NFA) ある状態で、ある入力に対して、複数の遷移先がある。 正規表現からＮＦＡを作る例。 入力によらない遷移もある。 遷移してもしなくてもいい。ε遷移 正規表現からＮＦＡを作る例。 （３）ａ｜ｂ （１）ε空列記号 ａ ｂ ε （２）アルファベットの集合Ａの要素ａ （４）ａｂ ａ ｂ ａ ε ａ （５）ａ＊

ａ(ｂ|ｃ)＊　の例 ε ４ ３ ２ １ ａ １ ０ ａ ａ ３ ２ ｂ これら３つを合成する。 ε ３ ２ １ ｂ ｃ ０ ａ ４

決定性有限オートマトン(DFA) ＮＦＡではε遷移など、考えうるすべての状態遷移を 考慮して字句解析するのは効率が悪い。 ＮＦＡではε遷移など、考えうるすべての状態遷移を 考慮して字句解析するのは効率が悪い。 ＮＦＡから非決定的な遷移を取り除いたものがＤＦＡ。 ある状態から、入力によって遷移する先はたかだか一つ。 ＮＦＡからＤＦＡへ変換するアルゴリズムが存在する。

NFAからDFAへの変換 同じ状態から遷移する状態をまとめた状態集合を作成。 εでたどれる先もまとめること。 状態の集合からの遷移を作成。ここでも、同じ状態 からの遷移先が複数ある場合は、遷移先をまとめる。 ａ ε 1 2 1,2 ａ ε 1 2 3 4 5 ａ b c 1,2 ａ 4 3,5 b c

a(b|c)*の、NFAからDFAへの変換例 ε ３ ２ １ ｂ ｃ ０ ａ ４ 1,2, 4 ０ 2,3,4 ａ ｂ ｃ

ｂ ａ ｃ ｂ ａ 詳しくは、参考文献を見ること。 ｃ 「コンパイラの構成と最適化」 中田育男著 オーム社 院の講義で使う教科書なので、 1,2, 4 ０ 2,3,4 ａ ｂ ｃ ０ 1,2,3,4 ａ ｂ ｃ 詳しくは、参考文献を見ること。 「コンパイラの構成と最適化」 中田育男著　オーム社 院の講義で使う教科書なので、 図書館にある。

字句読み取りの例 簡単な浮動小数点数を定義する。 [浮動少数数点定数の構文規則] [浮動小数点定数の正規表現] 〈浮動小数点数〉→ （（ε｜ｄｄ＊）．ｄｄ＊｜ｄｄ＊．）（ε｜ｅ（ε｜＋｜－｜）ｄｄ＊）｜ｄｄ＊ｅ（ε｜＋｜－）ｄｄ＊ 〈浮動小数点定数〉 → 〈小数点定数〉（ε｜〈指数部〉）｜〈数字列〉〈指数部〉 〈小数点定数〉 （ε｜〈数字列〉）．〈数字列〉｜〈数字列〉． 〈指数部〉 ｅ（ε｜〈符号〉）〈数字列〉 〈符号〉 ＋｜－ 〈数字列〉 〈数字〉｜〈数字列〉〈数字〉 〈数字〉 0｜１｜２｜３｜４｜５｜６｜７｜８｜９

浮動小数点定数のNFA 1 f d ε ０ + . - 2 3 4 5 6 7 8 9 10 11 12 13 e

浮動小数点定数のDFA 0,2 12 3,5,f d 1,2, 6,10 3 13,f . e + - 8 4,5,f 9,f 11,12 7,8

状態数を最小にした浮動小数点定数のDFA 5 6 d ０ . e 4 2 1 3 - +