【正文】 / ? s=install(yytext,VARIABLE,level,0)。 ? =n。} ? {NUMBER} { ? intn。return ASGN。cc++。} ? = { cc++。} ? ( { cc++。} ? , { cc++。} ? = { cc++。 } /*copy a line of input file*/ ? { cc++。 ? %) ? %% ? { cc++。 正規(guī)文法和有窮自動機的等價性 ?采用下面的規(guī)則可以從正規(guī)文法 G直接構(gòu)造一個有窮 自動機 NFA M；使得 L（ M）＝ L（ G）： ?M的字母表與 G的終結(jié)符集相同 ?為 G中的每個非終結(jié)符生成 M的一個狀態(tài)， G的開始符 S 是開始狀態(tài) S 72 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?增加一個新狀態(tài) Z，作為 NFA的終態(tài) ?對 G中的形如 A tB的規(guī)則（其中 t為終結(jié)符或 ?， A和 B為 非終結(jié)符的產(chǎn)生式），構(gòu)造 M的一個轉(zhuǎn)換函數(shù) f(A,t)=B ?對 G中形如 A t的產(chǎn)生式，構(gòu)造 M的一個轉(zhuǎn)換函數(shù) f(A,t)=Z 73 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?例 ：與文法 G［ S］等價的 NFA M如圖 ?G[S]: ?S a A ?S bB ?S ε ?A aB ? A bA ?B aS ?B bA ?B ε 74 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?有窮自動機轉(zhuǎn)換成等價的正規(guī)文法： ?對轉(zhuǎn)換函數(shù) f(A,t)=B,可寫一產(chǎn)生式： A tB ?對可接受狀態(tài) Z，增加一產(chǎn)生式： Z ε ?有窮自動機的初態(tài)對應(yīng)文法開始符 ?有窮自動機的字母表為文法的終結(jié)符集 75 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?例 ： 給出不圖 NFA等價的正規(guī)文法 G ?G＝（｛ A， B， C， D｝，｛ a， b}， P， A），其中 P為： ?A a B ?C ε ?A bD ?D aB ?B bC ?D bD ?C aA ?D ε ?C bD 76 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 167。所構(gòu)造的 NFA為： 65 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 66 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 67 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 68 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?例 為 r=(a|b)*abb構(gòu)造 NFA N,使得 L(N)=L(r) ?從左到右分解 r,令 r1=a,第 1個 a,則有 令 r2=b,則有 令 r3=r1|r2,則有 令 r4=r339。 正規(guī)式和有窮自動機的等價性 ?對于 ∑ 上的一個 NFA M，可以構(gòu)造一個 ∑ 上的正規(guī)式 R,使得 L(R)=L(M) ?第一步，在 M的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個結(jié)，一個為 x結(jié) 點，一個為 y結(jié)點。 T3=?closure(move(T1,b))={1,2,4,5,6,7,9}，將 T3加 入 C中， T3未被標(biāo)記 49 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 T2： ?closure(move(T2,a))={1,2,3,4,6,7,8}，即 T1， T1已 在 C中。用 [S1 S2... Sj]表示 S 的元素，其中 S1, S2,... Sj是 K的狀態(tài)。若 x和 y都是正規(guī)式 ， B?VN ，則： (R1) 對形如 A xy的 正規(guī)產(chǎn)生式 ，重寫為 ： A xB， B y (R2)對形如 A x*y的 正規(guī)產(chǎn)生式 ，重寫為： A xB， A y， B xB， B y (R3)對形如 A x?y的 正規(guī)產(chǎn)生式 ，重寫為 : A x， A y 不斷應(yīng)用 R做變換，直到每個產(chǎn)生式右端只含一個 VN 24 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 例 將 r=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法 令 S是文法的開始符號，形成 S a(a|d)*： R1 S aA A (a|d)* R2 S aA A (a|d)B A ? B (a|d)B B ? R3 S aA A ? A aB A dB B aB B dB B ? 25 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ： 基本上是上述過程的逆過程，最后只剩下一個開始符 號定義的正規(guī)式，其轉(zhuǎn)換規(guī)則如表 ： 26 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?例 G[s]: S aA S a A aA A dA A a A d ① S aA|a A aA|a|dA|d (a|d)A|(a|d) (a|d)*(a|d) ② s=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)=a((a|d)*|ε) ③ r=a(a|d)* 27 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 167。|(|)| …… 其中 l表示 a~z中的任何一個英文字母， d表示 0~9中 的任何一個數(shù)字 13 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?例 ： ?無符號數(shù) d余留無符號數(shù) |.十進(jìn)小數(shù) e指數(shù)部分 ?余留無符號數(shù) d余留無符號數(shù) |.十進(jìn)小數(shù) e指數(shù) 部分 | ? ?十進(jìn)小數(shù) d余留十進(jìn)小數(shù) ?余留十進(jìn)小數(shù) e指數(shù)部分 | d余留十進(jìn)小數(shù) |? ?指數(shù)部分 d余留整指數(shù) |s整指數(shù) ?整指數(shù) d余留整指數(shù) ?余留整指數(shù) d余留整指數(shù) |? 其中， s表示正或負(fù)號 (+,) 14 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 二 .正規(guī)式 ?正規(guī)表達(dá)式（ regular expression）是說明單詞的 pattern的一種重要的表示法（記號），是定義正規(guī)集 的工具 15 盛威網(wǎng)：專業(yè)的計算機學(xué)習(xí)網(wǎng)站 ?定義（正規(guī)式和它所表示的正規(guī)集）： ?設(shè)字母表為 ?，輔助字母表 ?`={?， ?， ?， ?， ?， ?， ?} ??和 ?