第三章詞法分析及有窮自動機第1頁，課件共127頁，創作于2023年2月第三章詞法分析及有窮自動機

主要內容

●詞法分析程序的設計過程。●描述單詞的文法：正規文法和正規式及它們之間的轉換。●單詞識別機制（有窮自動機）。●正規式，正規文法和有窮自動機三者之間相互轉換。第2頁，課件共127頁，創作于2023年2月§1.詞法分析程序的任務一、詞法分析程序的任務及處理方式

1.詞法分析程序的任務主要任務：從左至右逐個字符地對源程序進行掃描，產生一個個單詞序列，用以語法分析。詞法分析程序（掃描程序）：執行詞法分析的程序。第3頁，課件共127頁，創作于2023年2月2.詞法分析程序的處理方式詞法分析程序與語法分析程序接口方式有兩種：第一種方式：

將詞法分析作為單獨一遍掃描，即在語法分析之前，實現源程序的詞法分析工作。其輸出（單詞串）形成一個中間文件（內部形式的源程序表），然后移交給語法分析程序。第4頁，課件共127頁，創作于2023年2月第二種方式：將詞法分析程序編寫成一個子程序，每當語法分析程序需要讀一個新單詞時，便去調用它。

注：后一種方式比較好。因為不需要在內存中構造和保存中間文件。第5頁，課件共127頁，創作于2023年2月二、詞法分析程序的I/O1.輸入 字符串表示的源程序

2.輸出 單詞符號序列或單詞符號。

1)程序語言的單詞符號單詞：指語言中具有獨立意義的最小語法單位。語言中的單詞符號：一般可歸結為五種：保留字（基本字）：如if,for,and等――個數確定標識符：表示常量、變量、類型、過程等名稱――個數不確定常數：如34，-0.37等――個數不確定運算符：如+，-，*，/，<等――個數確定界線符：如逗號，分號，括號等――個數確定第6頁，課件共127頁，創作于2023年2月注：·保留字，運算符，界線符可列表，供詞法分析程序查詢；

·標識符和常數可用正規文法或正規式描述，供詞法分析程序識別。2)輸出的單詞形式二元組：（單詞的種別碼，單詞自身值）

1o

單詞的種別碼：表示單詞的種類分類的原則：處理簡單分類的方法：使每一個單詞對應一個整數碼分類的目的：最大限度地區別各個單詞 單詞地分類法有多種：一種一類一字一類或一符一類第7頁，課件共127頁，創作于2023年2月具體：保留字：一字一種。如：

if 1 then2

。。。標識符：統歸一種。常數：整數，實數，布爾統為一種或按類型分整數 11實數 12布爾 13

或全體一種第8頁，課件共127頁，創作于2023年2月+ 29 :=17= 21- 14<>18>=22* 15<19>23/ 16<=20…運算符：+，-，*，/，>，<等統為一種；或一符一種：

第9頁，課件共127頁，創作于2023年2月2o

單詞自身值（可有可無） 單詞自身值是單詞的機內代碼或者單詞在表格中的地址碼。如：標識符：自身的字符串（1，’a’）常數：自身的二進制數（11，’100’的二進制數）例：一種一類的單詞輸出形式 設保留字、標識符、常數、運算符、分界符的種別碼分別為1，2，3，4，5；將ifa>1thenb:=10表示為一種一類的單詞輸出形式。第10頁，課件共127頁，創作于2023年2月ifa>1thenb:=10＝>詞法分析器=>(1,’if’)(字符串表示的源程序)(2,’a’),(4,’>’)(3,’1’的二進制數)(1,’then’)(2,’b’)(4,’:=’)(3,’10’的二進制數)第11頁，課件共127頁，創作于2023年2月例：采用一字一類或一符一類地分類技術，則保留字單詞自身值可無，但事先構造一個保留字單詞對照表，其值可在詞表中查到。ifa>1thenb:=10＝>詞法分析器=>(1,◎)字符串表示的源程序(10,‘a’)(23,◎)(3,’1’的二進制數)(2,◎)(10,’b’)(17,◎)(11,’10’的二進制數)上面符號◎表示要查保留詞表第12頁，課件共127頁，創作于2023年2月表2.1保留字單詞表單詞類別碼單詞類別碼...............If1+29Then2-14else3*15......

/16............>23for19:=17...第13頁，課件共127頁，創作于2023年2月§2.詞法分析程序的設計過程一、詞法分析程序的設計過程設計過程：詞法分析程序設計過程：①把有的單詞（如：標識符和常數）用正規文法或正規式描述；②將正規文法或正規式轉換成等價的狀態轉換圖（最小化的DFA圖）；③根據狀態轉換圖設計詞法分析程序（狀態轉換圖可視為詞法分析程序的框圖）。轉換規則分裂法子集法

狀態轉換圖（DFA圖）第14頁，課件共127頁，創作于2023年2月二、用狀態轉換圖設計詞法分析程序

1.詞法分析程序的預處理詞法分析程序在識別單詞前，需要對輸入到緩沖區的源程序進行預處理。預處理：刪去無用的空格，跳格，回車和換行等編輯性字符；刪去注釋部分每次對一串定長（如120個字符）的輸入字符進行預處理，并裝入一個指定的掃描緩沖區中。第15頁，課件共127頁，創作于2023年2月掃描緩沖區是一個一分為二的區域，每一個區域可容納120個字符，且相互交替使用。搜索指針從單詞起點開始搜索，如果遇到半區的邊界但尚未達到單詞的終點時，則可將后續的120個輸入字符裝進緩沖區的另一半中。第16頁，課件共127頁，創作于2023年2月2.狀態轉換圖狀態轉換圖是為了識別正規文法或正規式而專門設計的有向圖。他是有窮自動機的非形式化表示。狀態轉換圖的組成：

1o

有限個狀態結點狀態結點代表正規文法的非終結符（用單圈表示）；開始狀態結點：用雙箭頭指示；終止狀態結點：用雙圈表示。

2o弧線→弧上的標記x指明在射出弧的結點狀態下可能出現的輸入字符或字符類,即終結符。(→表示機器的識別方向).大多數單詞結構是用正規文法描述的x第17頁，課件共127頁，創作于2023年2月例：<標識符>∷=<字母>|<標識符><字母>|<標識符><數字><整數>∷=<數字>|<整數><數字><運算符>∷=+|-|*|/|….<界線符>∷=；|，|(|)|…..。。。3.由正規文法構造狀態轉換圖1)左線性正規文法構造狀態轉換圖 左線性正規文法的一般形式：U∷=a|wa第18頁，課件共127頁，創作于2023年2月左線性正規文法構造狀態轉換圖的步驟如下：增加一個開始狀態結點s（假定文法的詞匯表中不含s）；以每個非終結符為狀態作結點；對于形如U∷=a的每一個規則，引一條從開始狀態s到狀態U的弧，弧上標記為a；

對于形如U∷=wa的每一個規則，引一條從狀態w到狀態U的弧，弧上標記為a；以識別符號為終止狀態。第19頁，課件共127頁，創作于2023年2月例：設有正規文法G[Z]：

Z∷=U0|V1 U∷=Z1|1 V∷=Z0|0（描述的語言為L(G)={01,10}）則狀態轉換圖如下：＋以開始符號Z作終態新增加開始狀態S第20頁，課件共127頁，創作于2023年2月例：標識符的轉換圖：

從開始狀態出發到某一終止狀態結點為止，所經過的路徑上的符號串，稱能為該狀態轉換圖所接收（識別）的符號串。如：標識符x26為上述轉換圖識別，識別路徑為第21頁，課件共127頁，創作于2023年2月2)

右線性正規文法構造狀態轉換圖右線性正規文法U∷=a|aV構造狀態轉換圖的步驟：增加一個終止狀態結點z（假定文法的詞匯表中不含z）；以每個非終結符為狀態作結點；對于形如U∷=a的每一個規則，引一條從開始狀態U到終止狀態z的弧，弧上標記為a；對于形如U∷=aV的每一個規則，引一條從狀態U到狀態V的弧，弧上標記為a；以識別符號為開始狀態。第22頁，課件共127頁，創作于2023年2月４．根據狀態轉換圖設計詞法分析程序狀態轉換圖實際上是編寫詞法分析程序的框圖根據狀態轉換圖寫出相應的詞法分析程序的方法：

1o對于每個狀態構造一小段程序。 功能：從輸入串中讀一個字符；判明讀入字符與由此狀態出發的哪條弧上的標記匹配，便轉至相匹配的那條弧所指的狀態；均不匹配時便失敗（不能達到正常出口）第23頁，課件共127頁，創作于2023年2月2o再根據圖形決定小段程序之間的調用。 注：詞法分析程序除了識別單詞外，還可為語法程序提供更多的信息。因此，可在這些小段程序中加上一些語義處理（如對數值進行10=>2等）例：設有關于單詞<無符號數>的文法G=(VN,VT,P,N1)其中，VN={N1,N2,N3,N4,N5,N6,N7}VT={d,．,e,f,∧}P： N1∷=dN2|．N3|eN5 N2∷=dN2|．N3|eN5|∧ N3∷=dN4

這里d表示數字（0～9）；e＝10；f＝；∧表示空字符；N1表示無符號數，其一般形式為：d…d．d…defd…dN4∷=dN4|eN5|∧N5∷=dN7|fN6N6∷=dN7N7∷=dN7|∧第24頁，課件共127頁，創作于2023年2月試構造識別此單詞的詞法分析程序1>根據右線性正規文法，畫出狀態轉換圖N1=>3N2=>34N2=>34·N3=>34·5N4

=>34·56N4=>34·56(達到出口),自上而下的推導過程。第25頁，課件共127頁，創作于2023年2月2>根據狀態轉換圖寫詞法分析程序為每一個狀態結點寫一個過程或函數：對N1結點：ProcedurePN1 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elseerror End;第26頁，課件共127頁，創作于2023年2月對N2結點：ProcedurePN2 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elsereturn; End;對N3,N4,N5,N6,N7結點分別寫出程序段：……第27頁，課件共127頁，創作于2023年2月§3正規式與有窮自動機為了進一步討論詞法分析程序的自動生成，需要將狀態轉換圖的概念加以形式化；同時將由正規文法描述的單詞由正規式描述，可利用有窮自動機生成詞法分析程序。一、正規式與正規集 語言的單詞結構不僅由正規文法描述，還可以由正規式描述。第28頁，課件共127頁，創作于2023年2月例：<標識符>∷=<字母>|<標識符><字母>|<標識符><數字>

此正規文法描述了一個語言的集合。定義在{字母，數字}上的以字母開頭的符號串的集合。這個集合還可以用正規式描述：字母(字母|數字)*。正規式描述的字符串的集合稱為正規集1．正規式（也稱正則式，正則表達式）和正規集的遞歸定義設有字母表∑={a1,a2,…,an},那么(1)ε,Φ,ai都是∑上的正規式，它們所描述的正規集分別為{ε}，Φ，{ai}；第29頁，課件共127頁，創作于2023年2月(2)若e1和e2都是∑上的正規式，它們所描述的正規集L(e1)、L(e2)，則：1o正規式的“或”（|）運算：e1|e2也是正規式，相應正規集為L(e1|e2)=L(e1)∪L(e2)；2o正規式的“連接”（.）運算：e1e2也是正規式，相應正規集為L(e1e2)=L(e1)L(e2)；3o正規式的“閉包”（*）運算:(e1)*也是正規式，相應正規集為

L((e1)*)=(L(e1))*；(3)僅由有限次使用(1),(2)定義的表達式才是∑上的正規式，由這些正規式所表示的字符集才是∑上的正規集。第30頁，課件共127頁，創作于2023年2月例：設∑={a,b}，則∑上的正規式和正規集有正規式正規集1o

a和baL(a)={a}和L(b)={b}L(a)=L(a)∪L(a)∪L(a)∪…={a}={a,aa,...}基本3oa|bL(a|b)=L(a)∪L(b)={a,b}4oabL(ab)=L(a)L(b)={ab}5oa*L(a*)=(L(a))*=L(a)∪L(a)∪L(a)∪….={a}*={ε,a,aa,aaa,..…}復合6oba*L(ba*)=L(b)L(a*)={b,ba,baa,baaa,……}7oa|ba*L(a|ba*)=L(a)∪L(ba*)={a,b,ba,baa,……}8o(a|b)*L((a|b)*)=(L(a|b))*={a,b}*={ε,a,b,aa,ab,……所有ab組成的串}9oa(a|b)*L(a(a|b)*)=L(a)(L(a)∪L(b))*={a}{a,b}*10o(a|b)*(aa|bb)(a|b)*L((a|b)*(aa|bb)(a|b)*)={a,b}*{aa,bb}{a,b}*012+123++2o第31頁，課件共127頁，創作于2023年2月

注：.正規式僅由字母∑中的終結符號，通過或，連接和閉包三種運算組成的式子。例：有字母表∑={a，b}，下面正規式，求正規集。

ba*正規集：b開頭后面跟0個或若干個a。

a(a|b)*正規集：a開頭后面跟0個或a、b任意排列。例：有字母表∑={a，b}，下面用自然語言描述的正規集，求正規式(可能不唯一)。以ab結尾的所有字符串。(a|b)*ab

包含偶數個b的所有字符串。(bb)*

只包含一個a的所有字符串。b*ab*

不包含ab子串的所有字符串。b*a*

以a開頭b結尾的所有字符串。a(a|b)*b第32頁，課件共127頁，創作于2023年2月

２．正規式的性質（1）正規式的等價性定義：若正規式e1與e2描述的正規集相同，即L(e1)=L(e2)，則e1與e2等價，記做e1=e2。（2）正規式的代數性質設r,s,t為正規式，正規式服從的代數規律有：1or|s=s|r“或”滿足交換律2or|(s|t)=(r|s)|t“或”滿足結合律3o(rs)t=r(st)“連接”滿足結合律。

“連接”不滿足交換律4or(s|t)=rs|rt(s|t)r=sr|tr“連接”滿足分配律5oεr=rrε=r

ε

是“連接”的恒等元素第33頁，課件共127頁，創作于2023年2月(3)正規式的恒等式 設A和B式正規式，有例：證明：A*=ε|AA*成立。 證明:利用對應的正規集來證明：

L(AA*|ε)=L(A)L(A*)UL(ε)=L(A)L(A)*UL(ε)=L(A)((L(A))UL((A))U(L(A))…..)UL(ε)=L(ε)U((L(A))U(L((A))U(L(A))…..)=(L(A)*)=L(A*)∴A*=AA*|ε例：設∑={d,．,e,+,-}則∑上的正規式：

d*(．dd*|ε)(e(+|-|ε)dd*|ε)表示無符號數：2.12,3.6e-2等。表示無符號數的正規式，比表示無符號數的正規文法顯得直觀，簡潔。1o（A*）*=A*2oA|BA=(ε|B)A3oAA*=A*A；A=AA*4oA*=ε|AA*;A*=(A|ε)*012312+第34頁，課件共127頁，創作于2023年2月3．正規文法與正規式的轉換關系：對任意一個正規文法存在定義同一語言的正規式反之：對于每一個正規式，存在一個生成同一語言的正規文法。兩者之間具有等價的轉換關系。 有的語言容易用正規文法定義，有的語言則更容易用正規式定義轉換：1o

正規式-——>正規文法將∑上的一個正規式轉換成正規文法G=(VN,VT,S,P)：首先：令VT=∑第35頁，課件共127頁，創作于2023年2月再確定產生式P和VN，其方法：

對任何正規式r，選擇非終結符S生成產生式S∷=r，并將S定義為G的識別符號。<a>若r含有正規式x,y,對形如A∷=xy（連接的變換）產生式，用A∷=xB,B∷=y兩個產生式替換。其中B是新選擇的非終結符。<b>對已經轉換成文法中的形如：A∷=x*y

（閉包和連接的變換）的產生式，則重寫為：

A∷=xA注：若y是ε則，A→xA A∷=yA→

ε<c>對形如：A∷=x|y

（或的變換）的產生式，重寫為A∷=x,A∷=y<d>不斷利用上述規則作變換，直到每個產生式右部最多含有一個終結符為止。第36頁，課件共127頁，創作于2023年2月例：將正規式R=a(a|d)*轉換成相應的正規文法。解：令S是文法的識別符號，則首先形成：

S∷=a(a|d)*然后形成：

S∷=aA,A∷=(a|d)*(其中A∈VN)對于A∷=(a|d)*重寫為：

A∷=(a|d)A A∷=ε對于A∷=(a|d)A重寫成：A∷=aA,A∷=dA最后轉換的等價正規文法G=(VN,VT,S,P) VT={a,d} VN={S,A} P:S∷=aA A∷=aA|dA|ε第37頁，課件共127頁，創作于2023年2月2o正規文法——>正規式 基本是上述的逆過程。最后只剩下一個識別符號定義的產生式，且產生式的右部不含非終結符。其轉換規則如下表：規則文法產生式正規式1A∷=xB,B∷=yA=xy2A∷=xA|yA=x*y3A∷=x,A∷=yA=x|y注：正規文法與正規式互相轉換，關鍵式：A→xA|yA=x*y第38頁，課件共127頁，創作于2023年2月例：正規文法G[s]：

S∷=aA S∷=a A∷=aA A∷=dA A∷=a A∷=d求正規式解：先有：S＝aA|a規則3 A=(aA|dA)|(a|d) 規則3再將A的正則式變成：A=(a|d)A|(a|d) “或”分配律根據規則2變成：A=(a|d)*(a|d)再代入S的右部得：S=a(a|d)*(a|d)|a再利用正則式代數變換：

S=a((a|d)*(a|d)|ε) S=a(a|d)*

即：a(a|d)*為所求的正則式第39頁，課件共127頁，創作于2023年2月簡便轉換方法是:(1)將正規文法中的每一個非終結符表示成關于它的一個正規方程,獲得一個聯立方程組.(2)依據求解規則:若x∷=αx|β,寫成方程x=αx+β(“|”用“+”表示);則解為x=α*β.若x∷=xα|β,寫成方程x=xα+β(“|”用“+”表示);則解為x=βα*.以及正規式的分配律,交換律和結合律求關于文法識別符號的正規式方程組的解.此解就是關于文法識別符號S的一個正規式.例如,上例:先寫出正規式方程組(方程組中用“+”代替“|”): S∷=aA|a 寫成:S=aA+a……（1）

A∷=aA|dA|a|d 寫成:A=aA+dA+a+d……（2）將（2）式簡化為：A=(a+d)A+(a+d)使用求解規則：A=(a|d)*(a|d)……（3）將（3)的A代入（1)式：S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)∴a((a|d)*(a|d)|ε)=a(a|d)*即為所求的正規式。第40頁，課件共127頁，創作于2023年2月

例：設有正規文法G:Z∷=0AA∷=0A|0BB∷=1A|ε試給出該文法的正規式。解：給出相應的正規式方程組：

Z=0A……（1）

A=0A+0B……（2）

B=1A+ε……（3）（3）代入（2）中的B得：A=0A+01A+0=(0+01)A+0使用求解規則：A=(0|01)*0……（4）（4）代入（1）式中的A得：Z=0(0|01)*0所以，0(0|01)*0即為所求的正規式。例：設有正規文法G:P:{A::=aB|bB,B::=aC|a|b,C::=aB}相應的正規式方程：A=aB+bB………（1）

B=aC+a+b………(2)C=aB……….(3)(3)代入(2)中的C:B=aaB+a+b…….(4)第41頁，課件共127頁，創作于2023年2月

對(4)式使用求解規則：B=(aa)*(a|b)…….(5)

將（5）代入(1)式中的B：A=(a|b)(aa)*(a|b)∴(a|b)(aa)*(a|b)即為所求。二、有窮自動機(FA)自動機：是一種能進行運算，并能實現自我控制的裝置。裝有程序的計算機也具有運算和自我控制能力，因此計算機是一部自動機所謂有窮自動機：自動機受囿于它能存儲的信息量，因此是有限的（有窮的）自動機是識別符號串處理的強有力的工具，因而它成為研究詞法分析器的重要基礎。有窮自動機分為：確定的有窮自動機（DFA）非確定的有窮自動機（NFA）第42頁，課件共127頁，創作于2023年2月１．確定的有窮自動機（DFA）(1)DFA的形式定義：一個DFAM是一個五元組：

M=(S,∑,f,S0,F)其中：S：非空有窮的狀態集：每個元素是一個狀態。∑：有窮輸入字母表；每個元素是輸入的一個字符。

f：狀態轉換函數：是從S×∑－>S的單值映射函數：

f(S1,a)=S2S0∈S是唯一的開始狀態

FS是終止狀態集，可空（識別不出的字符串）例：設有DFAM=({0,1,2,3},{a,b},f,0,{3})其中：f：f(0,a)=1 f(0,b)=2DFA的函數式表示

f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3第43頁，課件共127頁，創作于2023年2月(2)DFA的狀態圖表示：開始狀態為0，終止狀態為3，狀態集為{0,1,2,3}，字母表為：{a,b}

一般：假定DFAM含有m個狀態，n個輸入字符，則狀態圖含有m個結點，每個結點最多有n條弧射出。第44頁，課件共127頁，創作于2023年2月(3)DFA的矩陣表示：矩陣的行表示狀態，列表示輸入字符，矩陣中的元素表示相應狀態行和輸入字符列下的新狀態。即K行a列為f(K,a)的值。DFA的功能：對于∑*中的任何字符串α,若存在一條從開始結點到某一終態結點的道路，其路上所有弧的標記符連成的字符串等于α，則稱α能為DFA所識別（接受）。特別：若DFA的開始態結點同時又是終態結點，則空串可為DFA所識別。狀態\字符ab012132213333第45頁，課件共127頁，創作于2023年2月注：

①DFA有3種表示法：函數表示，狀態圖表示，狀態矩陣表示。

②DFA的確定性表現在轉換函數f:S×∑－>S是一個單值函數。即：對于任何狀態s∈S，和輸入符號a∈∑,f(s,a)能唯一確定下一個狀態。③可以證明：若存在一個正規文法G，G產生的語言L（G）,當且僅當存在一個∑上的確定有窮自動機M，使得L（G）＝L（M）。 即：正規文法G在∑上描述的語言，一定存在DFA能夠識別這個語言。反之：若存在一個被DFA識別的語言，一定由存在的正規文法所描述。④由于DFA能識別正規文法描述的單詞，因此要想構造識別單詞的詞法分析程序，也就成為怎樣構造DFA的問題了。第46頁，課件共127頁，創作于2023年2月2.非確定的有窮自動機（NFA）定義：一個NFA也是一個五元組：

M＝（S，∑，f，S0，F）其中：S，∑，F同DFAS0S是一個非空開始狀態集f：是一個多值的轉換函數：S×∑－>S的子集映射NFA與DFA的區別：NFA有一個開始狀態集，而DFA只有一個開始狀態；NFA轉換函數是多值函數，DFA的轉換函數是單值函數。第47頁，課件共127頁，創作于2023年2月例：設有NFAM＝（S,∑,f,S0,F）其中，S={q0,q1,q2,q3},∑={x,y},S0={q0},F={q1}f: f(q0,x)={q1,q2} f(q0,y)={q0} f(q1,x)={q0} f(q1,y)={q1,q2} f(q2,x)={q3} f(q2,y)={q3} f(q3,x)={q1,q3} f(q3,y)={q3}NFAM的狀態圖表示：第48頁，課件共127頁，創作于2023年2月狀態\字符xyq0{q1,q2}{q0}q1{q0}{q1,q2}q2{q3}{q3}q3{q1,q3}{q3}NFAM的矩陣表示：注：DFA是NFA的特例；對于每個NFAM，存在一個DFAM’,使得L(M)=L(M’)對于任何兩個有窮自動機M和M’，若L(M)=L(M’)，則稱M與M’等價。第49頁，課件共127頁，創作于2023年2月三、由正規式構造NFA或將NFA轉換成正規式１．理論依據定理：正規式與有窮自動機是等價的。１o

∑上的NFAM，可以構造∑上的正規式R，使：

L(M)=L(R)２o

在∑上的每個正規式R，可以構造∑上的NFAM使：

L(R)=L(M)注：由正規式（或正規文法）構造有窮自動機的意義在于：將單詞的描述結構轉換為對單詞的識別結構。第50頁，課件共127頁，創作于2023年2月２．由正規式構造NFA

方法：分裂法輸入：∑上的正規式R輸出：識別R的NFA步驟：1o引進一個開始狀態結點x和終止狀態結點y：第51頁，課件共127頁，創作于2023年2月

2o若R為復合公式，分裂R直到每條邊上只留下一個符號（可以為ε）為止；3o

分裂的結果：保證一個唯一的開始狀態結點和終止狀態結點。第52頁，課件共127頁，創作于2023年2月例：設∑={x,y}上的正規式e=xy*(xy|yx)x*,構造一個NFAM，使得L(M)=L(e)解:第53頁，課件共127頁，創作于2023年2月例：已知正則式e=0(1*)*|01 ，求：NFA ∵(A*)*=A* (A|A*=A*) ∴e=0(1*)*|01（利用恒式化簡，然后構造NFA）

=01*|01=0(1*|1)=01*構造NFA：第54頁，課件共127頁，創作于2023年2月３．將NFA轉換成正規式方法：合并法

（與分裂法相反） 輸入：NFAM

輸出：一個正規式e

步驟：

1o

對于NFAM中的開始狀態和終止狀態分別新設置一個唯一的開始狀態和終止狀態，使所設的開始狀態到原開始狀態連接ε弧；原終止狀態到所設的終止狀態連接ε弧。s為新增的開始狀態Z為新增的終止狀態第55頁，課件共127頁，創作于2023年2月2o

利用下列規則進行合并，直到圖中只剩下新設置的開始態和終止態為止。那么在開始態和終止態弧上的正規式便是所求的結果。第56頁，課件共127頁，創作于2023年2月例：已知NFA如下，求正規式e1o新設置一個唯一的開始狀態和終止狀態：第57頁，課件共127頁，創作于2023年2月2o

按照合并規則進行合并

∴e=(x|y)*(xy*y|yx*x)第58頁，課件共127頁，創作于2023年2月四、NFA到DFA的轉換（NFA的確定化）

1.理論依據和目的

定理：若L為一個能被NFA接受的語言，則存在一個能接受L的DFA： 即：L(NFAM)=L(DFAM)

目的：①

消除NFA中ε弧。ε弧會使自動機做無用功。

②合并NFA中不確定的狀態。不確定狀態不僅給自動機識別字符串帶來困難，而且使得編制相應的詞法分析程序變得更為復雜。

NFA到DFA的轉換的基本思想：

DFA的每一個狀態對應于NFA的一組狀態（狀態集合）。

方法：子集法

第59頁，課件共127頁，創作于2023年2月2.子集法分兩種情況介紹NFA的確定化：①不含ε弧的NFA的確定化。②含ε弧的εNFA的確定化 由NFAA=（S,∑,f,S0,F）構造DFAA’=（S’,∑,f’,q0,F’）方法：1o

DFAA’的輸入字母表∑與NFAA的∑完全相同2o

把NFAA的每一個狀態子集作為DFAA’的一個狀態，因此該構造方法稱為子集法。第60頁，課件共127頁，創作于2023年2月3o

設NFAA的任一狀態子集{r1，r2，…,rn},ri∈S(i=1,2,…,n),令r’=[r1，r2，…,rn],r’∈S’。取a∈∑,DFAA’的映射函數定義為：

f’(r’,a)=q’∈S’

其中，q’=[q1，q2，…,qm],而{q1，q2，…,qm}=f(r1,a)∪f(r2,a)∪…∪f(rm,a)。4oDFAA的開始狀態q0={S1，S2，…,SK}，其中，Si∈S0(i=1,2,…,K)5oDFAA的終止狀態F’={e’|e’=[e1，e2，…,ep],{e1，e2，…,ep}∩F≠Φ}第61頁，課件共127頁，創作于2023年2月具體操作方法：1o

依據NFA,構造確定化矩陣：

步驟：設狀態S0是NFA的開始狀態，以[S0]作為DFA的開始狀態，[S0]∈S’.再由f’([S0],a)=[S1,S2]（a∈∑）若：f’([S0],b)=[S0]（b∈∑）則：[S0]狀態對于輸入字符a,b的映射分別是狀態[S1,S2]與[S0]。其中：[S1,S2]∈S’是DFA的新狀態。第62頁，課件共127頁，創作于2023年2月再求新狀態[S1,S2]對于a,b的映射，設：

f’([S1,S2],a)=[S0,S3]∈S’ f’([S1,S2],b)=[S1,S2,S3]∈S’，即：[S0,S3]和[S1,S2,S3]均為DFA的新狀態。每得到一個新狀態，就繼續求新狀態對a,b的映射，直到再沒有新狀態為止。

2o

依據1o求出的確定化矩陣，代換出確定化的狀態轉換矩陣。

3o

依據確定化的狀態轉換矩陣畫出狀態轉換圖。（1）不含ε弧的NFA的確定化第63頁，課件共127頁，創作于2023年2月例:設有NFA的N=({q0,q1,q2,q3},{x,y},f,{q0},{q1})的狀態轉換圖如下：求等價的DFA（見前例）

第64頁，課件共127頁，創作于2023年2月解：1o依據NFA，構造確定化矩陣：狀態\輸入xy{q0}{q1,q2}{q0}{q1,q2}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q1,q3}{q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}第65頁，課件共127頁，創作于2023年2月2o

依據構造的確定化矩陣，代換成確定化的狀態轉換矩陣(用符號重寫確定化矩陣)

將確定化矩陣中的{q0}，{q1,q2}，{q0,q3}……分別用符號標記：A1,A2,……，A6即可。狀態\輸入xyA1A2A1A2A3A4A3A4A3A4A5A4A5A6A6A6A6A6第66頁，課件共127頁，創作于2023年2月3o

依據確定化的轉換矩陣畫出狀態轉換圖確定開始狀態為：A1(代替[q0])終止狀態為：A2，A4，A5，A6（A2，A4，A5，A6分別代替{q1,q2}，{q1,q2,q3}，{q0,q1,q3}，{q0,q1,q2,q3},其中包含NFA中的終止態q1）第67頁，課件共127頁，創作于2023年2月（2）εNFA的確定化（帶有空移或空環路的NFA）設εNFAM=(Q,∑∪{ε},f,Q0,F)，有：

1o狀態子集I的ε閉包（記為ε-closure(I)）I蘊涵于Q,狀態子集I的ε-closure(I)定義如下：若狀態q∈I，則q∈ε-closure(I);若狀態q∈ε-closure(I),q’是由q出發經多條ε弧到達的狀態，則q’∈ε-closure(I)，顯然，

ε-closure(I)蘊涵于Q第68頁，課件共127頁，創作于2023年2月例：設有狀態轉換圖如下：

顯然，狀態集Q={1,2,3,4,5,6,7,8}若子集I={1}，則：ε-closure(I)={1,2}(∵狀態1∈I,∴1∈ε-closure(I)；又∵從狀態1出發經ε弧可到達狀態2∴2∈ε-closure(I))若子集I={4，5}，則：ε-closure(I)={2,4,5,6,7,8}第69頁，課件共127頁，創作于2023年2月2o狀態集合I的a弧轉換表示為

f(I,a)={q’|f(q,a)=q’,q∈I}=J（其中J蘊涵Q）即：J是由子集I中的狀態出發，經過一條a弧（跳過a弧前的任意條ε弧）可到達的狀態的集合。令：Ia=ε-closure(J)表示：子集Ia是從子集I中任意狀態出發，經a弧（前后可跳過ε弧）而到達的狀態的集合。例：上例，若子集I={1},根據定義：子集J=f({1},a)={5,3,4}

于是：子集Ia=εclosure(J)=εclosure({5,3,4}={5,3,4,6,2,8,7}1,2的定義是為了消除空弧或空環。第70頁，課件共127頁，創作于2023年2月例：已知εNFAM如下圖。下面以此為例介紹εNFA確定化過程。解：依據εNFA的開始狀態集{S},求ε-closure({S})={S}（匯集S射出ε弧的結點集合）作為DFA的開始狀態。不斷地按新的非空子集求對輸入符號x,y的Ix和Iy，并將新的Ix或Iy作為DFA的狀態。這一過程一直重復到不再出現新的Ix或Iy為止。第71頁，課件共127頁，創作于2023年2月如：Ix=ε-closure({1})={1,2,3} Iy=ε-closure(Φ)=Φ∵Ix為非空新子集，作為DFA的狀態，且繼續以{1,2,3}求Ix和Iy。

Ix=ε-closure({1,2,3})={4} Iy=ε-closure({1,2,3})={2,3,5}

其中，{4}和{2,3,5}作為DFA的結點，且又是新的Ix,Iy,,繼續求Ix，ly，過程如下矩陣：IxIy{S}{1,2,3}Φ{1,2,3}{4}{2,3,5}{4}Φ{6,7,Z}{2,3,5}{4,6,7,Z}{2,3,5}{6,7,Z}{7,Z}Φ{4,6,7,Z}{7,Z}{6,7,Z}{7,Z}{7,Z}Φ第72頁，課件共127頁，創作于2023年2月分別：將七種狀態集：{S}，{1,2,3},{4},{2,3,5}, {6,7,Z},{4,6,7,Z},{7,Z}用符號q0~q6命名得DFA七 種狀態矩陣：DFA圖如下：

即為所求的DFA。IxIyq0q1Φq1q2q3q2Φq4q3q5q3q4q6Φq5q6q4q6q6Φ第73頁，課件共127頁，創作于2023年2月例：已知εNFA（如圖），求與之等價的DFA。

解：求DFA的開始狀態（與上例不同）

ε-closure({x})={x,0,1}，作為DFA的開始態。構造確定化矩陣：IaIb{x,0,1}{0,2,1}{0,1}{0,2,1}{0,2,1}{0,1,3}{0,1}{0,2,1}{0,1}{0,1,3}{0,2,1}{0,y,1}{0,y,1}{0,2,1}{0,1}IaIbABCBBDCBCDBEEBC第74頁，課件共127頁，創作于2023年2月畫DFA的圖形表示第75頁，課件共127頁，創作于2023年2月五、DFA的化簡（DFA的最小化）

1.化簡DFA的目的尋找一個狀態數比M少的DFAM’，使得L(M)=L(M’)DFA的狀態少，則依據它編寫的詞法分析程序就簡單。

2.化簡化簡問題：

①使化簡后的DFA中，沒有多余的狀態。②使化簡后的DFA中，沒有兩個是相互等價的狀態。－－采用分割法。第76頁，課件共127頁，創作于2023年2月所謂多余狀態：從自動機的開始狀態出發，輸入任何的字符串也不能到達的那個狀態。從自動機的開始狀態到某個結點有弧，但該結點無弧通向終止狀態。不可到達的狀態對于生成自動機的語言毫無意義。因此，應該從自動機中刪去。第77頁，課件共127頁，創作于2023年2月兩個狀態s和t等價的條件是：一致性條件：狀態s和t必須同時為可接受狀態（終止狀態）或不可接受狀態（非終止狀態）。漫延條件：對于所有輸入符號，狀態s和t必須轉換到等價的狀態集里。

如果兩個狀態不等價，則稱這兩個狀態是可區別的。自動機中的非終止狀態與終止狀態是可區別的（∵不滿足一致性條件）第78頁，課件共127頁，創作于2023年2月非終止狀態0，2，1，3與終止狀態4可區別。不滿足一致性條件。狀態2與狀態3可區別（∵狀態2讀入b后到達2;狀態3讀入b后到達4，而2和4不等價：即2，3不滿足漫延條件）。注：分割法就是使狀態滿足漫延條件和一致性條件。關鍵：滿足漫延條件的分割方法。第79頁，課件共127頁，創作于2023年2月3.用分割法化簡DFA

基本思想：將DFA的狀態集分成若干個互不相交的子集，使每個子集中的狀態都是等價的，而不同狀態子集中的狀態則是不等價的。即是可區分的。1o

首先，將DFA的狀態分成兩個子集：終止狀態子集和非終止狀態子集。（因為終止狀態與非終止狀態是可區別的）。（使狀態滿足一致性條件）2o

然后對每個子集進行再分解。分解后的兩個狀態屬于同一個子集，當且僅當對于任何一個輸入字符，它們的映射屬于同一個子集，此過程一直執行到不能再分解為止。（使狀態滿足漫延條件）3o

將分解的每個子集作為化簡后的DFA的每一個狀態。且含有原來開始狀態的子集和含有原來終止狀態的子集分別作為開始狀態和終止狀態。第80頁，課件共127頁，創作于2023年2月

具體DFA的化簡過程。例：已知有DFA圖如下，化簡DFA：

解：1o將所有終止狀態歸為一個子集S1={q1,q3,q4,q5};其余非終止狀態歸為另一個子集：S2={q0,q2}第81頁，課件共127頁，創作于2023年2月2o按可區別性分解子集S1和S2

分解S1：∵f(q1,x)=q2∈S2 f(q3,x)=q4∈S1 f(q4,x)=q5∈S1 f(q5,x)=q5∈S1 (也可對y字符進行)∴將S1分解成兩個子集S1’={q1},S2’={q3,q4,q5}

分解S2： ∵f(q0,x)=q1∈S1’ f(q2,x)=q3∈S2’ ∴將S2分解成兩個子集{q0},{q2}最后分解成4個子集：{q1},{q3,q4,q5},{q0},{q2}分別用q1,q3,q0,q2來替換成4個子集的狀態名。DFA的化簡：第82頁，課件共127頁，創作于2023年2月用狀態矩陣形式輔助完成化簡xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5分解：S1={q0,q2},S2={q1,q3,q4,q5}對x，S2分解：S21={q1},S22={q3,q4,q5}對x，s1分解：S12={q0},s12={q2},S22對x或y不能分解。最后得到分解：{q0},{q1},{q2},{q3,q4,q5}第83頁，課件共127頁，創作于2023年2月例：將DFA（如下圖）最小化。解：1o

將終止態與非終止態的結點分為2個子集：

=({A,B,C,D},{E})(其中S0={A,B,C,D},S1={E})第84頁，課件共127頁，創作于2023年2月20分解子集：S0＝{A,B,C,D}對a：對b：f(A,a)=B∈S0寫成{A,B,C,D}a={B}∵B包含在{A,B,C,D}中,∴{A,B,C,D}對a不被分裂f(B,a)=B∈S0f(C,a)=B∈S0f(D,a)=B∈S0f(A,b)=C∈S0寫成{A,B,C,D}b={C,D,E}∵{C,D,E}既不包含在{A,B,C,D}中，又不包含在{E}中，∴{A,B,C,D}對b要被分裂。f(B,b)=D∈S0f(C,b)=C∈S0f(D,b)=E∈S1第85頁，課件共127頁，創作于2023年2月∴=({A,B,C},{D},{E})(若令S2={A,B,C}，S3={D},S4={E})再分解：{A,B,C}對a：對b：f(A,a)=B∈S2寫成{A,B,C}a={B}∵B包含在{A,B,C}中,∴{A,B,C}對a不被分裂f(B,a)=B∈S2f(C,a)=B∈S2f(A,b)=C∈S2寫成{A,B,C}b={C,D}∵{C,D}既不包含在{A,B,C}中，又不包含在{D}中，∴{A,B,C}對b要被分裂。f(B,b)=D∈S3f(C,b)=C∈S2第86頁，課件共127頁，創作于2023年2月∴＝（{A,C},{B},{D},{E}）再分解：{A,C}∵{A,C}a={B}(∵{B}包含在{B}中,∴對a,{A,C}不被分裂) {A,C}b={C}(∵{C}包含在{A,C}中，∴對b,{A,C}不被分裂)

結論：A,C狀態等價。整個分解終止。∴ =（{A,C},{B},{D},{E}）DFA最小化為：IaIbABCBBDCBCDBEEBC注：可通過DFA確定化矩陣，應用狀態滿足漫延條件和一致性條件，直接得出等價的狀態。如：上面的確定化矩陣，{B}b={D},{D}b={E},而E,D不等價，導致B,D不等價，所以，D和B要分裂。第87頁，課件共127頁，創作于2023年2月例：已知正規式R=l(l|d)*,求最小DFA解：步驟：1o求DFA第88頁，課件共127頁，創作于2023年2月2o求DFA子集法：構造確定化的矩陣IlId{x}{1,2,y}Φ{1,2,y}{2,y}{2,y}{2,y}{2,y}{2,y}IlIdABΦBCCCCC第89頁，課件共127頁，創作于2023年2月3o最小化DFA分割法：首先將DFA分解成兩個子集：=({A},{B,C}){B,C}不能分解：對l： 對d：∴B,C等價：去掉C

最小化DFA：

注：實現時，擴充為：

且規定：字符串的長度為n,f(B,l)=C寫成{B,C}l={C}f(C,l)=Cf(B,d)=C寫成{B,C}d={C}f(C,d)=C第90頁，課件共127頁，創作于2023年2月六、由最小化的DFA到詞法分析程序的構造若指明DFA的每一個狀態要完成的任務再把從狀態0出發的弧上所標記的輸入字符視為控制條件則：DFA實際上就是一個程序流程圖。例：上例最小化DFA：

要識別一個標識符是否結束，必須讀到該標識符后繼字符是分界符（或非l,d）因此，實現時，將標識符DFA作適當修改：第91頁，課件共127頁，創作于2023年2月如果賦予狀態A,B,Z一定的操作，則DFA變為識別標識符程序的框圖。第92頁，課件共127頁，創作于2023年2月§4.正規文法與有窮自動機之間的轉換一、正規文法到有窮自動機的轉換分別就左,右線性文法到有窮自動機的轉換1.右線性文法到有窮自動機的轉換 設給定右線性文法G=(VN,VT,P,S),則相應的有窮自動機M=(Q,∑,f,q0,Z).

轉換方法：(1)將VN中每一個非終結符視作M1中的一個狀態，并增加一個終結狀態D,DVN,令Q=VN∪{D},Z={D},∑=VT,q0=S,f函數構造如下：(2)對G中每一形如:A∷=aB的產生式(A,B∈VN,a∈VT∪{ε}),令f(A,a)=B;(3)對G中每一形如:A∷=a的產生式(A∈VN,a∈VT),第93頁，課件共127頁，創作于2023年2月令f(A,a)=D;(注意：D是終結狀態)(4)對G中每一形如:A∷=ε的產生式(A∈VN),令f(A,ε)=D;

顯然，這樣構造的M是具有一個開始狀態的NFA。例：構造下列右線性文法G[Z]的有窮自動機。

Z∷=0AA∷=0A|0BB∷=1A|1則構造等價自動機M=({Z,A,B,D},{0,1},f,{Z},{D}),其中：

f(Z,0)={A},f(A,0)={A,B},f(B,1)={D},f(B,1)={A}右線性文法構造狀態圖

A

B

Z

D

0

1

0

1

0第94頁，課件共127頁，創作于2023年2月狀態矩陣表示：2.左線性正規文法到有窮自動機的轉換設給定義左線性正規文法G=(VN,VT,P,S),則相應的有窮自動機M=(Q,∑,f,q0,Z).(1)新增加一個初始狀態q0,且q0VN;將VT中每個非終止狀態視作M中的狀態，令Q=VN∪{q0},并將G的開始符號S看成終結狀態，即Z={S},∑=VT;(2)對G中每一形如:A∷=Ba的產生式(A,B∈VN,a∈VT∪{ε}),令f(B,a)=A;

01Z{A}ΦA{A,B}ΦBΦ{A,D}DΦ

Φ第95頁，課件共127頁，創作于2023年2月(3)對G中每一形如:A∷=a的產生式(A∈VN,a∈VT∪{ε}),令f(q0,a)=A;例，構造G[A]的自動機A∷=A1|B1B∷=B0|0根據轉換方法，與G對應的自動機M=({S,A,B},{0,1},f,S,{A}),其中：

f(A,1)=A,

f(B,1)=A,

f(B,0)=B,

f(S,0)=B其狀態圖：它為確定的，且識別的語言為：L(M)=L(G[A])=00*11*第96頁，課件共127頁，創作于2023年2月二、有窮自動機到正則文法的轉換給定有窮自動機M=(Q,∑,f,q0,Z),按下列方法構造對應右線性文法G=(VN,VT,P,S):(1)令VN=Q，VT=∑，S=q0;(2)若f(A,a)=B,且B不是終結狀態,則將A∷=aB加到p中；(3)若f(A,a)=B,且B是終結狀態,則將A∷=aB|a或A∷=aB,B∷=ε加到p中；(4)若G的開始符號S是一個終結狀態，則將S∷=ε

加到p中。例：設DFAM=({A,B,C,D},{0,1},f,A,{B}),其中：

f(A,0)=B,f(B,1)=C,f(C,0)=B,

第97頁，課件共127頁，創作于2023年2月

（1）根據函數式構造右線性正規文法G[A]：

A→0B|0,B→1C,C→0C|0

或A∷=0B,B∷=1C|ε,C∷=0B（2）將函數式換成狀態圖，然后轉換成右線性正規文法。由函數式得到等價的DFAM:根據狀態轉換圖，所求右線性文法G=({A,B,C},{0,1},P,A),P為：

A∷=0B|0,B∷=1C,C∷=0B|0

或A∷=0B,B∷=1C|ε,C∷=0B注：以開始狀態作為開始符號，然后依弧的方向寫出產生式右邊的式子。若到達的是終結狀態弧，則，該弧上的符號要作為產生式右邊的式子。該自動機所識別的語言為0(01)*.第98頁，課件共127頁，創作于2023年2月注：1.自動機3種形式：函數式、狀態圖和狀態矩陣都可以轉換成正規文法。例：已知自動機3種形式如下，轉換成右線性正規文法01SBΦBBAAΦAf（S,0）=B，f（B,0）=B,f（B,1）=A,f（A,1）=A.轉換成右線性正規文法G[S]=({S,A,B}，{0,1}，P，S)P:S→0B，B→0B|1A|1，A→1A|1.2.通過狀態圖將左右線性正規文法可以互換上例狀態圖轉化成左線性正規文法G[A],P:A→A1|B1，B→B0|0(終結狀態作為開始符號，原來開始狀態作為終結狀態，然后以弧逆方向寫出產生式右邊的式子。）第99頁，課件共127頁，創作于2023年2月§5.詞法分析程序的編寫方法及實驗要求一、詞法分析程序編寫方法兩種方法：手工編寫方法：根據識別語言單詞的狀態圖，使用某種高級語言，例如c語言直接編寫詞法分析程序。利用詞法分析程序的自動生成工具LEX自動生成此法分析程序。下面僅介紹手工編寫詞法分析程序的構造過程。二、詞法分析程序構造過程：1.分析列出待分析語言的所有單詞符號，編寫對應的種別碼。例：c語言子集的單詞符號及種別碼：(1)有窮的單詞符號：第100頁，課件共127頁，創作于2023年2月關鍵字：main,void,if,then,while,for,printf,scanf,int,…運算符：+,-,*,/,>,>=,<,<=,==,!=,(,),…分界符：{,},;,:,，,[,],…編寫對應的種別碼：單詞符號種別碼單詞符號種別碼單詞符號種別碼單詞符號種別碼main1=21,30‘‘39int2+22;31‘\0100char3-23:32ERROR-1if4*24>33else5/25<34for6(26>=35while7)27<=36ID10{28==37NUM11}29!=38第101頁，課件共127頁，創作于2023年2月(2)無窮的單詞符號應寫出對應的文法。如：標識符(ID)和常數(NUM) ID：letter(letter|digit)*(ID種別碼見上表) letter∷=a|b|…|z|A|B|…|Z digit∷=0|1|…|9常數：整常數：NUM:digit(digit)*(NUM種別碼見上表)2.畫單詞的狀態轉換圖(下頁)第102頁，課件共127頁，創作于2023年2月Z1035678941011letter非letter非digitletter|digitdigit非digitdigit+-*/>其它=100n其它出錯處理……第103頁，課件共127頁，創作于2023年2月3.根據狀態圖和單詞符號的種別碼表，構造詞法分析程序簡單的方法：讓每個狀態對應一小段程序。在此引進詞法分析程序所用的全局變量和需要調用的函數；(1)ch字符變量，存放當前讀入的源程序字符。(2)token字符數組，存放構成單詞符號的字符串.(3)getch()讀字符函數，每調用一次從輸入緩沖區中讀入源程序的下一個字符放在ch中，并把讀字符指針指向下一個字符串。(4)getbc()函數，每次調用時，檢查ch中的字符第104頁，課件共127頁，創作于2023年2月是否為空白字符。是，則反復調用getch()，直至ch讀入一個非空白字符為止。(5)concat()函數,每次調用把當前ch中的字符與token中的字符串連接。例如：token字符數組中原有值為”ab”,ch存放著”c”，經調用concat后，token中的值為:”abc”.(6)lett(ch)和digi()布爾函數，分別用來判斷ch中的字符是否為字母和數字，從而給出true或false值。(7)reserve()整型函數，對token中的字符串查種別碼表，若是一個關鍵字，則返回他的種別碼,第105頁，課件共127頁，創作于2023年2月否則返回標識符的種別碼10。(8)retract()函數，讀字符指針回退一個字符。(9)return()函數，收集并攜帶必要信息返回調用程序。即返回語法分析程序。(10)dtb()十進制轉換函數，它將token中的數字出轉換成二進制數值表示，并以此作為涵數值返回。根據狀態轉換圖，用c語言編寫的詞法分析程序如下：scaner(){ token=NULL;第106頁，課件共127頁，創作于2023年2月 getch(); getbc(); if(lett(ch)) { while(lett(ch)||digi(ch))//識別關鍵字和標識符

{ cancat();