[理學(xué)]編譯原理第三章(存儲版)
【正文】 tate=3。 } if (state==3 amp。 分離法 對自動機(jī) M進(jìn)行最小化，即尋找一個狀態(tài)數(shù)比 M更少的DFA M’，使得 M和 M’所識別的符號串相同。 例、將以下自動機(jī)最小化： A B F C D E G a b a b b b b a b a 例： P98（例 ） 六、正則表達(dá)式到 DFA的轉(zhuǎn)換 正則定理 ：對于任意的正則表達(dá)式 RE，均可構(gòu)造一個有 窮自動機(jī) FA，使得 FA所接受的符號串的集合 與 RE所接受的符號串集合等價。 按步驟 2得到最終的類劃分后，取每一類中的一個狀態(tài)作代表，而刪除其他一切等價的狀態(tài)，則所有這些狀態(tài)代表構(gòu)成了最小化自動機(jī) M’的狀態(tài)集合。然后在自動機(jī)的狀態(tài)轉(zhuǎn)換表中尋找相同的兩行，如這兩行對應(yīng)的狀態(tài) S i和 Sj屬于同一類，則可以合并。} break。break。 default: state=0。 } (2)直接轉(zhuǎn)換法 int scanner(){ state=1。 while(TT[S,ch])!=undef amp。 ? 練習(xí)：寫出以下符號串集合所對應(yīng)的正則表達(dá)式： 以 0開始以 1結(jié)尾的所有二進(jìn)制數(shù)字串； L(G)={a2n+1b2ma2p+1|n=0, p=0, m=1} 解答： 0(0|1)*1 a(aa)*bb(bb)*a(aa)* 例、相同 0、 1串中夾一個 a的符號串的集合： Ayay y(0|1)* 例： P75 有窮自動機(jī) 一、自動機(jī)與正則文法、正則表達(dá)式具有相 同的表達(dá)能力。 ? 符號串： 也可稱為字或句子，用 ?表示空符號串。 每個界限符號有一個詞法單元，如左右括號、逗號、分號等。 read(y)?！? [11](ID,”x”) [12](ASS_OP,”:=”) [13](ID,”x”) [14](PLUS_OP,”+”) [15](ID,”y”) [16](END,”end”) 詞法單元由兩部分組成：（詞法單元名，屬性值 ) 詞素是一個詞法單元的一個實(shí)例。 四、空格符、制表符和換行符的處理 ? 空格符 、制表符只有詞法意義而沒有語法和語義上的意 義，因此詞法分析后需刪除，但字符串中的空格符不能 刪除； ? 換行符對錯誤處理具有重要的意義，在發(fā)現(xiàn)錯誤時指出 錯誤的行號，因此詞法分析時不能刪除。 ? 是正則表達(dá)式 , L( ? )={ } ? 是正則表達(dá)式 , L(? ) = {? } a ? ? 是正則表達(dá)式 , L( a )= { a } 例、以 00結(jié)尾的二進(jìn)制數(shù)字串對應(yīng)的正則表達(dá)式為： 設(shè) A,B? , 則 : R ? (A) ? R? , L((A) )=L(A)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1