第二章詞法分析-文庫吧資料
2025-07-26 19:51本頁面
【正文】 示簡潔 d1 ? r1 d2 ? r2 . . . dn ? rn – 各個(gè) di的名字都不同 – 每個(gè) ri都是 ? ?{d1, d2, … , di1 }上的正規(guī)式 詞法記號的描述與識別 ? 正規(guī)定義的例子 – C語言的標(biāo)識符是字母、數(shù)字和下劃線組成的串 letter_ ? A | B | … | Z | a | b | … | z | _ digit ? 0 | 1 | … | 9 id ? letter_(letter_ |digit)* 詞法記號的描述與識別 ? 正規(guī)定義的例子 ? 無符號數(shù)集合，例 1946,63E8,?6 digit ? 0 | 1 | … | 9 digits ? digit digit* optional_fraction ? .digits|? optional_exponent ? ( E ( + | ? | ? ) digits ) | ? number?digits optional_fraction optional_exponent ? 簡化表示 number ? digit+ (.digit+)? (E(+|?)? digit+)? 詞法記號的描述與識別 ? 正規(guī)定義的例子（進(jìn)行下一步討論的例子） while ? while do ? do relop ? | = | = | | | = letter ? A | B | … | Z | a | b | … | z id ? letter (letter | digit )* number ? digit+ (.digit+)? (E (+ | ?)? digit+)? delim ? blank | tab | newline ws ? delim+ 詞法記號的描述與識別 轉(zhuǎn)換圖 ? 關(guān)系算符的轉(zhuǎn)換圖 0 5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 開始 = = = * * other other 詞法記號的描述與識別 ? 標(biāo)識符和關(guān)鍵字的轉(zhuǎn)換圖 9 10 11 開始 letter other * letter或 digit return(installId( )) 詞法記號的描述與識別 ? 無符號數(shù)的轉(zhuǎn)換圖 number ? digit+ (.digit+)? (E (+ | ?)? digit+)? 開始 19 12 13 14 15 16 17 18 digit digit digit digit digit digit other . E +/? E digit other other return( installNum( ) ) * 詞法記號的描述與識別 ? 空白 的轉(zhuǎn)換圖 delim ? blank | tab | newline ws ? delim+ 21 22 開始 delim other * delim 20 有 限 自 動 機(jī) 不確定的有限自動機(jī) （ 簡稱 NFA） 一個(gè)數(shù)學(xué)模型 ， 它包括： 有限的狀態(tài)集合 S 輸入符號集合 ? 轉(zhuǎn)換函數(shù) move : S ? ( ??{?} ) ? P(S) 狀態(tài) s0是唯一的開始狀態(tài) F ? S是接受狀態(tài)集合 識別語言 (a|b)*ab 的 NFA 1 2 開始 a 0 a b b 輸 入 符 號 a b 0 {0, 1} {0} 1 ? {2} 2 ? ? 狀 態(tài) ? NFA的轉(zhuǎn)換表 有 限 自 動 機(jī) 識別語言 (a|b)*ab 的 NFA 1 2 開始 a 0 a b b 有 限 自 動 機(jī) ? 例 識別 aa*|bb*的 NFA 1 2 開始 a 0 a b b 3 4 ? ? 確定的有限自動機(jī)（簡稱 DFA) 一個(gè)數(shù)學(xué)模型，包括： 有限的狀態(tài)集合 S 輸入字母集合 ? 轉(zhuǎn)換函數(shù) move : S ? ? ? S， 且可以是部分函數(shù) 唯一的開始狀態(tài) s0 接受狀態(tài) 集合 F ? S 1 2 開始 a 0 a b b a b 識別語言 (a|b)*ab 的 DFA 有 限 自 動 機(jī) 有 限 自 動 機(jī) ? 例 DFA，識別 {0,1}上能被 5整除的二進(jìn)制數(shù) 已讀過 尚未讀 已讀部分的值 某時(shí)刻 101 0111000 5 讀進(jìn) 0 1010 111000 5 ? 2 = 10 讀進(jìn) 1 10101 11000 10 ? 2 + 1= 21 5個(gè)狀態(tài)即可，分別代表已讀部分的值除以 5的余數(shù) ? 例 DFA，識別 {0,1}上能被 5整除的二進(jìn)制數(shù) 0 1 2 3 開始 4 1 0 0 1 0 1 0 1 0 1 有 限 自 動 機(jī) 10102 = 1010 1112 = 710 ? 例 DFA,接受 0和 1的個(gè)數(shù)都是偶數(shù)的字符串 0 0 0 0 3 2 1 1 奇 0奇 1 奇 0偶 1 1 0 1 1 開始 偶 0偶 1 偶 0奇 1 有 限 自 動 機(jī) NFA到 DFA的變換 子集構(gòu)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1