Presentation is loading. Please wait.

Presentation is loading. Please wait.

コンパイラ 2012年10月15日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html.

Similar presentations


Presentation on theme: "コンパイラ 2012年10月15日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html."— Presentation transcript:

1 コンパイラ 2012年10月15日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp)

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

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

4 バッカス記法(Backus Naur Form, BNF)
<>で囲まれたものを構文要素と呼ぶ。 例では字句を定義しているが、字句解析済みの場合もある。 Javaのように名前に日本語文字集合が使える場合は、 こんなに単純に記述できない。ASCII文字集合なら簡単。 →の左側の要素は右側で構成される。 |は「または」を意味する。 <数字>→0|1|2|3|4|5|6|7|8|9 <英字>→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z       |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z <名前>→<英字>|<名前><英字>|<名前><数字>

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

6 非決定性有限オートマトン(NFA) ある状態で、ある入力に対して、複数の遷移先がある。 正規表現からNFAを作る例。
入力によらない遷移もある。 遷移してもしなくてもいい。ε遷移 正規表現からNFAを作る例。 (3)a|b (1)ε空列記号 ε (2)アルファベットの集合Aの要素a (4)ab ε (5)a*

7 a(b|c)* の例 ε これら3つを合成する。 ε

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

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

10 a(b|c)*の、NFAからDFAへの変換例
ε 1,2, 4 2,3,4

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

12 字句読み取りの例 簡単な浮動小数点数を定義する。 [浮動少数数点定数の構文規則] [浮動小数点定数の正規表現] 〈浮動小数点数〉→
((ε|dd*).dd*|dd*.)(ε|e(ε|+|-|)dd*)|dd*e(ε|+|-)dd* 〈浮動小数点定数〉 〈小数点定数〉(ε|〈指数部〉)|〈数字列〉〈指数部〉 〈小数点定数〉 (ε|〈数字列〉).〈数字列〉|〈数字列〉. 〈指数部〉 e(ε|〈符号〉)〈数字列〉 〈符号〉 +|- 〈数字列〉 〈数字〉|〈数字列〉〈数字〉 〈数字〉 0|1|2|3|4|5|6|7|8|9

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

14 浮動小数点定数の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

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


Download ppt "コンパイラ 2012年10月15日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html."

Similar presentations


Ads by Google