【文章內(nèi)容簡介】 relop pointer to table entry pointer to table entry LT LE EQ NE GT GE 狀態(tài)轉(zhuǎn)換圖 ?transition diagram，識別單詞 start other = 0 6 7 8 狀態(tài) 動作：在前一狀態(tài)時，讀入標(biāo)記符號將轉(zhuǎn)入指向的狀態(tài) 初態(tài)：識別的開始 終態(tài)：識別出單詞 所有其他符號（如此例表示除=外所有符號） 確定的：一個狀態(tài)發(fā)出的不同的邊不可能標(biāo)記相同的符號 如何識別單詞？ ?詞法分析器（算法） ?已讀入符號串（前綴） +未讀入符號串 —— 與模式進(jìn)行匹配 ?狀態(tài)轉(zhuǎn)換圖 ——一種詞法分析算法描述 ? TD??模式 ?已讀入符號串 ??狀態(tài) ?邊 ??下一符號、應(yīng)采取的動作 狀態(tài)轉(zhuǎn)換圖 狀態(tài) ??符號串集合 如何識別單詞？（續(xù)） ?TD工作方式 ?開始識別，初態(tài) ?讀入符號，轉(zhuǎn)換狀態(tài) ?終態(tài)，接受?。粺o法轉(zhuǎn)換，失敗！ 例 start other = 0 6 7 8 * return(G) return(GE) = : 已經(jīng)接受“ ”，且已經(jīng)多讀取一個其他符號，需退回這個符號 例 ：所有關(guān)系運算符 start 0 other = 6 7 8 return(relop, LE) 5 4 = 1 2 3 other = * * return(relop, NE) return(relop, LT) return(relop, EQ) return(relop, GE) return(relop, GT) 例 、 ：標(biāo)識符與分隔符 id : delim : start delim 28 other 30 29 delim * return( get_token(), install_id()) start letter 9 other 11 10 letter or digit * Either returns ptr or “0” if reserved 例 ：無符號數(shù) 19 12 14 13 16 15 18 17 start other digit . digit E + | digit digit digit digit E digit * start digit 25 other 27 26 digit * start digit 20 . 21 digit 24 other 23 digit digit 22 * return(num, install_num()) num ? digit+ (.digit+)? (E(+|)? digit+)? 12 關(guān)鍵字的處理 ?關(guān)鍵字 /保留字與標(biāo)識符一樣進(jìn)行匹配 ?保存在符號表或一個特殊的關(guān)鍵字表中，保存關(guān)鍵字的符號串和單詞值（一般不需要） ?當(dāng)識別出標(biāo)識符 /關(guān)鍵字，查詢表 ?若與某個關(guān)鍵字匹配，返回對應(yīng)的單詞，和單詞值（若有的話） ?若與任何關(guān)鍵字都不匹配，則認(rèn)為是標(biāo)識符，進(jìn)行相應(yīng)處理 狀態(tài)轉(zhuǎn)換圖的實現(xiàn) ? 為每個狀態(tài)構(gòu)造一段代碼 ? 普通狀態(tài) ?讀取字符 ?每條出射邊的處理：根據(jù)字符轉(zhuǎn)換狀態(tài) ?其他情況，錯誤 ? 終態(tài) ?返回單詞，單詞值 ? 錯誤處理 ? 嘗試其他狀態(tài)轉(zhuǎn)換圖 ? 嘗試完畢，與任何單詞都不匹配，詞法錯誤，錯誤恢復(fù) 實現(xiàn)代碼 state = 0。 token nexttoken() { while(1) { switch (state) { case 0: c = nextchar()。 ?如何工作 ? ?如何擴(kuò)展 ? 狀態(tài) 實現(xiàn)代碼 /* c is lookahead character */ if (c== blank || c==tab || c== newline) { state = 0。 lexeme_beginning++。 /* advance beginning of lexeme */ } 作用 ? 實現(xiàn)代碼（續(xù)） else if (c == ??) state = 1。 else if (c == ?=?) state = 5。 else if (c == ??) state = 6。 else state = fail()。 break。 … /* cases 18 here */ 不是比較運算符，怎么辦？ 實現(xiàn)代碼（續(xù)） int state = 0, start = 0。 int lexical_value。 /* “返回” 詞法值 */ int fail() { forward = lexeme beginning。 switch (start) { case 0: start = 9。 break。 case 9: start = 12。 break。 case 12: start = 20。 break。 case 20: start = 25。 break。 case 25: recover()。 break。 default: /* piler error */ } return start。 } 不是比較運算符，是不是標(biāo)識符呢？ 也不是標(biāo)識符，是不是數(shù)值常量呢？ 什么都不是，那就是詞法錯誤了。 實現(xiàn)代碼（續(xù)） case 9: c = nextchar()。 if (isletter(c)) state = 10。 else state = fail()。 break。 實現(xiàn)代碼（續(xù)） case 10: c = nextchar()。 if (isletter(c)) state = 10。 else if (isdigit(c)) state = 10。 else state = 11。 break: 實現(xiàn)代碼（續(xù)） case 11。 retract(1)。 install_id()。 return ( gettoken() )。 … /* cases 1224 here */ case 25: c = nextchar()。 if (isdigit(c)) state = 26。 else state = fail()。 break。 實現(xiàn)代碼（續(xù)） case 26: c = nextchar()。 if (isdigit(c)) state = 26。 else state = 27。 break。 case 27: retract(1)。 install_num()。 return ( NUM )。 } } } 有限自動機(jī) ? 正規(guī)式 ————?識別程序（ recognizer） ? 有限自動機(jī)（ finite automata） ? 非確定有限自動機(jī) NonDeterministic Finite Automata (NFAs) 一個狀態(tài)對同一個輸入符號，有多個可能的動作 ? 確定有限自動機(jī) Deterministic Finite Automata (DFAs) 一個狀態(tài)對一個輸入符號，至多有一個動作 如何轉(zhuǎn)換？ NFA和 DFA ? 都可識別正規(guī)式，時－空折衷 ? NFA ? 正規(guī)式 ——?NFA ? “不精確 ” ，占用內(nèi)存少，速度慢 ? DFA ? 正規(guī)式 ——?DFA ? “精確 ” ，占用內(nèi)存大，速度快 ? NFA?DFA， DFA?NFA 簡單 復(fù)雜 非確定有限自動機(jī) ? 數(shù)學(xué)模型，表示為五元組 M = { S, Σ,δ, s0, F }，其中 1. S：有限狀態(tài)集 2. Σ：有窮字母表，其元素為輸入符號 3. δ： S Σ到 S的子集的映射，即 δ: S (Σ?{e}) ?2S，狀態(tài)轉(zhuǎn)換函數(shù) 。 4. s0∈ S是唯一的初態(tài) 5. 是一個終態(tài)集（可空） SF ?表示方式 ? 五元組 ? δ用函數(shù)形式表示， δ(s, a) = S’意味著，若當(dāng)前狀態(tài)為 s，輸入符號為 a時，下一個狀態(tài)可以是集合 S’中任意一個 ? 狀態(tài)轉(zhuǎn)換圖 ? 狀態(tài)（圓圈）、邊、終態(tài) … ? 狀態(tài)轉(zhuǎn)換矩陣 ? 行 —狀態(tài)，列 —符號，表項 —轉(zhuǎn)換狀態(tài)集 ? 適合計算機(jī)實現(xiàn) 例： (a|b)*abb S = { 0, 1, 2, 3 } s0 = 0 F = { 3 } ? = { a, b } d(0,a) = { 0, 1 } d(0,b) = { 0 } d(1,b) = { 2 } d(2,b) = { 3 } start 0 3 b 2 1 b a a b 允許 e (null)邊 j i e 轉(zhuǎn)換狀態(tài)，但不讀入符號 例： (a|b)*abb（續(xù)） 狀態(tài)轉(zhuǎn)換矩陣 state i n p u t 0 1 2 a b { 0, 1} { 2 } { 3 } { 0 } NFA如何工作？ ?NFA接受 （ accept） 符號串 x ??存在 一條從初態(tài)到終態(tài)的路徑，路徑上的符號組成 x ?NFA M定義的語言 ： M接受的符號串集合 ，記為 L(M) 狀態(tài) ??符號串集合 終態(tài) ??L(M) NFA如何工作（續(xù)） start 0 3 b 2 1 b a a b ? 對給定符號串，跟蹤狀態(tài)轉(zhuǎn)換 ? 若符號讀取完，且處于終態(tài)，接受 EXAMPLE: Input: ababb move(0, a) = 1 move(1, b) = 2 move(2, a) = ? (undefined) REJECT ! move(0, a) = 0 move(0, b) = 0 move(0, a) = 1 move(1, b) = 2 move(2, b) = 3 ACCEPT ! OR NFA如何工作（續(xù)） ?不是所有路徑都表示接受 ?aabb ?路徑 0 ? 0 ? 1 ? 2 ? 3表示接受 ?而 0 ? 0 ? 0 ? 0 ? 0表示不接受 start 0 3 b 2 1 b a a b 處理未定義狀態(tài)轉(zhuǎn)換 ? 定義一個額外的“ 死狀態(tài) ” ? 所有未定義的狀態(tài)轉(zhuǎn)換都指向它 ? 它自身的狀態(tài)轉(zhuǎn)換都指向自身 start 0 3 b 2 1 b a a b 4 a, b a a ? NFA與正規(guī)式 /編譯器的關(guān)系 ?單詞 ??模式 ??正規(guī)式 ??NFA???詞法分析程序 ?單詞是詞法分析的基本構(gòu)件 ?詞法分析器可用一組 NFA來描述，每個NFA表示一個單詞 NFA例 2 ?(a (b*c)) | (a (b | c+)?) 0 4 2 1 3 5 start c b e c b c e a ?可接受 abbc 例 2的另一解法 3 2 b c a 1 6 5 7 c a c 4 b a (b*c) a (b | c+)? 例 2另一解法（續(xù)） 3 2 b c a 1 6 5 7 c a c 4 b 0 e e 兩個狀態(tài)轉(zhuǎn)換圖，進(jìn)行“并”操作 確定有限自動機(jī) ? 五元組定義 M = { S, Σ, d, s0, F }，其中 1. S：有限狀態(tài)集 2. Σ：有窮字母表 3. δ： S Σ到 S的單值映射，即 δ: S Σ? S 4. s0∈ S是唯一的初態(tài) 5. 是一個終態(tài)集（可空） SF ?沒有 e 值域為 S，不是 S的子集的集合 算法 模擬 DFA