【正文】 詞法分析程序的自動構造工具也廣泛應用于許多方面，如用以生成一個程序，可識別印刷電路板中的缺陷，又如開關線路設計和文本編輯的自動生成等。 典型例題及解答 1（ 0｜ 1） *101相應的 DFA 83 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 DFA最小化 84 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 scanner的 LEX的源文件，請給 出 scanner對輸入串 ababcbacaabaababaa的輸出結果： %% a+b*a {printf( `1%s\n`,yytext)。 ? cc += yyleng。 return Semicolon。} ? = { cc++。 return Period。 return GT。 ? int cc=0。在消結過程中，逐步用正規(guī)式來標記弧 61 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?其消結的規(guī)則如下： ?最后 x和 y結點間的弧上的標記則為所求的正規(guī)式 r 62 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 以例 NFA M為例， M的狀態(tài)圖在圖 ，求 正規(guī)式 r,使 L(r)=L(M) 63 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 64 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?對于 ∑ 上的一個正規(guī)式 R，可以構造一個 ∑ 上的 NFA M，似的 L(M)=L(R) ?語法制導方法：按正規(guī)式的語法結構指引構造過程，首先 將正規(guī)式分解成一系列子表達式，然后使用下面規(guī)則為 r 構造 NFA，對 r的各種語法結構的構造規(guī)則具體描述如下： 1. ① 對于正規(guī)式 216。令 T2=?closure(move(T0,b)) ={1,2,4,5,6,7}，將 T2加入 C中， T2未被標記 T1： ?closure(move(T1,a))={1,2,3,4,6,7,8}，即 T1， T1已 在 C中?！??”、“ ? ”和 “ ?” 都是左結合的 18 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 令 ?={a， b}, ?上的正規(guī)式和相應的正規(guī)集的例子有： –正規(guī)式 正規(guī)集 –a {a} –a?b {a,b} –ab {ab} –(a?b)(a?b) {aa,ab,ba,bb} –a ? {? ,a,a, …… 任意個 a的串 } –(a?b)? {? ,a,b,aa,ab …… 所有由 a和 b組成 的串 } –(a?b)?(aa?bb)(a?b)? {??上所有含有兩個相繼的 a或兩個 相繼的 b組成的串 } 19 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ?={d， ?， e， +， },則 ?上的正規(guī)式 d?(?dd ?? ? )(e(+? ??)dd? ??) 其中 d為 0~9的數(shù)字 表示的是： 無符號數(shù)的集合 20 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?若兩個正規(guī)式 e1和 e2所表示的正規(guī)集相同 ,則說 e1和 e2等價 ,寫 作 e1=e2 ?例如： e1= (a?b)， e2 = b?a ?又如： e1= b(ab)? , e2 =(ba)?b e1= (a?b)? , e2 =(a??b?)? 21 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有： ?r?s=s?r “或”服從交換律 ?r?(s?t)=(r?s)?t “或”的可結合律 ?(rs)t=r(st) “連接”的可結合律 ?r(s?t)=rs?rt (s?t)r=sr?tr 分配律 ??r=r r?=r ?是“連接”的恒等元素（零一律） ?r?r=r r?=??r?rr?… “或”的抽取律 22 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 三 .正規(guī)文法和正規(guī)式的等價性 ?上的一個正規(guī)式 r轉(zhuǎn)換成文法 G=(VN,VT,P,S)： 令 VT＝ ∑，確定產(chǎn)生式和 VN的元素用如下辦法 ： 23 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?選擇一個非終結符 S生成產(chǎn)生式 S r，并將 S定為 G的 識別符號。 詞法分析程序的設計 源程序 詞法分析程序 語法分析程序 Token get token …. ?主要任務：讀源程序，產(chǎn)生單詞符號 ?其他任務： ?濾掉空格，跳過注釋、換行符 ?追蹤換行標志，復制出錯源程序， ?宏展開， …… 5 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 一 .詞法分析程序不語法分析程序的接口方式 ?詞法分析工作可以是獨立的一遍，把字符流的源程序 變?yōu)?單詞序列 ，輸出在一個 中間文件 上，這個文件作 為語法分析程序的 輸入 而繼續(xù)編譯過程 6 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?更通常情況，常將詞法分析程序設計成一個 子程序 ， 每當語法分析程序需要一個單詞時，則調(diào)用該子程序。|(|)| …… 其中 l表示 a~z中的任何一個英文字母， d表示 0~9中 的任何一個數(shù)字 13 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ： ?無符號數(shù) d余留無符號數(shù) |.十進小數(shù) e指數(shù)部分 ?余留無符號數(shù) d余留無符號數(shù) |.十進小數(shù) e指數(shù) 部分 | ? ?十進小數(shù) d余留十進小數(shù) ?余留十進小數(shù) e指數(shù)部分 | d余留十進小數(shù) |? ?指數(shù)部分 d余留整指數(shù) |s整指數(shù) ?整指數(shù) d余留整指數(shù) ?余留整指數(shù) d余留整指數(shù) |? 其中， s表示正或負號 (+,) 14 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 二 .正規(guī)式 ?正規(guī)表達式（ regular expression）是說明單詞的 pattern的一種重要的表示法（記號），是定義正規(guī)集 的工具 15 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?定義（正規(guī)式和它所表示的正規(guī)集）： ?設字母表為 ?，輔助字母表 ?`={?， ?， ?， ?， ?， ?， ?} ??和 ?都是 ?上的正規(guī)式，它們所表示的正規(guī)集分別為 {?}和 { } ?任何 a? ?， a是 ?上的一個正規(guī)式，它所表示的正規(guī)集 為 {a} 16 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?假定 e1和 e2都是 ?上的正規(guī)式，它們所表示的正規(guī)集分別 為 L(e1)和 L(e2)，那么， (e1), e1? e2, e1?e2, e1?也都是正規(guī) 式 ,它們所表示的正規(guī)集分別為 L(e1), L(e1)?L(e2), L(e1)L(e2)和 (L(e1))? ?僅由有限詞使用上述三步驟而定義的表達式才是 ?上的 正規(guī)式，僅由這些正規(guī)式所表示的字