【正文】 個終態(tài)集。 ?f是一個從 S Σ*到 S的子集映照，即 f： S Σ*→2 S（多值函數(shù)） 2S表示冪集，若 S={0， 1}，則 2S ={{ }， {0}， {1}， {0， 1}}。 0 1 1 非確定有限自動機（ NFA） ㈠ NFA定義 一個非確定的有限自動機 M是一個五元式 M=（ S， Σ， f， S0， Z） ?S是一個有限集，它的每一個元素稱為狀態(tài)。路徑上的標(biāo)記依次連接為 101，則稱 α= 101可為 M所識別或接受。 ?DFA M所識別的字全體記為 L(M)。 0 1 1 1 1 1 接上例 0 , 1 0 , 1 ㈣ 字 α可為 DFA M識別 ?對于一個字 α，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的路徑，且路徑上的所有弧的標(biāo)記依序連接成的字為 α，則稱 α可為DFA M所識別或接受。 39。 ㈢ DFA M可用一個（確定的）狀態(tài)轉(zhuǎn)換圖表示 例識別二進(jìn)制數(shù)的 DFA可用（確定的）狀態(tài)轉(zhuǎn)換圖表示如下： 狀態(tài) /字符 39。) = 1 ㈡ 狀態(tài)轉(zhuǎn)換矩陣 函數(shù) f可用矩陣表示，行表示狀態(tài)，列表示輸入字符，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。) = f(1, 39。) = f(1, 39。) = f(0, 39。}， f， 0， {1}） 其中 f的定義如下： f(0, 39。,39。 例：一個識別二進(jìn)制數(shù)的確定有限自動機 M=（ {0， 1}， {39。 ?s0∈ S，是唯一的一個初態(tài)。 ?Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。 證： L(α|α) = L(α)∪ L(α) = L(α) ∵ L(α|α) = L(α) ∴ α|α =α ㈣ 正規(guī)式滿足下列關(guān)系 ①交換律： α|β = β|α ② 結(jié)合律： α|(β|γ) = (α|β)|γ， α(βγ) = (αβ) γ ③ 分配律： α(β|γ) = αβ|αγ， (β|γ)α = βα|γα ④ εα = αε= α ㈤ 例 設(shè) α =a|b|……|z ， β = 0|1|……|9 。 例子詳見本書第 21頁 ㈡ 實際意義 ?有窮字母表 Σ是程序設(shè)計語言所使用的字符集的抽象 ?正規(guī)集是程序設(shè)計語言單詞集的抽象 ?正規(guī)式是程序設(shè)計語言構(gòu)詞規(guī)則的抽象 ㈢ 正規(guī)式相等原理 二個正規(guī)式是相等的，當(dāng)且僅當(dāng)二個正規(guī)式所表示的正規(guī)集是相等的。 ?正規(guī)式運算符優(yōu)先性依次為 :*、 推廣到一般，正規(guī)式 α自身的 n次積αα…α 是正規(guī)式，可記為 αn，其相應(yīng)正規(guī)集記為 L(αn)，顯然 L(αn)= L(α) n。β)是正規(guī)式，其相應(yīng)正規(guī)集記為 L(αβ)，且令 L(αβ)= L(α)L(β)。 ?若 α、 β為正規(guī)式，相應(yīng)正規(guī)集分別記為 L(α)和 L(β)，則 α|β是正規(guī)式，其相應(yīng)正規(guī)集記為 L(α|β) ，且令 L(α|β)=L(α)∪ L(β)。 若 V=U，則 UV=VV=V2 正規(guī)式與正規(guī)集 ㈠ 正規(guī)式和正規(guī)集的定義： ?ε和 Φ是 ∑上的正規(guī)式，相應(yīng)的正規(guī)集為 {ε}、 { }。 ?根據(jù)定義可以證明 V+ = V1∪ V2∪ …… ∪ Vn(詳見本書 18頁 )。 設(shè) V={0,1}，則 V*={ε, 0, 1, 00, 01, 10, 11, 000, 001, ……} 閉包 V*中的每個字都是由 V中的字經(jīng)有限次連接而成。 ε 空字 { } 空集 {ε} 集合僅有一個元素 ε ② ∑* ∑上所有字的全體，包括 ε。 ㈡ 字（字符串） ∑上字符所構(gòu)成的有限序列。i39。i39。i++) if(strcmp(token,table[i])==0) return code[i]。 for(int i=0。 char reserve(char token[]) {//基本字及編碼表 const char *table[]={begin,end,integer,real}。考慮簡化程序設(shè)計，將基本字作為一種特殊標(biāo)識符來處理。\039。 //找到尾 token[i]=c。\039。 void concat(char token[],char c) { for(int i=0。i39。 //返回標(biāo)識符或基本字的二元式 } ………………………………… //其余單詞識別程序略 }//end of scanner ① 拼接函數(shù) concat(token[],ch) concat為拼接函數(shù)，它有二個參數(shù)。)strcpy(,token)。 //查基本字表函數(shù) if(==39。) concat(token,buf[i++])。 buf[i]=39。 amp。||buf[i]=39。 buf[i]=39。 amp。){ while(buf[i]=39。 buf[i]=39。 amp。 //進(jìn)入標(biāo)識符或基本字的識別 if(buf[i]=39。 39。 //用于拼接單詞的字符數(shù)組，識別前清空。//用于存放單詞二元式，識別前清空。\039。 //靜態(tài)局部變量，掃描緩沖區(qū)指示器。 struct code_val scanner(char *buf) //每調(diào)用一次返回一個單詞的二元式 {//buf為掃描緩沖區(qū)存放經(jīng)預(yù)處理的源程序。char val[20]。 //拼接單詞函數(shù) char reserve(char token[])。 //單詞識別程序 (掃描器 )，每調(diào)用一次返回一個單詞的二元式。 }。 struct code_val{ //結(jié)構(gòu)用于存放單詞二元式 char code。則緩沖區(qū)指針值不變；否則緩沖區(qū)指針值加 1，指向下一字符。若終態(tài)結(jié)點帶有星號 39。 ㈣ 根據(jù)狀態(tài)轉(zhuǎn)換圖編制程序 狀態(tài)轉(zhuǎn)換圖就是程序控制流程圖，每個結(jié)點對應(yīng)一段程序。39。39。39。y39。y39。y39。+39。+39。+39。+39。+39。x39。是預(yù)處理程序添加的），單詞識別程序（掃描器）共使用狀態(tài)轉(zhuǎn)換圖 5次。設(shè)源程序為 x+++y（ 39。 下圖是識別 、 +和 ++的狀態(tài)轉(zhuǎn)換圖。若為加號，則進(jìn)入狀態(tài) 10。 將上述三個圖合并視為一個圖，初始狀態(tài)為 0。識別出的字符串（單詞）為 134.。 例，識別實常數(shù)和整常數(shù)的狀態(tài)轉(zhuǎn)換圖如下所示： 空格 數(shù)字 數(shù)字 數(shù)字 ③ 小數(shù)點 ④ 非數(shù)字 * 非數(shù)字非小數(shù)點 小數(shù)點 * 數(shù)字 ⑦ 數(shù)字 ⑧ 非數(shù)字 * 非數(shù)字 （出錯） 設(shè)輸入串為 134.+ …… ，從初態(tài) 0出發(fā)，經(jīng)路徑 到達(dá)終態(tài) 5，路徑上標(biāo)記依次連接而成的字符串為 134.+，退回多讀的字符 39。若退回的是空格，該空格將成為下一個單詞的前導(dǎo)空格。在識別標(biāo)識符的過程中，當(dāng)讀入的字符不是字母或數(shù)字，可能是空格，說明當(dāng)前正在識別的單詞已完全讀入。由于空格不是任何單詞的組成部分（除字符串常數(shù)），故在識別單詞前，應(yīng)將單詞的前導(dǎo)空格濾去。 ④單詞的尾部空格作為單詞的結(jié)束標(biāo)志，單詞的前導(dǎo)空格在識別單詞前濾去，所以在初態(tài) 0有一個標(biāo)記為空格的自回路。 字母數(shù)字 空格 字母 ① 非字母數(shù)字 * ③ 若當(dāng)前狀態(tài)是 1，只有當(dāng)輸入字符為非字母數(shù)字，才可能到達(dá)狀態(tài) 2，顯然多讀了一個字符，這就是終態(tài)結(jié) 2上星號‘ *’的含義，它并不是正在識別的標(biāo)識符的組成部分。 ② 一個狀態(tài)轉(zhuǎn)換圖包含若干個狀態(tài)（結(jié)點），其中有一個是初態(tài)，用符態(tài)轉(zhuǎn)換圖至少有一個終態(tài)，表示已識別出一個字符串（單詞），終態(tài)用雙圈表示。狀態(tài)之間用箭弧連接。 ㈡ 狀態(tài)轉(zhuǎn)換圖基本概念及應(yīng)用 ①狀態(tài)轉(zhuǎn)換圖是一個有向圖。 ①詞法分析不作為獨立一遍 ②詞法分析作為獨立一遍（本書采用） 狀態(tài)轉(zhuǎn)換圖和詞法分析器手工構(gòu)造 ㈠ 引入狀態(tài)轉(zhuǎn)換圖的必要性 若不考慮科學(xué)計數(shù)法形式，程序設(shè)計語言的無符號實型常數(shù)有三種書寫形式，它們是： 無小數(shù)部分形式 134. 無整數(shù)部分形式 .12 完全形式 如果考慮科學(xué)計數(shù)法形式，則無符號實型常數(shù)識別更復(fù)雜。 ㈢ 遍和編譯程序的結(jié)構(gòu) 遍決定了編譯程序的結(jié)構(gòu)。遍數(shù)多一點還有一個好處，即整個編譯程序的邏輯結(jié)構(gòu)較為清晰。當(dāng)一遍工作完之后，內(nèi)存空間大部分被釋放。 ㈡ 遍引入的歷史背景 早期的計算機內(nèi)存較小，編譯程序相對而言體積較大。詞法分析器對于所有單詞的識別，最多只要向前看一個字符就足夠了。 這樣空格、 TAB和換行符不再是沒有意義的了，這也就是為什么在詞法分析預(yù)處理中將空格、 TAB和換行符保留下來的原因。 ②將空格、 TAB和換行符視為界符。 超前搜索導(dǎo)致詞法分析器實現(xiàn)困難。 解決辦法是超前搜索，一直掃描到右括號后面的字符。 ?IF()GOTO55 邏輯 IF，當(dāng) M等于 5轉(zhuǎn)標(biāo)號為 55的語句。 例標(biāo)準(zhǔn) Fortran對基本字不加保護，用戶可以把它們用作普通標(biāo)識符。 20. end procedure 基本字的識別和超前搜索 程序設(shè)計語言單詞以基本字識別最為困難，原因如下： ①有些語言對基本字不加保護，用戶可用作普通標(biāo)識符。 then in_ment←false //離開注釋 16. end if 17. old_c←cur_c: cur_c← 文件下一個字符 18. end while 19. i←i+1:buf[i] ←39。 and cur_c=39。 then cur_c← cur_c+32 10. if cur_c=制表符 or cur_c=換行符 then cur_c← 空格 11. i←i+1:buf[i]← cur_c //送入掃描緩沖區(qū) 12. end if 13. end if 14. else //當(dāng)前字符處于注釋中 15. if old_c=39。 and cur_c≤39。 and cur_c=換行符 then i←i 1 //是續(xù)行符 8. else 9. if cur_c≥39。 then //進(jìn)入注釋 5. i←i 1:in_ment←true 6. else 7. if old_c=39。 and cur_c=39。 ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧ in_ment: f ……… f / t ………… t / f ……… f 0. procedure pro_process() //掃描緩沖區(qū) buf[ ]和掃描緩沖區(qū)指針 i 1. old_c←? \0?:in_ment←false: cur_c← 文件第一個字符 :i←1 2. while not eof(“”) do //文件尚未處理完 3. if not in_ment then //當(dāng)前字符未處于注釋中 4. if old_c=39。 ?當(dāng)讀入 “ /*” ，布爾變量 in_ment的值由 false變?yōu)閠rue；當(dāng)讀入 “ */” ， 布爾變量 in_ment的值由 true變?yōu)?false。 ?定義布爾變量 in_ment，記錄當(dāng)前處理字符是否處于注釋。 ?每調(diào)用一次，將經(jīng)預(yù)處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描器識別單詞。39。 b e g i n r e a l r , h , s 。 ?對于受書寫格式限制的語言（例 Fortran和 Cobol），還應(yīng)識別標(biāo)號區(qū)，正確給出語句標(biāo)號。為了簡化判斷，可在預(yù)處理時，將換行符和 TAB統(tǒng)一替換為空格。 ?換行符、 TAB和空格具有界符作用，預(yù)處理時通常予以保留。 詞法分析器可在輸入緩沖區(qū)上直接識別單詞，但從程序設(shè)計的角度來看，若把源程序預(yù)處理一下，則單詞識別就比較容易。），當(dāng)一個單詞過長（例字符串常數(shù)），可分多行列出。 ?有些語言還提供續(xù)行功能（例 C語言中的續(xù)行符 39。 \n \t s = 2 * 3 . \ \n 1 4 * r * ( r + h ) \n E n d \n \0 . . . . . . \0 源程序讀入后，輸入緩沖區(qū)的內(nèi)容如下所示： ㈡ 預(yù)處理 詞法分析器通常由二個部分構(gòu)成： 預(yù)處理程序 掃描器（單詞識別程序） ① 分成二部分的理由 ?目前使用的程序設(shè)計語言大都采用自由格式書寫，允許在單詞之間存在多余的空格、換行和制表符（ TAB）。為續(xù)行符。 設(shè)源程序如下所示，其中 39。例如，由多個字符構(gòu)成的單詞有可能被緩沖區(qū)邊界所打斷（留作習(xí)題）。早期計算機內(nèi)存較小，只能在內(nèi)存設(shè)置長度有限的緩沖區(qū)，分段讀入源程序進(jìn)行處理。{39。 NUL