词法分析课件

1

詞法分析

22.1詞法分析器的設計考慮及

手工構造詞法分析任務：從檔讀入根源程式，去除根源程式中與編譯無關的編輯字元、注釋等，由字元拼接單詞。每當識別出一個單詞，就用單詞的內部碼（單詞二元式）替換。執行詞法分析任務的程式稱為詞法分析器。32.1.1單詞類型及二元式編碼㈠單詞類型任何程式設計語言的單詞都可將其分為5種類型，它們是：基本字 real、integer、……識別字 通常為以字母開始的數字字母串（簡單變數、標號、……）常數 整常數（123）、實常數（123.456）、……運算符 +、*、/、……界符 ;、(、)、……㈡單詞的性質基本字、運算符和界符對於某一程式設計語言來說是確定的，而根源程式中的識別字和常數的個數是不確定的，隨根源程式而異。有些單詞由單個字元構成，而有些單詞由多個字元構成。4㈢單詞二元式編碼經詞法分析後，單詞用二元式(code,val)表示。code表示單詞的種別，用整數碼表示。單詞種別表示單詞的語法特性，在語法分析時使用。val表示單詞的值，在本書中用字串表示。單詞值表示了單詞的語義特性，在語義分析時使用。㈣編碼原則通常將識別字歸為一種，常數按類型分種，基本字、運算符及界符採用一符一種。如果一個種別僅包含一個單詞，那麼單詞種別就可代表該單詞，無需給出單詞值。為了輸入和處理的方便，無意義的單詞值用字符串"NUL"表示。若一個種別含有多個單詞，除給出種別外，還需給出它的值。5㈤實例設有某一程式設計語言，其部分單詞二元式編碼如下所示：單詞單詞種別單詞值integeraNULrealcNULbegin{NULend}NUL識別字i字串形式符號名無符號整常數x字串形式數字無符號實常數y字串形式數字==NUL**NUL++NUL((NUL))NUL,,NUL;;NUL

計算園柱體表面積的根源程式（輸入輸出略）如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/Realr,h,s;s=2*3.14*r*(r+h)End

根據單詞二元式編碼，上述程式的單詞二元式序列應為：

('{',"NUL") …………62.1.2根源程式的輸入及預處理

㈠根源程式的輸入

分段讀入處理（早期）全部讀入後處理

根源程式以檔形式存於外存，首先要將其讀入記憶體才可進行詞法分析。早期電腦記憶體較小，只能在內存設置長度有限的緩衝區，分段讀入根源程式進行處理。在編制程式時，必須考慮由於根源程式分段讀入所產生的問題。例如，由多個字元構成的單詞有可能被緩衝區邊界所打斷（留作習題）。目前電腦所使用的的記憶體已超過若干年前硬碟容量，電腦記憶體足以容納根源程式的全部，故根源程式可一次全部讀入記憶體進行處理。7

設根源程式如下所示，其中'\'為續行符。Begin/*S=2*3.14*R*R+2*3.14*R*H*/\n\tReal

r,h,s;\n\ts=2*3.\\n14*r*(r+h)\nEnd\n\0......\0根源程式讀入後，輸入緩衝區的內容如下所示：8㈡預處理詞法分析器通常由二個部分構成： 預處理程式 掃描器（單詞識別程式）①分成二部分的理由目前使用的程式設計語言大都採用自由格式書寫，允許在單詞之間存在多餘的空格、換行和跳位字元（TAB）。根源程式通常帶有注釋，注釋不是程式的必要組成部分。有些語言還提供續行功能（例C語言中的續行符'\'），當一個單詞過長（例字串常數），可分多行列出。對於Fortran和Cobol之類語言，根源程式還受到書寫格式的限制。

詞法分析器可在輸入緩衝區上直接識別單詞，但從程式設計的角度來看，若把根源程式預處理一下，則單詞識別就比較容易。9②預處理主要工作刪除注釋刪除續行符，以及後續換行符(0AH)。換行符、TAB和空格具有界符作用，預處理時通常予以保留。在後面的分析中可以看到，它們的存在反而給後續的單詞識別帶來方便。為了簡化判斷，可在預處理時，將換行符和TAB統一替換為空格。大多數語言（除C語言）不區分大小寫，可在預處理時，將大寫字母變換成小寫字母，或相反，以方便後續處理。對於受書寫格式限制的語言（例Fortran和Cobol），還應識別標號區，正確給出語句標號。識別續行標誌，把相繼行撚接在一起，給出語句結束符。beginrealr,h,s;

s=2*3.14*r*(r+h)

end\0...\0上述根源程式經預處理後，掃描緩衝區中的內容如下所示：10㈢預處理例用偽代碼編寫一個預處理程式，要求如下：去除根源程式中注釋（根源程式中的注釋用/*……*/標記，不允許嵌套使用）去除根源程式中續行符（\）將TAB和換行符替換為空格將大寫字母變換成小寫在根源程式尾部添加字元'#'，這是編譯程序內部的一個特殊的單詞，以示根源程式結束。每調用一次，將經預處理的根源程式全部送入記憶體中的掃描緩衝區，供掃描器識別單詞。11①演算法說明用偽代碼編寫預處理程式，輸入和預處理可同時進行，無需輸入緩衝區，將讀入後經預處理的根源程式直接送掃描緩衝區buf[1..n]。定義布爾變數in_comment，記錄當前處理字元是否處於注釋。若in_comment

的值為false，則表示當前讀入字元未處於注釋中，此時應將當前處理字元存入掃描緩衝區；若in_comment

的值為true，則表示當前處理字元處於注釋中，此時無需將該字元存入buf中，相當於掉棄。當讀入“/*”，布爾變數in_comment的值由false變為true；當讀入“*/”，布爾變數in_comment的值由true變為false。可用變數cur_c記錄當前正在處理的字元，用old_c記錄剛處理過的字元。

ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧin_comment:f………f/t…………t/f………f120.procedurepro_process() //掃描緩衝區buf[]和掃描緩衝區指針i1.old_c←‘\0’:in_comment←false:cur_c←檔第一個字元:i←12.whilenoteof(“source.txt”)do//檔尚未處理完3. ifnotin_commentthen//當前字元未處於注釋中4. ifold_c='/'andcur_c='*'then//進入注釋5. i←i-1:in_comment←true6. else7. ifold_c='\'andcur_c=換行符theni←i-1//是續行符8. else9. ifcur_c≥'A'andcur_c≤'Z'thencur_c←cur_c+3210. ifcur_c=跳位字元orcur_c=換行符thencur_c←空格11. i←i+1:buf[i]←cur_c //送入掃描緩衝區12. endif13. endif14. else//當前字元處於注釋中15. ifold_c='*'andcur_c='/'thenin_comment←false

//離開注釋16. endif 17. old_c←cur_c:cur_c←檔下一個字元18.endwhile19.i←i+1:buf[i]←'#'20.endprocedure132.1.3基本字的識別和超前搜索

程式設計語言單詞以基本字識別最為困難，原因如下：

①有些語言對基本字不加保護，用戶可用作普通識別字。

②基本字、用戶定義的識別字和常數之間可能沒有分隔符號。

例標準Fortran對基本字不加保護，用戶可以把它們用作普通識別字。讓我們來觀察下麵三個Fortran語言語句。IF(5.EQ.M)GOTO55

邏輯IF，當M等於5轉標號為55的語句。IF(5)=55 IF為數組名，IF(5)為下標變數IF(X+Y)110,120,130

算術IF，當X+Y<0，轉標號為110的語句；當X+Y等於0，轉標號為120的語句；當X+Y>0，轉標號為130的語句顯然僅根據IF無法判斷其為何種單詞，可能是基本字，也可能是識別字。14

解決辦法是超前搜索，一直掃描到右括弧後面的字元。若該字元為字母G或g，則為邏輯IF；若為數字，則為算術IF；若為=，則為識別字。超前搜索導致詞法分析器實現困難。為了降低詞法分析器的複雜性，避免超前搜索，在實際實現中，大多數語言的編譯程序對用戶採取了二條限制措施：

①所有基本字均為保留字，用戶不得使用它們作為識別字。

②將空格、TAB和換行符視為界符。在基本字、用戶定義的識別字和常數之間，若沒有運算符或界符，則至少用一個空格（或TAB、換行符）加以分隔。

這樣空格、TAB和換行符不再是沒有意義的了，這也就是為什麼在詞法分析預處理中將空格、TAB和換行符保留下來的原因。採用上述二條限制措施，對用戶來講是完全可接受的，並且已成為程式員進行程式設計的慣例。詞法分析器對於所有單詞的識別，最多只要向前看一個字元就足夠了。152.1.4遍㈠遍的基本概念由外存獲得前一遍的工作結果(對於第一遍而言，從外存獲得根源程式)，完成它所含的有關階段工作之後，再把結果存於外存。㈡遍引入的歷史背景早期的電腦記憶體較小，編譯程序相對而言體積較大。使用遍技術的優點在於，可根據當前遍的工作，裝入相應的工作程式。當一遍工作完之後，記憶體空間大部分被釋放。當下一遍進入後，幾乎可以使用全部存儲空間。遍數多一點還有一個好處，即整個編譯程序的邏輯結構較為清晰。但是，遍數多勢必增加輸入輸出所耗費的時間。㈢遍和編譯程序的結構遍決定了編譯程序的結構。在本書中，詞法分析器是以函數形式書寫的，函數的返回值是一個單詞的二元式。

①詞法分析不作為獨立一遍

②詞法分析作為獨立一遍（本書採用）162.1.5狀態轉換圖和詞法分析器手工構造㈠引入狀態轉換圖的必要性若不考慮科學計數法形式，程式設計語言的無符號實型常數有三種書寫形式，它們是： 無小數部分形式 134.

無整數部分形式 .12

完全形式 3.14

如果考慮科學計數法形式，則無符號實型常數識別更複雜。直接編寫識別無符號實型常數的程式有一定難度，狀態轉換圖是構造單詞識別程式（掃描器）的一種較好工具。㈡狀態轉換圖基本概念及應用①狀態轉換圖是一個有向圖。在狀態轉換圖中，結點代表狀態，用園圈表示。狀態之間用箭弧連接。箭弧上的標記代表在射出結狀態下可能出現的合法的輸入字元。17②一個狀態轉換圖包含若干個狀態（結點），其中有一個是初態，用符號指示，是識別字串的起點。狀態轉換圖至少有一個終態，表示已識別出一個字串（單詞），終態用雙圈表示。例，識別識別字的狀態轉換圖如下所示：其中0為初態，2為終態。18③若當前狀態是1，只有當輸入字元為非字母數字，才可能到達狀態2，顯然多讀了一個字元，這就是終態結2上星號‘*’的含義，它並不是正在識別的識別字的組成部分。此時應將其退回，下次識別單詞從該字元開始。

④單詞的尾部空格作為單詞的結束標誌，單詞的前導空格在識別單詞前濾去，所以在初態0有一個標記為空格的自回路。在詞法分析預處理中，空格作為界符被保留下來。由於空格不是任何單詞的組成部分（除字串常數），故在識別單詞前，應將單詞的前導空格濾去。由於空格的特殊性，狀態轉換圖中用虛線表示（若當前輸入字元是空格，重新進入1狀態）。在識別識別字的過程中，當讀入的字元不是字母或數字，可能是空格，說明當前正在識別的單詞已完全讀入。為程式處理方便起見，不管是什麼字元，均將其退回。若退回的是空格，該空格將成為下一個單詞的前導空格。19⑤一個狀態轉換圖可用於識別單詞，從初態出發，經一條通路到達某一終態，路徑上的標記依次連接而成的字串，即為狀態轉換圖識別出的單詞。例，識別實常數和整常數的狀態轉換圖如下所示：20設輸入串為"134.+……"，從初態0出發，經路徑

到達終態5，路徑上標記依次連接而成的字串為"134.+"，退回多讀的字元'+'，識別出的字串（單詞）為"134."。21⑥一個程式設計語言單詞的識別，可以用若干張狀態轉換圖予以描述，雖然用一張圖也可以，但用若干張圖，有時會有助於概念的清晰化。將上述三個圖合併視為一個圖，初始狀態為0。從初態0出發，若當前輸入字元是字母，則進入狀態1；若為數字，則進入狀態3；若為小數點，則進入狀態7。若為加號，則進入狀態10。否則，或進入其他單詞的識別（若有的話），或出錯（非法字元）。下圖是識別"#"、"+"和"++"的狀態轉換圖。22㈢利用狀態轉換圖識別單詞狀態轉換圖每次只能識別一個單詞，若根源程式中有N個單詞，則需使用狀態轉換圖N次。設根源程式為"x+++y#"（'#'是預處理程式添加的），單詞識別程式（掃描器）共使用狀態轉換圖5次。從初態0出發，讀入'x'進入狀態1，在狀態1讀入'+'，進入終態2，識別出識別字"x"，退回'+'；從初態0出發，讀入'+'進入狀態10，在狀態10讀入'+'，進入終態11，識別出運算符"++"；從初態0出發，讀入'+'進入狀態10，在狀態10讀入'y'，進入終態12，識別出運算符"+"，退回'y'；從初態0出發，讀入'y'進入狀態1，在狀態1讀入'#'，進入終態2，識別出識別字"y"，退回'#'；從初態0出發，讀入'#'進入狀態13，識別出單詞"#"，識別出單詞"#"意味著整個根源程式中字元處理完畢。23㈣根據狀態轉換圖編制程式狀態轉換圖就是程式控制流程圖，每個結點對應一段程式。分叉結點：if語句或switch語句含自回路結點：while語句終態結點：return語句返回單詞的二元式。若終態結點帶有星號'*'，則緩衝區指針值不變；否則緩衝區指針值加1，指向下一字元。下麵是根據識別識別字的狀態轉換圖編制的部分掃描程式。

struct

code_val{ //結構用於存放單詞二元式

charcode;charval[20];};

struct

code_val

scanner(char*buf);//單詞識別程式(掃描器)，每調用一次返回一個單詞的二元式。

voidconcat(char

token[],charc); //拼接單詞函數

charreserve(chartoken[]); //查基本字表函數24struct

code_val{ charcode;charval[20];};struct

code_val

scanner(char*buf)//每調用一次返回一個單詞的二元式{//buf為掃描緩衝區存放經預處理的根源程式。

staticinti=0; //靜態局部變數，掃描緩衝區指示器。

struct

code_valt={'\0',"NUL"};//用於存放單詞二元式，識別前清空。

chartoken[20]=""; //用於拼接單詞的字元數組，識別前清空。

//去除前導空格

while(buf[i]=='')i++;//進入識別字或基本字的識別

if(buf[i]>='a'&&buf[i]<='z'){

while(buf[i]>='a'&&buf[i]<='z'||buf[i]>='0'&&buf[i]<='9')

concat(token,buf[i++]); //拼接函數

t.code=reserve(token); //查基本字表函數

if(t.code=='i')strcpy(t.val,token); //是識別字

returnt; //返回識別字或基本字的二元式

} ………………… //其餘單詞識別程式略}//endofscanner25①拼接函數concat(token[],ch)concat為拼接函數，它有二個參數。設在調用前token[]內容為"beg",輸入字元ch為'i'，則調用拼接函數concat後，token的內容為"begi"。voidconcat(char

token[],charc){

for(inti=0;token[i]!='\0';i++); //找到尾

token[i]=c;token[++i]='\0';}②查基本字表函數reserve(token[])基本字通常是由字母構成，符合識別字規則。考慮簡化程式設計，將基本字作為一種特殊識別字來處理。設置一個基本字表（包括相應二元式編），當狀態轉換圖識別出一個識別字時，就去查對這張表，確定它是基本字還是識別字。charreserve(chartoken[]){//基本字及編碼表

constchar*table[]={"begin","end","integer","real"};constcharcode[]={"{}ac"};

for(inti=0;i<strlen(code);i++)

if(strcmp(token,table[i])==0)returncode[i];return'i';//識別字的單詞種別為'i'}begin}end{integerarealc0123262.2正規式、自動機及詞法分析器的自動生成272.2.1基本概念㈠有窮字母表∑

符號有限集，它的每個元素稱為字元。㈡字（字串）

∑上字元所構成的有限序列。①空字不包含任何字元的字，稱為空字，記為ε（空字相當於高級語言中的空串“”）。

ε 空字

{} 空集

{ε} 集合僅有一個元素ε②∑*∑上所有字的全體，包括ε。例：∑={0，1} ∑*={ε，0，1，00，01，10，11，000，001，……}28③（集合的）積運算定義：設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，規定V0={ε}。設V={0,1}，則V*={ε,0,1,00,01,10,11,000,001,……}閉包V*中的每個字都是由V中的字經有限次連接而成。⑤（集合的）正則閉包定義：設V

Σ*，V的正則閉包記為V+，且定義V+=VV*。根據定義可以證明V+=V1∪V2∪……∪Vn(詳見本書18頁)。設V={0,1}，則V+=V1∪V2∪……∪Vn={0,1,00,01,10,11,000,001,……}，V+可理解為二進位數的全體。若V=U，則UV=VV=V2292.2.2正規式與正規集㈠正規式和正規集的定義：ε和Φ是∑上的正規式，相應的正規集為{ε}、{}。若字元a∈∑，則字元a是正規式，相應正規集為{a}。若α、β為正規式，相應正規集分別記為L(α)和L(β)，則α|β是正規式，其相應正規集記為L(α|β)，且令L(α|β)=L(α)∪L(β)。若α、β為正規式，相應正規集分別記為L(α)和L(β)，則αβ(或α·β)是正規式，其相應正規集記為L(αβ)，且令L(αβ)=L(α)L(β)。若α=β，則L(αβ)=L(αα)=

L(α2)=L(α)2。推廣到一般，正規式α自身的n次積αα…α是正規式，可記為αn，其相應正規集記為L(αn)，顯然L(αn)=L(α)n。）若α為正規式，相應正規集記為L(α)，則α*=α0|α1|α2|……|αn是正規式，規定α0=ε，其相應正規集記為L(α*)，且令L(α*)=L(α)*。正規式運算符優先性依次為:*、·、︱,可用園括弧改變運算順序。例子詳見本書第21頁30㈡實際意義有窮字母表Σ是程式設計語言所使用的字元集的抽象正規集是程式設計語言單詞集的抽象正規式是程式設計語言構詞規則的抽象㈢正規式相等原理二個正規式是相等的，當且僅當二個正規式所表示的正規集是相等的。例：設α是正規式，求證α|α=α。證： L(α|α)=L(α)∪L(α)=L(α) ∵L(α|α)=L(α) ∴α|α=α㈣正規式滿足下列關係①交換律：α|β=β|α②結合律：α|(β|γ)=(α|β)|γ，α(βγ)=(αβ)γ③分配律：α(β|γ)=αβ|αγ，(β|γ)α=βα|γα④εα=αε=α31㈤例設α=a|b|……|z，β=0|1|……|9。描述識別字的正規式：

α(α|β)*

描述二進位數的正規式：

(0|1)(0|1)*描述無符號整常數的正規式：

ββ*

描述無符號實常數的正規式：

ββ*.β*|.ββ*|(ββ*.β*|.ββ*|ββ*)(E|e)(+|-|ε)ββ*123.45 123.322.2.3確定有限自動機（DFA）㈠DFA定義一個確定有限自動機M是一個五元式

M=(S，Σ，f，s0，Z)S是一個有限集，它的每一個元素稱為狀態。Σ是一個有窮字母表，它的每個元素稱為一個輸入字元。f是一個從S×Σ至S的映照，即f：S×Σ→S（單值函數）例f(si,a)=sj，表示當現行狀態為si，若輸入字元為a，則轉移到下一狀態sj，sj稱為si的後繼狀態。s0∈S，是唯一的一個初態。Z

S，是一個終態集。例：一個識別二進位數的確定有限自動機

M=（{0，1}，{'0','1'}，f，0，{1}）其中f的定義如下：

f(0,'0')=1、f(0,'1')=1、f(1,'0')=1、f(1,'1')=133㈡狀態轉換矩陣函數f可用矩陣表示，行表示狀態，列表示輸入字元，該矩陣稱為狀態轉換矩陣。只要對初態和終態作適當標記，可用一個狀態轉換矩陣來表示DFA。㈢DFAM可用一個（確定的）狀態轉換圖表示例識別二進位數的DFA可用（確定的）狀態轉換圖表示如下：狀態/字元'0''1'011111接上例34㈣字α可為DFAM識別對於一個字α，若存在一條從初態結到某一終態結的路徑，且路徑上的所有弧的標記依序連接成的字為α，則稱α可為DFAM所識別或接受。若DFAM的初態結同時又是終態結，則稱空字ε可為DFAM所識別或接受。DFAM所識別的字全體記為L(M)。設α=1012=5

因從初態0出發，存在一條到終態1的路徑。路徑上的標記依次連接為101，則稱α=101可為M所識別或接受。

L(M)={α|α為二進位數}。352.2.4非確定有限自動機（NFA）㈠NFA定義一個非確定的有限自動機M是一個五元式

M=（S，Σ，f，S0，Z）S是一個有限集，它的每一個元素稱為狀態。Σ是一個有窮字母表，它的每個元素稱為一個輸入字元。f是一個從S×Σ*到S的子集映照，即f：S×Σ*→2S（多值函數）2S表示冪集，若S={0，1}，則2S={{}，{0}，{1}，{0，1}}。S0

S，是一個非空初態集，即NFA的初態不一定唯一。Z

S，是一個終態集。

DFA和NFA的主要區別為：映照f（函數），DFA的映照f是從"狀態×字元"映射到"狀態"，f為單值函數；而NFA的映照f是從"狀態×字"映射到"狀態子集"，f為多值函數。36例某一非確定有限自動機

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）㈡NFAM可用一個（非確定的）狀態轉換圖表示37㈢字α可為NFAM識別對於Σ*中的一個字α，若在NFAM中存在一條從某一初態到某一終態的路徑，且路徑上的所有標記依序連接成的字為α，則稱α可為NFAM所識別或接受。若M的某些結既是初態結又是終態結，或者存在一條從某個初態結到某個終態結的ε道路，那麼空字ε可為M所接受。非確定有限自動機M所識別的字全體記為L(M)。對於任何二個有限自動機M和M'，若L(M)=L(M')，則稱二個有限自動機M和M'等價。DFA是NFA的特例，對於每個NFAM存在一個DFAM'，使得L(M)=L(M')。382.2.5正規式與確定有限自動機的等價性

對於Σ上的每個正規式V，存在一個Σ上的確定有限自動機M，使得L(V)=L(M)。㈠V

NFA①將V表示成拓廣NFA②根據下麵三條規則對V進行分裂（規則基於識別的語言不變），直至每條弧上的標記為Σ上的一個字元或ε。

V

39例，已知正規式(a|b)*(aa|bb)構造它的NFA。40㈡NFA

DFA

為了便於描述NFA確定化演算法，我們引進二個概念。①I的ε閉包

I的ε閉包記為ε_CLOSURE(I)或CLOSURE(I)，設I是NFAM狀態集的一個子集，I的ε閉包定義為：若狀態s∈I，則s∈ε_CLOSURE(I)。若狀態s∈I，則從狀態s出發，經一條或多條ε弧所能到達的狀態s'也屬於ε_CLOSURE(I)。②IaI NFAM狀態集的一個子集

Ja

從I出發經一條a弧所能到達的狀態全體

Ia

ε_CLOSURE(Ja)41設I={1}，則CLOSURE(I)=CLOSURE({1})={1,2}。設I={5,4,3}，則CLOSURE(I)=CLOSURE({5,4,3})={5,4,3,6,2,8,7}。接上例設I={1，2}，則

Ja={4,5}∪{3}={3,4,5}

Ia

=CLOSURE({3,4,5})={5,4,3,6,2,8,7}③NFA確定化演算法IIa（a∈∑）Ib（b∈∑）CLOSURE({X})1）數據結構及初始狀態手工計算422）演算法描述0.procedureNFA_TO_DFA1. p_cur←1 //當前指針，指示當前處理的狀態子集。2. p_end←1 //表尾指針3. I[1]←CLOSURE({X})4. whilep_cur≤p_end

5. fori←1ton //設∑={x1,x2,…,xn}6. ifIXi[p_cur]≠{}andIXi[p_cur]

I[1..p_end]then7. p_end←p_end+18. I[p_end]←IXi[p_cur]9. endif10. endfor11. p_cur←p_cur+112. endwhile13.endprocedure43IIaIb{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}

根據上述演算法對NFAM進行確定化。因NFAM具有6個狀態，狀態子集個數（包括空集）最多為64，故表的長度不會超過26-1=63，迴圈必然在有限步中結束。3）結果處理將I中的每個子集視為DFAM'的一個狀態。ε_CLOSURE({X})視為DFAM'的初態。將所有含有原NFA終態(即Y)的DFAM'狀態視為終態。將I、Ia、Ib、……視為DFAM’狀態轉換矩陣，即函數f。4）重新標記狀態/字元ab0121322143324140是初態，3和4為終態。445）用（確定的）狀態轉換圖表示

構造過程採用子集法，從字的識別角度來看，DFAM'和NFAM是等價的。452.3詞法分析器的自動生成

輸入正規式（構詞規則），經自動生成器加工，其結果為DFA。詞法分析器的自動生成器輸入正規式輸出DFA（狀態轉換矩陣）㈠自動生成過程概述①構造描述每個單詞的正規式Pi(1≤i≤N)。②根據正規式Pi構造NFAMi(1≤i≤N)，假定初態均為0。在構造NFAMi的同時，逐步並且最終形成識別全部單詞的NFAM。③NFAM確定化④重新標記，構造DFAM'。46㈡實例（模型語言的詞法）①模型語言字元集{'a'..'z'，'0'..'9'，'+'，'='，'*'，','，';'，'('，')'，'#'}②模型語言單詞集基本字：begin、end、integer、real識別字：以字母開始的數字字母串無符號整常數：數字串運算符：+、*、++、=界符：,、;、(、)、#③單詞編碼基本字：begin('{',"NUL"}、end('}',"NUL")、integer('a',"NUL")、real('c',"NUL")識別字：('i',字串) 無符號整常數：('x',字串)運算符:=('=',"NUL")、+('+',"NUL")、*('*',"NUL")、++('$',"NUL")界符：,(',',"NUL")、;(';',"NUL")、(('(',"NUL")、)(')',"NUL")、#('#',"NUL")47②構造NFAM實例解：①構造正規式（令α=a|b|c|d|……|z、β=0|1|2|3|4|5|6|7|8|9）識別字

α(α|β)*無符號整常數

ββ*運算符 單詞本身（例'='的正規式為'='，"++"的正規式為"++"）界符 單詞本身（例';'的正規式為';'）基本字通常是由字母構成，符合識別字規則，將基本字作為一種特殊識別字來處理（可設置保留字表，二者區分可通過查表）。48③NFAM確定化IIαIβI=I+I*I,I;I(I)I#{0}{1,12,13}{2,14,15}{3}{4,5}{6}{7}{8}{9}{10}{11}{1,12,13}{12,13}{12,13}{2,14,15}{14,15}{3}{4,5}{16}{6}{7}{8}{9}{10}{11}{12,13}{12,13}{12,13}{14,15}{14,15}{16}49④重新標記，構造DFAM'。狀態/字元αβ=+*,;()#0123456789101111121234135678910111111121213注：0為初態，其餘均為終態。50㈢掃描器控制程式工作原理每次識別單詞，控制程式總是從初態出發，不斷讀入字元，進入下一狀態，尋求最長匹配，直到無法前進為止，這樣始終多讀一個字元。在狀態遷移過程中，需用Token數組保存讀入字元。在無法前進時，若發現當前狀態為終態，則認為識別出一個單詞，反之出錯，即Token數組所保存的字串不構成一個單詞，而是根源程式中的一個錯誤詞形。事先設置一個單詞二元式編碼表，它包括除識別字和整常數以外的所有單詞（基本字、運算符和界符）。當DFA識別出一個單詞，就根據Token數組所保存的字串去查表。若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為識別字和整常數二者之一，只要稍加判斷即可區分。首字元為字母的是識別字，首字元為數字的是無符號整常數。51DFA每次只能識別一個單詞，需多次使用DFA來識別根源程式中單詞，直到根源程式中的字元全部處理完。由於構造的方法不同，在DFA某一個終態中，有可能包含原NFA中的二個終態或更多，即在該狀態可識別出二個詞形相似的單詞，這就存在一個優先匹配問題。此時，需調整單詞二元式編碼表中的單詞排列順序，將需優先匹配的單詞排在表的較前面，這樣在單詞查找過程，讓其先得到匹配。

設根源程式為“x+++y#”（‘#’是預處理程式添加的），掃描器共使用確定有限自動機5次（見下頁）。52從初態0出發，讀入'x'進入狀態1，在狀態1讀入'+'，無法前進。因當前所處狀態1為終態，故識別出一個單詞。查表未果，由於首字元為字母，故單詞"x"為識別字，返回單詞二元式編碼('i',"x")並退回'+'。從初態0出發，讀入'+'進入狀態4，在狀態4讀入'+'，進入終態13，在狀態13讀入'+'，無法前進。因當前所處狀態13為終態，故識別出一個單詞。查表，確認識別出單詞為"++"，返回單詞二元式編碼('$',"NUL")並退回'+'。從初態0出發，讀入'+'進入狀態4，在狀態4讀入'y'，無法前進。因當前所處狀態4為終態，故識別出一個單詞。查表，確認識別出單詞為"+"，返回單詞二元式編碼('+',"NUL")並退回'y'；從初態0出發，讀入'y'進入狀態1，在狀態1讀入'#'，無法前進。因當前所處狀態1為終態，故識別出一個單詞。查表未果，由於首字元為字母，故單詞"y"為識別字，返回單詞二元式編碼('i',"y")並退回'#'。從初態0出發，讀入'#'，進入狀態10。由於無法再讀入字元，即查表，確認識別出單詞為"#"，返回單詞二元式編碼('#',"NUL")。識別出單詞"#"意味著整個根源程式中字元全部處理完畢。53㈣掃描器控制程式的實現⑴狀態轉換矩陣的數位化控制程式是根據DFA來工作的，首先要將狀態轉換矩陣數位化，空白用0表示。在預處理中，空格作為界符被保留下來。單詞的前導空格在識別一個單詞前被濾去，單詞的尾部空格用作單詞的終止標誌，故在狀態轉換矩陣中，應增加空格列，該列每個元素的值均標記為0。因26個字母作用相同，故可用一列表示。在查表時可將26個字母轉換成1個，例'a'。因10個數字作用相同，故可用一列表示