從正規(guī)式到詞法分析-資料下載頁
2025-08-15 20:25本頁面
【正文】 則。 17 2 直接編碼的詞法分析器（續(xù) 1） 1032aabbbbaa2. 識別 (a|b)*abb的程序框架 main(){ char buf[]=abba, *ptr=buf。 while (*ptr!=39。39。 ) { l0: while (*ptr==39。b39。) ptr++。 // state 0 l1: while (*ptr==39。a39。) ptr++。 // state 1 switch (*ptr) { case 39。a39。: goto l1。 case 39。b39。: ptr++。 switch (*ptr) // state 2 { case 39。a39。: goto l1。 case 39。b39。: ptr++。 switch (*ptr) // state3 { case 39。a39。: goto l1。 case 39。b39。: goto l0。 case 39。39。: coutyesendl。 return。 default: break。 } default: break。 } default: break。 } break。 // 遇到非法字符 } cout no endl。 } 18 3 兩類分析器的比較 表驅(qū)動 直接編碼 分析器的速度 慢 快 程序與模式的關(guān)系 無關(guān) 有關(guān) 分析器的規(guī)模 較大 較小 適合的編寫方法 工具生成 手工編寫 詞法分析器生成器簡介（上機課中再介紹） 1 構(gòu)造詞法分析器的全過程均有算法： 正規(guī)式 － NFA－ DFA－ 最小化 DFA－ 詞法分析器 （ 分析表 ） 2 LEX的基本結(jié)構(gòu) 根據(jù)正規(guī)式構(gòu)造的分析表＋驅(qū)動器框架 （ 不變的 ） 3 利用 LEX構(gòu)造詞法分析器的關(guān)鍵 ① 用 LEX提供的正規(guī)式集合設(shè)計記號的模式； ② 用 LEX提供的語義支持識別記號或指出輸入中的錯誤 。 19 本章小結(jié)（略） 詞法分析的兩個重要環(huán)節(jié)： 規(guī)定所有合法輸入＋識別合法輸入 重要內(nèi)容： 1 記號 、 模式與單詞 2 記號的說明：模式的形式化描述－正規(guī)式 3 記號的識別：有限自動機 NFA：與正規(guī)式有對應(yīng)關(guān)系 ， 易于構(gòu)造 ， 狀態(tài)數(shù)少； DFA：確定性便于記號的識別 ， 不易構(gòu)造 ， 狀態(tài)數(shù)可能會多； 記號識別的方法： a. 模擬 DFA： b. 模擬 NFA（ 特殊情況下 ） ：需要動態(tài)計算狀態(tài)子集 。 4 從正規(guī)式到詞法分析器 （ 等價變換的過程 ） 正規(guī)式描述模式 由正規(guī)式構(gòu)造 NFA NFA的確定化 （ 子集法： smove， ε 閉包 ） DFA的最小化 （ 可區(qū)分概念 ） 詞法分析器：表驅(qū)動 （ 自動生成 ） 與直接編碼 （ 手工編寫 ） 20 第二章 結(jié)束 21 算法 求 ε 閉包 輸入 狀態(tài)集 T。 輸出 狀態(tài)集 T的 ε 閉包 方法 用下邊的函數(shù)計算 ε 閉包 function ε閉包 (T) is begin for T中每個狀態(tài) t loop 加入 t到 U。 push(t)。 end loop。 while 棧不空 loop pop(t)。 for 每個 u=move(t, ε) loop if u不在 U中 then 加入 u到 U。 push(u)。 end if。 end loop。 end loop。 return U。 endε閉包 。 用算法計算 ε 閉包 ({s2})： U stack 1. {s2} s2 2. {s2, s4} s4 3. {s2, s4, s5} s5 4. {s2, s4, s5} 問題： 試將函數(shù)直接寫為遞歸的 返回 兩個數(shù)據(jù)結(jié)構(gòu)： 閉包 U和模擬遞歸的 stack s1s2as3as4 s5ε ε
高考資料相關(guān)推薦
鄂ICP備17016276號-1