字句解析.

Presentation on theme: "字句解析."— Presentation transcript:

1 字句解析

2 字句解析 字句解析：ソースプログラムの「文字の列」を言語として意味を持つ最小単位であるトークン(字句)として認識する 字句解析器: 一般に字句解析器は構文解析器から呼び出される手続き(関数)として実現される 字句解析器はトークン名とその属性(つづりなど)を報告する 本講義ではどのようにして字句解析器を作るかについて解説

3 字句解析 例) if(sum+A10>123) トークン 　 トークン名 sum i A10 i 123 n if 　　 if + + ( ( ) ) > >　　　　　　　 if ( sum + A10 > 123 )

4 字句解析 トークンの文字列構成規則は正規表現で定義される プログラムはその規則に従って書かれる 字句解析器が行うこと： 入力された文字列を正規表現にしたがって解析しトークンを認識する もし入力された文字列が正規表現に従ったものとなっていなければそのことを報告する 字句解析器の生成手順 トークンの正規表現→非決定性有限オートマトン→ 決定性有限オートマトン→字句解析器

5 正規表現 トークンを構成する文字列がどのように構成されるかを正規表現によって定義する 準備1：用語 アルファベット Σ：記号(文字)の有限集合 例) Σ={0,1} アルファベットΣ上の記号列：アルファベット中の記号によって作られる有限の列 例) アルファベットΣ上の記号列： 0, 001, 1010 空列 ε：長さが0の記号列 (長さ：記号の個数) 連接：記号列xの後に記号列yをつなげたものを xとyの連接と呼び，xyと表記 例)記号列001と記号列1010の連接は

6 正規表現 準備2：記号列の集合に対する演算 記号列の集合L1、L2に対する演算の定義 L1とL2の和集合： L1∪L2={x|x∈L1かx∈L2} L1とL2の連接： L1L2={xy|x∈L1,y∈L2} Lのべき乗： L0 ={ε}, L1=L, Li=Li-1L 連接を“積”と考える Lのクリーネ閉包： L*=L0∪L1∪L2∪...∪L∞ Lの0回以上の繰り返し Lの正の閉包： L+= L1∪L2∪...∪L∞ Lの1回以上の繰り返し

7 正規表現 記号列の集合L1、L2に対する演算の定義 例) L1={0, 1} L2={ab, cd, efg} 和集合　 　　　　L1∪L2=　 連接 　　L1L2= 　　　 べき乗　 L10= L11= L12= クリーネ閉包 　　　　L1*= 　　　 正の閉包 L1+= {0, 1 , ab, cd, efg} {0ab, 0cd, 0efg, 1ab, 1cd, 1efg} {ε} {0, 1} {00, 01, 10, 11} {ε ,0, 1, 00, 01, 10, 11, 000, 001,...} {0, 1, 00, 01, 10, 11, 000, 001,...}

8 正規表現 アルファベットΣ上の正規表現の定義 正規表現 その正規表現に従った記号列の集合 ε {ε} a {a} r|s L(r)∪L(s)　(｜は交換律を満たす) rs L(r)L(s) r* (L(r))* (r) L(r) ただし a∈Σ， だたし rとsは正規表現でその正規表現に従った記号列集合はL(r)とL(s) 演算子の優先順位は、*，連接，| rr*をr+と略記することもある

9 正規表現 例題)Σ={0,1,a,b}とする 次の正規表現で表される記号列集合を求めよ a|b a1* (0|1)|(a|b) (0|1)(a|b) (0|1)* a|a*b {a,b} {a, a1, a11, a111,…} {0, 1, a, b} {0a, 0b, 1a, 1b} {ε, 0, 1, 00, 01,...} {a, b, ab, aab,...}

10 正規表現 実際の正規表現の記述に際しては，Σ中の記号以外の記号を導入し，それで部分的な正規表現を表す: 正規定義 (0|1)|(a|b) を表現するのに D → 0| L → a|b D | L

11 有限オートマトン(finite automaton)
有限オートマトンでトークンの認識ができる 認識：正規表現に合致しているか否か 合致している場合には受理にいたる 正規表現によって定義されたトークンを認識する有限オートマトンを機械的に作成できる 正規表現から，有限オートマトンを作成し，それをプログラムで実現すれば，字句解析を行うプログラムー字句解析器ーを作成できる

12 特別な状態：初期(開始)状態と最終(受理)状態 状態と記号の対を状態集合へ写像する遷移関数
有限オートマトン 有限オートマトンの要素 状態の集合 特別な状態：初期(開始)状態と最終(受理)状態 状態と記号の対を状態集合へ写像する遷移関数 a 状態 入力記号 a b ,2 1 3 a a b 1 2 3 b 例)正規表現 a(a|b)*ab を認識する有限オートマトンの遷移図による表現と遷移表による表現

13 有限オートマトンが入力を受理する過程 例)aabab
受理に至ればそのトークンは正規表現に合致 受理状態以外で終了するもしくは遷移先がなくなった場合には合致していない a a b 2 1 3 b a(a|b)*abを認識する有限オートマトン

14 例題) a(a|b)*abを認識する有限オートマトンが入力 ababbabを受理する過程を示せ
2 1 3 b a(a|b)*abを認識する有限オートマトン

15 前述の有限オートマトンでは，遷移(の方向)が一通りでない(非決定性)場合がある 例)状態1でaを読み込んだ場合
非決定性有限オートマトン 前述の有限オートマトンでは，遷移(の方向)が一通りでない(非決定性)場合がある 例)状態1でaを読み込んだ場合 同じ記号による遷移に非決定性があるような有限オートマトンを非決定性有限オートマトン(ＮＦＡ)と呼ぶ a a a b 2 3 1 b a(a|b)*abを認識する非決定性有限オートマトン

16 NFAでは空列εによる遷移(ε遷移：何も読み込まずに遷移する)も許されるため，NFAにはε遷移による非決定性も存在する
非決定性有限オートマトン NFAでは空列εによる遷移(ε遷移：何も読み込まずに遷移する)も許されるため，NFAにはε遷移による非決定性も存在する a a b a ε ε 6 1 2 3 4 5 a ε b ε a a a b 2 3 1 a(a|b)*abを認識する非決定性有限オートマトン b

17 例)下のNFAがaababを認識する過程 0 a 1 ε 2 a 3 ε2 b 3 ε 4 a 5 b 6
非決定性有限オートマトン 例)下のNFAがaababを認識する過程 0 a 1 ε 2 a 3 ε2 b 3 ε 4 a 5 b 6 　　 例題)同様にababbabを認識する過程を示せ a a b a ε ε 5 6 1 2 3 4 a ε b ε a(a|b)*abを認識する非決定性有限オートマトン 0 a 1 ε 2 b 3 ε2 a 3 ε2 b 3 ε2 b 3 ε 4 a 5 b 6

18 決定性有限オートマトン(DFA) 決定性有限オートマトン(DFA)：ＮＦＡの特別な場合 各状態で同じ入力記号に対する遷移が高々一通り ε遷移が無い 任意のNFAに対し，同じ正規表現を認識するDFAを作成可能

19 例)a(a|b)*abを認識する決定性有限オートマトン
例題)上のDFAがaababを認識する過程を示せ a b a 2 a a 1 a 4 b b 3 b 0 a 1 a 2 b 4 a 2 b 4

20 正規表現から非決定性有限オートマトンを作る
まず正規表現を部分的な正規表現rに分割 各部分正規表現に対して以下に示す部分NFAを作る (1)r→ε (3)r→ r1|r (2)r→ a(a∈Σ) ε r1 ε ε r2 a r2 r1

21 正規表現から非決定性有限オートマトンを作る
　 (4)r→ r1r (5)r→r1* 次に部分NFAをまとめる r1 r2 ε r2 r1 ε r1

22 正規表現から非決定性有限オートマトンを作る
例)a(a|b)*abをNFAに変換する 　 a(a|b)*ab=r1r4r1r2とおく ここでr1→a, r2→b, r3→a|b, r4→(r3)*とする (1)r (4) r4 (2)r (3)r (5) r3を代入すると a b r3 ε

23 正規表現から非決定性有限オートマトンを作る
　よってa(a|b)*ab=r1r4r1r2は 例題)(ab)*|aaのNFAを示せ a a b a ε ε 5 6 1 2 3 4 a ε b ε a b 1 3 2 4 ε 5

24 NFAをDFAに変換する NFAのある状態から，一つの入力記号で遷移して到達できる状態が複数個ある(状態集合)場合，それらをDFAの一つの状態としていく そのDFAの状態間での遷移を求める すなわち次の二つを求める DFAの状態の集合Dstates 遷移表Dtable

25 NFAをDFAに変換する 例のNFA 例のDFA a(a|b)*ab a a b ε ε a 5 6 1 2 3 4 a ε b ε a b
1 2 3 4 a ε b ε a 例のDFA a(a|b)*ab b 2,3,4,5 a a a 1,2,4 a 2,3,4,6 b 2,3,4 b b

26 NFAをDFAに変換する 状態集合を記録していくために下の演算を使用する Ns：NFAの状態集合 ε-closure(Ns)：Ns中の各NFA状態から，ε遷移だけで(ε遷移の繰返し可) 到達できるNFA状態の和集合(Nsも含む) ただし，ε-closure(φ)=φ goto(Ns,a)： Ns中の各NFA状態から，入力記号aによる一回の遷移で到達するNFA状態の和集合

27 ε-closure({3})={2,3,4} {3}中の各NFA状態から，ε遷移だけで到達できるNFA状態の和集合({3}も含む)
NFAをDFAに変換する 例) ε-closure({3})={2,3,4} {3}中の各NFA状態から，ε遷移だけで到達できるNFA状態の和集合({3}も含む) a a b a ε ε 5 6 1 2 3 4 a ε b ε

28 goto({1,2,4},a)={3,5} {1,2,4}中の各NFAのある状態から，入力記号aにる一回の遷移で到達するNFA状態の和集合
NFAをDFAに変換する 例) goto({1,2,4},a)={3,5} {1,2,4}中の各NFAのある状態から，入力記号aにる一回の遷移で到達するNFA状態の和集合 a a b a ε ε 5 6 1 2 3 4 a ε b ε

29 NFAをDFAに変換する 次の二つを求める DFAの状態の集合Dstates 遷移表Dtable： Dtable[T,a]は，DFAの状態Tでaによる遷移先のDFA状態

30 初期化：D0=ε-closure({0}), Dstates:={D0}, D0はマーク無し
NFAをDFAに変換する 初期化：D0=ε-closure({0}), Dstates:={D0}, D0はマーク無し while Dstates 中に無マークの状態Tがある do begin Tにマーク付け; for Σ中の各入力記号xについて do begin U:= ε-closure(goto(T,x)); if Uが空集合でなくかつDstates中に無い then Uを無マークでDstatesに追加； Dtable[T,x]:=U end 但しNFAでの受理状態を含むDFAの状態は受理状態とする

31 初期化：D0=ε-closure({0})={0} Dstates:={D0}, D0はマーク無し
NFAをDFAに変換する 初期化：D0=ε-closure({0})={0} Dstates:={D0}, D0はマーク無し a a b a ε ε 5 6 1 2 3 4 a ε b ε

32 while Dstates 中に無マークの状態D0がある do begin D0にマーク付け; for 入力記号aについて do
NFAをDFAに変換する Dstates:{D0}={{0}} while Dstates 中に無マークの状態D0がある do begin D0にマーク付け; for 入力記号aについて do begin U:= ε-closure(goto(D0,a))={1,2,4}; if Uが空集合でなくかつDstates中に無い then UをD1として無マークでDstatesに追加； Dtable[D0,a]:=D1 a b a ε ε a 5 6 1 2 3 4 a ε b ε

33 while Dstates 中に無マークの状態D0がある do begin D0にマーク付け; for 入力記号bについて do
NFAをDFAに変換する Dstates:{D0}={{0}} while Dstates 中に無マークの状態D0がある do begin D0にマーク付け; for 入力記号bについて do begin U:= ε-closure(goto(D0,b))={}; if Uが空集合でなくかつDstates中に無い then ； Dtable[D0,b]:={} a b a ε ε a 5 6 1 2 3 4 a ε b ε

34 while Dstates 中に無マークの状態D1がある do begin D1にマーク付け; for 入力記号aについて do
NFAをDFAに変換する Dstates:{D0,D1}={{0},{1,2,4}} while Dstates 中に無マークの状態D1がある do begin D1にマーク付け; for 入力記号aについて do begin U:= ε-closure(goto(D1,a))={2,3,4,5}; if Uが空集合でなくかつDstates中に無い then UをD2として無マークでDstatesに追加； Dtable[D1,a]:=D2 a b a ε ε a 5 6 1 2 3 4 a ε b ε

35 Dstates:{D0,D1,D2}={{0},{1,2,4},{2,3,4,5}}
NFAをDFAに変換する Dstates:{D0,D1,D2}={{0},{1,2,4},{2,3,4,5}} while Dstates 中に無マークの状態D1がある do begin D1にマーク付け; for 入力記号bについて do begin U:= ε-closure(goto(D1,b))={2,3,4}; if Uが空集合でなくかつDstates中に無い then UをD3として無マークでDstatesに追加； Dtable[D1,b]:=D3 a b a ε ε a 5 6 1 2 3 4 a ε b ε

36 Dstates:{D0,D1,D2,D3}={{0},{1,2,4},{2,3,4,5},{2,3,4}}
NFAをDFAに変換する Dstates:{D0,D1,D2,D3}={{0},{1,2,4},{2,3,4,5},{2,3,4}} while Dstates 中に無マークの状態D2がある do begin D2にマーク付け; for 入力記号aについて do begin U:= ε-closure(goto(D2,a))={2,3,4,5}; if Uが空集合でなくかつDstates中に無い then ； Dtable[D2,a]:=D2 a b a ε ε a 5 6 1 2 3 4 a ε b ε

37 Dstates:{D0,D1,D2,D3}={{0},{1,2,4},{2,3,4,5},{2,3,4}}
NFAをDFAに変換する Dstates:{D0,D1,D2,D3}={{0},{1,2,4},{2,3,4,5},{2,3,4}} while Dstates 中に無マークの状態D2がある do begin D2にマーク付け; for 入力記号bについて do begin U:= ε-closure(goto(D2,b))={2,3,4,6}; if Uが空集合でなくかつDstates中に無い then UをD4として無マークでDstatesに追加； Dtable[D2,b]:=D4 a b a ε ε a 5 6 1 2 3 4 a ε b ε

38 while Dstates 中に無マークの状態D3がある do begin D3にマーク付け; for 入力記号aについて do
NFAをDFAに変換する Dstates:{D0,D1,D2,D3,D4}= {{0},{1,2,4},{2,3,4,5},{2,3,4},{2,3,4,6}} while Dstates 中に無マークの状態D3がある do begin D3にマーク付け; for 入力記号aについて do begin U:= ε-closure(goto(D3,a))={2,3,4,5}; if Uが空集合でなくかつDstates中に無い then ； Dtable[D3,a]:=D2 a b a ε ε a 5 6 1 2 3 4 a b ε ε

39 Dstates:{D0,D1,D2,D3,D4}= {{0},{1,2,4},{2,3,4,5},{2,3,4},{2,3,4,6}}
NFAをDFAに変換する Dstates:{D0,D1,D2,D3,D4}= {{0},{1,2,4},{2,3,4,5},{2,3,4},{2,3,4,6}} Dtable[D3,b]:=D3 Dtable[D4,a]:=D2 Dtable[D4,b]:=D3 a a b a ε ε 5 6 1 2 3 4 a ε b ε

40 Dstates:{D0,D1,D2,D3,D4}= {{0},{1,2,4},{2,3,4,5},{2,3,4},{2,3,4,6}}
NFAをDFAに変換する Dstates:{D0,D1,D2,D3,D4}= {{0},{1,2,4},{2,3,4,5},{2,3,4},{2,3,4,6}} Dtable[D0,a]:=D1 Dtable[D0,b]:= - Dtable[D1,a]:=D2 Dtable[D1,b]:=D3 Dtable[D2,a]:=D2 Dtable[D2,b]:=D4 Dtable[D3,a]:=D2 Dtable[D3,b]:=D3 Dtable[D4,a]:=D2 Dtable[D4,b]:=D3 a 2 b 2,3,4,5 a a a 1,2,4 a 2,3,4,6 1 4 b 2,3,4 b 3 b

41 正規表現を認識するDFAで状態数の最小のものが唯一存在する
NFAをDFAに変換する 正規表現を認識するDFAで状態数の最小のものが唯一存在する a 2 b 2,3,4,5 a a a 1,2,4 a 2,3,4,6 1 4 b 2,3,4 b 3 b a 2 b 2,3,4,5 a a a 1,2,3,4 2,3,4,6 1 3 4 b b

42 正規表現を認識するDFAで状態数の最小のものが唯一存在する
NFAをDFAに変換する 正規表現を認識するDFAで状態数の最小のものが唯一存在する 正規表現a*のNFA a ε ε 1 2 3 ε ε 正規表現a*のDFA 正規表現a*の状態数最小DFA a a a 0,1,2,3 0,1,3 1,2,3

43 正規表現を認識するDFAで状態数の最小のものが唯一存在する
NFAをDFAに変換する 正規表現を認識するDFAで状態数の最小のものが唯一存在する 正規表現(a|b)*のNFA a ε ε 1 2 3 b ε ε 正規表現(a|b)*の状態数最小 DFA 正規表現(a|b)*のDFA a a a 0,1,2,3 0,1,3 1,2,3 b b b

44 課題1 アルファベットΣ={a,b}上で... 問題1 次の正規表現を受理するNFAを作成せよ． また各NFAでababbabを受理する過程を示せ． 1-1. (a|b)*a(a|b) 1-2. (a*|b*)* 問題 2 課題1のNFAに対応するDFAを作成せよ． また各DFAでababbabを受理する過程を示せ． 提出方法：A4レポート用紙 提出期限：6月22日(水)授業開始時

45 本スライドの著作権について 本スライドは，電気通信大学大学院情報システム学研究科で，平成17年度前期に開講される｢計算機システム基礎(本多担当分)」の講義資料ならびに本講義受講生の講義復習用資料として本多弘樹によって制作されたもので，その著作権は本多弘樹に属します． 本講義の受講生が，本講義の復習に際し，本スライド閲覧するために本スライドをコピーすることを許可します． 上記以外の目的のために，本スライドを閲覧・コピー・改変・配布することを禁じます．