【正文】 |α) = L(α) ∴ α|α =α ㈣ 正規(guī)式滿足下列關(guān)系 ①交換律： α|β = β|α ② 結(jié)合律： α|(β|γ) = (α|β)|γ， α(βγ) = (αβ) γ ③ 分配律： α(β|γ) = αβ|αγ， (β|γ)α = βα|γα ④ εα = αε= α ㈤ 例 設(shè) α =a|b|……|z ， β = 0|1|……|9 。 ?s0∈ S，是唯一的一個初態(tài)。,39。) = f(0, 39。) = f(1, 39。 ㈢ DFA M可用一個（確定的）狀態(tài)轉(zhuǎn)換圖表示 例識別二進(jìn)制數(shù)的 DFA可用（確定的）狀態(tài)轉(zhuǎn)換圖表示如下： 狀態(tài) /字符 39。 0 1 1 1 1 1 接上例 0 , 1 0 , 1 ㈣ 字 α可為 DFA M識別 ?對于一個字 α，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的路徑，且路徑上的所有弧的標(biāo)記依序連接成的字為 α，則稱 α可為DFA M所識別或接受。路徑上的標(biāo)記依次連接為 101，則稱 α= 101可為 M所識別或接受。 ?f是一個從 S Σ*到 S的子集映照，即 f： S Σ*→2 S（多值函數(shù)） 2S表示冪集，若 S={0， 1}，則 2S ={{ }， {0}， {1}， {0， 1}}。 例某一非確定有限自動機(jī) M=（ {1， 2， 3， 4， 5， 6}， {a， b}， f， {1， 2}， {3}） 其中 f的定義為： f(1,a)={4， 5}、 f(5， ε)={6}、 f(6， ε)={2}、 f(2， ab)={3} 其余情況 f(si， α) = { }（ α∈ Σ*， si∈ S） ㈡ NFA M可用一個（非確定的）狀態(tài)轉(zhuǎn)換圖表示 ⑤ ε ⑥ a ε ① ② ab a ④ ㈢ 字 α可為 NFA M識別 ?對于 Σ*中的一個字 α，若在 NFA M中存在一條從某一初態(tài)到某一終態(tài)的路徑，且路徑上的所有標(biāo)記依序連接成的字為 α，則稱 α可為 NFA M所識別或接受。若 L(M) = L(M39。使得 L(M)=L(M39。 ① ab ② ① a ③ b ② b ① a|b ② ① ② a ① a* ② ① ε ③ ε ② a V 例，已知正規(guī)式 (a|b)*(aa|bb)構(gòu)造它的 NFA。也屬于 ε_CLOSURE(I)。 2. p_end←1 //表尾指針 3. I[1]←CLOSURE({X}) 4. while p_cur≤p_end 5. for i←1 to n //設(shè) ∑={x1,x2,…,x n} 6. if IXi[p_cur]≠{ } and IXi[p_cur] I[1..p_end] then 7. p_end←p_end+1 8. I[p_end]←I Xi[p_cur] 9. end if 10. end for 11. p_cur←p_cur+1 12. end while 13. end procedure I Ia Ib {X,1,2} {1,3,2} {1,4,2} {1,3,2} {1,3,Y,2} {1,4,2} {1,4,2} {1,3,2} {1,Y,4,2} {1,3,Y,2} {1,3,Y,2} {1,4,2} {1,Y,4,2} {1,3,2} {1,Y,4,2} 根據(jù)上述算法對 NFA M進(jìn)行確定化。 ?ε_CLOSURE({X})視為 DFA M39。 ?將 I、 Ia、 Ib、 …… 視為 DFA M?狀態(tài)轉(zhuǎn)換矩陣，即函數(shù) f。 ① a a a a ○ 0 b a b b ② b b 詞法分析器的自動生成 輸入正規(guī)式（構(gòu)詞規(guī)則），經(jīng)自動生成器加工，其結(jié)果為DFA。 ③ NFA M確定化 ④重新標(biāo)記，構(gòu)造 DFA M39。z39。939。=39。,39。(39。39。,NUL}、 end(39。,NUL)、 real (39。,字符串 ) ?無符號整常數(shù)： (39。,NUL)、 +(39。,NUL)、++(39。,NUL)、 。(39。39。=39。39。 狀態(tài) /字符 α β = + * , 。 ?在無法前進(jìn)時，若發(fā)現(xiàn)當(dāng)前狀態(tài)為終態(tài)，則認(rèn)為識別出一個單詞，反之出錯，即 Token數(shù)組所保存的字符串不構(gòu)成一個單詞，而是源程序中的一個錯誤詞形。首字符為字母的是標(biāo)識符，首字符為數(shù)字的是無符號整常數(shù)。 設(shè)源程序?yàn)椤?x+++y”（‘ ?是預(yù)處理程序添加的），掃描器共使用確定有限自動機(jī) 5次（見下頁）。+39。i39。+39。+39。$39。+39。因當(dāng)前所處狀態(tài) 4為終態(tài)，故識別出一個單詞。y39。39。i39。39。,NUL)。單詞的前導(dǎo)空格在識別一個單詞前被濾去，單詞的尾部空格用作單詞的終止標(biāo)志，故在狀態(tài)轉(zhuǎn)換矩陣中，應(yīng)增加空格列，該列每個元素的值均標(biāo)記為 0。 ?因 10個數(shù)字作用相同，故可用一列表示。 ( ) 空格 0 1 2 3 4 5 6 7 8 9 10 0 1 11 11 0 0 0 0 0 0 0 0 0 2 0 12 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 13 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0 0 0 0 12 0 12 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如右所示： ? 轉(zhuǎn)換函數(shù) 0． procedure Tra(c) 1. if c是字母 then c←39。 3. return c 4. end procedure 單詞 code 單詞 code 1 begin { 8 * * 2 end } 9 ， , 3 integer a 10 。 ?單詞二元式編碼表 0. procedur scanner( ) 1. ←39。 ?使用 DFA的控制程序遠(yuǎn)較手工構(gòu)造的掃描器簡單，并且控制程序與源語言的單詞集無關(guān)。 ?用戶可使用 LEX提供的語言編寫源程序，源程序由描述單詞的正規(guī)式和單詞的二元式編碼構(gòu)成。例： the big elephent ate a banana ㈠ 語法樹 根據(jù)英語的語法，上述句子的語法結(jié)構(gòu)可用圖（語法樹）表示如下： ?非葉結(jié)點(diǎn)稱為語法單位，在形式語言中稱為非終結(jié)符。 1. 句子 → 主語 謂語 2. 主語 → 冠詞 形容詞 名詞 3. 冠詞 →the|a 4. 形容詞 →big 5. 名詞 →elephant|banana 6. 謂語 → 動詞 直接賓語 7. 直接賓語 → 冠詞 名詞 8. 動詞 →ate ㈢ 由規(guī)則推導(dǎo)句子 可用規(guī)則來推導(dǎo)出句子。但意義是荒謬的，也就是說句子的語義是錯誤的。 ①遞歸定義：定義某事物，又用到該事物本身。 例： V→Uy|Z ， U→xV 因存在推導(dǎo) V Uy xVy，故存在間接遞歸。 利用遞歸文法，可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。 ㈠ 文法和語言 一個文法 G是一個四元式 (VT,VN,S,P)，其中 ?VT是一個終結(jié)符的非空有限集，終結(jié)符通常用小寫字母表示。 ① 終結(jié)符是語言的基本符號，即程序設(shè)計(jì)語言的單詞。 ?S是一個特殊的非終結(jié)符（ S∈ VN），稱為開始符號。但對于程序設(shè)計(jì)語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計(jì)語言的語法結(jié)構(gòu)。 ?間接右遞歸：若 y=ε，則 V xU。 例： U→xUy ，通常用大寫字母表示非終結(jié)符，用小寫字母表示終結(jié)符。 綜上所述，語言結(jié)構(gòu)通常是用文法來定義和描述，文法是由終結(jié)符、非終結(jié)符、開始符號（特殊非終結(jié)符）及產(chǎn)生式四個要素構(gòu)成。 上述英文句子可用下述規(guī)則來描述： 句子 主語 謂語 冠詞 形容詞 名詞 謂語 the 形容詞 名詞 謂語 the big 名詞 謂語 the big elephant 謂語 the big elephant 動詞 直接賓語 the big elephant ate 直接賓語 the big elephant ate 冠詞 名詞 the big elephant ate a 名詞 the big elephant ate a banana 上述推導(dǎo)可簡單表示為： 句子 the big elephant ate a banana。 ?葉結(jié)點(diǎn)稱為單詞符號，在形式語言中稱為終結(jié)符。 結(jié)論 結(jié) 束 第 3章 程序設(shè)計(jì)語言的語法描述 文法的引入 上下文無關(guān)文法 文法舉例（略） 使用文法對程序設(shè)計(jì)語言的結(jié)構(gòu)進(jìn)行定義和描述。所以，自動構(gòu)造詞法分析器的難點(diǎn)在于構(gòu)造 DFA，對于實(shí)際程序設(shè)計(jì)語言來說，用人工構(gòu)造 DFA是不可能的，必須由程序來實(shí)現(xiàn)。:←Nul:Token[]← 2. i←i+1:c←buf[i]: 當(dāng)前狀態(tài) ← 初態(tài) 3． while DFA[當(dāng)前狀態(tài) ,c]≠0 do 4. Token←Token,c //將 Token中字符串拼接字符 c后送 Token 5. 當(dāng)前狀態(tài) ← DFA[當(dāng)前狀態(tài) ,Tra(c)] 6. i←i+1 //指向下一字符 7. if buf[i]為空 then break 8. else c←buf[i] 9. end if 10. end while 11． if not(當(dāng)前狀態(tài) ∈ 終態(tài)集 ) then output Error:exit 12. ← 根據(jù) Token[]查表的結(jié)果 13. if =??? then //?表示單詞二元式編碼表中無 14. if Token首字符是字母 then =?i? //是標(biāo)識符 15. if Token首字符是數(shù)字 then =?x? //是整常數(shù) 16. ←Token[] //此時單詞有值 17. end if 18. return t 19. end procedure ?控制程序的工作原理和手工構(gòu)造相類似，差異在于如何實(shí)現(xiàn)狀態(tài)遷移。 4 real c 11 ( ( 5 = = 12 ) ) 6 + + 13 7 ++ $ 14 ? DFA終態(tài)集 Z={1,2,3,4,5,6,7,8,9,10,11,12,13} 在上例中，除初態(tài) 0外，其余狀態(tài)均為終態(tài)，故終態(tài)集可不設(shè)置。 2. if c是數(shù)字 then c←39。039。在查表時可將 26個字母轉(zhuǎn)換成 1個，例 39。 ㈣ 掃描器控制程序的實(shí)現(xiàn) ?狀態(tài)轉(zhuǎn)換矩陣的數(shù)字化 ?控制程序是根據(jù) DFA來工作的，首先要將狀態(tài)轉(zhuǎn)換矩陣數(shù)字化，空白用 0表示。由于無法再讀入字符，即查表，確認(rèn)識別出單詞為 ，返回單詞二元式編碼 (39。39。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識別出一個單詞。y39。+39。y39。+39。因當(dāng)前所處狀態(tài) 13為終態(tài)，故識別出一個單詞。+39。+39。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識別出一個單詞。x39。 ?由于構(gòu)造的方法不同，在 DFA某一個終態(tài)中，有可能包含原 NFA中的二個終態(tài)或更多，即在該狀態(tài)可識別出二個詞形相似的單詞，這就存在一個優(yōu)先匹配問題。當(dāng) DFA識別出一個單詞，就根據(jù) Token數(shù)組所保存的字符串去查表。 ㈢ 掃描器控制程序工作原理 ?每次識別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進(jìn)入下一狀態(tài)，尋求最長匹配，直到無法前進(jìn)為止，這樣始終多讀一個字符。 ③ NFA M確定化 I Iα Iβ I= I+ I* I, I。39。=39。)39。3