1、Compiler Construction Principles 第三章第三章 詞法分析詞法分析 詞法分析程序功能詞法分析程序功能 詞法分析程序的編寫方法詞法分析程序的編寫方法 正規(guī)文法與有窮自動(dòng)機(jī)正規(guī)文法與有窮自動(dòng)機(jī) 正規(guī)式與有窮自動(dòng)機(jī)正規(guī)式與有窮自動(dòng)機(jī) 語(yǔ)言單詞符號(hào)的兩種定義方式語(yǔ)言單詞符號(hào)的兩種定義方式Compiler Construction Principles 詞法分析的任務(wù)是對(duì)字符串表示的源程詞法分析的任務(wù)是對(duì)字符串表示的源程 序從左到右地進(jìn)行掃描和分解，根據(jù)語(yǔ)言序從左到右地進(jìn)行掃描和分解，根據(jù)語(yǔ)言 的詞法規(guī)則識(shí)別出一個(gè)一個(gè)具有獨(dú)立意義的詞法規(guī)則識(shí)別出一個(gè)一個(gè)具有獨(dú)立意義 的單詞

2、符號(hào)。的單詞符號(hào)。輸入：源程序輸入：源程序輸出：?jiǎn)卧~符號(hào)輸出：?jiǎn)卧~符號(hào) 3.1 詞法分析程序的功能詞法分析程序的功能 Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 關(guān)鍵字關(guān)鍵字 也稱基本字，例如，也稱基本字，例如，C語(yǔ)言中語(yǔ)言中 的的if，else，while, do等等, 這些字在語(yǔ)言中具這些字在語(yǔ)言中具有固定的意義，一般不作為標(biāo)識(shí)符使用。有固定的意義，一般不作為標(biāo)識(shí)符使用。標(biāo)識(shí)符標(biāo)識(shí)符 表示各種名字，如變量名、常表示各種名字，如變量名、常 量名、數(shù)組名和函數(shù)名等。量名、數(shù)組名和函數(shù)名等。語(yǔ)言的語(yǔ)言的單詞符號(hào)單

3、詞符號(hào)是指語(yǔ)言中具有獨(dú)立是指語(yǔ)言中具有獨(dú)立 意義的最小語(yǔ)法單位意義的最小語(yǔ)法單位 。Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 常數(shù)常數(shù) 各種類型的常數(shù)，如整型常數(shù)各種類型的常數(shù)，如整型常數(shù) 125、實(shí)型常數(shù)、實(shí)型常數(shù)0.718、布爾型常數(shù)、布爾型常數(shù)TRUE 等等 。運(yùn)算符運(yùn)算符 如、如、*、/、等。、等。 分界符分界符 如如 ，、；、（、）、：等，、；、（、）、：等 。Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 詞法分析程序

4、輸出單詞的形式詞法分析程序輸出單詞的形式 詞法分析程序所輸出的單詞符號(hào)詞法分析程序所輸出的單詞符號(hào)通常表示成如下的二元組：通常表示成如下的二元組：（單詞種別，單詞自身的值）（單詞種別，單詞自身的值）Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 單詞種別單詞種別 單詞種別表示單詞的種類，它是單詞種別表示單詞的種類，它是語(yǔ)法分析需要的信息。語(yǔ)法分析需要的信息。為處理方便為處理方便通常讓每種單詞對(duì)通常讓每種單詞對(duì)應(yīng)一個(gè)整數(shù)碼。應(yīng)一個(gè)整數(shù)碼。Compiler Construction Principles 3.1.2 單

5、詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 常數(shù)常數(shù): : 可統(tǒng)歸為一種，也可按類型可統(tǒng)歸為一種，也可按類型 （整型、實(shí)型、布爾型等）分種（整型、實(shí)型、布爾型等）分種。關(guān)鍵字關(guān)鍵字: : 可將其全體視為一種，也可可將其全體視為一種，也可 以一字一種。以一字一種。標(biāo)識(shí)符標(biāo)識(shí)符: : 一般統(tǒng)歸為一種。一般統(tǒng)歸為一種。運(yùn)算符和界符運(yùn)算符和界符: : 可采用一符一種的分法，可采用一符一種的分法，也可以統(tǒng)歸為一種。也可以統(tǒng)歸為一種。Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 單詞自身的值單詞自身的值 一個(gè)種別只含一個(gè)

6、單詞符號(hào) 一個(gè)種別含有多個(gè)單詞符號(hào) (1) 對(duì)于標(biāo)識(shí)符其自身值是標(biāo)識(shí)符自 身的字符串； (2) 常數(shù)自身值是常數(shù)本身的二進(jìn)制 數(shù)值。 Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 (3) 用指向某類表格一個(gè)特定項(xiàng)目指 針值來區(qū)分同類中不同的單詞。例如, 對(duì)于標(biāo)識(shí)符用它在符號(hào)表的入口指針作為它自身值; 常數(shù)用它在常數(shù)表的入口指針作為它自身的值。 Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 常數(shù)自身的值用常數(shù)本身的值 (轉(zhuǎn)變成 標(biāo)準(zhǔn)二

7、進(jìn)制形式) 表示；對(duì)例子: if (a1) b =100；假定: 基本字、運(yùn)算符和界符都是一符一種； 標(biāo)識(shí)符自身的值用自身的字符串表示；Compiler Construction Principles 3.1.2 單詞符號(hào)及輸出單詞的形式單詞符號(hào)及輸出單詞的形式 假設(shè): 標(biāo)識(shí)符的種別編碼為整數(shù)10 ； 常數(shù)的種別編碼為整數(shù)11 ； 基本字if種別編碼為2 ； 賦值號(hào)的種別編碼為17 ； 大于號(hào)的種別編碼為23 ； 分號(hào)的種別編碼為26 ； 左括號(hào)的種別編碼為29 ； 右括號(hào)的種別編碼為30 ；則程序段 ： Compiler Construction Principles 3.1.2 單詞符號(hào)及

8、輸出單詞的形式單詞符號(hào)及輸出單詞的形式 if (a1) b =100；在經(jīng)詞法分析程序掃 描后，它所輸出的單詞符號(hào)串是： （2， ） 基本字if （29， ） 左括號(hào) (（10，a） 標(biāo)識(shí)符a（23， ） 大于號(hào) （11，1） 常數(shù) 1（30， ） 右括號(hào) )（10，b） 標(biāo)識(shí)符b（17， ） 賦值號(hào) = （11，100）常數(shù) 100（26, ） 分號(hào) ；Compiler Construction Principles例如while， id，指向i的符號(hào)表入口的指針 ， id，指向j的符號(hào)表入口的指針do， if， id，指向i的符號(hào)表入口的指針 id，指向i的符號(hào)表入口的指針WhileWhi

9、le ij dodo if if ij then then i:i-j elseelse j:=jiCompiler Construction Principles3.1.3 把詞法分析設(shè)計(jì)成一個(gè)獨(dú)立程序把詞法分析設(shè)計(jì)成一個(gè)獨(dú)立程序（1）組織成一遍掃描； （2）作為語(yǔ)法分析和語(yǔ)義分析的子程序原因：-簡(jiǎn)化設(shè)計(jì)-改進(jìn)編譯效率-增加編譯系統(tǒng)的可移植性 字符串表示的源程序詞法分析器字符單詞符號(hào)取下一個(gè)單詞符號(hào)語(yǔ)法分析器Compiler Construction Principles 3.3 單詞符號(hào)的兩種定義方式單詞符號(hào)的兩種定義方式正規(guī)式 以標(biāo)識(shí)符為例: Il|Il|Id 或 Il|lT Tl|d|

10、lT|dT 以標(biāo)識(shí)符為例: l ( l | d )* 正規(guī)文法Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集設(shè)有字母表=a1, a2, an ，在字母表 上的正規(guī)式和它所表示的正規(guī)集可用如 下規(guī)則來定義： 1. 是 上的正規(guī)式，它所表示的正規(guī) 集是 ，即空集 。 2. 是 上的正規(guī)式，它所表示的正規(guī) 集僅含一空符號(hào)串，即。 3. ai是上的一個(gè)正規(guī)式，它所表示的 正規(guī)集是由單個(gè)符號(hào)ai 所組成，即ai。Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集4. 如果 e1和 e2 是上的正規(guī)式，它們所表示的正規(guī)

11、集分別為 L(e1)和L(e2) ，則： (1) e1 | e2是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1 | e2)=L(e1 )L(e2)(2) e1.e2 也是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1e2)=L(e1)L(e2) (3) (e1)*也是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)*)=(L(e1)*Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集 正規(guī)式中包含三種運(yùn)算符：連接“”，或“| |”和閉包“* *”。其中閉包運(yùn)算的優(yōu)先級(jí)最高，連接運(yùn)算次之，或運(yùn)算最低。連結(jié)符“”一般可省略不寫。這三種運(yùn)算符均是左結(jié)合的

12、。 Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集 例1 設(shè)有字母表=a,b ，根據(jù)正規(guī)式與 正規(guī)集的定義，則有： a 和 b是正規(guī)式，相應(yīng)正規(guī)集為2. a | b 是正規(guī)式，相應(yīng)正規(guī)集為3. ab 是正規(guī)式，相應(yīng)正規(guī)集為L(zhǎng)(a)=a , L(b)=b L(a | b )=L(a)L(b)=a ,bL(ab)=L(a)L(b)=ab=abCompiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集4. (a | b)* 是正規(guī)式，相應(yīng)正規(guī)集為 例如， a ,b* 的子集 an bn | n

13、1 就不是一個(gè)正規(guī)集， 不能用正規(guī)式來描述，也不能用正規(guī)文法來描述，只能用上下文無關(guān)法來描述。 需要指出的是，對(duì) a,b*的任一子集不能認(rèn)為是一個(gè)正規(guī)集。 L(a | b)*)= (L(a | b)* =a ,b*=, a, b, aa, ab, ba, bb, Compiler Construction Principles5. ba a*是正規(guī)式，相應(yīng)的正規(guī)集為L(zhǎng)(ba a* )=L(b)L(a a*)=b,ba,baa,baaa, (a | b)*(aa | bb) (a | b)* 是正規(guī)式，相應(yīng)正規(guī)集為即上所有含兩個(gè)相繼a或兩個(gè)相繼b組成的串。L(a | b)*(aa | bb) (

14、a | b)*) =L(a | b)*)L(aa | bb)L(a | b)*) a,b*aa,bba,b*Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集 例2 設(shè)=a,b,c,則 aa*bb*cc* 是上的一個(gè)正規(guī)式 , 它所表示的正規(guī)集： L= abc, aabc, abbc, abcc, aaabc, = ambnck | m, n, k1a+b+c+Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集 例3 設(shè)程序語(yǔ)言字母表是鍵盤字符集合，則程序語(yǔ)言部分單詞符號(hào)可用如下正規(guī)

15、式定義： 關(guān)鍵字 if | else | while | do標(biāo)識(shí)符 l (l | d)* l代表az中任一字母整常數(shù) dd* d代表09中任一數(shù)字關(guān)系運(yùn)算符 = Compiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集如果正規(guī)式 R1 和 R2 描述的正規(guī)集相同, 則我們稱正規(guī)式R1與R2等價(jià)。 記為 R1R2。例如，(a|b)*=(a*b*)* ; b(ab)*=(ba)*bCompiler Construction Principles 3.2.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集正規(guī)式具有如下性質(zhì) :1A | B = B | A (交換律)

16、 2A | ( B | C) = (A | B) | C (結(jié)合律) 3A(BC) = (AB)C (結(jié)合律) 4A(B | C) = AB | AC (分配律) 5(A | B)C = AC | BC (分配律) 6 A | A = A7 A* = AA* | = A | A* = (A | )*8 (A* )* = A*令A(yù) , B 和 C 均為正規(guī)式，則Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式 1. 正規(guī)文法到正規(guī)式的轉(zhuǎn)換對(duì)G=(VN,VT,P,S),存在一個(gè) =VT上的正規(guī)式r : L(r)=L(G) AxB, By

17、 A=xy AxAy A=xy Axy A=xyCompiler Construction Principles例 有正規(guī)文法Gs:SaA|a AaAadAd 試給出該文法生成語(yǔ)言的正規(guī)式。 A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a=a(ad)(ad)=a(ad)+) R=a(ad)Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式2. 正規(guī)式到正規(guī)文法的轉(zhuǎn)換對(duì)上的正規(guī)式r ,存在一個(gè)RG=(VN,VT,P,S)：L(G)=L(r)(1) 令 VT= 。(2) 對(duì)任何正規(guī)式R生成正規(guī)產(chǎn)生式S R(3) 若a和

18、b都是正規(guī)式，對(duì)形如 Aab 的 規(guī)則轉(zhuǎn)換成 AaB 和 Bb 兩規(guī)則， 其中B是新增的非終結(jié)符。Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式(4) 對(duì)已轉(zhuǎn)換的文法中, 形如A a*b 的規(guī) 則，進(jìn)一步轉(zhuǎn)換 成 A aA | b 。 (5) 不斷利用規(guī)則(3)和(4)進(jìn)行變換，直到 每條規(guī)則最多含有一個(gè)終結(jié)符為止。Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式 例1 將 R=(a | b)(aa)*(a | b) 轉(zhuǎn)換成相應(yīng)的 正規(guī)文法 令A(yù)是文法開始符號(hào)，根據(jù)規(guī)則

19、(2)變換為 根據(jù)規(guī)則(3)變換為 A (a | b)(aa)*(a | b)A (a | b)BB (aa)*(a | b)Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式對(duì)B根據(jù)規(guī)則(4)變換為 根據(jù)規(guī)則(3)變換為即前面例2中的文法。A aB | bBB aaB | a | bA aB | bBB aC | a | bC aB A a*bA aA | b轉(zhuǎn)換成B (aa)*(a | b)Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式 例2 將描述標(biāo)識(shí)符的正規(guī)式 R

20、=l ( l | d )* 轉(zhuǎn)換成相應(yīng)的正規(guī)文法令I(lǐng)為文法的開始符號(hào)，根據(jù)規(guī)則(2)有 根據(jù)規(guī)則(3)變換為 根據(jù)規(guī)則(4)變換為 I l ( l | d )* I lT T ( l | d )* I lT T ( l | d )T | Compiler Construction Principles 3.2.2 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式進(jìn)一步變換為 去掉 規(guī)則即前面描述標(biāo)識(shí)符的右線性文法。 I lT T lT | dT | I l | lT T l | d | lT | dT Compiler Construction Principles 3.3 正規(guī)式與有窮自動(dòng)機(jī)正規(guī)式與有窮自動(dòng)

21、機(jī) 有窮自動(dòng)機(jī)是具有離散輸入與輸出系統(tǒng)的一種抽象數(shù)學(xué)模型。 有窮自動(dòng)機(jī)有“確定的”和“非確定的”兩類，確定的有窮自動(dòng)機(jī)和非確定的有窮自動(dòng)機(jī)都能準(zhǔn)確地識(shí)別正規(guī)集。 Compiler Construction Principles 3.3.1 確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)（確定有窮自動(dòng)機(jī)（DFA）一個(gè)確定有窮自動(dòng)機(jī)M是一個(gè)五元組Q是一個(gè)有窮狀態(tài)集合，每一個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有窮輸入字母表，每個(gè)元素稱為一個(gè)輸入字符。M=( Q, , f, S, Z )Compiler Construction Principles 表示當(dāng)前狀態(tài)為qi ，輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)q

22、j , qj 稱為qi 的一個(gè)后繼狀態(tài)。f 是一個(gè)從Q 到Q的單值映射：M=( Q, , f, S, Z )f ( qi , a) = qj (qi , qj Q, a ) 3.3.1 確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)Compiler Construction Principles 單值函數(shù)是指 f(q i, a) 唯一地確定了下一個(gè)要轉(zhuǎn)移的狀態(tài)，即每個(gè)狀態(tài)的所有輸出邊上標(biāo)記的輸入字符不同，見下圖。S1S2S3S4abc 3.3.1 確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)Compiler Construction PrinciplesSQ ，是唯一的一個(gè)初態(tài)。ZQ ，是一個(gè)終態(tài)集。 3.3.1 確定有窮自動(dòng)

23、機(jī)確定有窮自動(dòng)機(jī)M=( Q, , f, S, Z )Compiler Construction Principles 例 設(shè)DFA M=(q0 , q1 , q2,a, b, f , q0 ,q2) 其中 狀態(tài)轉(zhuǎn)換矩陣f ( q0 , a) = q1 f ( q0 , b) = q2 f ( q1 , a) = q1 f ( q1 , b) = q1 f ( q2 , a) = q2 f ( q2 , b) = q1 狀態(tài) 字符 a q0 b q1 q2 q1 q1 q1 q2 q1 q2 Compiler Construction Principles 一個(gè) DFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖

24、。 例中DFA M=(q0 , q1 , q2,a, b, f , q0 ,q2) 的狀態(tài)轉(zhuǎn)換圖如下圖所示。f ( q0 , a) = q1 f ( q0 , b) = q2 f ( q1 , a) = q1 f ( q1 , b) = q1 f ( q2 , a) = q2 f ( q2 , b) = q1 q0q1q2bbbaaaCompiler Construction Principles 對(duì)*中的任何符號(hào)串，若存在一條從初態(tài)結(jié)到終態(tài)結(jié)的道路, 在這條路上所有弧的標(biāo)記連結(jié)成的符號(hào)串等于 , 則稱為DFA M所識(shí)別(或接受)。M所識(shí)別的符號(hào)串的全體記為 L(M) ，稱為DFA M所識(shí)別的

25、語(yǔ)言。 例中的DFA M所識(shí)別的語(yǔ)言為L(zhǎng)(M) = ba*。 q0q1q2bbbaaaCompiler Construction Principlesl例例：證明證明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, baaCompiler Construction PrinciplesDFA的行為很容易用程序來模擬.DFA M=（Q，f，S，Z）的行為的模擬程序Q:=S；

26、c:=getchar;while ceof do Q:=f(Q,c); c:=getchar; ;if K is in Z then return (yes) else return (no)Compiler Construction PrinciplesDFA的確定性表現(xiàn)在1）轉(zhuǎn)換函數(shù)f:QQ是一個(gè)單值函數(shù)，也就是說，對(duì)任何狀態(tài)qkQ，和輸入符號(hào)a，f(qk,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。2）初始狀態(tài)是唯一的Compiler Construction Principles 3.

27、3.2 非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī)（非確定有窮自動(dòng)機(jī)（NFA）一個(gè)非確定有窮自動(dòng)機(jī)M是一個(gè)五元組 其中：Q, , Z 意義同DFA ，f 和 S不同 于DFA 。 M=( Q, , f, S, Z) Compiler Construction Principles (1) 狀態(tài)轉(zhuǎn)換函數(shù)f 不是單值函數(shù),它是一 個(gè)多值函數(shù)：f(qi ,a) =某些狀態(tài)的集合 非確定的有窮自動(dòng)機(jī)還 允許 f(qi ,)=某些狀態(tài)的集合。 由圖可知 f( S1, a)=S1 , S2 , S3 (2) SQ ，是非空初態(tài)集。是非空初態(tài)集。 S1S2S3S4aaca 3.3.2 非確定有窮自動(dòng)機(jī)

28、非確定有窮自動(dòng)機(jī)Compiler Construction Principles其中 例 設(shè)有NFA M=(1,2,3,a,b,f,1,3,2)例中 NFA M 對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩如下表所示。 f (1, a) = 3 f (1 , b) = 1,2 f (2, a) = f (2 , b) = 3 f (3, a) = f (3 , b) = 2 狀態(tài) 字符 a 1 b 2 3 3 1,2 2 3 Compiler Construction Principles例中 NFA M 對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下圖所示。 1abb23bb其中 例 設(shè)有NFA M=(1,2,3,a,b,f,1,3,2)f (

29、1, a) = 3 f (1 , b) = 1,2 f (2, a) = f (2 , b) = 3 f (3, a) = f (3 , b) = 2 Compiler Construction Principles 例中NFA M 所識(shí) 別的語(yǔ)言為 L(M) = b*(b|ab)(bb)*1abb23bb 3.3.2 非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī)Compiler Construction Principles 例中 NFA M ,對(duì)符號(hào)串 =bbb可由3條路來識(shí)別。 由NFA的定義可知，同一個(gè)符號(hào)串 可由多 條路來識(shí)別。 第二條路：狀態(tài)1狀態(tài)1狀態(tài)2； 第一條路：狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)2

30、； 第三條路：狀態(tài)3狀態(tài)2狀態(tài)3狀態(tài)2； 1abb23bbCompiler Construction Principles 事實(shí)上DFA是NFA 的特例, 即對(duì)于每個(gè)NFA M 存在 DFA M ,使 L(M) = L(M)。因此，我們利用有窮自動(dòng)機(jī)構(gòu)造詞法分析程序的方法是從語(yǔ)言單詞的描述中構(gòu)造出非確定的有窮自動(dòng)機(jī)，再將非確定的有窮自動(dòng)機(jī)轉(zhuǎn)化為確定的有窮自動(dòng)機(jī)，并將其化簡(jiǎn)為狀態(tài)最少化的DFA , 然后對(duì)DFA的每一個(gè)狀態(tài)構(gòu)造一小段程序?qū)⑵滢D(zhuǎn)化為識(shí)別語(yǔ)言單詞的詞法分析程序。Compiler Construction Principles對(duì)于一個(gè)NFA，由于狀態(tài)轉(zhuǎn)換函數(shù) f 是一個(gè) 多值函數(shù) ，因

31、此，對(duì)于它們有f ( q, a)=q1 , q2 , q3,qn也就是說，DFA的每一個(gè)狀態(tài)代表NFA狀態(tài) 集合的某個(gè)子集，這個(gè)DFA使用它的狀態(tài)去記 錄在NFA讀入輸入符號(hào)之后可能到達(dá)的所有狀 態(tài)的集合,我們稱此構(gòu)造方法為子集法。 即是NFA狀態(tài)集合的一個(gè)子集，為了將NFA 轉(zhuǎn)換為DFA，把狀態(tài)集合q1 , q2 , q3, qn看作 一個(gè)狀態(tài)A。3.3.3 NFA確定化為DFA的方法Compiler Construction Principles 輸入：一個(gè)NFA N 輸出：一個(gè)接受（識(shí)別）相同語(yǔ)言的DFA M 方法：利用構(gòu)造 閉包的方法將NFA確定化 為DFA。 1. 狀態(tài)集合 I 的

32、閉包的概念。 設(shè)I是NFA N的一個(gè)狀態(tài)子集, closure(I)定義 如 下： (1) 若sI , 則 s closure(I) (2) 若sI ,那么從s出發(fā)經(jīng)過任意條弧而能到達(dá) 的任何狀態(tài) s，都屬于 closure(I) Compiler Construction Principles 由定義可知, closure(I) 表示所有那些從I中的元素出發(fā)經(jīng)過 道路所能到達(dá)的NFA的狀態(tài)所組成的集合, I中任何狀態(tài)也在其中，因?yàn)樗鼈兪峭ㄟ^ 通路到達(dá)自身的。該集合對(duì)DFA來說是一個(gè)狀態(tài)。 3.3.3 NFA確定化為確定化為DFA的方法的方法 Compiler Construction Pri

33、nciples closure(0)=0,1,2,3, 即 0,1,2,3 中的任一狀態(tài)都是從NFA的初態(tài)0出發(fā)， 經(jīng)任意條道路可到達(dá)的狀態(tài)。通過下圖理解狀態(tài)集合 I 的 一閉包。 這個(gè)狀態(tài)集合實(shí)際就是要求的DFA的初態(tài)。0123456789bbCompiler Construction Principlesl2. 狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體J= move(I,a) =f( I,a)=f(I1,a)f(I2,a)f(I3,a)f(I4,a)Compiler Construction Princ

34、iples因?yàn)樵跔顟B(tài)A中只有狀態(tài)0有b的轉(zhuǎn)移，轉(zhuǎn)移 到的狀態(tài)為4和7。若令A(yù)=0,1,2,3,則那么令B= closure(4,7)=4,5,6,7,8,9即是DFA在狀態(tài)A下遇到輸入符號(hào)b，轉(zhuǎn)移到 的后繼狀態(tài)。 J=f(A,b)=f(0,b)f(1,b)f(2,b)f(3,b)=4,70123456789bbCompiler Construction Principles2. 從 NFA N 構(gòu)造 DFA M 的算法 已知 NFA N=( Q, , f, x, y)求 DFA M=( Q, , f , 初態(tài), 終態(tài)集 )開始令Q= 3.3.3 NFA確定化為確定化為DFA的方法的方法 Com

35、piler Construction Principles 求DFA M的初態(tài)CLOSURE(x),并置為無標(biāo)記送入Q; while ( Q中存在一個(gè)無標(biāo)記的狀態(tài) T= s1, s2, s3, , sn ) 標(biāo)記T;for ( 每個(gè)輸入符號(hào)a ) J = f (s1, s2, s3, , sn,a ) U = CLOSURE( J );if (U不在Q中 & U不為空) 置U為無標(biāo)記并送入Q;if (U不為空) 置MT, a =U;if (U中至少有一個(gè)是N的終態(tài)) U為M的終態(tài); /* 求 f ( T, a )=U */= f ( s1, a )f ( s2 , a ) f ( sn

36、, a );Compiler Construction Principles例1 將下圖所示的NFA N確定化。 其等價(jià)DFA的開始狀態(tài)為:A=CLOSURE(X) =X, 0, 1作為未標(biāo)記的狀態(tài)添加到Q中(標(biāo)記的狀態(tài)如A記為A)。 b X, 0, 1 aAQaX12Y3bba0bQ=A(1)Compiler Construction Principlesf(A,a)=CLOSURE(f(X,0,1,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=Af(A,b)=CLOSURE(f(X,0,1,b) =CLOSURE( 0)=0,1=C

37、Compiler Construction Principlesf(A,a)=CLOSURE(f(X,0,1,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,Cf(A,b)=CLOSURE(f(X,0,1,b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BCCompiler Construction Principlesf(A,a)=CLOSURE(f(X,0,1,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,Cf(A,b)=CL

38、OSURE(f(X,0,1,b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC對(duì)A做標(biāo)記Compiler Construction Principlesf(B,a)=CLOSURE(f(0,1,2,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,Cf(B,b)=CLOSURE(f(0,1,2,b) =CLOSURE( 0,3)=0,1,3=D 0,1,2 0,1 0,1,2 0,1 BC(2)在Q中取BCompiler Construction Principlesf(B,a)=CLOSURE

39、(f(0,1,2,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,Df(B,b)=CLOSURE(f(0,1,2,b) =CLOSURE( 0,3)=0,1,3=D 0,1,2 0,1 0,1,2 0,1 BC(2)在Q中取B 0,1,2 0,1,3 0,1,3 DCompiler Construction Principlesf(C,a)=CLOSURE(f(0,1,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,Df(C,b)=CLOSURE(f(0,1,

40、b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC(3)在Q中取C 0,1,2 0,1,3 0,1,3 DCompiler Construction Principlesf(C,a)=CLOSURE(f(0,1,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,Df(C,b)=CLOSURE(f(0,1,b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC(3)在Q中取C 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 Compiler Con

41、struction Principlesf(D,a)=CLOSURE(f(0,1,3,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,Df(D,b)=CLOSURE(f(0,1,3,b) =CLOSURE( 0,Y)=0,1,Y=E 0,1,2 0,1 0,1,2 0,1 BC(3)在Q中取D 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 Compiler Construction Principlesf(D,a)=CLOSURE(f(0,1,3,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0,

42、 1 aAQaX12Y3bba0bQ=A,B,C,D,Ef(D,b)=CLOSURE(f(0,1,3,b) =CLOSURE( 0,Y)=0,1,Y=E 0,1,2 0,1 0,1,2 0,1 BC(3)在Q中取D 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 0,1,Y E 0,1,2 0,1,Y 標(biāo)記D,將E加入QCompiler Construction Principlesf(E,a)=CLOSURE(f(0,1,Y,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,D,Ef(E,b)=CLOSURE(f(

43、0,1,Y,b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC(4)在Q中取E 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 0,1,Y E 0,1,2 0,1,Y 未增加新的狀態(tài),且已無其它狀態(tài)可處理Compiler Construction Principlesf(E,a)=CLOSURE(f(0,1,Y,a) =CLOSURE( 0, 2)=0,1,2=Bb X, 0, 1 aAQaX12Y3bba0bQ=A,B,C,D,Ef(E,b)=CLOSURE(f(0,1,Y,b) =CLOSURE( 0)=0,1=C 0,1,2 0,1 0,

44、1,2 0,1 BC(4)在Q中取E 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 0,1,Y E 0,1,2 0,1,Y 0,1,2 0,1 Q已無其它狀態(tài)可處理Compiler Construction PrinciplesABCDEaaaaabbbbbb X, 0, 1 0, 1, Y 0, 1, 3 0, 1 0, 1, 2 a 0, 1, 2 0 ,1, 2 0, 1 0, 1, 2 0, 1 0, 1, Y 0, 1 EDCBAQ 0, 1, 3 0, 1, 2 0, 1, 2 Compiler Construction Principles例2 將下面的NFA N確

45、定化。01436578910abbb2aCompiler Construction Principles例3 將下面的NFA N確定化。 首先確定其初態(tài) ,命名為0狀態(tài) QdlX1,2,Y1,2,Y2,Y2,Y2,Y2,Y2,Y0210 =CLOSURE(X)=XX2Y1lld02l1llddCompiler Construction Principles例4 將下面的NFA N確定化。 首先確定其初態(tài) ,命名為0狀態(tài) Q10X1,2,Y1,2,Y2,Y2,Y2,Y0210 =CLOSURE(X)=XX2Y101010121Compiler Construction Principles 3.

46、3.4 DFA的化簡(jiǎn)的化簡(jiǎn) 1. DFA的化簡(jiǎn) 所謂一個(gè)DFA M 的化簡(jiǎn)是指尋找一個(gè)狀態(tài)數(shù)比 M 少的 DFA M ，使得 L(M)=L(M) 。 (1) 沒有多余狀態(tài)。化簡(jiǎn)了的DFA滿足兩個(gè)條件:(2) 它的狀態(tài)集中沒有兩個(gè)狀態(tài)是 互相等價(jià)的。 Compiler Construction Principles 所謂有窮自動(dòng)機(jī)的多余狀態(tài)是指從該自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的狀態(tài)。 3.3.4 DFA的化簡(jiǎn)的化簡(jiǎn) 2. 多余狀態(tài)Compiler Construction Principles3.等價(jià)狀態(tài) 設(shè) DFA M(Q,f, S0, F), s, t Q ，若對(duì)任何 *, f

47、 (s , )F 當(dāng)且僅當(dāng)f (t , )F ，則稱狀態(tài) s 和 t 是等價(jià)的。 例如，終態(tài)與非終態(tài)是可區(qū)別的。因?yàn)榻K態(tài)有一條到達(dá)自身的道路，而非終態(tài)沒有到達(dá)終態(tài)的道路。 如果 s 和 t 不等價(jià), 則稱 s 和 t 是可區(qū)別的。Compiler Construction Principles5.化簡(jiǎn)方法 一致性條件: 狀態(tài)s和t必須同時(shí)為 終態(tài)或非終態(tài)。 4.兩個(gè)狀態(tài)等價(jià)的條件: 蔓延性條件: 對(duì)于所有輸入符號(hào)a, 狀態(tài) s 和 t 必須轉(zhuǎn)到等價(jià)的狀態(tài)里。輸入：一個(gè)DFA M 。 輸出：接受與M相同語(yǔ)言的DFA M ， 且其狀態(tài)數(shù)最少。 Compiler Construction Princ

48、iples 無多余狀態(tài)下把無多余狀態(tài)下把M的狀態(tài)集的狀態(tài)集 Q 分劃分劃成一些不相交的子集，使得每個(gè)子集中成一些不相交的子集，使得每個(gè)子集中任何兩個(gè)狀態(tài)是等價(jià)的，而任何兩個(gè)屬任何兩個(gè)狀態(tài)是等價(jià)的，而任何兩個(gè)屬于不同子集的狀態(tài)都是可區(qū)別的。于不同子集的狀態(tài)都是可區(qū)別的。化簡(jiǎn)方法化簡(jiǎn)方法: : 然后在每個(gè)子集中任取一個(gè)狀態(tài)作然后在每個(gè)子集中任取一個(gè)狀態(tài)作“代表代表”, 而刪去子集中其余狀態(tài)而刪去子集中其余狀態(tài), 并把并把射向其余狀態(tài)的箭弧都改作射向作射向其余狀態(tài)的箭弧都改作射向作“代代表表”的狀態(tài)中。的狀態(tài)中。 Compiler Construction PrinciplesA,F,GI,L,MW

49、,ZE,H,KO,R,T,XCompiler Construction PrinciplesAMWHTCompiler Construction Principles下面給出化簡(jiǎn)算法的具體執(zhí)行步驟下面給出化簡(jiǎn)算法的具體執(zhí)行步驟: 1. 將將DFA M的狀態(tài)集的狀態(tài)集Q分成兩個(gè)子集：終分成兩個(gè)子集：終態(tài)集態(tài)集F和非終態(tài)集和非終態(tài)集F，形成初始分劃形成初始分劃。 2. 對(duì)對(duì)使用如下方法建立新分劃使用如下方法建立新分劃NEW： (1) 把把G分劃成新的子集，使得分劃成新的子集，使得G的兩個(gè)的兩個(gè)狀態(tài)狀態(tài)s和和t屬于同一子集，當(dāng)且僅當(dāng)對(duì)任何屬于同一子集，當(dāng)且僅當(dāng)對(duì)任何輸入符號(hào)輸入符號(hào)a ，狀態(tài)狀態(tài)s和

50、和t轉(zhuǎn)換到的狀態(tài)都屬轉(zhuǎn)換到的狀態(tài)都屬于于的同一子集。的同一子集。 對(duì)對(duì)的每個(gè)狀態(tài)子集的每個(gè)狀態(tài)子集G: Compiler Construction Principles 用用G分劃出的所有新子集替換分劃出的所有新子集替換G, 形形 成新的分劃成新的分劃NEW； 如果如果NEW，則執(zhí)行第則執(zhí)行第4步；否則令步；否則令 NEW，重復(fù)第重復(fù)第2步。步。 分劃結(jié)束后，對(duì)分劃中的每個(gè)狀態(tài)子集，分劃結(jié)束后，對(duì)分劃中的每個(gè)狀態(tài)子集，選出一個(gè)狀態(tài)作代表，而刪去其它一切選出一個(gè)狀態(tài)作代表，而刪去其它一切等價(jià)的狀態(tài)，并把射向其它狀態(tài)的箭弧等價(jià)的狀態(tài)，并把射向其它狀態(tài)的箭弧改為射向這個(gè)作為代表的狀態(tài)。改為射向這個(gè)作

51、為代表的狀態(tài)。Compiler Construction Principles例例1. 將右面的將右面的DFA最小化最小化 初始分劃初始分劃=(A,B,C,DE) A,B,C,Da=B分析分析 由圖可知，給定由圖可知，給定的的DFA中無多余狀態(tài)。中無多余狀態(tài)。 A,B,C,Db=C,D,E=(A,B,CDE) A,B,Ca=BA,B,Cb=C,D=(A,CBDE) A,Ca=BA,Cb=C=(A,CBDE) ABCDEaaaaabbbbbEDBAaaaabbbbCompiler Construction Principles例例2. 將右面的將右面的DFA M最小化最小化 1,2l =2 =(

52、1,20) 分析分析 由圖可知，由圖可知，給定的給定的DFA無多無多余狀態(tài)。余狀態(tài)。 初始分劃初始分劃=(1,20) 1,2d =2 02llldd1d01llCompiler Construction Principles 3.4.1 由正規(guī)式由正規(guī)式R構(gòu)造構(gòu)造NFA 輸入：字母表上的正規(guī)式R 輸出：識(shí)別(接受)語(yǔ)言L(R)的NFA N 引進(jìn)初始結(jié)點(diǎn)X和終止結(jié)點(diǎn)Y，把R 表示成拓廣轉(zhuǎn)換圖2. 分析R的語(yǔ)法結(jié)構(gòu)，用如下規(guī)則對(duì)R 中的每個(gè)基本符號(hào)構(gòu)造NFA。 方法：XYRCompiler Construction Principles(1) R=, 構(gòu)造NFA如圖所示。 (2) R= , 構(gòu)造N

53、FA如圖所示。 (3) R= a (a), 構(gòu)造NFA如圖所示。 XYXYXYa 3.4.1 由正規(guī)式由正規(guī)式R構(gòu)造構(gòu)造NFA Compiler Construction Principles (4) 若R是復(fù)合正規(guī)式，則按下圖的轉(zhuǎn)換規(guī)則 對(duì)R進(jìn)行分裂和加進(jìn)新結(jié), 直至每個(gè)邊上 只留下一個(gè)符號(hào)或 為止。 對(duì)于代換為ABr1r2ACBr1r2對(duì)于ABr1| r2代換為對(duì)于代換為ABr1*ABr1r2ACBr1 3.4.1 由正規(guī)式由正規(guī)式R構(gòu)造構(gòu)造NFA Compiler Construction Principles3. 整個(gè)分裂過程中, 所有新結(jié)均采用不同 的名字，保留X，Y為全圖唯一初態(tài)結(jié)

54、 和終態(tài)結(jié)。 3.4.1 由正規(guī)式由正規(guī)式R構(gòu)造構(gòu)造NFA Compiler Construction Principles 例1 試構(gòu)造識(shí)別語(yǔ)言R = (a | b)*abb 的NFA N, 使 L(N)=L(R)。首先將R表示成如下拓廣轉(zhuǎn)換圖 XY(a | b)*abb從左到右分裂RX12Y(a | b)*3bbaX12Y3bba0ba 3.4.1 由正規(guī)式由正規(guī)式R構(gòu)造構(gòu)造NFA Compiler Construction Principles 例2 試構(gòu)造識(shí)別標(biāo)識(shí)符的NFA，描述標(biāo)識(shí)符的正 規(guī)式R= l ( l | d )*首先將R表示成如下拓廣轉(zhuǎn)換圖 XYl (l | d)*從左到右

55、分裂RX2Y1lld 3.4.1 由正規(guī)式R構(gòu)造NFA Compiler Construction Principles 例3 試構(gòu)造正規(guī)式 R= 0 ( l* )* | 01 的NFA。首先將R表示成如下拓廣轉(zhuǎn)換圖 XY01*從左到右分裂RX2Y101首先利用正規(guī)式的等價(jià)性化簡(jiǎn)正規(guī)式 ( l* )*=1* R=01* | 01=0 (1* | 1) =01*( A* )*=A* A | A*=A* 3.4.1 由正規(guī)式R構(gòu)造NFA Compiler Construction Principles 3.4.2 有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換 1. 在 M 的轉(zhuǎn)換圖上添加兩個(gè)結(jié)點(diǎn)： X 結(jié)和Y結(jié)。從X

56、結(jié)用連線連結(jié)到M的所有初態(tài)結(jié)點(diǎn)，從 M 的所有終態(tài)結(jié)點(diǎn)用連線連結(jié)到 Y 結(jié)，從而構(gòu)成一新的非確定有窮自動(dòng)機(jī) M，它只有一個(gè)初態(tài)結(jié) X和一個(gè)終態(tài)結(jié)Y。顯然，L(M)=L(M)。即，這兩個(gè)NFA是等價(jià)的。 Compiler Construction Principles 2. 逐步消去M中的其它結(jié)點(diǎn)，直至只剩下X，Y結(jié)點(diǎn)。在消除結(jié)點(diǎn)過程中，逐步用正規(guī)式來標(biāo)記相應(yīng)的箭弧。 消除結(jié)點(diǎn)的過程是很直觀的，只需反復(fù)使用下圖的替換規(guī)則即可。 Compiler Construction Principles對(duì)于代換為ABr1r2ACBr1r2對(duì)于ABr1| r2代換為代換為ABr1r2*r3ABr1r2對(duì)于AC

57、Br1r3r2Compiler Construction Principles例例1. 設(shè)有窮自動(dòng)機(jī)的狀態(tài)圖如圖所示。設(shè)有窮自動(dòng)機(jī)的狀態(tài)圖如圖所示。 SUVZ110001試求該自動(dòng)機(jī)識(shí)別語(yǔ)言的正規(guī)式。試求該自動(dòng)機(jī)識(shí)別語(yǔ)言的正規(guī)式。 SUZ1100XvY10（a）XszY10100101(b)R=(10|01)(10|01)* X(c)*)01|10)(01|10(YCompiler Construction Principles3.5 正規(guī)文法與有窮自動(dòng)機(jī)正規(guī)文法與有窮自動(dòng)機(jī)l前面提到程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)可用喬前面提到程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)可用喬母斯基母斯基3型文法型文法正規(guī)文法來描述正規(guī)文

58、法來描述l對(duì)于正規(guī)文法所描述的語(yǔ)言可用一種有窮對(duì)于正規(guī)文法所描述的語(yǔ)言可用一種有窮自動(dòng)機(jī)來識(shí)別自動(dòng)機(jī)來識(shí)別l下面分別就左線性正規(guī)文法下面分別就左線性正規(guī)文法/右線性正規(guī)文右線性正規(guī)文法給出構(gòu)造相應(yīng)有窮自動(dòng)機(jī)的方法法給出構(gòu)造相應(yīng)有窮自動(dòng)機(jī)的方法Compiler Construction Principles3.5.13.5.1右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換則相應(yīng)的有窮自窮自動(dòng)機(jī)則相應(yīng)的有窮自窮自動(dòng)機(jī) M = (Q , , f , q0 , Z )1. 令令 Q= VND (D VN) Z=D = VT q0=S2. 對(duì)對(duì)G中每一形中每一形 AaB (A ,BVN

59、 ,aVT) 的產(chǎn)生式的產(chǎn)生式 , 令令 f (A , a)=B設(shè)給定了一個(gè)右線性正規(guī)文法設(shè)給定了一個(gè)右線性正規(guī)文法 G = (VN ,VT , P , S) /a= AB令令f (A , )=B AaBAaCompiler Construction Principles3. 對(duì)對(duì)G中每一形如中每一形如Aa(AVN ,aVT) 的產(chǎn)生式的產(chǎn)生式, 令令 f (A , a)=D4. 對(duì)對(duì)G中每一形如中每一形如A (AVN )的產(chǎn)生的產(chǎn)生 式式, 令令A(yù)為接受狀態(tài)或令為接受狀態(tài)或令 f (A , )=DCompiler Construction Principles例例1 構(gòu)造下述文法構(gòu)造下述文法

60、GZ的有窮自動(dòng)機(jī)。的有窮自動(dòng)機(jī)。 其狀態(tài)圖如圖其狀態(tài)圖如圖(a)或或(b)所示。所示。 Z0AA0A | 0BB1A | Compiler Construction Principles M = (Q , , f , q0 , Z ) G = (VN ,VT , P , S) M=( VND, VT ,f, Z, D)M=( Z,A,B,D, 0,1),f, Z, D)f =? 根據(jù)規(guī)則來確定Compiler Construction Principlesf(Z,0)=A f(Z,1)= f(z, )= f(A,0)=A,B f(A,1)= f(A, )=f(B,0)= f(B,1)=A f(B, )