復習—編譯原理第3章

1、2021-10-151計算機學院計算機學院編 譯 原 理主講人：鄭麗萍主講人：鄭麗萍時間：時間：2014-20152014-2015學年第二學期學年第二學期聯(lián)系方式：聯(lián)系方式：2021-10-152 詞法分析程序又稱掃描器，是編譯過程的第一步，是下詞法分析程序又稱掃描器，是編譯過程的第一步，是下一步進行語法分析的基礎。詞法分析的任務一步進行語法分析的基礎。詞法分析的任務: :從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位最小語法單位“單詞單詞”，并將其轉(zhuǎn)化為內(nèi)部編碼形式。，并將其轉(zhuǎn)化為內(nèi)部編碼形式。刪除無用的空白字符和回車字符以及其

2、他非實質(zhì)性字符。刪除無用的空白字符和回車字符以及其他非實質(zhì)性字符。刪除注釋。刪除注釋。1.1. 進行詞法檢查進行詞法檢查, ,報告所發(fā)現(xiàn)的錯誤。報告所發(fā)現(xiàn)的錯誤。詞法分析的任務詞法分析的任務2021-10-153n 逐個讀入源程序字符，然后按照構(gòu)詞規(guī)則切分成一列逐個讀入源程序字符，然后按照構(gòu)詞規(guī)則切分成一列單詞，再轉(zhuǎn)換成單詞序列。單詞是語言中具有獨立意單詞，再轉(zhuǎn)換成單詞序列。單詞是語言中具有獨立意義的最小單位。義的最小單位。n 詞標詞標(token(token）是單詞的機內(nèi)表示，其格式由實現(xiàn)系統(tǒng)）是單詞的機內(nèi)表示，其格式由實現(xiàn)系統(tǒng)規(guī)定。規(guī)定。單詞符號一般可分為下列五種：單詞符號一般可分為下列五

3、種：n 基本字，關(guān)鍵字；基本字，關(guān)鍵字；n 標識符；標識符；n 常數(shù)（量）；常數(shù)（量）；n 運算符；運算符；n 分隔符分隔符單詞的劃分單詞的劃分 2021-10-154單詞符號的內(nèi)部表示單詞符號的內(nèi)部表示 詞法分析的功能是識別出的具有獨立意義的單詞，并轉(zhuǎn)化為詞法分析的功能是識別出的具有獨立意義的單詞，并轉(zhuǎn)化為相應的內(nèi)部表示。相應的內(nèi)部表示。詞法分析的輸出常采用二元式詞法分析的輸出常采用二元式(class(class，value),value),如圖如圖3.33.3所示。所示。classclass為以整數(shù)碼或助記符為以整數(shù)碼或助記符,value,value則是該單詞的值則是該單詞的值( (如變量

4、名如變量名在符號表中的序號在符號表中的序號, ,常數(shù)的二進制表示常數(shù)的二進制表示, ,以及運算符和分隔符以及運算符和分隔符的編碼的編碼, ,等等等等) )class單詞類別單詞類別 value單詞值單詞值 圖圖3.3 詞法分析程序的輸出形式詞法分析程序的輸出形式 2021-10-155由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖l 一個狀態(tài)轉(zhuǎn)換圖是由一組矢線連接的有限個節(jié)點所組成的一個狀態(tài)轉(zhuǎn)換圖是由一組矢線連接的有限個節(jié)點所組成的有向圖。有向圖。l每個節(jié)點均代表在識別或分析過程中掃描器的狀態(tài)，其中每個節(jié)點均代表在識別或分析過程中掃描器的狀態(tài)，其中有一個是開始狀態(tài)有一個是開始狀態(tài)( (帶箭頭

5、帶箭頭) )，至少有一個狀態(tài)是結(jié)束狀態(tài)，至少有一個狀態(tài)是結(jié)束狀態(tài)（雙圈）。（雙圈）。 l狀態(tài)間用矢線連接，矢線上標記有符號，表示在矢線射出狀態(tài)間用矢線連接，矢線上標記有符號，表示在矢線射出端的狀態(tài)下，讀入矢線上標記的符號可轉(zhuǎn)換到矢線指向的端的狀態(tài)下，讀入矢線上標記的符號可轉(zhuǎn)換到矢線指向的狀態(tài)。狀態(tài)圖只有狀態(tài)。狀態(tài)圖只有有窮個狀態(tài)有窮個狀態(tài)。12開始a0abb2021-10-156正規(guī)文法形式：正規(guī)文法形式：AaAa或或ABaABa（左線性）或（左線性）或AaBAaB（右線性）（右線性）其中：其中：A,BVnA,BVn，aVt;aVt;正規(guī)文法描述語言單詞，狀態(tài)轉(zhuǎn)換圖可識別單詞，它們之間正規(guī)文法

6、描述語言單詞，狀態(tài)轉(zhuǎn)換圖可識別單詞，它們之間存在等價關(guān)系。存在等價關(guān)系。一一. .對于右線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖對于右線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖設設G=(Vn,Vt,P,S)G=(Vn,Vt,P,S)是一右線性文法是一右線性文法,Vn,Vn中的每個非終結(jié)符號對中的每個非終結(jié)符號對應狀態(tài)圖中的一個結(jié)點應狀態(tài)圖中的一個結(jié)點, ,且的開始符號所標記的結(jié)點為初且的開始符號所標記的結(jié)點為初態(tài)結(jié)點態(tài)結(jié)點; ;增設一個不屬于的符號增設一個不屬于的符號F F標記終態(tài)結(jié)點。標記終態(tài)結(jié)點。|V|VN N|=k,|=k,共有共有k+1k+1個節(jié)點（狀態(tài)）。個節(jié)點（狀態(tài)）。2021-10-157對于對于G G中的每一條形如

7、中的每一條形如AaAa的規(guī)則，從結(jié)點的規(guī)則，從結(jié)點A A引一條矢線到引一條矢線到終態(tài)結(jié)點終態(tài)結(jié)點F F，并用符號，并用符號a a標記這條矢線。標記這條矢線。對于對于G G中每一條形如中每一條形如AaBAaB的規(guī)則，從結(jié)點的規(guī)則，從結(jié)點A A引一條矢線到引一條矢線到結(jié)點結(jié)點B B，并用符號，并用符號a a標記這條矢線。標記這條矢線。注意注意: :文法文法G G中含有無用符號和無用產(chǎn)生式須事先予以刪除中含有無用符號和無用產(chǎn)生式須事先予以刪除; ;若若L(G),L(G),則初態(tài)結(jié)點則初態(tài)結(jié)點S S也同時是一個終態(tài)結(jié)點也同時是一個終態(tài)結(jié)點; ;若若G G中含有中含有產(chǎn)生式產(chǎn)生式A,A,則將結(jié)點則將結(jié)點

8、A A設置為終態(tài)結(jié)點設置為終態(tài)結(jié)點; ;右線性文法構(gòu)造狀態(tài)圖規(guī)則右線性文法構(gòu)造狀態(tài)圖規(guī)則2021-10-158baabVSUa例如：文法例如：文法GS SaU|bV UbV|a VaU|bbQ右線性文法狀態(tài)圖構(gòu)造實例右線性文法狀態(tài)圖構(gòu)造實例2021-10-159狀態(tài)轉(zhuǎn)換圖對符號串的識別狀態(tài)轉(zhuǎn)換圖對符號串的識別 利用狀態(tài)轉(zhuǎn)換圖可識別相應文法所表示的符號串利用狀態(tài)轉(zhuǎn)換圖可識別相應文法所表示的符號串。12開始a0abb定義：定義：設設VVT T * * ，如果狀態(tài)轉(zhuǎn)換圖中存在一條從，如果狀態(tài)轉(zhuǎn)換圖中存在一條從初態(tài)初態(tài)到到終態(tài)終態(tài)的路徑，此路徑上的標記符號順序相連構(gòu)成符號串的路徑，此路徑上的標記符號順

9、序相連構(gòu)成符號串，則稱，則稱為為狀態(tài)圖所識別串狀態(tài)圖所識別串。狀態(tài)圖識別語言：狀態(tài)圖識別語言：狀態(tài)圖所識別的串集合。狀態(tài)圖所識別的串集合。2021-10-1510 對符號串對符號串W=aW=a1 1a a2 2a a3 3a an n，a ai i V VT T 識別過程：識別過程：l 從初態(tài)從初態(tài)S S出發(fā)，自左至右逐個掃描出發(fā)，自左至右逐個掃描W W中的字符，在中的字符，在S S狀態(tài)下掃狀態(tài)下掃視的符號為視的符號為a a1 1；l 在節(jié)點在節(jié)點S S所射出諸矢線中尋找標記為所射出諸矢線中尋找標記為a a1 1的矢線的矢線( (若不存在，若不存在，則說明則說明W W有錯有錯) )；l 讀入讀

10、入a a1 1，沿矢線方向到下一狀態(tài)，在此狀態(tài)時掃描，沿矢線方向到下一狀態(tài)，在此狀態(tài)時掃描a a2 2，l 直至直至W W中全部字符讀完且進入終態(tài)中全部字符讀完且進入終態(tài)F,F,則則W W已被接受。已被接受。對符號串的識別過程對符號串的識別過程2021-10-1511狀態(tài)圖的一種實現(xiàn)狀態(tài)圖的一種實現(xiàn)-狀態(tài)矩陣法狀態(tài)矩陣法程序設計語言一般含有若干類單詞符號程序設計語言一般含有若干類單詞符號, ,我們可首先為每類我們可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖單詞建立一張狀態(tài)轉(zhuǎn)換圖, ,然后將這些狀態(tài)轉(zhuǎn)換圖合并成一然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖張統(tǒng)一的狀態(tài)圖, ,最后再據(jù)此構(gòu)造詞法分析程序。最后

11、再據(jù)此構(gòu)造詞法分析程序。計算機內(nèi)表示狀態(tài)轉(zhuǎn)換圖的方法之一是計算機內(nèi)表示狀態(tài)轉(zhuǎn)換圖的方法之一是狀態(tài)矩陣狀態(tài)矩陣。狀態(tài)矩陣：狀態(tài)圖中的各個狀態(tài)狀態(tài)矩陣：狀態(tài)圖中的各個狀態(tài)S S1 1，S S2 2，S Sn n為行，以可為行，以可能輸入的輸入符號能輸入的輸入符號a a1 1，a a2 2，a am m為列，組成一個為列，組成一個n n行行m m列矩列矩陣。陣。2021-10-1512BnmBnBnmBBBmBBBB212222111211 a1 a2 am SnSS21B Bijij=BS=BSi i,a,aj j 含義：當前狀態(tài)含義：當前狀態(tài)S Si i，正掃視符號，正掃視符號a aj j，則以

12、序偶（，則以序偶（S Si i，a aj j）去查）去查詢矩陣詢矩陣B B，掃描器根據(jù)，掃描器根據(jù)B Bijij的指示，執(zhí)行相應的語義動作，轉(zhuǎn)到的指示，執(zhí)行相應的語義動作，轉(zhuǎn)到S Sk k狀態(tài)。若某狀態(tài)。若某a aj j不與不與S Si i配對，即狀態(tài)圖中從節(jié)點配對，即狀態(tài)圖中從節(jié)點S Si i不存在以不存在以a aj j為為標記的射出矢線，則標記的射出矢線，則B Bj j置為置為“errorerror”, ,進行詞法錯誤檢查和處進行詞法錯誤檢查和處理。理。2021-10-1513有限自動機（有限自動機（FAFA） u有限自動機是一種具有離散輸入與輸出系統(tǒng)的數(shù)學模型有限自動機是一種具有離散輸入

13、與輸出系統(tǒng)的數(shù)學模型,是狀是狀態(tài)轉(zhuǎn)換圖的形式化。在這種數(shù)學模型中有有限個狀態(tài)，狀態(tài)間態(tài)轉(zhuǎn)換圖的形式化。在這種數(shù)學模型中有有限個狀態(tài)，狀態(tài)間存在著轉(zhuǎn)換關(guān)系。系統(tǒng)可以處于有限個狀態(tài)中的任意一個之中，存在著轉(zhuǎn)換關(guān)系。系統(tǒng)可以處于有限個狀態(tài)中的任意一個之中，系統(tǒng)的當前狀態(tài)概括了有關(guān)過去輸入的信息。系統(tǒng)的當前狀態(tài)概括了有關(guān)過去輸入的信息。u當系統(tǒng)處在某個狀態(tài)之下讀入一個字符時，會使系統(tǒng)所處的當系統(tǒng)處在某個狀態(tài)之下讀入一個字符時，會使系統(tǒng)所處的狀態(tài)發(fā)生變化，從而形成狀態(tài)轉(zhuǎn)換。改變后的狀態(tài)稱為后繼狀狀態(tài)發(fā)生變化，從而形成狀態(tài)轉(zhuǎn)換。改變后的狀態(tài)稱為后繼狀態(tài)。態(tài)。2021-10-1514在狀態(tài)轉(zhuǎn)換中，后繼狀態(tài)可

14、能為一個，也可能為多個。有限自在狀態(tài)轉(zhuǎn)換中，后繼狀態(tài)可能為一個，也可能為多個。有限自動機分確定的和不確定的。動機分確定的和不確定的。所謂所謂“確定的有限自動機確定的有限自動機” ( Deterministic Finite ( Deterministic Finite Automata DFA)Automata DFA)是指在當前的狀態(tài)下，輸入一個符號，有限自動是指在當前的狀態(tài)下，輸入一個符號，有限自動機將轉(zhuǎn)換到唯一的后繼狀態(tài)；機將轉(zhuǎn)換到唯一的后繼狀態(tài)；“不確定的有限自動機不確定的有限自動機” (Nondeterministic Finite (Nondeterministic Finite

15、Automata NFA)Automata NFA)在當前狀態(tài)下輸入一個符號，可能有兩種或兩種在當前狀態(tài)下輸入一個符號，可能有兩種或兩種以上可選擇的后繼狀態(tài)。以上可選擇的后繼狀態(tài)。 有限自動機的分類有限自動機的分類2021-10-1515確定的有限自動機確定的有限自動機 1、確定的有限自動機定義、確定的有限自動機定義將前面介紹的狀態(tài)轉(zhuǎn)換圖抽象將前面介紹的狀態(tài)轉(zhuǎn)換圖抽象,可得到一個確定的有限自動機可得到一個確定的有限自動機M（記作（記作DFA M）是一個五元組）是一個五元組:M=（ K， ，f，S0，Z）其中：其中： K：是一個有限狀態(tài)的集合。：是一個有限狀態(tài)的集合。 ：是一個有限個輸入字符組成

16、的字母表：是一個有限個輸入字符組成的字母表 f：狀態(tài)轉(zhuǎn)換函數(shù)，是一個：狀態(tài)轉(zhuǎn)換函數(shù)，是一個KK的單值映射，的單值映射， 形形式為式為f (p, a)=q 。 S0：S0K，是唯一的初始狀態(tài)。，是唯一的初始狀態(tài)。 Z：ZK，稱為終結(jié)狀態(tài)集合。，稱為終結(jié)狀態(tài)集合?？梢娍梢?一個確定的有限自動機是相應的狀態(tài)圖的一種形式描述。一個確定的有限自動機是相應的狀態(tài)圖的一種形式描述。這是一個單值函數(shù)，指明當前這是一個單值函數(shù)，指明當前狀態(tài)為狀態(tài)為p，輸入符號為，輸入符號為a時，自時，自動機將從狀態(tài)動機將從狀態(tài)p轉(zhuǎn)換到下一個狀轉(zhuǎn)換到下一個狀態(tài)態(tài)q，q稱為稱為p的后繼狀態(tài)。的后繼狀態(tài)。2021-10-1516DF

17、A M=（S，U，V，Q，a，b，f，S，Q）其中）其中f定義為：定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（U，b）=V例：例：SaU|bV UbV|a VaU|bbaabVSUabQ2021-10-15172 2、確定的有限自動機狀態(tài)圖、確定的有限自動機狀態(tài)圖 u確定的有限自動機確定的有限自動機M M可以用狀態(tài)圖來表示?？梢杂脿顟B(tài)圖來表示。u狀態(tài)圖中的結(jié)點代表狀態(tài)，它與自動機中的狀態(tài)集合狀態(tài)圖中的結(jié)點代表狀態(tài)，它與自動機中的狀態(tài)集合K K相相對應，其中包括初始狀態(tài)對應，其中包括初始狀態(tài)S S0 0和終結(jié)狀態(tài)集合和終結(jié)狀態(tài)集合Z Z。u狀態(tài)間用

18、矢線連接，矢線上標記有輸入符號，每條矢線狀態(tài)間用矢線連接，矢線上標記有輸入符號，每條矢線對應一個狀態(tài)轉(zhuǎn)換函數(shù)對應一個狀態(tài)轉(zhuǎn)換函數(shù)f f，矢線上標記的輸入符號集合就是，矢線上標記的輸入符號集合就是字母表字母表。 2021-10-15183 3、確定的有限自動機狀態(tài)轉(zhuǎn)換矩陣、確定的有限自動機狀態(tài)轉(zhuǎn)換矩陣u確定的有限自動機確定的有限自動機M M還可以用狀態(tài)轉(zhuǎn)換矩陣來表示。還可以用狀態(tài)轉(zhuǎn)換矩陣來表示。u矩陣中的第一列元素與自動機中的狀態(tài)集合矩陣中的第一列元素與自動機中的狀態(tài)集合K K相對應，且相對應，且初始狀態(tài)初始狀態(tài)S S0 0是第一列的第一個元素，右上角標記是第一列的第一個元素，右上角標記* *的

19、元素對的元素對應終結(jié)狀態(tài)。應終結(jié)狀態(tài)。u矩陣中的第一行元素與字母表矩陣中的第一行元素與字母表中的每個輸入符號相對中的每個輸入符號相對應。矩陣中的元素對應每個狀態(tài)轉(zhuǎn)換函數(shù)。應。矩陣中的元素對應每個狀態(tài)轉(zhuǎn)換函數(shù)。u如果有狀態(tài)轉(zhuǎn)換函數(shù)如果有狀態(tài)轉(zhuǎn)換函數(shù)f(p,a)=q,f(p,a)=q,其中其中p,qK,ap,qK,a，那么，那么，就在矩陣中狀態(tài)就在矩陣中狀態(tài)p p對應的行和符號對應的行和符號a a對應的列單元中填入對應的列單元中填入q q。2021-10-15194 4、確定的有限自動機接受的語言、確定的有限自動機接受的語言 為了講解確定的有限自動機如何接受或識別字符串，首先，為了講解確定的有限自

20、動機如何接受或識別字符串，首先，我們對狀態(tài)轉(zhuǎn)換函數(shù)作補充定義：我們對狀態(tài)轉(zhuǎn)換函數(shù)作補充定義： f(S,)=Sf(S,)=S f(S,aw)=f(f(S,a),w),a f(S,aw)=f(f(S,a),w),a，ww* *，即，即w w是是上的字符串上的字符串例如例如, ,有有f(0,a)=1 f(0,a)=1 且且f(1,b)=2,f(1,b)=2,則則 f(0,ab)=f(f(0,a),b)=f(1,b)=2f(0,ab)=f(f(0,a),b)=f(1,b)=2對一個確定的有限自動機對一個確定的有限自動機M M以及某個字符串以及某個字符串x x（xx* *），如），如果有果有f(Sf(S

21、0 0, x)=S, x)=S，且，且SZSZ，則字符串，則字符串x x就被該自動機就被該自動機M M所接受。所接受。即將即將f的定義域擴充到的定義域擴充到K*2021-10-1520u從狀態(tài)圖上看，如果一個字符串能被自動機接受，則存在從狀態(tài)圖上看，如果一個字符串能被自動機接受，則存在一條從初始狀態(tài)到某一終結(jié)狀態(tài)的通路，且將這條通路上所一條從初始狀態(tài)到某一終結(jié)狀態(tài)的通路，且將這條通路上所有矢線標記的符號一次連接起來就組成了字符串有矢線標記的符號一次連接起來就組成了字符串x x。u若初始狀態(tài)也是終結(jié)狀態(tài)，或是存在一條從初始狀態(tài)到某若初始狀態(tài)也是終結(jié)狀態(tài)，或是存在一條從初始狀態(tài)到某一終結(jié)狀態(tài)的路徑

22、，路徑上的所有標記都是一終結(jié)狀態(tài)的路徑，路徑上的所有標記都是，則，則可被可被DFADFA接受。接受。 u一個確定的有限自動機一個確定的有限自動機M M所接受的語言就是所能接受的字所接受的語言就是所能接受的字符串構(gòu)成的集合，用符串構(gòu)成的集合，用L L（M M）表示，可定義為：）表示，可定義為： L L（M M）=x|f(S=x|f(S0 0,x)Z,x)Z，xx* * 2021-10-1521l DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)的確定性表現(xiàn)在轉(zhuǎn)換函數(shù) :KK是一個單值函是一個單值函數(shù)，即：對任何狀態(tài)數(shù)，即：對任何狀態(tài)kK以及輸入符號以及輸入符號a， (k,a)能唯能唯一確定下一個狀態(tài)。一確定下一個狀

23、態(tài)。l 從狀態(tài)轉(zhuǎn)換圖來看，若字母表從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有含有n個輸入字符，那么個輸入字符，那么任何一個狀態(tài)結(jié)點最多有任何一個狀態(tài)結(jié)點最多有n條弧射出，而且每條弧以一個條弧射出，而且每條弧以一個不同的輸入字符標記。不同的輸入字符標記。總總 結(jié)：結(jié)：2021-10-1522非確定的有限自動機非確定的有限自動機 非確定的有限自動機與確定的有限自動機的區(qū)別主要是狀非確定的有限自動機與確定的有限自動機的區(qū)別主要是狀態(tài)轉(zhuǎn)換函數(shù)態(tài)轉(zhuǎn)換函數(shù)f f為多值函數(shù)。為多值函數(shù)。1 1、非確定的有限自動機定義、非確定的有限自動機定義一個非確定的有限自動機一個非確定的有限自動機NFA MNFA M是一個五元式是一

24、個五元式M=M=（K K，f f，S S0 0，Z Z）其中其中:K:K：有窮狀態(tài)集：有窮狀態(tài)集; ; ：輸入字母表：輸入字母表 S S0 0：開始狀態(tài)：開始狀態(tài)S S0 0K; ZK; Z：終止狀態(tài)集：終止狀態(tài)集ZKZKf f：狀態(tài)轉(zhuǎn)換函數(shù)，為：狀態(tài)轉(zhuǎn)換函數(shù)，為K K到到K K的子集的映射。的子集的映射。形式為形式為 f( Sf( Si i, a, aj j )=S )=Sk1k1,S,Sk2k2, ,S,Skmkm 非確定的有限自動機同樣可以用狀態(tài)圖和狀態(tài)轉(zhuǎn)換矩陣來非確定的有限自動機同樣可以用狀態(tài)圖和狀態(tài)轉(zhuǎn)換矩陣來表示，表示方法與確定的相同。表示，表示方法與確定的相同。 2021-10-1

25、5232 2、非確定的有限自動機接受的語言、非確定的有限自動機接受的語言與確定的有限自動機一樣，為了判別一個字符串與確定的有限自動機一樣，為了判別一個字符串x x能否被能否被NFA MNFA M接受，我們還需要對狀態(tài)轉(zhuǎn)換函數(shù)做補充定義：接受，我們還需要對狀態(tài)轉(zhuǎn)換函數(shù)做補充定義：f(S,)=Sf(S,)=S f(S,aw)=f(f(S,a),w),a,w f(S,aw)=f(f(S,a),w),a,w* *再設再設f(S,a)=Sf(S,a)=Sk1k1,S,Sk2k2, , , S, Skmkm 且定義且定義 f(Sf(Sk1k1,S,Sk2k2, ,S,Skmkm,w)=,w)=m mi=1

26、i=1f(Sf(Skiki,w),w)表示從表示從M M的當前狀態(tài)集出發(fā)，掃描字符串的當前狀態(tài)集出發(fā)，掃描字符串x x后，所到達的狀態(tài)集后，所到達的狀態(tài)集等于從當前狀態(tài)集的每一個狀態(tài)出發(fā)，掃描字符串等于從當前狀態(tài)集的每一個狀態(tài)出發(fā)，掃描字符串x x后所到達后所到達的狀態(tài)集之和。的狀態(tài)集之和。即將即將f的定義域擴充的定義域擴充到到2K*2021-10-1524對于某個字符串對于某個字符串 x（x *），），若有若有f (S0, x )=K，且，且K Z ，則則x為為M所接受。所接受。從狀態(tài)圖上看，如果一個字符串能被非確定的自動機接從狀態(tài)圖上看，如果一個字符串能被非確定的自動機接受，則至少存在一條

27、從初始狀態(tài)到某一終結(jié)狀態(tài)的通路，受，則至少存在一條從初始狀態(tài)到某一終結(jié)狀態(tài)的通路，且將這條通路上所有矢線標記的符號依次連接起來就組且將這條通路上所有矢線標記的符號依次連接起來就組成了字符串成了字符串x。NFA M所接受的語言為所接受的語言為 L（M）=x | f(S0, x )Z ， x * NFA所接受的語言所接受的語言2021-10-1525*上的符號串上的符號串t被被NFA M接受也可理解為：接受也可理解為：l 對于對于中的串中的串t t，若存在一條從某初態(tài)到某一終態(tài)，若存在一條從某初態(tài)到某一終態(tài)的路徑，且這條路上所有弧的標記字依序連接成的串的路徑，且這條路上所有弧的標記字依序連接成的串

28、等于等于t t，則稱，則稱t t可為可為NFA MNFA M所識別所識別( (接受接受) )。l 若若M M的某些結(jié)點既是初態(tài)又是終態(tài)，或者存在一條從的某些結(jié)點既是初態(tài)又是終態(tài)，或者存在一條從某個初態(tài)到某個終態(tài)的路徑某個初態(tài)到某個終態(tài)的路徑, ,其上所有弧的標記均為其上所有弧的標記均為，那么那么可被可被M M所接受。所接受。符號串被符號串被NFA所接受所接受2021-10-1526NFANFA與與DFADFA的等價性的等價性 所謂所謂NFANFA的確定化的確定化, ,是指對任給的是指對任給的NFA,NFA,都能相應的構(gòu)造一都能相應的構(gòu)造一DFA,DFA,使它們有相同的接受集。使它們有相同的接受

29、集。證明的思路證明的思路: :讓所要構(gòu)造的讓所要構(gòu)造的DFADFA去模擬相應的去模擬相應的NFANFA的工作過程的工作過程, ,即用即用DFADFA的一個狀態(tài)去記錄的一個狀態(tài)去記錄NFANFA讀入一個輸入符號后可能到達讀入一個輸入符號后可能到達的所有狀態(tài)。的所有狀態(tài)。定理定理3.13.1對于字母表對于字母表上的任一上的任一NFA M,NFA M,必存在必存在上與上與M M等價的等價的DFA MDFA M 。證明證明: :設設M=(K, ,f, SM=(K, ,f, S0 0, Z), Z)是是上的一個上的一個NFA,NFA,今構(gòu)今構(gòu)造一個造一個上的上的DFA MDFA M=(K=(K,f,f,

30、S,S0 0,Z,Z),),其方法如下其方法如下: :2021-10-1527K K=2=2K K 。例如。例如, ,對對K K的一個子集的一個子集SS1 1,S,S2 2, ,S,Si i,我們用記號我們用記號SS1 1,S,S2 2, ,S,Si i 表示表示K K中的一個狀態(tài)中的一個狀態(tài), ,特別地特別地, ,令令S S0 0=S=S0 0 映射映射f f的定義為：的定義為： 當且僅當當且僅當 f(Sf(S1 1,S,S2 2, ,S,Si i,a)=R,a)=R1 1,R,R2 2, ,R,Rj j 時時 f f(S(S1 1,S,S2 2, ,S,Si i,a)=R,a)=R1 1,

31、R,R2 2, ,R,Rj j 終態(tài)集終態(tài)集Z Z定義為定義為 Z Z=Sp,Sq,=Sp,Sq,SrSp,Sq,SrSp,Sq,SrK,SrK且且Sp,Sq,Sp,Sq,SrZ ,SrZ 2021-10-1528具有具有動作的動作的FAFA u一個具有一個具有動作的有限自動機動作的有限自動機NFA M也是一個五元式也是一個五元式 M=（K， ，f ， S0，Z）其中其中, K,S0,Z的含義同前的含義同前,而而f卻是卻是K()到到2k的一個映的一個映射。射。u對于對于f(q,a)則由狀態(tài)則由狀態(tài)p組成：當組成：當NFA處于狀態(tài)處于狀態(tài)q而掃視的輸而掃視的輸入字符為入字符為a(a或或a =)時

32、，它的下一個狀態(tài)將是時，它的下一個狀態(tài)將是p。2021-10-1529具有具有動作的動作的NFANFA的確定化的確定化為了實現(xiàn)為了實現(xiàn)NFA到到DFA 的轉(zhuǎn)化，首先介紹兩個狀態(tài)子集的計算方的轉(zhuǎn)化，首先介紹兩個狀態(tài)子集的計算方法，它們是從法，它們是從NFA到到DFA 的轉(zhuǎn)化過程中需要計算的狀態(tài)子集。的轉(zhuǎn)化過程中需要計算的狀態(tài)子集。 1、狀態(tài)集、狀態(tài)集P的的閉包閉包 設設P是一是一NFA M的狀態(tài)集的狀態(tài)集K的一個子集，則的一個子集，則-closure (P) 稱為狀稱為狀態(tài)集態(tài)集P的的閉包，閉包，閉包也是狀態(tài)集閉包也是狀態(tài)集K的一個子集，其計算方法如的一個子集，其計算方法如下：下：1）若）若q

33、P，則，則q -closure (P)，即，即P的所有成員都是的所有成員都是P的的閉閉包的成員（狀態(tài)包的成員（狀態(tài)q本身包含在這個集合之中）本身包含在這個集合之中）2）若）若q P，那么從，那么從q出發(fā)經(jīng)過任意條出發(fā)經(jīng)過任意條弧而能到達的任何狀態(tài)弧而能到達的任何狀態(tài)都屬于都屬于-closure (P)。 2021-10-15302、狀態(tài)集、狀態(tài)集P的的a弧轉(zhuǎn)換集弧轉(zhuǎn)換集設設P仍是一仍是一NFA M的狀態(tài)集的子集，的狀態(tài)集的子集，P= p1, p2,p n ,a，即即a是字母表是字母表的一個輸入符號，則的一個輸入符號，則P的的a弧轉(zhuǎn)換集為：弧轉(zhuǎn)換集為：Pa=-closure (J)，其中其中 J

34、=f(p1,p2,p n, a)=f(p1, a )f(p2,a)f (p n, a)即即J是從狀態(tài)子集是從狀態(tài)子集P中的每個狀態(tài)出發(fā)，沿著標記為中的每個狀態(tài)出發(fā)，沿著標記為a的矢線而的矢線而轉(zhuǎn)移到達的狀態(tài)所組成的集合。轉(zhuǎn)移到達的狀態(tài)所組成的集合。從定義可知，狀態(tài)集從定義可知，狀態(tài)集P的的a弧轉(zhuǎn)換集弧轉(zhuǎn)換集Pa也是狀態(tài)子集，其元素為也是狀態(tài)子集，其元素為從從P的每個狀態(tài)出發(fā)，沿著標記為的每個狀態(tài)出發(fā)，沿著標記為a的矢線所轉(zhuǎn)移到達的后繼狀的矢線所轉(zhuǎn)移到達的后繼狀態(tài)的集合，再加上這些后繼狀態(tài)集合中的每個狀態(tài)的態(tài)的集合，再加上這些后繼狀態(tài)集合中的每個狀態(tài)的閉包，即閉包，即轉(zhuǎn)移后再經(jīng)轉(zhuǎn)移后再經(jīng)矢線所能

35、到達的狀態(tài)的集合。矢線所能到達的狀態(tài)的集合。 狀態(tài)集狀態(tài)集P的的a弧轉(zhuǎn)換集弧轉(zhuǎn)換集2021-10-15313、根據(jù)、根據(jù)NFA M構(gòu)造構(gòu)造DFA M(子集法子集法)基本思路基本思路:首先將首先將-closure(S0)作為作為M的初態(tài)的初態(tài)q0,然后對于所有的然后對于所有的輸入符號輸入符號a ,將將q0的的a弧轉(zhuǎn)換集作為弧轉(zhuǎn)換集作為M的狀態(tài)的狀態(tài),如此如此等等等等,直到不再有新的狀態(tài)出現(xiàn)為止。直到不再有新的狀態(tài)出現(xiàn)為止。下面我們通過一個例子來介紹根據(jù)下面我們通過一個例子來介紹根據(jù)NFA M構(gòu)造構(gòu)造DFA M的方法的方法。子集法實現(xiàn)子集法實現(xiàn)NFA到到DFA轉(zhuǎn)換轉(zhuǎn)換2021-10-1532例題：

36、假設有一個不確定的有限自動機例題：假設有一個不確定的有限自動機NFA M= （K， ，f ，S0 ，Z），），其中其中K=1,2,3,4，=a,b,c，S0 =1， Z=4，狀態(tài)圖如圖狀態(tài)圖如圖3.13所示。所示。接受的語言：接受的語言：L(M) =a m b | m1 a c n | n1 ，構(gòu)造一個構(gòu)造一個DFA M= （K， ，f ，q0，Z），），使使L(M)=L(M) 1234aaaccb圖圖3.13 NFA M的狀態(tài)圖的狀態(tài)圖 2021-10-1533構(gòu)造確定的有限自動機過程如下：構(gòu)造確定的有限自動機過程如下：1）首先根據(jù)）首先根據(jù)閉包的計算方法求閉包的計算方法求NFA M的開始狀

37、態(tài)的開始狀態(tài)S0的的閉包，從而確定閉包，從而確定DFA M的開始狀態(tài)的開始狀態(tài)q0。 q0 =-closure(S0)= -closure(1)=1，42）根據(jù)弧轉(zhuǎn)換集的計算方法求開始狀態(tài)）根據(jù)弧轉(zhuǎn)換集的計算方法求開始狀態(tài)q0對每個輸入符對每個輸入符號的弧轉(zhuǎn)換集號的弧轉(zhuǎn)換集q0a、q0b和和q0c從而確定與開始狀態(tài)從而確定與開始狀態(tài)q0有關(guān)的有關(guān)的狀態(tài)轉(zhuǎn)換函數(shù)。狀態(tài)轉(zhuǎn)換函數(shù)。f(q0,a)=q0a =-closure( f(1,4,a) )=-closure(f(1, a )f(4, a ) )=-closure(2,3)=2,31234aaaccb2021-10-1534將將2,3作為新狀態(tài)

38、作為新狀態(tài),并令并令q1 =2,3，即得到，即得到f(q0,a)= q1q0的的b弧轉(zhuǎn)換集弧轉(zhuǎn)換集q0b= -closure( f(1，4,b) ) = -closure()= ,即即 f(q0,b) = ；q0的的c弧轉(zhuǎn)換集弧轉(zhuǎn)換集q0c= -closure( f(1，4,c) ) = -closure()= ; f(q0,c) = ； 1234aaaccb2021-10-1535由于由于f(q0,b) = ，f(q0,c) =，說明沒有新狀態(tài)產(chǎn)生。至此，說明沒有新狀態(tài)產(chǎn)生。至此，我們得到有關(guān)開始狀態(tài)我們得到有關(guān)開始狀態(tài)q0的全部狀態(tài)轉(zhuǎn)換函數(shù)只有一個，即的全部狀態(tài)轉(zhuǎn)換函數(shù)只有一個，即f(q0

39、,a)= q1。 1234aaaccb2021-10-15363）按步驟）按步驟2的方法，對每個新狀態(tài)計算相關(guān)的狀態(tài)轉(zhuǎn)換函數(shù)。的方法，對每個新狀態(tài)計算相關(guān)的狀態(tài)轉(zhuǎn)換函數(shù)。計算狀態(tài)計算狀態(tài)q1(2,3)的狀態(tài)轉(zhuǎn)換函數(shù)：的狀態(tài)轉(zhuǎn)換函數(shù)：q1的的a弧轉(zhuǎn)換集弧轉(zhuǎn)換集q1a=-closure( f(2，3,a) ) =-closure(2)= 2將將2作為新狀態(tài)作為新狀態(tài), 并令并令q2=2 q1的的b弧轉(zhuǎn)換集弧轉(zhuǎn)換集q1b=-closure( f(2，3,b) ) =-closure(4)= 4將將4作為新狀態(tài)作為新狀態(tài), 并令并令q3=4 q1的的c弧轉(zhuǎn)換集弧轉(zhuǎn)換集q1c=-closure(f(2，

40、3,c)=-closure(3,4)=3,4將將3，4作為新狀態(tài)作為新狀態(tài), 并令并令q4=3,4至此，得到有關(guān)開始狀態(tài)至此，得到有關(guān)開始狀態(tài)q1的全部狀態(tài)轉(zhuǎn)換函數(shù)。的全部狀態(tài)轉(zhuǎn)換函數(shù)。 f(q1, a ) =q2 ， f(q1, b ) = q3，f(q1, c) = q41234aaaccb2021-10-1537接下來，計算狀態(tài)接下來，計算狀態(tài)q2、q3、q4的有關(guān)狀態(tài)轉(zhuǎn)換函數(shù)如下：的有關(guān)狀態(tài)轉(zhuǎn)換函數(shù)如下：f(q2, a ) = 2=q2 , f(q2, b ) = 4=q3 , f(q2,c ) = f(q3,a ) = , f(q3,b ) = , f(q3,c ) = f(q4,

41、a ) = ，f(q4, b ) =，f(q4, c ) = 3,4= q4 計算到此，不再有新狀態(tài)出現(xiàn)。計算到此，不再有新狀態(tài)出現(xiàn)。 1234aaaccb2021-10-1538 4）根據(jù)上面求出的各個狀態(tài)確定終結(jié)狀態(tài)集）根據(jù)上面求出的各個狀態(tài)確定終結(jié)狀態(tài)集Z=p| p Z ， 其中其中p為為M的每個狀態(tài)子集。的每個狀態(tài)子集。因為因為q0 =1,4、q1 = 2,3、q2=2、q3=4、q4=3,4，而而Z=4，q0、q3、q4與與Z相交不為空，所以確定終結(jié)狀態(tài)集相交不為空，所以確定終結(jié)狀態(tài)集 Z= q0, q3 , q42021-10-1539最后最后,我們得到確定的有窮自動機如下：我們得

42、到確定的有窮自動機如下：DFA M= (q0, q1 , q2, q3 , q4,a,b,c, f, q0 , q0, q3 , q4)其中狀態(tài)轉(zhuǎn)換函數(shù)為：其中狀態(tài)轉(zhuǎn)換函數(shù)為：f(q0,a)= q1 f(q1,a)= q2，f(q1,b)= q3，f(q1,c)= q4f(q2,a)= q2，f(q2,b)= q3f(q4, c ) = q4該轉(zhuǎn)換后的自動機的狀態(tài)圖及狀態(tài)轉(zhuǎn)換矩陣如圖該轉(zhuǎn)換后的自動機的狀態(tài)圖及狀態(tài)轉(zhuǎn)換矩陣如圖3.14(a)、(b)所所示。示。 2021-10-1540q0q1q2q3q4aaabbcc圖圖3.14 (a)轉(zhuǎn)換后的轉(zhuǎn)換后的DFA M的狀態(tài)圖的狀態(tài)圖 狀態(tài)狀態(tài) c

43、a b q0 * q1 q1q4 q2 q3 q2 q2 q3 q3 * q4 *q4圖圖3.14(b)轉(zhuǎn)換后的轉(zhuǎn)換后的DFA M的狀態(tài)轉(zhuǎn)換矩陣的狀態(tài)轉(zhuǎn)換矩陣 得到的確定的自動機接收的語言為得到的確定的自動機接收的語言為: : L(M)=a L(M)=am m b | m1 acb | m1 acn n | n1 | n1 與原來不確定的有限自動機接收的語言與原來不確定的有限自動機接收的語言L(ML(M) )一樣。一樣。 2021-10-1541 DFA DFA狀態(tài)數(shù)的最小化狀態(tài)數(shù)的最小化u對于一個對于一個NFA,NFA,當把它確定化后當把它確定化后, ,得到的得到的DFADFA所具有的狀態(tài)數(shù)

44、可所具有的狀態(tài)數(shù)可能并不是最小的。在設計詞法分析程序時，效率是很重要的一能并不是最小的。在設計詞法分析程序時，效率是很重要的一個因素。如果可能的話，我們應該構(gòu)造盡可能小的個因素。如果可能的話，我們應該構(gòu)造盡可能小的DFADFA。u自動機理論中有一個很重要的結(jié)論：自動機理論中有一個很重要的結(jié)論：定理定理3.2 3.2 對于有同一接受集的對于有同一接受集的FAFA，與之等價且具有最小狀態(tài)數(shù)，與之等價且具有最小狀態(tài)數(shù)的的DFADFA在同構(gòu)意義下在同構(gòu)意義下( (即不顧狀態(tài)的命名即不顧狀態(tài)的命名) )是唯一的。是唯一的。u從任何從任何FAFA中都可以得到這個最少狀態(tài)的中都可以得到這個最少狀態(tài)的DFAD

45、FA。 2021-10-1542n 最小狀態(tài)最小狀態(tài)DFA的含義的含義:n 沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài))；n 沒有等價狀態(tài)（不可區(qū)別）。沒有等價狀態(tài)（不可區(qū)別）。n 一個一個DFA可以通過消除多余狀態(tài)和合并等價狀態(tài)轉(zhuǎn)換可以通過消除多余狀態(tài)和合并等價狀態(tài)轉(zhuǎn)換成最小的與之等價的成最小的與之等價的DFA。n 有窮自動機的多余狀態(tài)指：從自動機的開始狀態(tài)出發(fā)，有窮自動機的多余狀態(tài)指：從自動機的開始狀態(tài)出發(fā)，任何輸入串都不能到達的狀態(tài)。任何輸入串都不能到達的狀態(tài)。2021-10-15431 1、可區(qū)分狀態(tài)與等價狀態(tài)、可區(qū)分狀態(tài)與等價狀態(tài)設設s s和和t t是一是一DFA MDFA M的兩個不同

46、狀態(tài)，的兩個不同狀態(tài)，u如果狀態(tài)如果狀態(tài)s,ts,t為某一輸入串為某一輸入串w w所區(qū)分所區(qū)分, ,是指從是指從s,ts,t中之一出發(fā)中之一出發(fā), ,當掃視完當掃視完w w之后到達之后到達M M的終態(tài)的終態(tài), ,但從另一個狀態(tài)出發(fā)但從另一個狀態(tài)出發(fā), ,當掃視完同當掃視完同一個一個w w后而進入非終態(tài)。后而進入非終態(tài)。u如果如果s s和和t t不可區(qū)分不可區(qū)分( (即對任何輸入串即對任何輸入串w,w,當且僅當當且僅當f(s,w)Z,f(t,w)Z),f(s,w)Z,f(t,w)Z),則稱則稱s s和和t t等價。等價。2021-10-1544 C和和F同是終態(tài)同是終態(tài), C和和F讀入讀入a都到

47、達都到達C,讀入讀入b都到達都到達E. C和和F等價等價(不可區(qū)別不可區(qū)別)；E和和D同是終態(tài)同是終態(tài),讀入讀入a均到達均到達F,讀入讀入b均到均到達達D，因此，因此E和和D等價（不可區(qū)別）等價（不可區(qū)別）。CDBAEFSbaaaaabbbbbbaa 而而A，B是是可區(qū)別的可區(qū)別的。因為。因為A和和B可可由輸入由輸入b來區(qū)別，對輸來區(qū)別，對輸入入b，A走到非接受狀態(tài)走到非接受狀態(tài)B B，而，而B走到接受狀態(tài)走到接受狀態(tài)D。 判定兩個判定兩個狀態(tài)狀態(tài)p p和和q q不等價，只要找到一個不等價，只要找到一個w w*， 使使 （p,w)p,w) F F 且且 （q,w) q,w) F F，或，或者相

48、反。者相反。 W W稱為判別序列。稱為判別序列。2021-10-15452 2、DFADFA化簡算法化簡算法( (分割法分割法) )基本思路基本思路: :將將M M的狀態(tài)集的狀態(tài)集K K逐步進行劃分逐步進行劃分, ,以期最后按上述狀態(tài)以期最后按上述狀態(tài)的等價關(guān)系將的等價關(guān)系將K K劃分為劃分為r(rK)r(rK)個互不相交的子集個互不相交的子集, ,使得屬使得屬于同一子集中的任何兩個狀態(tài)都是等價的于同一子集中的任何兩個狀態(tài)都是等價的, ,而屬于不同子集的而屬于不同子集的任意兩個狀態(tài)都是可區(qū)分的。任意兩個狀態(tài)都是可區(qū)分的。設設DFA M= DFA M= （K K，f f，q q0 0，Z Z），

49、化簡算法如下：），化簡算法如下：1 1）將）將M M的狀態(tài)集的狀態(tài)集K K劃分成終態(tài)集劃分成終態(tài)集Z Z和非終態(tài)集和非終態(tài)集K KZ Z，記為，記為=Z, =Z, K KZ Z 2021-10-15462）設當前的劃分）設當前的劃分 中已含有中已含有m個子集，即個子集，即 =I1,I2,I m ，其，其中，屬于不同子集的狀態(tài)是可區(qū)分的，而屬于同一子集的諸狀中，屬于不同子集的狀態(tài)是可區(qū)分的，而屬于同一子集的諸狀態(tài)則是待區(qū)分的。即需對每一子集態(tài)則是待區(qū)分的。即需對每一子集Ii=Si1,Si2,Sin中的各個狀態(tài)中的各個狀態(tài)逐一檢查，看能否對它們再進行區(qū)分。逐一檢查，看能否對它們再進行區(qū)分。設設Si

50、p和和S i q是子集是子集Ii中的兩個狀態(tài)，若有某個中的兩個狀態(tài)，若有某個a，使，使f( Sip, a)= S j u、f( S i q, a)=S k v ，而狀態(tài)，而狀態(tài)S j u和和S k v屬于不同的子集屬于不同的子集I j和和I k，故故S j u與與S k v為某一為某一w所區(qū)分，從而所區(qū)分，從而Sip和和S i q必為必為aw所區(qū)分，故應所區(qū)分，故應將將Sip和和S i q分為兩個子集。分為兩個子集。2021-10-15473）重復第）重復第2步，直到所有子集都不能細分為止。步，直到所有子集都不能細分為止。4）將每個子集中的等價狀態(tài)合并成一個等價代表狀態(tài)。將狀）將每個子集中的等

51、價狀態(tài)合并成一個等價代表狀態(tài)。將狀態(tài)函數(shù)態(tài)函數(shù)(矩陣矩陣)中的所有狀態(tài)用相應的等價代表狀態(tài)表示。從狀中的所有狀態(tài)用相應的等價代表狀態(tài)表示。從狀態(tài)圖上看，要將一個子集中的等價狀態(tài)結(jié)點合并成一個結(jié)點。態(tài)圖上看，要將一個子集中的等價狀態(tài)結(jié)點合并成一個結(jié)點。2021-10-1548正規(guī)表達式與正規(guī)集正規(guī)表達式與正規(guī)集 u詞法分析程序自動生成系統(tǒng)的實現(xiàn)涉及正規(guī)表達式和有限自詞法分析程序自動生成系統(tǒng)的實現(xiàn)涉及正規(guī)表達式和有限自動機理論。動機理論。u假設有字母表假設有字母表=0，1，那么，字母表上的每個元素都是正，那么，字母表上的每個元素都是正規(guī)表達式，這樣的正規(guī)表達式表示的語言只有一個句子。規(guī)表達式，這樣

52、的正規(guī)表達式表示的語言只有一個句子。例如，例如，0是一個正規(guī)表達式，表示的語言為是一個正規(guī)表達式，表示的語言為0，該語言只有一，該語言只有一個句子個句子0。u如果想表示更加復雜的語言，就必須使用運算符組成復雜的如果想表示更加復雜的語言，就必須使用運算符組成復雜的正規(guī)表達式，這一點很像用加減乘除運算符構(gòu)造算術(shù)表達式。正規(guī)表達式，這一點很像用加減乘除運算符構(gòu)造算術(shù)表達式。u在正規(guī)表達式中可使用的運算符有連接、或和閉包在正規(guī)表達式中可使用的運算符有連接、或和閉包。 2021-10-1549n 每一程序設計語言都有它自己的字符集每一程序設計語言都有它自己的字符集。語言中的每。語言中的每一單詞或是一單詞

53、或是上的單個字符上的單個字符, ,或是或是上的字符上的字符”按一定方按一定方式式”( (即進行一定的連接即進行一定的連接, ,或及閉包運算或及閉包運算) )組成的字符串。組成的字符串。n 如果把每一類單詞均視為一種語言如果把每一類單詞均視為一種語言, ,那么每一類單詞都可那么每一類單詞都可以用一個正規(guī)式來描述以用一個正規(guī)式來描述, ,而每一類單詞中的全體單詞也就而每一類單詞中的全體單詞也就組成了相應的正規(guī)集。組成了相應的正規(guī)集。n 正規(guī)式正規(guī)式( (正規(guī)表達式正規(guī)表達式) )是定義正規(guī)集的數(shù)學工具，是說明是定義正規(guī)集的數(shù)學工具，是說明單詞的模式單詞的模式(pattern)(pattern)的一種重要表示法（記號）。正規(guī)的一種重要表示法（記號）。正規(guī)式描述的集合稱作正規(guī)集。式描述的集合稱作正規(guī)集。正規(guī)表達式與正規(guī)集的定義正規(guī)表達式與正規(guī)集的定義2021-10-1550設設是有窮字母表，在是有窮字母表，在上的