1、第四章 詞法分析詞法分析程序的設計單詞的掃描工具 有窮自動機 正規(guī)式和有窮自動機的等價性 正規(guī)文法和有窮自動機間的轉換4.1 詞法分析程序的設計 實現(xiàn)詞法分析（lexical analysis）的程序 逐個讀入源程序字符并按照構詞規(guī)則切分成一系列單詞。 單詞是語言中具有獨立意義的最小單位:包括保留字、標識符、運算符、標點符號和常量等 回顧回顧 什麼是詞法分析程序 詞法分析程序的輸出 單詞符號分為5種：1 標識符2 常數(shù)3 基本字（關鍵字）4 運算符5 界符例：if i=5 then x:=y；保留字if (3,if)標識符i （1，指向i符號表的入口）等號 （4，）常數(shù)5 （2，5）保留字th

2、en （3，then）標識符x （1，指向x符號表的入口）賦值號:= （4，:=）標識符y （1，指向y的符號表的入口）分號； （5，；） 詞法分析程序作為一個獨立階段詞法分析必須作為獨立的一遍嗎？當然可以把詞法分析安排成獨立的一遍，讓它把整個源程序翻譯成一連串的單詞符號（二元式）的形式存放于中間文件中 。將詞法分析程序安排成一個子程序，每當語法分析器需要一個單詞符號時就調用這個子程序。 源程序詞法分析程序語法分析程序Tokenget token4.2 單詞的描述工具 正規(guī)文法（正規(guī)文法（regular grammar）： G=(VN,VT,S,P),其中p中的每一個規(guī)則都滿足： A aB或A

3、 a，其中 TVaVBAN,程序設計語言中的單詞可以用下述規(guī)則描述： l|l l|d|l|d +|-|*|/|=. 正則表達式,正規(guī)表達式. 是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學工具。正規(guī)式和它所表示的正規(guī)集的遞歸定義 設字母表為，輔助字母表=，和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ；任何a，a是上的一個正規(guī)式，它所表示的正規(guī) 集為a；假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)

4、L(e2)和(L(e1)。1.僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。例:令=a，b， 上的正規(guī)式和相應的正規(guī)集的例子有：正規(guī)式 正規(guī)集a aab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,a, 任意個a的串正規(guī)式 正規(guī)集(ab) ,a,b,aa,ab 所有由a和b組成的串(ab)(aabb)(ab) 上所有含有兩個相繼的a或兩個相 的b組成的串 例 令=l，d，則上的正規(guī)式 r=l(l d) 其中l(wèi)代表字母,d代表數(shù)字,例 =d，e，+，,則上的正規(guī)式 d(dd )(e(+)dd )表示的是無符號數(shù)的集合。其中d

5、為09的數(shù)字。 程序設計語言的單詞都能用正規(guī)式程序設計語言的單詞都能用正規(guī)式 來定義來定義. .正規(guī)式的等價 若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。例如： e1= (ab)， e2 = ba e1= b(ab) , e2 =(ba)b 正規(guī)式服從的代數(shù)規(guī)律 設設r,s,t是正規(guī)式是正規(guī)式 r s=s r “或或”服從交換律服從交換律 r (s t)=(r s) t “或或”的可結合律的可結合律 (rs)t=r(st) “連接連接”的可結合律的可結合律r(s t)=rs rt (s t)r=sr tr 分配律分配律 r=r, r =r 是是“連接連接”的恒

6、等元素的恒等元素 零一零一律律r r=r r = r rr “或或”的抽取律的抽取律正規(guī)式到正規(guī)文法 對上的正規(guī)式r ,存在一個RG=(VN,VT,P,S)： L(G)=L(r)。 初始： VT= , S VN ，生成正規(guī)產生式 Sr (R.1) 對形如 Ar1r2的正規(guī)產生式： Ar1B Br2 BVN (R.2)對形如Arr1的正規(guī)產生式： ArB Ar1 BrBBr1 BVN(R.3)對形如Ar1r2的正規(guī)產生式: Ar1 A r2 不斷應用R做變換，直到每個產生式右端至多有一個VN例 r=a(ad) Sa(ad) SaA A(ad) A(ad)B A B(ad)B B Gs: SaA

7、A VT=a,d AaBVN=S,A,B AdB BaB BdB B正規(guī)文法到正規(guī)式:對G=(VN,VT,P,S),存在一個 =VT上的正規(guī)式r : L(r)=L(G)轉換規(guī)則文法產生式文法產生式正規(guī)式正規(guī)式規(guī)則規(guī)則1規(guī)則規(guī)則2規(guī)則規(guī)則3xBAyB yxAA|xAyAA=xyA=x*yA=x|yGs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a=a(ad)(ad)=a(ad)+) R=a(ad)例如：例如：常常遇到的術語 Token 單詞,詞標，符號 lexeme詞素，詞位 pattern模式，式樣 幫助理解術語 In general，ther

8、e is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token. The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by

9、 the pattern for a token. e.g. Const pi=3.14159；中的pi是token “identifier”的lexeme，其pattern為letter followed by letters and/or digit.詞法分析器的設計1、輸入和預處理2、單詞符號的識別保留字：一般可以視全體為一種，也可以一字一種。常數(shù)：按照類型來分（整，實，布爾型等等）算符：一符一種界符：一符一種標識符：統(tǒng)歸為一種狀態(tài)轉換圖轉換圖：有向圖。它是設計詞法分析程序的一種好途徑。 結點代表狀態(tài)，用圓圈表示，狀態(tài)之間用箭弧連接。箭弧上的標記表示在射出結點狀態(tài)下可能出現(xiàn)的輸入字符和字

10、符類。 大多數(shù)程序語言的單詞符號都可以用轉換圖來實現(xiàn)。 手工設計詞法分析器：構造一個識別某個簡單語言的所有單詞符號的轉換圖，用程序實現(xiàn)狀態(tài)轉換。把關鍵字作為一類特殊的標識符來處理，因此關鍵字不專設對應的轉換圖。因此應該將種別編碼放在一個保留字表中。當轉換圖識別出一個標識符時，就去查對這張表，確定是否為關鍵字狀態(tài)轉換圖的實現(xiàn)轉換圖實現(xiàn)：每個狀態(tài)對應一小段程序。 為了更好地使用狀態(tài)轉換圖構造詞法分析程序，為了討論詞法分析程序地自動生成，需要將上述轉換圖的概念稍加形式化。4.3 4.3 有窮自動機有窮自動機 有窮自動機(也稱有限自動機)作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語

11、言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。 有窮自動機分為兩類： 確定的有窮自動機(Deterministic Finite Automata) 不確定的有窮自動機(Nondeterministic Finite Automata) 。關于有窮自動機有窮自動機我們將討論如下題目確定的有窮自動機DFA不確定的有窮自動機NFANFA的確定化DFA的最小化確定的有窮自動機DFADFA定義：一個確定的有窮自動機（DFA）M是一個五元組：M=（K，f，S，Z）其中1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.是一個有窮字母表，它的每個元素稱為一

12、個輸入符號，所以也稱為輸入符號表；DFA定義3.f是轉換函數(shù)，是在KK上的映射。 即，如f（ki，a）=kj，（kiK，kjK）就意味著，當前狀態(tài)為ki，輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4.SK是唯一的一個初態(tài)；5.Z K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。一個DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉換圖)。 假定DFA M含有m個狀態(tài)，

13、n個輸入字符，那么這個狀態(tài)圖含有m個結點，每個結點最多有n個弧射出，整個圖含有唯一一個初態(tài)結點和若干個終態(tài)結點，初態(tài)結點冠以雙箭頭“=”或標以“-”，終態(tài)結點用雙圈表示或標以“+”，若 f(ki,a)=kj，則從狀態(tài)結點ki到狀態(tài)結點kj畫標記為a的弧； DFA 的狀態(tài)圖表示bSUVQaaaba，b一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=”標明初態(tài)；否則第一行即是初態(tài)，相應終態(tài)行在表的右端標以1，非終態(tài)標以0。DFA 的矩陣表示的矩陣表示abSUVUQVVUQQQQ字符字符狀態(tài)狀

14、態(tài)0001 為了說明DFA如何作為一種識別機制,我們還要理解下面的定義 * *上的符號串上的符號串t t在在DFADFA M M上運行上運行一個輸入符號串t，將它表示成Tt1的形式，其中T，t1 *。 在DFA M=（K，f，S，Z）上運行運行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK 擴充轉換函數(shù)f為 K*K上的映射，且： f（ki，）= ki* *上的符號串上的符號串t t被被DFADFA M M接受接受M=（K，f，S，Z）若t *，f(S，t)=P，其中S為 M的開始狀態(tài)，P Z，Z為終態(tài)集。則稱t為DFA M所接受接受（識別識別）.例例：證明證明t=baab被下

15、圖的被下圖的DFA所接受所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U，a），），b） =f（Q，b）=QQ屬于終態(tài)。屬于終態(tài)。得證。得證。bSUVQabba, baaDFA M所能接受的符號串的全體記為L(M). 對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M與M是等價的. 結論： 上一個符號串集V是正規(guī)的，當且僅當存在一個上的確定有窮自動機M，使得V=L(M)。 DFA的確定性表現(xiàn)在轉換函數(shù)f:KK是一個單值函數(shù)。 也就是說，對任何狀態(tài)kK，和輸入符號a，f(k,a)唯一地確定了下

16、一個狀態(tài)。從狀態(tài)轉換圖來看，若字母表含有n個輸入字符，那末任何一個狀態(tài)結點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。DFA的行為很容易用程序來模擬.DFA M=（K，f，S，Z）的行為的模擬程序 K:=S； c:=getchar; while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no)reviewRegular expressions on the alphabet are defined by the following recursive rules:1) Ev

17、ery symbol of is a regular expression2) and f is a regular expression3) if r1 and r2 are regular expressions, so are (r1 ) r1 r2 r1 | r2 r1 *4) Nothing else is a regular expression. = 0,1,2,3,4,5,6,7,8,9 (1|2|3|4|5|6|7|8|9|0) * is a regular expression(1|2|3|4|.8|9|0) (1|2|3.|8|9|0) * is a regular ex

18、pression(1|2|3.|8|9|0)+reviewDFA M=（K，f，S，Z）1) A finite set of states, one of which is designated the initial state or start state, and some of which are designated as final states.2) An alphabet of possible input symbols.3) A finite set of transitions that specifies for each state and for each symb

19、ol of the input alphabet, which state to go to next.DFA DFA = digit,not digit不確定的有窮自動機NFA定義 NFA M=K，f，S，Z， 其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種映射，SK是初始狀態(tài)集，Z K為終止狀態(tài)集.例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z狀態(tài)圖表示SPZ00,1111矩陣表示矩陣表示01SPS,Z0PZ0ZPP1簡化為01SPS,Z0P.Z0ZPP

20、1f為K * 到K的子集（2 K）的一種映射具有轉移的不確定的有窮自動機 123abc有如下定理: 對任何一個具有轉移的不確定的有窮自動機NFA N，一定存在一個不具有轉移的不確定的有窮自動機NFA ，使得L(M)=L(N)。與上例等價的一個NFA.2acbb31acacbb類似DFA, 對NFA M=K，f，S，Z也有如下定義*上的符號串t在NFA M上運行.一個輸入符號串t，（我們將它表示成Tt1的形式，其中T，t1 *）在NFA M上運行運行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符號串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，

21、則稱t為NFA M所接受接受（識別識別） *上的符號串t被NFA M接受也可以這樣理解 對于中的任何一個串t，若存在一條從某一初態(tài)結到某一終態(tài)結的道路，且這條道路上所有弧的標記字依序連接成的串(不理那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。 若M的某些結既是初態(tài)結又是終態(tài)結，或者存在一條從某個初態(tài)結到某個終態(tài)結的道路,其上所有弧的標記均為，那么空字可為M所接受。00011110100011100000010001100NFA M所能接受的符號串的全體記為 L(M)結論： 上一個符號串集V是正規(guī)的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。(0|1)*(

22、000|111)(0|1) DFA是NFA的特例. 對每個NFA N 一定存在一個DFA ，使得 L(M)=L(N)。對每個NFA N存在著與之等價的DFA M。 有一種算法，將NFA轉換成接受同樣語言的DFA.這種算法稱為子集法子集法. 從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)，NFA到相應的DFA的構造的基本思路是： DFADFA的每一個狀態(tài)對的每一個狀態(tài)對應應NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達到的所有狀態(tài).1. 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為-closure(I)，定義為一狀態(tài)集，

23、是狀態(tài)集I中的任何狀態(tài)S經任意條弧而能到達的狀態(tài)的集合。 狀態(tài)集合I的任何狀態(tài)S都屬于-closure(I)。2. 狀態(tài)集合狀態(tài)集合I I的的a a弧轉換弧轉換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經過一條a弧而到達的狀態(tài)的全體。狀態(tài)集合I的有關運算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa NFA確定化算法: 假設NFA N=(K, ,f,K0,Kt)，按如下辦法構造一個DFA M=(S

24、, ,d,S0,St)，使得L(M)=L(N)：1. M的狀態(tài)集S由K K的一些子集的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；2 M和N的輸入字母表是相同的，即是；3 轉換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)；5 St=Si Sk. Se，其中Si

25、Sk. SeS且Si , Sk,. SeKt構造NFA N的狀態(tài)狀態(tài)K K的子集的子集的算法：假定所構造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(tài)K的子集。1 開始，令-closure(K0)為C中唯一成員，并且它是未被標記的。2 while （C中存在尚未被標記的子集T）do 標記T； for 每個輸入字母a do U:= -closure(move(T,a)； if U不在C中 then 將U作為未標記的子集加在C中 NFA的確定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41

26、,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb 等價的DFAaCDBAEFSbaaaaabbbbbabF確定有窮自動機的化簡 說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。 有窮自動機的多余狀態(tài)，從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；

27、或者從這個狀態(tài)沒有通路到達終態(tài)。 兩個狀態(tài)s和t可區(qū)別：不滿足兼容性同是終態(tài)或同是非終態(tài)傳播性從s出發(fā)讀入某個aa和從t出發(fā) 讀入某個a到達的狀態(tài)等價。 DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別） C和D同是終態(tài),讀入a到達C和F, C和F同是終態(tài), C和F讀入a都到達C,讀入b都到達E. C和D等價aCDBAEFSbaaaaabbbbbabF最小狀態(tài)DFA 對于一個DFA M =（K,f, k0,kt)， 存在一個最小狀態(tài) DFA M =（K,f, k0,kt)， 使L(M)=L(M). 結論 接受L的最小狀態(tài)有窮自動機

28、不計同構是唯一的。“分割法”DFA的最小化算法的核心 把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的. 算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己. DFA的最小化算法 DFA M =（K,f, k0, kt),最小狀態(tài)DFA M 1.構造狀態(tài)的一初始劃分：終態(tài)kt 和非終態(tài)Kt兩組(group) 2.對施用過程過程PPPP 構造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復2

29、. 4.為final中的每一組選一代表，這些代表構成M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉換f(k,a)=r.M 的開始狀態(tài)是含有S0的那組的代表 M 的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài).過程過程PPPP : Construction of newFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbol

30、s a, states s and t have transitions on a to states in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in n e w by the set of all subgroups formed end DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B 2:C,D,E,F CDBAEFSbaaaaaabbbbbbaA S,BbBSDBASaaabbbbaa1.對于上的一個NFA M，可以構造一個上的正規(guī)式R,使得

31、L(R)=L(M)。2.對于上的一個正規(guī)式R，可以構造一個上的NFA M，使的L(M)=L(R)。4.5 有窮自動機和正規(guī)表達式的等價性有窮自動機和正規(guī)表達式的等價性 對于上的一個NFA M，可以構造一個上的正規(guī)式R,使得L(R)=L(M) 將狀態(tài)轉換圖的概念拓廣，令每條弧可以用一個正規(guī)式做標記：從上的一個正規(guī)式R構造上的一個NFA M，使得L(M)=L(R) :第一種： “語法制導”的方法，即按正規(guī)式的語法結構指引構造過程，構造規(guī)則具體描述如下： .“對于上的一個正規(guī)式R,可以構造一個上的NFA M， ，使得L(M)=L(R).” 說明一種構造方法： (1)R=,構造任一具有空終態(tài)集的NFA

32、 M (2） R= ，構造的NFA M=(k0, ,f,k0.k0): f（k0,a)對于 所有a都沒定義。 (3）R=a,構造的NFA M=(k0,k1,f,k0.k1): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（1）（2）（3）分別應用到R1,R2 ，產生M1= =(K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交.構造的NFA M= (K1K2k,f,k,F) : k是新增加的狀態(tài)符號， f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a). 若k1F1且k2F2則 F=F1 F2，否則F=F1 F2 k(5)R=

33、R1.R2 將步驟（1）（2）（3）分別應用到R1,R2 產生M1=(K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交.構造的NFA M= (K1K2,f,k1,F2) : f包含f1和f2,且f(k,a)=f1(k,a),當 kF1時; f(k,a)=f2(k,a),當 k K2時;f(k1, )=k2,(6)R=R1*將步驟（1）（2）（3）分別應用到R1,產生M1=(K1,f1,k1,F1), 構造的NFA M= (K1 k0,F F0 ,f,k0,F0)其中 k0,F F0 是新增加的兩個狀態(tài),f(k,a)=f1(k,a),當 kF1時; f(k0,

34、)=f(F1 , )= k1,F F0 ,第二種 狀態(tài)圖方法對于正規(guī)式x,x 構造的NFAX對于正規(guī)式 ,構造的NFA（三種） FSF對于正規(guī)式R= ,構造的NFA FS對于正規(guī)式r, r= R1|R2構造的NFA對于正規(guī)式r, r=R1 R2構造的NFA對于正規(guī)式r, r=R1*構造的NFA第三種 使用替換規(guī)則R=(a|ab)* b b* 4.6 正規(guī)文法和有窮自動機間的轉換正規(guī)文法和有窮自動機間的轉換定理定理 設設G=（VN，VT，P，S）是3 3型文法，則存在一個有窮自型文法，則存在一個有窮自 動機動機 M=(K, , f, A, Z)M=(K, , f, A, Z)，使得使得L(M)=

35、L(G)L(M)=L(G)有窮自動機有窮自動機NFA M NFA M 這樣構造：這樣構造： = = VT K= K= VN N, NN, N為一個新狀態(tài)為一個新狀態(tài), ,它不在它不在VN中 A=S A=S Z=N Z=N 對對G G中的形如中的形如 DtBDtB的產生式的產生式, ,t t為終結符或為終結符或,有有f(D,t)=Bf(D,t)=B； 對對G G中形如中形如DtDt的產生式，的產生式， t t為終結符或為終結符或,有有f(D,t)=N;f(D,t)=N;G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZababDtBDtB的產

36、生式的產生式, ,t t為終結符或為終結符或,有有f(D,t)=Bf(D,t)=B；DtDt的產生式，的產生式， t t為終結符或為終結符或,有有f(D,t)=N;f(D,t)=N;FA轉換為RG定理定理 已知一有窮自動機M= (K, , f, A, Z),存在有一個3型文法G = （VN，VT，P，S）,使得L(G)=L(M)G 的定義： VT = VN= K S = A 若 f(D,t)=B ，則DtB在P中 若 f(D,t)=B ，且B在Z中，則Dt在P中G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb 正規(guī)式用于說明(描述)單詞的結構十分簡潔方便。而把一個正規(guī)式編譯(或稱轉換)為一個NFA進而轉換為相應的DFA，這個NFA或DFA正是識別該正規(guī)式所表示的語言的句子的識別器。基于這種方法來構造詞法分析程序詞法分析程序的設計技術可應用于其它領域，比如查詢語言以及信息檢索系統(tǒng)等，這種應用領域的程序設計特點是，通過字符串模式的匹配來引發(fā)動作詞法分析程序的自動構造工具也廣泛應用于許多方面，如用以生成一個程序，可識別印刷電路板中的缺陷，又如開關線路設計和文本編輯的自動生成等。 本章小結 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識別單詞，交由語法分析程序接下去。