編譯原理第四章

1、1詞法分析程序的設(shè)計(jì)原則 單詞的描述技術(shù)單詞的識(shí)別機(jī)制詞法分析程序的自動(dòng)構(gòu)造原理第4章 詞法分析及其自動(dòng)構(gòu)造2回顧回顧 什麼是詞法分析程序4實(shí)現(xiàn)詞法分析（lexical analysis）的程序 逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。 是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。 詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行 ?？梢院驼Z(yǔ)法分析結(jié)合在一起作為一遍。3 詞法分析程序和語(yǔ)法分析程序的關(guān)系源程序詞法分析程序語(yǔ)法分析程序Tokenget token.源程序詞法分析程序語(yǔ)法分析程序4 詞法分析程序的主要任務(wù)主要任務(wù)： 讀源程序，產(chǎn)生單詞符號(hào)

2、詞法分析程序的其他任務(wù)其他任務(wù)： 濾掉空格，跳過(guò)注釋、換行符 追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序， 宏展開(kāi)，5詞法分析程序的輸出 4詞法分析程序所輸出的單詞符號(hào)常常采用以下二元式表示：4 (單詞種別，單詞自身的值)。 4(標(biāo)識(shí)符，指向該標(biāo)識(shí)符所在符號(hào)表中位置的指針)語(yǔ)法分析需要的信息 編譯其它階段需要的信息 6 詞法分析工作從語(yǔ)法分析工作獨(dú)立出來(lái)的原因： 簡(jiǎn)化設(shè)計(jì) 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性 7單詞的描述工具-正規(guī)表達(dá)式正規(guī)表達(dá)式 回顧正規(guī)文法正規(guī)文法描述的是VT上的正規(guī)集，即是正規(guī)語(yǔ)言4 標(biāo)識(shí)符l|l字母數(shù)字字母數(shù)字l|d|l字母數(shù)字|d字母數(shù)字無(wú)符號(hào)整數(shù)d|d無(wú)符號(hào)整數(shù)運(yùn)算符+|-|*

3、|/|=|等號(hào)|等號(hào)等號(hào)=界符，|；|(|)| 8正規(guī)式 正規(guī)式也稱正則表達(dá)式,是定義正規(guī)集的數(shù)學(xué)工具。 正規(guī)表達(dá)式（regular expression）是說(shuō)明單詞的模式(pattern)的一種重要的表示法（記號(hào)），我們用以描述單詞符號(hào)。94設(shè)字母表為，輔助字母表=，|，*，(，) 。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ； 任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a； 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1), e1|e2, e1e2, e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(e1), L(e1)L(e2), L(

4、e1)L(e2)和(L(e1)*。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。 10令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子 a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab) a a,b ab aa,ab,ba,bb ,a,aa, 任意個(gè)a的串 ,a,b,aa,ab,bb 所有由 a和b組成的串 上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串11討論例1 令=l，d，則上的正規(guī)式 r=l(l d) 定義的正規(guī)集為: l,ll,ld,ldd,其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式 即是 字母(字母|數(shù)字) ,它表示的

5、正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”, 多數(shù)程序設(shè)計(jì)語(yǔ)言允許的的標(biāo)識(shí)符的詞法規(guī)則.例2=d，e，+，-,則上的正規(guī)式 d(dd )(e(+- )dd )表示的是無(wú)符號(hào)數(shù)的集合。其中d為09的數(shù)字。 程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式 來(lái)定義來(lái)定義. .12正規(guī)文法與正規(guī)式4r-G變換 對(duì)任何正規(guī)式r，選擇一個(gè)非終結(jié)符S生成產(chǎn)生式Sr叫做正規(guī)產(chǎn)生式，并將S定為G的識(shí)別符號(hào)。若x和y都是正規(guī)式，對(duì)形如Axy的正規(guī)產(chǎn)生式，重寫(xiě)成：AxB，By兩個(gè)正規(guī)產(chǎn)生式，其中B是新選擇的非終結(jié)符對(duì)已形成的形如Ax*y的正規(guī)產(chǎn)生式，重寫(xiě)為：AxBAyBxBBy B為一新非終結(jié)

6、符。對(duì)形如Ax|y的正規(guī)產(chǎn)生式，重寫(xiě)為：Ax，Ay不斷利用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式都符合三型文法的要求。 134將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法：4令S是文法的開(kāi)始符號(hào)Sa(a|d)*，4 SaA A(a|d)*， 重寫(xiě)第二條 4SaAA(a|d)B，AB(a|d)B和B進(jìn)而變換為SaABaBAaBBdBAdBBA即為所求。144文法GSSaASaAaAAdA4 AaAd4S=aA|aA=(aA|dA)|(a|d)再將A的正規(guī)式變換A=(a|d)A|(a|d)， 4 A=(a|d)*(a|d)，4 A 右端代入S的正規(guī)式：S=a(a|d)*(a|d)|a再利用正規(guī)式的代數(shù)變換可依

7、次得到S=a(a|d)*(a|d)|)S=a(a|d)*即a(a|d)*為所求。 15有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)將討論如下內(nèi)容：確定的有窮自動(dòng)機(jī)DFA不確定的有窮自動(dòng)機(jī)NFANFA的確定化DFA的最小化16有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)式所表示的集合.應(yīng)用有窮自動(dòng)機(jī)這個(gè)理論，為詞法分析程序的自動(dòng)構(gòu)造尋找有效的方法和工具。 有窮自動(dòng)機(jī)分為兩類(lèi)：確定的有窮自動(dòng)機(jī)(Deterministic Finite Automata)和不確定的有 窮自動(dòng)機(jī)(Nondeterministic Finite Automata) 。17確定的有窮自動(dòng)機(jī)

8、DFADFA定義：一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，f，S，Z）其中1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)表；18DFA定義3.f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如 f（ki，a）=kj，（kiK， kj K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj ，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4.SK是唯一的一個(gè)初態(tài)；5.Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。19一個(gè)DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=Uf（

9、V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q20 DFA 的狀態(tài)圖表示4f(ki,a)=kj表示為從ki到kj的標(biāo)記為a的弧線bSUVQaaaba，bb21DFA 的矩陣表示的矩陣表示abSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)0001224DFA的表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個(gè)單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)kK，和輸入符號(hào)a，f(k,a)唯一地確定了下一個(gè)狀態(tài)。4從狀態(tài)轉(zhuǎn)換圖來(lái)看，若字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。 4對(duì)于對(duì)于*中的任何符號(hào)串中的任何符號(hào)串t，如果存

10、在一條，如果存在一條從初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的道路，從初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的道路，而且這條路上的所有弧的標(biāo)記符連接成而且這條路上的所有弧的標(biāo)記符連接成的符號(hào)串等于的符號(hào)串等于t，稱，稱t可以為可以為DFA M所接所接受。受。4若若M的初態(tài)結(jié)點(diǎn)同時(shí)也是終態(tài)結(jié)點(diǎn)，則的初態(tài)結(jié)點(diǎn)同時(shí)也是終態(tài)結(jié)點(diǎn)，則空字可被空字可被M所識(shí)別（接受）所識(shí)別（接受）23244*上的符號(hào)串上的符號(hào)串t被被M接受接受- 若t*，f(S，t)=P，其中S為 M的開(kāi)始狀態(tài)，PZ，Z為終態(tài)集。- 則稱t為DFA M所接受（識(shí)別）4*上的符號(hào)串上的符號(hào)串t在在M上上運(yùn)行運(yùn)行一個(gè)輸入符號(hào)串t，表示成t1t2的形式-其中t1，t2

11、*,在DFA M上運(yùn)行的定義為：- f（Q， t1t2 ）=f（f（Q， t1 ）， t2 ） 其中QK - 擴(kuò)充轉(zhuǎn)換函數(shù)f，是K*K上的映射， 且： f（ki，）= ki25* *上的符號(hào)串上的符號(hào)串t t被被DFADFA M M接受接受例例：證明證明t=baab被下圖的被下圖的DFA所接受所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U，a），），b） =f（Q，b）=QQ屬于終態(tài)。屬于終態(tài)。得證。得證。bSUVQabba, baa26DFA M所能接受的符號(hào)串的全體記為L(zhǎng)(M).結(jié)論： 上一個(gè)符

12、號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有窮自動(dòng)機(jī)M，使得V=L(M)。27DFA的行為很容易用程序來(lái)模擬.DFA M=（K，f，S，Z）的行為的模擬程序 K:=S； c:=getchar; while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no)28DFA = digit,not digit29不確定的有窮自動(dòng)機(jī)NFA定義NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種映射，S K是初始狀態(tài)集，Z K為終止?fàn)顟B(tài)集

13、.30例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Z f（P，1）=Zf（Z，0）=Pf（Z，1）=P31狀態(tài)圖表示SPZ00,111132矩陣表示矩陣表示01SPS,Z0PZ0ZPP1簡(jiǎn)化為01SPS,Z0P.Z0ZPP133具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)f為K * 到K的子集（2 K）的一種映射 123abc34有如下定理: 對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA N，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA ，使得L(M)=L(N)。與上例等價(jià)的一個(gè)NFA.cb2acbb31acab35類(lèi)似DFA, 對(duì)NFA M=K，f，S

14、，Z也有如下定義*上的符號(hào)串t在NFA M上運(yùn)行.一個(gè)輸入符號(hào)串t，（我們將它表示成Tt1的形式，其中T，t1 *）在NFA M上運(yùn)行運(yùn)行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符號(hào)串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，則稱t為NFA M所接受接受（識(shí)別識(shí)別）36 *上的符號(hào)串t被NFA M接受也可以用狀態(tài)轉(zhuǎn)換圖來(lái)理解 對(duì)于中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為的弧)等于t，則稱t可為NFA M所識(shí)別(讀出或接受)。 若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)

15、，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為，那么空字可為M所接受。37NFA M所能接受的符號(hào)串的全體記為 L(M)結(jié)論： 上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的不確定的有窮自動(dòng)機(jī)M，使得V=L(M)。3800011110100011100000010001100特點(diǎn)？特點(diǎn)？39(0|1)*(000|111)(0|1)*40確定有限自動(dòng)機(jī)和不確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)和不確定有限自動(dòng)機(jī)關(guān)系關(guān)系 DFA是NFA的特例。 對(duì)每個(gè)NFA N一定存在一個(gè)DFA ，使得 L(M)=L(N)。 找一種算法，將找一種算法，將NFA轉(zhuǎn)換成接受同轉(zhuǎn)換成接受同樣語(yǔ)言的樣語(yǔ)言的DF

16、A. 子集法子集法. 與某一與某一NFA等價(jià)的等價(jià)的DFA不唯一不唯一.等等價(jià)價(jià)41先定義對(duì)狀態(tài)集合I的有關(guān)運(yùn)算：1. 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S而能到達(dá)的狀態(tài)的集合。 狀態(tài)集合I的任何狀態(tài)-closure(I)。2. 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，表示為move(I,a) 定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)而到達(dá)的狀態(tài)的全體。42狀態(tài)集合I的有關(guān)運(yùn)算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-

17、closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa43 NFA確定化算法: NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個(gè)DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的狀態(tài)集S由K K的一些子集的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對(duì)于子集S1, S2= S2, S1,來(lái)說(shuō)，S的狀態(tài)就是S1 S2；442 M和N的輸入字母表是相同的，即是；3 轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其

18、中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開(kāi)始狀態(tài)；5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt45構(gòu)造NFA N的狀態(tài)狀態(tài)K K的子集的子集的算法：假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(tài)K的子集。1 開(kāi)始，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。462 while （C中存在尚未被標(biāo)記的子集T）do 標(biāo)記T； for 每個(gè)輸入字母a do U:= -closure(move(T,a)； i

19、f U不在C中 then 將U作為未標(biāo)記的子集加在C中 47 NFA的確定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,f4f35621iaaaabbbb49 等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF50確定有窮自動(dòng)機(jī)的化簡(jiǎn) 一個(gè)

20、有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說(shuō)，它沒(méi)有多余狀態(tài)并且它的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的。 一個(gè)有窮自動(dòng)機(jī)可以通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。 多余狀態(tài)，是指：從自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒(méi)有通路到達(dá)終態(tài)。 51 DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒(méi)有多余狀態(tài)(死狀態(tài))沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t等價(jià)等價(jià)：滿足兼容性同是終態(tài)或同是非終態(tài)傳播性從s出發(fā)讀入所有aa和從 t出發(fā)讀入所有a到達(dá)的狀態(tài)等價(jià)。分析52最小狀態(tài)DFA對(duì)于一個(gè)DFA M =（K,f, k0,kt)，存在一個(gè)最小狀

21、態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論 接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。53“分割法”DFA的最小化算法的核心 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 算法假定每個(gè)狀態(tài)射出的弧都是完全的,否則,引入一個(gè)新?tīng)顟B(tài),叫死狀態(tài),該狀態(tài)是非終態(tài)，將不完全的輸入弧都射向該狀態(tài)，對(duì)所有輸入，該狀態(tài)射出的弧還回到自己.54 DFA的最小化算法 DFA M =（K,f, k0, kt),最小狀態(tài)DFA M 1.構(gòu)造狀態(tài)的一初始劃分： 終態(tài)kt 和非終態(tài)K- kt兩組(

22、group) 2.對(duì)施用過(guò)程過(guò)程PPPP 構(gòu)造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復(fù)2 . 4.為final中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉(zhuǎn)換f(k,a)=r55 M 的開(kāi)始狀態(tài)是含有S0的那組的代表 M 的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài).56過(guò)程過(guò)程PPPP : Construction of new 對(duì)對(duì)每一個(gè)狀態(tài)組每一個(gè)狀態(tài)組G進(jìn)行下述工作：進(jìn)行下述工作：將將G劃分為子組。劃分為子組。G的兩個(gè)狀態(tài)的兩個(gè)狀態(tài)s和和t分分在同一子組的充要條件是：對(duì)所有的在同

23、一子組的充要條件是：對(duì)所有的輸入符號(hào)輸入符號(hào)a，狀態(tài)，狀態(tài)s和和t的的a轉(zhuǎn)換都是轉(zhuǎn)換都是的的同一組中的狀態(tài)。同一組中的狀態(tài)。形成的所有子組成為形成的所有子組成為new的狀態(tài)組。的狀態(tài)組。 57 DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbba S,BA bB SDBASaaabbbbaa58詞法分析程序的自動(dòng)構(gòu)造 詞法分析程序的自動(dòng)構(gòu)造方法,這個(gè)方法基于有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性,即即： 1.對(duì)于上的一個(gè)NFA M，可以構(gòu)造一個(gè)上的正規(guī)式R,使得L(R)=L(M)。2.對(duì)于上的一個(gè)

24、正規(guī)式R，可以構(gòu)造一個(gè)上的NFA M，使的L(M)=L(R)。59RNFA從上的一個(gè)正規(guī)式R構(gòu)造上的一個(gè)NFA M，使得L(M)=L(R)的方法?！罢Z(yǔ)法制導(dǎo)”的方法，即按正規(guī)式的語(yǔ)法結(jié)構(gòu)指引構(gòu)造過(guò)程，構(gòu)造規(guī)則具體描述如下： 60對(duì)于正規(guī)式 ,構(gòu)造的NFA 61對(duì)于正規(guī)式 ,構(gòu)造的NFA 62對(duì)于正規(guī)式a ,構(gòu)造的NFA 63對(duì)于正規(guī)式r, r= s|t構(gòu)造的NFA s和t相應(yīng)的NFA分別為N(s)和N(t), 64對(duì)于正規(guī)式r, r=st 構(gòu)造的NFA65對(duì)于正規(guī)式r, r = s*構(gòu)造的NFA對(duì)于正規(guī)式r, r = （s）構(gòu)造的NFA4同S的NFA一樣6667正規(guī)表達(dá)式正規(guī)表達(dá)式 1*0(0+1)*舉例舉例:從從正規(guī)表達(dá)式正規(guī)表達(dá)式構(gòu)造等價(jià)的構(gòu)造等價(jià)的 - NFA100+1 11* 68從從正規(guī)表