【文章內(nèi)容簡介】 內(nèi)存較小，編譯程序相對而言體積較大。使用遍技術的優(yōu)點在于，可根據(jù)當前遍的工作，裝入相應的工作程序。當一遍工作完之后，內(nèi)存空間大部分被釋放。當下一遍進入后，幾乎可以使用全部存儲空間。遍數(shù)多一點還有一個好處，即整個編譯程序的邏輯結構較為清晰。但是，遍數(shù)多勢必增加輸入輸出所耗費的時間。 ㈢ 遍和編譯程序的結構 遍決定了編譯程序的結構。在本書中，詞法分析器是以函數(shù)形式書寫的，函數(shù)的返回值是一個單詞的二元式。 ①詞法分析不作為獨立一遍 ②詞法分析作為獨立一遍（本書采用） 狀態(tài)轉換圖和詞法分析器手工構造 ㈠ 引入狀態(tài)轉換圖的必要性 若不考慮科學計數(shù)法形式，程序設計語言的無符號實型常數(shù)有三種書寫形式，它們是： 無小數(shù)部分形式 134. 無整數(shù)部分形式 .12 完全形式 如果考慮科學計數(shù)法形式，則無符號實型常數(shù)識別更復雜。 直接編寫識別無符號實型常數(shù)的程序有一定難度，狀態(tài)轉換圖是構造單詞識別程序（掃描器）的一種較好工具。 ㈡ 狀態(tài)轉換圖基本概念及應用 ①狀態(tài)轉換圖是一個有向圖。在狀態(tài)轉換圖中，結點代表狀態(tài)，用園圈表示。狀態(tài)之間用箭弧連接。箭弧上的標記代表在射出結狀態(tài)下可能出現(xiàn)的合法的輸入字符。 ② 一個狀態(tài)轉換圖包含若干個狀態(tài)（結點），其中有一個是初態(tài)，用符態(tài)轉換圖至少有一個終態(tài)，表示已識別出一個字符串（單詞），終態(tài)用雙圈表示。 例，識別標識符的狀態(tài)轉換圖如下所示： ○ j x ○ i y ○ k 其中 0為初態(tài)， 2為終態(tài)。 字母數(shù)字 空格 字母 ① 非字母數(shù)字 * ③ 若當前狀態(tài)是 1，只有當輸入字符為非字母數(shù)字，才可能到達狀態(tài) 2，顯然多讀了一個字符，這就是終態(tài)結 2上星號‘ *’的含義，它并不是正在識別的標識符的組成部分。此時應將其退回，下次識別單詞從該字符開始。 ④單詞的尾部空格作為單詞的結束標志，單詞的前導空格在識別單詞前濾去，所以在初態(tài) 0有一個標記為空格的自回路。 在詞法分析預處理中，空格作為界符被保留下來。由于空格不是任何單詞的組成部分（除字符串常數(shù)），故在識別單詞前，應將單詞的前導空格濾去。由于空格的特殊性，狀態(tài)轉換圖中用虛線表示（若當前輸入字符是空格，重新進入 1狀態(tài)）。在識別標識符的過程中，當讀入的字符不是字母或數(shù)字，可能是空格，說明當前正在識別的單詞已完全讀入。為程序處理方便起見，不管是什么字符，均將其退回。若退回的是空格，該空格將成為下一個單詞的前導空格。 ⑤ 一個狀態(tài)轉換圖可用于識別單詞，從初態(tài)出發(fā)，經(jīng)一條通路到達某一終態(tài)，路徑上的標記依次連接而成的字符串，即為狀態(tài)轉換圖識別出的單詞。 例，識別實常數(shù)和整常數(shù)的狀態(tài)轉換圖如下所示： 空格 數(shù)字 數(shù)字 數(shù)字 ③ 小數(shù)點 ④ 非數(shù)字 * 非數(shù)字非小數(shù)點 小數(shù)點 * 數(shù)字 ⑦ 數(shù)字 ⑧ 非數(shù)字 * 非數(shù)字 （出錯） 設輸入串為 134.+ …… ，從初態(tài) 0出發(fā)，經(jīng)路徑 到達終態(tài) 5，路徑上標記依次連接而成的字符串為 134.+，退回多讀的字符 39。+39。，識別出的字符串（單詞）為 134.。 3 1 ③ . ④ + * 4 ⑥ 一個程序設計語言單詞的識別，可以用若干張狀態(tài)轉換圖予以描述，雖然用一張圖也可以，但用若干張圖，有時會有助于概念的清晰化。 將上述三個圖合并視為一個圖，初始狀態(tài)為 0。從初態(tài) 0出發(fā)，若當前輸入字符是字母，則進入狀態(tài) 1；若為數(shù)字，則進入狀態(tài) 3；若為小數(shù)點，則進入狀態(tài) 7。若為加號，則進入狀態(tài) 10。否則，或進入其它單詞的識別（若有的話），或出錯（非法字符）。 下圖是識別 、 +和 ++的狀態(tài)轉換圖。 空格 + ⑩ + 非 + * ㈢ 利用狀態(tài)轉換圖識別單詞 狀態(tài)轉換圖每次只能識別一個單詞，若源程序中有 N個單詞，則需使用狀態(tài)轉換圖 N次。設源程序為 x+++y（ 39。39。是預處理程序添加的），單詞識別程序（掃描器）共使用狀態(tài)轉換圖 5次。 ?從初態(tài) 0出發(fā)，讀入 39。x39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。+39。，進入終態(tài) 2，識別出標識符 x，退回 39。+39。； ?從初態(tài) 0出發(fā)，讀入 39。+39。進入狀態(tài) 10，在狀態(tài) 10讀入 39。+39。，進入終態(tài) 11，識別出運算符 ++； ?從初態(tài) 0出發(fā)，讀入 39。+39。進入狀態(tài) 10，在狀態(tài) 10讀入 39。y39。，進入終態(tài) 12，識別出運算符 +，退回 39。y39。； ?從初態(tài) 0出發(fā)，讀入 39。y39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。39。，進入終態(tài) 2，識別出標識符 y，退回 39。39。； ?從初態(tài) 0出發(fā)，讀入 39。39。進入狀態(tài) 13，識別出單詞 ，識別出單詞 意味著整個源程序中字符處理完畢。 ㈣ 根據(jù)狀態(tài)轉換圖編制程序 狀態(tài)轉換圖就是程序控制流程圖，每個結點對應一段程序。 ?分叉結點： if語句或 switch語句 ?含自回路結點： while語句 ?終態(tài)結點： return語句返回單詞的二元式。若終態(tài)結點帶有星號 39。*39。，則緩沖區(qū)指針值不變；否則緩沖區(qū)指針值加 1，指向下一字符。 下面是根據(jù)識別標識符的狀態(tài)轉換圖編制的部分掃描程序。 struct code_val{ //結構用于存放單詞二元式 char code。char val[20]。 }。 struct code_val scanner(char *buf)。 //單詞識別程序 (掃描器 )，每調(diào)用一次返回一個單詞的二元式。 void concat(char token[],char c)。 //拼接單詞函數(shù) char reserve(char token[])。 //查基本字表函數(shù) struct code_val{ char code。char val[20]。 }。 struct code_val scanner(char *buf) //每調(diào)用一次返回一個單詞的二元式 {//buf為掃描緩沖區(qū)存放經(jīng)預處理的源程序。 static int i=0。 //靜態(tài)局部變量，掃描緩沖區(qū)指示器。 struct code_val t={39。\039。,NUL}。//用于存放單詞二元式，識別前清空。 char token[20]=。 //用于拼接單詞的字符數(shù)組，識別前清空。 //去除前導空格 while(buf[i]==39。 39。) i++。 //進入標識符或基本字的識別 if(buf[i]=39。a39。 amp。amp。 buf[i]=39。z39。){ while(buf[i]=39。a39。 amp。amp。 buf[i]=39。z39。||buf[i]=39。039。 amp。amp。 buf[i]=39。939。) concat(token,buf[i++])。 //拼接函數(shù) =reserve(token)。 //查基本字表函數(shù) if(==39。i39。)strcpy(,token)。 //是標識符 return t。 //返回標識符或基本字的二元式 } ………………………………… //其余單詞識別程序略 }//end of scanner ① 拼接函數(shù) concat(token[],ch) concat為拼接函數(shù)，它有二個參數(shù)。設在調(diào)用前 token[]內(nèi)容為 beg, 輸入字符ch為 39。i39。，則調(diào)用拼接函數(shù) concat后， token的內(nèi)容為 begi。 void concat(char token[],char c) { for(int i=0。token[i]!=39。\039。i++)。 //找到尾 token[i]=c。token[++i]=39。\039。 } ② 查基本字表函數(shù) reserve(token[]) 基本字通常是由字母構成，符合標識符規(guī)則?？紤]簡化程序設計，將基本字作為一種特殊標識符來處理。設置一個基本字表（包括相應二元式編），當狀態(tài)轉換圖識別出一個標識符時，就去查對這張表，確定它是基本字還是標識符。 char reserve(char token[]) {//基本字及編碼表 const char *table[]={begin,end,integer,real}。 const char code[]={{}ac}。 for(int i=0。istrlen(code)。i++) if(strcmp(token,table[i])==0) return code[i]。 return 39。i39。 //標識符的單詞種別為 39。i39。 } begin } end { integer a real c 0 1 2 3 正規(guī)式、自動機及詞法分析器的自動生成 基本概念 ㈠ 有窮字母表 ∑ 符號有限集，它的每個元素稱為字符。 ㈡ 字（字符串） ∑上字符所構成的有限序列。 ① 空字 不包含任何字符的字，稱為空字，記為 ε（空字相當于高級語言中的空串“”）。 ε 空字 { } 空集 {ε} 集合僅有一個元素 ε ② ∑* ∑上所有字的全體，包括 ε。 例： ∑={0， 1} ∑*={ε， 0， 1， 00， 01， 10， 11， 000， 001， ……} ③ （集合的）積運算 定義：設 U、 V ∑*， U和 V的積記為 U V（或 UV）且定義為 UV={αβ|（ α∈ U） ∧ （ β∈ V） } ?積不滿足交換律 UV≠VU ?積滿足結合律 (UV)W=U(VW) 證明見本書 38頁 ?積滿足分配律 X(Y∪ Z)=XY∪ XZ ④ （集合的）閉包 設 V Σ*， V的閉包記為 V*且定義為 V自身的任意有限次積，即V*= V0∪ V1∪ V2∪ …… ∪ Vn，規(guī)定 V0 = {ε}。 設 V={0,1}，則 V*={ε, 0, 1, 00, 01, 10, 11, 000, 001, ……} 閉包 V*中的每個字都是由 V中的字經(jīng)有限次連接而成。 ⑤ （集合的）正則閉包 定義：設 V Σ*， V的正則閉包記為 V+，且定義 V+=VV*。 ?根據(jù)定義可以證明 V+ = V1∪ V2∪ …… ∪ Vn(詳見本書 18頁 )。 設 V={0, 1}，則 V+ = V1∪ V2∪ …… ∪ Vn={ 0, 1, 00, 01, 10, 11,000,001, …… } ， V+可理解為二進制數(shù)的全體。 若 V=U，則 UV=VV=V2 正規(guī)式與正規(guī)集 ㈠ 正規(guī)式和正規(guī)集的定義： ?ε和 Φ是 ∑上的正規(guī)式，相應的正規(guī)集為 {ε}、 { }。 ?若字符 a∈ ∑，則字符 a是正規(guī)式，相應正規(guī)集為 {a}。 ?若 α、 β為正規(guī)式，相應正規(guī)集分別記為 L(α)和 L(β)，則 α|β是正規(guī)式，其相應正規(guī)集記為 L(α|β) ，且令 L(α|β)=L(α)∪ L(β)。 ?若 α、 β為正規(guī)式，相應正規(guī)集分別記為 L(α)和 L(β)，則 αβ(或 αβ)是正規(guī)式，其相應正規(guī)集記為 L(αβ)，且令 L(αβ)= L(α)L(β)。若 α=β，則 L(αβ)= L(αα)= L(α2)=L(α)2。推廣到一般，正規(guī)式 α自身的 n次積αα…α 是正規(guī)式，可記為 αn，其相應正規(guī)集記為 L(αn)，顯然 L(αn)= L(α) n。） ?若 α為正規(guī)式，相應正規(guī)集記為 L(α)，則 α*= α0|α1| α2 | ……|α n是正規(guī)式，規(guī)定 α0 =ε，其相應正規(guī)集記為 L(α*)，且令 L(α*) =L(α) *。 ?正規(guī)式運算符優(yōu)先性依次為 :*、 、 ︱ ,可用園括號改變運算順序。 例子詳見本書第 21頁 ㈡ 實際意義 ?有窮字母表 Σ是程序設計語言所使用的字符集的抽象 ?正規(guī)集是程序設計語言單詞集的抽象 ?正規(guī)式是程序設計語言構詞規(guī)則的抽象 ㈢ 正規(guī)式相等原理 二個正規(guī)式是相等的，當且僅當二個正規(guī)式所表示的正規(guī)集是相等的。 例：設 α是正規(guī)式，求證 α|α = α。 證： L(α|α) = L(α)∪ L(α) = L(α) ∵ L(α|α) = L(α) ∴ α|α =α ㈣ 正規(guī)式