コンパイラ 第 3 回字句解析 決定性有限オートマトンの導出 http://www.no.knd.c.jp/compler 38 号館 4 階 N4 内線 5459 tks@no.knd.c.jp コンパイラの構造 字句解析系 構文解析系 制約検査系 中間コード生成系 最適化系 目的コード生成系 処理の流れ情報システムプロジェクト I の場合 output (); 字句解析系 output ( 変数名 ) ; 構文解析系 マイクロ構文の文法に従い解析 マクロ構文の文法に従い解析 <output_sttement> ::= output ( <exp> ) ; コード生成系 VSM アセンブラの文法に従い生成. PUSH & 2. OUTPUT 字句解析系 (lexcl nlyzer, scnner) 字句解析系 空白 コメントを読み飛ばす 単語 (token) に区切る エラーを検出 (ns >= 23 ) /* ns の値で分岐 */ ( 改行 ) ( 空白 )output ( ) ; 予約語 左括弧 ( 変数 ns 不等号 >= 整数 23 右括弧 ) 予約語 output : 単語への分割英語の場合 School o Scence nd Engneerng Knd Unversty 単語間に空白があるので区切るのは簡単日本語の場合きんきだいがくりこうがくぶきんき : だいがく : りこうがくぶ近畿大学理工学部きんきだ : いがくり : こうが : くぶ近畿だイガ栗黄河九分 区切り方を正しく決定するのは困難計算機言語の場合は? 単語への分割計算機言語の場合区切り記号で単語を判別できる mn () { nt, j, k; : mn( 区切り記号 ( が来たので mn で区切ると判別
マイクロ構文 ( 情報システムプロジェクト I の場合 ) (EBNF 記法で定義 ) または 回以上の繰り返し KProgrm ::= { Token WSpce } ( ファイル末 ) 変数名 整数 Token( 単語 ) ::= NAME INTEGER CHARACTER STRING 文字列文字 KEYWORD OPERATOR DELIMITER 予約語演算子区切り記号 WSpce( 空白 ) ::= ( スペース ) t ( タブ ) n ( 改行 ) Comment ( コメントは拡張課題 ) コメント マイクロ構文 ( 変数名, 整数, 文字 ) NAME( 変数名 ) ::= Alph { Alph Dec } INTEGER( 整数 ) ::= Pdec { Dec } x Xdec Xdec Xdec Xdec CHARACER( 文字 ) ::= ( シングルクォート ) Chrcter STRING( 文字列 ) ::= ( ダブルクォート ) { Chrcter } Alph {,,, z, A, B,, Z, _( アンダーバー )} Pdec {, 2,, 9} Dec {,, 2,, 9} Xdec {,, 2,, 9, A, B,, F} Chrcter ::= ( 任意の文字 ) マイクロ構文 ( 予約語 ) KEYWORD( 予約語 ) ::= o r n t n p u t c h r n p u t n t m n o u t p u t c h r o u t p u t n t o u t p u t s t r s e t s t r w h l e 予約語は変数名では使用不可拡張課題では e l s e 等も予約語 マイクロ構文 ( 演算子, 区切り記号 ) OPERATOR( 演算子 ) ::= = =! = < > & &! * / % = = = * = / = DELIMITER( 区切り記号 ) ::= ;, ( ) { } [ ] トークンの種類 ) { } [ ] ( 情報システムプロジェクトIの場合 ) トークン 記号 区切り記号 ;, ( 演比較演算子 ==!= < > (<=) (>=) 子算術演算子 * / % 算論理演算子! && 代入演算子 = = = *= /= 名前 変数名 定数 整数文字文字列 予約語 mn nt whle or nputnt nputchr outputnt outputchr outputstr setstr (else) (do) (rek) 区切り記号 トークン名 比較演算子 記号トークン名記号トークン名 ; SEMICOLON == EUAL, COMMA!= NOTE ( LPAREN < LESS ) RPAREM > GREAT { LBRACE } RBRACE [ LBRACKET ] RBRACKET 論理演算子 記号トークン名 && AND OR! NOT 2
トークン名 算術演算子 記号 トークン名 ADD SUB * MUL / DIV % MOD ( ) 単項演算子の と二項演算子の で共通して使用 ( ) 代入演算子 記号トークン名 = ASSIGN = ASSIGNADD = ASSIGNSUB *= ASSIGNMUL /= ASSIGNDIV (%=) ASSIGNMOD INC DEC トークン名 定数, 変数名, 予約語 文字列種別トークン名 数字の並び 整数 PINTEGER ( 任意の 文字 ) 文字 CHARACTER ( 任意の文字列 ) 文字列 STRING 英字の並び 変数名 NAME mn 予約語 MAIN nt 予約語 INT 予約語 IF whle 予約語 WHILE nputnt 予約語 INPUTINT : : : INTEGER と INT の違いに注意 字句解析の手順 字句解析 決定性有限オートマトンで解析 ( 最小の ) 決定性有限オートマトンを導出する必要があるマイクロ構文 非決定性有限オートマトン 決定性有限オートマトン 状態最小化 字句解析系 非 非決定性有限オートマトン () 以下の手法で帰納的に. ( 空記号列 ) に対する 2. φ( 空遷移関数集合 ) に対する 3. Σ に対する 4. R R 2 に対する 5. R R 2 に対する 6. R* に対する 7. R に対する (R, R 2, R : 正規表現 ) 非. ( 空記号列 ) に対する 2. φ( 空遷移関数集合 ) に対する 3. Σ に対する 入力が無くても状態遷移 状態遷移無し 入力 で状態遷移 非 4. R R 2 に対する R R 2 5. R R 2 に対する R R 2 (R, R 2 : 正規表現 ) 3
非 6. R* ( 回以上の繰り返し ) に対する R 7. R ( 回以上の繰り返し ) に対する R (R : 正規表現 ) 非決定性オートマトンへ r ::= ( )* ( )* 非決定性オートマトンへ r ::= ( )* 非決定性有限オートマトンの問題点 非決定性有限オートマトン 同一入力に対する状態遷移が複数存在 複数の遷移を全て解析する必要がある 決定性有限オートマトンに変形する q 非決定性有限オートマトン () 決定性有限オートマトン () 同一の入力で遷移できる状態をつの状態にまとめる q q 3 q 5 q 4 q 6 q 7 q 8 q 9 q から 入力で q 4 q 8 へ遷移可能 q q 4 q 8 をまとめる N = ( N, Σ, δ N, q N, F N ) D = ( D, Σ δ D, q D, F D ) closure (q) ::= q { N D } から 遷移できる状態集合 goto (q, ) ::= q { N D } から Σで遷移できる状態集合 4
, q q q F N closure (q) goto (q, ) goto (q, ) q {q, q } q の q {q } { } {, } q F {q F } q, 3 q 遷移は q 遷移 遷移 遷移を含む q F N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q { }, q } の {q, q } の 入力 入力 {, } q F {q F } q, 3 q q q F N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q, q } {, } { } φ {q F } {, } φ {q F } アルゴリズム D := {closure (q N ) }; /* D の初期入力 */ or ech q D { /* D 内の未実行の要素に対して実行 */ or ech Σ { r := closure (goto (q, )); (r D ) /* r は D の中に無いか? */ } } D := D r; /* r を D に加える */ δ D (q, ) := r; N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q, q } {, } { } φ {q F } {, } φ {q F } D closure (q) goto (q, ) goto (q, ) q, {q, q } {q, q } {q, q,, } closure ({q q }) goto ({q q }, ) goto ({q q }, ) N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q, q } {, } { } φ {q F } {, } φ {q F },,,, D closure (q) goto (q, ) goto (q, ) q, {q, q } {q, q } {q, q,, } q,, 2, 3 {q, q,, } {q, q } {q, q,,, q F } 5
N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q, q } {, } { } φ {q F } {, } φ {q F },,,,, D closure (q) goto (q, ) goto (q, ) q, {q, q } {q, q } {q, q,, } q,, 2, 3 {q, q,, } {q, q } {q, q,,, q F } q,, 2, 3,F {q, q,,, q F } {q, q, q F } {q, q,,, q F } N closure (q) goto (q, ) goto (q, ) q {q, q } {q, q } {q, q,, } q {q } {q, q } {, } { } φ {q F } {, } φ {q F },,,,,, D closure (q) goto (q, ) goto (q, ) q, {q, q } {q, q } {q, q,, } q,, 2, 3 {q, q,, } {q, q } {q, q,,, q F } q,, 2, 3,F {q, q,,, q F } {q, q, q F } {q, q,,, q F } q F {q, q, q F } {q, q, q F } {q, q,, } D closure (q) goto (q, ) goto (q, ) q, {q, q } {q, q } {q, q,, } q,, 2, 3 {q, q,, } {q, q } {q, q,,, q F } q,, 2, 3, F {q, q,,, q F } {q, q, q F } {q, q,,, q F } q,,f {q, q, q F } {q, q, q F } {q, q,, } は自分自身への遷移のみ q,,f q, q,,2,3 q,,2,3,f q F を含めば状態, q q q F q,,f q, q,,2,3 q,,2,3,f 決定性有限オートマトンの問題点 導出で得られた有限オートマトン 状態数が最小とは限らない 状態数の最小化を行う 状態最小化 状態最小化 状態の等価性を用いてを最適化 状態の等価性 状態 p と状態 q に対して同一の入力列を与えたとき その出力 (, 不 ) が全て同じ 状態 p と状態 q が等価である (p q) ( ) 等価性についての詳細は 論理回路 第 3 回講義を参照 6
状態数最小化の手順 手法 状態遷移表の分割. 異なる出力を生成する状態対をグループに分割 2. 以下を分割できなくなるまで繰り返す 同一の入力に対し の状態が異なるグループに属すればその状態対をグループに分割 3. グループごとにつの状態に併合 手法 2 状態併合表. 異なる出力を持つ状態対に を付ける 2. の状態対を記入 3. 以下を が付かなくなくなるまで繰り返す に が付いていればその状態対に を付ける 4. 等価な状態対を決定 グループ r 状態遷移表を用いた最小化 q q 状態 q q q q F q F q F, でグループ分け {q } {q,, } {q F } グループ 状態遷移表を用いた最小化 状態 r q q グループ q q F q F q, と の 入力グループが異なる を {q, }{ } に分割 {q } {q, } { } {q F } グループ 状態遷移表を用いた最小化 状態 r q q q q F グループ r 3 q F q {q }, のグループが全て同じ {q, } 分割終了 { } {q F } r 3 グループ 状態遷移表を用いた最小化 グループ 状態 r q q,2 r 3 r 3 q F r 3 r q q q q q q F q F q と q が異なるグループなら を付ける 最後まで が付かなければ等価 7
q q q の有無 不が異なる状態対に を付ける q q q δ(q, )δ(, ) δ(q, )δ(, ) q q q F q q 3 3 2 2 q F 3 3 3 3 2 F 2 F q F q F q q q 同一なら判定不要 q q q q F は なので 2 F に を付ける q q q q 3 3 2 2 q F 3 3 2 F 3 3 2 F q F 2 F 2 F q F q F q q q q q 最後まで が付かなかった {q, } が等価 q F 2 F 2 F q F 最小化前 q q 最小化後 r 3 r q F 8
決定性有限オートマトンの作成情報システムプロジェクト I の場合 OPERATOR( 一部 ) ::= = = = = 非決定性オートマトンへ = = 2 3 4 5 6 2 22 32 = 33 = 42 43 52 53 62 63 F 決定性オートマトンへ N =,,2,3, 4,5,6 2,F 2 2,F 2 2 22,F 22 22,F 3 3 32 32 32 33,F 33 33,F N = 4 4 42 42 42 43,F 43 43,F 5 5 52 52 52 53,F 53 53,F 6 6 62 62 62 63,F 63 63,F 決定性オートマトンへ D =,,2,3, 4,5,6,,2,3, 4,5,6 2,32, 52,F 22,42, 62,F 2,32,52,F 2,32,52,F 53,F 33,F 22,42,62,F 22,42,62,F 63,F 43,F 33,F 33,F 43,F 43,F 53,F 53,F 63,F 63,F 決定性オートマトン = = = = 状態数最小化は不要 決定性有限オートマトン ( 一部 ) ; A Z z _ ; 名前 = = = = = == 9 A Z z _ 9 整数 整数 9 9