編譯原理之詞法分析.ppt
《編譯原理之詞法分析.ppt》由會員分享,可在線閱讀,更多相關(guān)《編譯原理之詞法分析.ppt(96頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、第4章 詞法分析,本章將討論詞法分析程序的設(shè)計原則,單 詞的描述技術(shù),識別機(jī)制及詞法分析程序 的自動構(gòu)造原理。 4.1 詞法分析程序的設(shè)計 4.2 單詞的描述工具(正規(guī)式和正規(guī)文法) 4.3 有窮自動機(jī)(單詞的識別機(jī)制) 4.4 正規(guī)式和有窮自動機(jī)的等價性 4.5 正規(guī)文法和有窮自動機(jī)間的轉(zhuǎn)換 4.6 詞法分析程序的自動構(gòu)造,本章重點,單詞的描述工具 單詞的識別系統(tǒng) 設(shè)計和實現(xiàn)詞法分析程序 首先需要描述和刻畫程序設(shè)計語言中的原子單位單詞,其次需要識別單詞和執(zhí)行某些相關(guān)的動作。 描述程序設(shè)計語言的詞法的機(jī)制是正則表達(dá)式,識別機(jī)制是有窮狀態(tài)自動機(jī)。,回顧 什么是詞法分析程序,實現(xiàn)詞法分析(lexi
2、cal analysis)的程序 逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語言中具有獨立意義的最小單位,包括保留字、標(biāo)識符、運算符、標(biāo)點符號和常量等。 詞法分析是編譯過程中的一個階段,在語法分析前進(jìn)行 。也可以和語法分析結(jié)合在一起作為一遍,由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。,詞法分析程序的功能,詞法分析程序的功能是讀入源程序,輸出 單詞符號。 源程序 單詞符號 “詞法” “分析程序” “的” “功能” 假如你沒有中文分詞的概念,你會明白中文句子的含義嗎?,詞法分析器,,,詞法分析程序的功能,While ij do
3、 if ij then i:i-j else j:=jI while,i,,j, do, if,i,,j,then, i, := , i, - , j, else, j, :=, j, -, i,詞法分析器,,,4.1.1 詞法分析程序與語法分析程序的接口方式,4.1 詞法分析程序的設(shè)計,源程序,詞法分析程序,語法分析程序,,,Token,,get token,4.1.2 詞法分析程序的輸出,程序語言單詞的分類: 1關(guān)鍵字(保留字或基本字):begin,end 2標(biāo)識符:用來表示各種名字 3字面常數(shù):256,3 .14,true,abc 4 運算符:如,、、*、/ 等等 5分界符:如逗號,分
4、號,冒號等,4.1.2 詞法分析程序的輸出,詞法分析程序所輸出的單詞符號常常用以 下二元式表示: (單詞種別,單詞自身的值) 單詞的種別是語法分析需要的信息,而單 詞的值則是編譯其它階段需要的信息。 例如:在PASCAL的語句const i=25; yes=1; 中的單詞25和1的種別是常數(shù),常數(shù)的值是25和1。,4.1.3 將詞法分析工作分離的考慮,簡化設(shè)計 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性,4.2 單詞的描述工具,程序設(shè)計語言中的單詞是基本語法成分。 單詞符號的語法可以用有效的工具加以描 述。 基于描述工具,實現(xiàn)詞法分析程序的自動構(gòu)造。,4.2.1 正規(guī)文法,多數(shù)程序設(shè)計語言的單詞的語
5、法都能用正規(guī)文法或3型文法來描述。 程序設(shè)計語言中的幾類單詞可用下述規(guī)則 來描述: L|L L|d|L ,, d|d| +|-|*|/|=|=| ,|;|(|)|....... 其中L表示az中的任何一英文字母,d表 示09中的任一數(shù)字。,例4.1 無符號數(shù)的正規(guī)文法, d|.|e d|.| e| d e|d| d|s d d| 其中s表示正或負(fù)號+,-。,4.2.2 正規(guī)式,正規(guī)式也稱正則表達(dá)式,正規(guī)表達(dá)式 (regular expression)是說明單詞的模 式(pattern)的一種重要的表示法(記號) ,是定義正規(guī)集的數(shù)學(xué)工具。我們用以描 述單詞符號。下面是正規(guī)式和它
6、所表示的 正規(guī)集的遞歸定義。,正規(guī)式和它所表示的正規(guī)集,定義(正規(guī)式和它所表示的正規(guī)集): 設(shè)字母表為,輔助字母表=,,,,,,。 1.和都是上的正規(guī)式,它們所表示的正規(guī)集分別為和 ; 2. 任何a ,a是上的一個正規(guī)式,它所表示的正規(guī)集為a;,正規(guī)式和它所表示的正規(guī)集,3. 假定e1和e2都是上的正規(guī)式,它們所表示的正規(guī)集分別為L(e1)和L(e2),那么,(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1))。 4. 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式,僅由這些正規(guī)式所表示的
7、集合才是上的正規(guī)集。,正規(guī)式和它所表示的正規(guī)集,其中的“”讀為“或”(也有使用“+”代 替 “” 的);“ ”讀為“連接”;“” 讀為“閉包”(即,任意有限次的自重復(fù)連 接)。在不致混淆時,括號可省去,但規(guī)定算 符的優(yōu)先順序為“”、“ ”、“” 。連 接符“ ”一般可省略不寫?!啊?、“ ” 和“” 都是左結(jié)合的。,例4.2,令=a,b, 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有: 正規(guī)式 正規(guī)集 a a ab a,b ab ab (ab)(ab)aa,ab,ba,bb a ,a,a, 任意個a的串,正規(guī)式 正規(guī)集 (ab) ,a,b,aa,ab 所有由a 和b組成的串 (ab)(aabb)(a
8、b) 上所有含有兩個相繼的a或兩個相繼的b組成的串,例4.3 =d,.,e,+,-, 則上的正規(guī)式 d(.dd)(e(+-)dd) 表示的是無符號數(shù)的集合。其中d為0-9的數(shù)字。,例:令=l,d,則上的正規(guī)式r=l(ld)定義的正規(guī)集為:l,ll,ld,ldd,,其中l(wèi)代表字母,d代表數(shù)字, 正規(guī)式即是字母(字母|數(shù)字) ,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和多數(shù)程序設(shè)計語言允許的的標(biāo)識符的詞法規(guī)則。 含義: 上所有由字母開頭的串。 字母打頭的后跟字母和數(shù)字任意組合的串,若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。
9、 例如: e1= (ab), e2 = ba 又如: e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab),設(shè)r,s,t為正規(guī)式,正規(guī)式服從的代數(shù)規(guī)律有: 1. rs=sr “或”服從交換律 2. r(st)=(rs)t “或”的可結(jié)合律 3. (rs)t=r(st)“連接”的可結(jié)合律 4. r(st)=rsrt (st)r=srtr 分配律,5. r=r, r=r是“連接”的恒等元素零一律 6. rr=r r=rrr“或”的抽取律,4.2.3 正規(guī)文法和正規(guī)式的等價性,一個正規(guī)語言可以由正規(guī)文法定義,也可以由正規(guī)式定義,對任意一個正規(guī)文法,存在一個定義同一
10、個語言的正規(guī)式; 反之,對每個正規(guī)式,存在一個生成同一個語言的正規(guī)文法。,一、將上的一個正規(guī)式轉(zhuǎn)換成正規(guī)文法,將上的一個正規(guī)式r轉(zhuǎn)換成文法G=(VN,VT,S,P)。令其中的VT= ,確定產(chǎn)生式和VN用如下辦法: 對任何正規(guī)式r,選擇一個非終結(jié)符S生成產(chǎn)生式Sr,并將S定為G的識別符號。 若x和y都是正規(guī)式,對形如Axy的產(chǎn)生式,重寫成:A xB, B y兩產(chǎn)生式,其中B是新選擇的非終結(jié)符,即BVN,對已轉(zhuǎn)換的文法中的形如A x*y的產(chǎn)生式,重寫為:A xBA yB xBB y其中B為一新非終結(jié)符。 對形如A x|y的產(chǎn)生式,重寫為:A xA y 不斷利用上述規(guī)則做變換,直到每個產(chǎn)生式最多含有
11、一個終結(jié)符為止。,例4.4 將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法。 S a(a|d)* S aA A (a|d)* A (a|d)B,A ,B (a|d)B,B A aB A dB B aB B dB,二、將正規(guī)文法轉(zhuǎn)換成正規(guī)式,基本上是上述過程的逆過程,最后只剩下 一個開始符號定義的產(chǎn)生式,并且該產(chǎn)生 式的右部不含非終結(jié)符。,例4.5 文法GS,求該文法對應(yīng)的正規(guī)式,S aA S a A aA A dA A a A d,S = aA | a A = (aA|dA)|(a|d) A = (a|d)A|(a|d) A = (a|d)*(a|d) A = (a|d)+ S= a((a|d
12、)+ | ) S = a(a|d)*,4.3 有窮自動機(jī),有窮自動機(jī)(也稱有限自動機(jī))作為一種識別裝置,它能準(zhǔn)確地識別正規(guī)集,即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合,引入有窮自動機(jī)這個理論,正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。 有窮自動機(jī)分為兩類: 確定的有窮自動機(jī)(Deterministic Finite Automata) -- DFA 不確定的有窮自動機(jī)(Nondeterministic Finite Automata) -- NFA,關(guān)于有窮自動機(jī)我們將討論如下題目,確定的有窮自動機(jī)DFA 不確定的有窮自動機(jī)NFA NFA的確定化 DFA的最小化,4.3.1 確定
13、的有窮自動機(jī)DFA,DFA定義: 一個確定的有窮自動機(jī)(DFA)M是一個五元組:M=(K,,f,S,Z)其中 1.K是一個有窮集,它的每個元素稱為一個狀態(tài); (狀態(tài)集) 2.是一個有窮字母表,它的每個元素稱為一個輸入符號,所以也稱為輸入符號表;,DFA定義,3.f是轉(zhuǎn)換函數(shù),是在KK上的映射,即,如f(ki,a)=kj,(kiK,kjK)就意味著,當(dāng)前狀態(tài)為ki,輸入符為a時,將轉(zhuǎn)換為下一個狀態(tài)kj,我們把kj稱作ki的一個后繼狀態(tài); 4.SK是唯一的一個初態(tài); 5.Z K是一個終態(tài)集,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。,一個DFA 的例子:,例4.6 DFA M=(S,U,V,Q,a,b,f,S
14、,Q)其中f定義為: f(S,a)=Uf(V,a)=U f(S,b)=Vf(V,b)=Q f(U,a)=Qf(Q,a)=Q f(U,b)=Vf(Q,b)=Q,一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài) 轉(zhuǎn)換圖)。假定DFA M含有m個狀態(tài),n個輸入字 符,那么這個狀態(tài)圖含有m個結(jié)點,每個結(jié)點最 多有n個弧射出,整個圖含有唯一一個初態(tài)結(jié)點 和若干個終態(tài)結(jié)點,初態(tài)結(jié)點冠以雙箭頭“”或 標(biāo)以“-”,終態(tài)結(jié)點用雙圈表示或標(biāo)以“+”,若 f(ki,a)=kj,則從狀態(tài)結(jié)點ki到狀態(tài)結(jié)點kj畫標(biāo)記為 a的弧;,DFA 的狀態(tài)圖表示,b,f(S,a)=Uf(S,b)=V f(U,a)=Q f(U,b)=V
15、f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q,一個DFA還可以用一個矩陣表示,該矩陣 的行表示狀態(tài),列表示輸入字符,矩陣元 素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀 態(tài),即k行a列為f(k,a)的值。用雙箭頭“” 標(biāo)明初態(tài);否則第一行即是初態(tài),相應(yīng)終 態(tài)行在表的右端標(biāo)以1,非終態(tài)標(biāo)以0。,DFA 的矩陣表示,,0 0 0 1,為了說明DFA如何作為一種識別機(jī)制,我們還要理解下面的定義,*上的符號串t在DFA M上運行 一個輸入符號串t,(將它表示成Tt1的形式, 其中T,t1 *)在DFA M=(K,, f,S,Z)上運行的定義為: f(Q, Tt1)=f(f(Q,T),
16、t1) 其中QK 擴(kuò)充轉(zhuǎn)換函數(shù)f為 K*K上的映射,且: f(ki,)= ki,*上的符號串t被DFA 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被下圖的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)=Q Q屬于終態(tài)。 得證。,b,DFA M所能接受的符號串的全體記為L(M).對于任何兩個有窮自動機(jī)M和M,如果L(M)=L(M
17、 ),則稱M與M是等價的. 結(jié)論: 上一個符號串集V是正規(guī)的,當(dāng)且僅當(dāng)存在一個上的確定有窮自動機(jī)M,使得V=L(M)。,DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個單值函數(shù),也就是說,對任何狀態(tài)kK,和輸入符號a,f(k,a)唯一地確定了下一個狀態(tài)。 從狀態(tài)轉(zhuǎn)換圖來看,若字母表含有n個輸入字符,那末任何一個狀態(tài)結(jié)點最多有n條弧射出,而且每條弧以一個不同的輸入字符標(biāo)記。,4.3.2 不確定的有窮自動機(jī)NFA,定義 NFA M=K,,f,S,Z,其中K為狀態(tài)的有 窮非空集, 為有窮輸入字母表,f為K * 到K的子集(2 K)的一種映射,SK是初始狀 態(tài)集,Z K為終止?fàn)顟B(tài)集.,例子 NFA M=(S
18、,P,Z,0,1,f,S,P,Z) 其中 f(S,0)=P f(Z,0)=P f(P,1)=Z f(Z,1)=P f(S,1)=S,Z,狀態(tài)圖表示,狀態(tài)圖表示,矩陣表示,矩陣表示,類似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, 則稱t為NFA M所接受(識別),*上的符號串t被NFA M接受也可以這樣理解,對
19、于中的任何一個串t,若存在一條從 某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路,且這條道路上 所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo) 記為的弧)等于t,則稱t可為NFA M所識別(讀出 或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié), 或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路, 其上所有弧的標(biāo)記均為,那么空字可為M所接受。,4.3.3 NFADFA的轉(zhuǎn)換,從NFA的矩陣表示中可以看出,表項通常 是一狀態(tài)的集合,而在DFA的矩陣表示中,表項是一個狀態(tài),NFA到相應(yīng)的DFA的構(gòu)造 的基本思路是: DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達(dá)到的所有狀態(tài).,D
20、FA是NFA的特例.對每個NFA N一定存在一個DFA ,使得L(M)=L(N)。對每個NFA N存在著與之等價的DFA M 有一種算法,將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法. 與某一NFA等價的DFA不唯一.,定義對狀態(tài)集合I的幾個有關(guān)運算:,1. 狀態(tài)集合I的-閉包 表示為-closure(I),定義為一狀態(tài)集,是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于-closure(I)。 2. 狀態(tài)集合I的a弧轉(zhuǎn)換 表示為move(I,a)定義為狀態(tài)集合J,其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。,狀態(tài)集合I的有關(guān)
21、運算的例子,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;,NFA DFA(確定化)算法:,假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造 一個DFA M=(S, ,d,S0,St),使得 L(M)=L(N): 1. M的狀態(tài)集S由K的一些子集組成。用S1 S2... Sj表示S的元素,其中S1, S2,,... Sj是K的狀態(tài)。并且約定,狀態(tài)S1, S2,,... Sj是按某種規(guī)則排列的,即對于子集S1, S2= S2, S1,來說,S的狀態(tài)
22、就是S1 S2,2 M和N的輸入字母表是相同的,即是; 3 轉(zhuǎn)換函數(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 Sk... SeS且Si , Sk,,... SeKt,構(gòu)造NFA N的狀態(tài)K的子集的算法:,假定所構(gòu)造的子集族為C,即C= (T1, T2,,... TI), 其中T1, T2,,... TI為狀態(tài)K的子集。 1 開始,令-clos
23、ure(K0)為C中唯一成員,并且它是未被標(biāo)記的。,2 while (C中存在尚未被標(biāo)記的子集T)do 標(biāo)記T; for 每個輸入字母a do U:= -closure(move(T,a)); if U不在C中 then 將U作為未標(biāo)記的子集加在C中,例4.8 對圖4.4的NFA N確定化。,,NFA確定化為DFA的過程如下所示,Ia= -closure(move(I,a)) Ib= -closure(move(I,b)),DFA M 如圖4.6所示,,,4.3.4 確定有窮自動機(jī)的化簡,1 什么是多余狀態(tài)? 所謂有窮自動機(jī)的多余狀態(tài),是指這樣的狀態(tài):從自動機(jī)的開始狀態(tài)出發(fā),任何輸入
24、串也不能到達(dá)的那個狀態(tài);或者從這個狀態(tài)沒有通路到達(dá)終態(tài)。,4.3.4 確定有窮自動機(jī)的化簡,2 什么是等價狀態(tài)? 兩個狀態(tài)s和t等價:滿足 兼容性(一致性條件)同是終態(tài)或同是非終態(tài) 傳播性(蔓延性條件)對于所有輸入符號,狀態(tài)s和t必須轉(zhuǎn)換到等價的狀態(tài)里。,一個有窮自動機(jī)可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機(jī)。 說一個有窮自動機(jī)是化簡了的,即它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。,DFA的最小化就是尋求最小狀態(tài)DFA,最小狀態(tài)DFA的含義: 沒有多余狀態(tài)(死狀態(tài)) 沒有兩個狀態(tài)是互相等價(不可區(qū)別),C和D同是終態(tài),讀入a到達(dá)C和F, C和F同是終態(tài)
25、, C和F讀入a都到達(dá)C,讀入b都到達(dá)E. C和D等價,,最小狀態(tài)DFA,對于一個DFA M =(K,,f, k0,,kt),存在一個最小狀態(tài)DFA M =(K,,f, k0,,kt),,使L(M)=L(M).,“分割法”,DFA的最小化算法的核心 把一個DFA的狀態(tài)分成一些不相交的子集,使得任何不同的兩子集的狀態(tài)都是可區(qū)別的,而同一子集中的任何兩個狀態(tài)都是等價的. 算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài),將不完全的輸入弧都射向該狀態(tài),對所有輸入,該狀態(tài)射出的弧還回到自己.,例4.9 將圖4.8中的DFA M最小化,Step 1: P0=(1,2,3
26、,4, 5,6,7),Step 2: P1=(1,2, 3,4, 5,6,7),Step 3: P2=(1,2, 3, 4, 5,6,7),Step 4: P3=(1,2, 3, 4, 5, 6,7),Step 5: 令1代表1,2消去2,令6代表6,7消去7. 得到圖4.8(b) DFA M,4.4 正規(guī)式和有窮自動機(jī)DFA的等價性,1有窮自動機(jī)和正規(guī)表達(dá)式的等價性 對于上的一個NFA M,可以構(gòu)造 一個上的正規(guī)式R,使得L(R)=L(M)。 對于上的一個正規(guī)式R,可以構(gòu)造一個上的NFA M,使的L(M)=L(R)。,2有窮自動機(jī) NFA正規(guī)式,為M添加兩個結(jié)點的X,Y,X用連接到M的所有
27、初態(tài),Y用連接到M的所有終態(tài)。 利用下面三條規(guī)則: 反復(fù)三條規(guī)則,最后X,Y間的標(biāo)記就是所求的正規(guī)式R。,3.正規(guī)式有窮自動機(jī) NFA,(1).“語法制導(dǎo)”方法,即按正規(guī)式的語法結(jié)構(gòu)構(gòu)造。r為正規(guī)式,規(guī)則如下: r=,構(gòu)造任一具有空終態(tài)集的NFA M,,(b) r= ,,(c) r=a,(2).對于正規(guī)式r, r= r1|r2構(gòu)造的NFA,,(3).對于正規(guī)式r, r=r1r2構(gòu)造的NFA,4. 對于正規(guī)式r, r=r1*構(gòu)造的NFA,例4.10 以例4.7的NFA M為例,M的狀態(tài)圖如 圖4.3所示,求正規(guī)式r,使L(r)=L(M).,Step 1. 加入x, y結(jié)點,分別用弧連接到初態(tài)和
28、終態(tài). 如圖4.9(a)所示M,Step 2. 逐步消去M中的結(jié)點, 消去1,3之后如圖4.9(b).,Step 3. 逐步消去M中的結(jié)點, 消去2,4之后如圖4.9(c).,Step 4. 逐步消去M中的結(jié)點, 消去0之后如圖4.9(d).,Step 5. r=(a|b)*(aa|bb)(a|b)* 即為所求.,例4.11 為r=(a|b)*abb構(gòu)造NFA N,使得L(N)=L(r).,4.5 正規(guī)文法和有窮自動機(jī)的等價性,(一) 正規(guī)文法NFA M,L(M)=L(G). M的字母表與G的終結(jié)符集相同, =VT 為G中的每個非終結(jié)符生成一個同名狀態(tài),G的開始符號S是開始狀態(tài). 增加一個新狀
29、態(tài)Z作為NFA的終態(tài). 對G中的形如A tB的規(guī)則(其中t為終結(jié)符或, A,B為非終結(jié)符的產(chǎn)生式),構(gòu)造M的一個轉(zhuǎn)換函數(shù)f(A,t)=B. 對G中形如A t的產(chǎn)生式,構(gòu)造M的一個轉(zhuǎn)換函數(shù)f(A,t)=Z.,例4.12 與文法GS等價的NFA M如圖4.11.,GS: S aA S bB S A aB A bA B aS B bA B ,G=(A,B,C,D,a,b,P,A),其中P為:A aBA bDB bCC aAC bDC D aBD bDD ,(二) NFA M正規(guī)文法,L(G)=L(M). 對轉(zhuǎn)換函數(shù)f(A,t)=B,可寫成一產(chǎn)生式:AtB. 對可接受狀態(tài)Z,增加一產(chǎn)生式: Z.,
30、4.6 詞法分析程序的自動構(gòu)造,正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡 潔方便。而把一個正規(guī)式編譯(或稱轉(zhuǎn)換) 為一個NFA進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA,這個 NFA或DFA正是識別該正規(guī)式所表示的語言 的句子的識別器。基于這種方法來構(gòu)造詞 法分析程序,詞法分析程序的自動構(gòu)造工具LEX簡介,一.原理 單詞的結(jié)構(gòu)用正規(guī)式描述 正規(guī)式 NFA DFA min DFA 二.用LEX建立詞法分析程序的過程,三.lex源程序 lex源程序由三部分組成 聲明 %% 翻譯規(guī)則 %% 輔助過程,聲明包括變量,顯明常量和正規(guī)定義式。 翻譯規(guī)則的形式為: p1 動作1 p2 動作2
31、 p n 動作n,每個pi是正規(guī)定義式的名子,每個動作i是正規(guī)定義式pi識別某類單詞時,詞法分析器應(yīng)執(zhí)行動作的程序段。用C書寫。 輔助過程是動作需要的,這些過程用C書寫,可以分別編譯。 詞法分析器返回給語法分析器一個單詞, ,把單詞的屬性值存放于全程變量yylval中。,作業(yè):P72,1.(1) 5,本章小結(jié),詞法分析程序是編譯第一階段的工作,它 讀入字符流的源程序,按照詞法規(guī)則識別 單詞,交由語法分析程序接下去。 本章講述了詞法分析程序設(shè)計原則,并介紹了分 別作為正規(guī)集的描述機(jī)制和識別機(jī)制的正規(guī)式和 有窮自動機(jī)。在此基礎(chǔ)上給出了詞法分析程序自動 構(gòu)造工具,如LEX的原理。,
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 汽車制造工藝學(xué)-第1章概述ppt課件
- 中樞神經(jīng)系統(tǒng)磁共振序列應(yīng)用課件
- 高考生物大一輪復(fù)習(xí)-第19課時-遺傳基本定律的知識梳理與題型探究ppt課件-新人教版
- 高中物理15斜拋運動ppt課件粵教版必修
- 七年級地理上冊3.2氣溫和降水(第2課時降水的變化干濕區(qū))ppt課件 中圖版
- (人教版)角的初步認(rèn)識課件
- 小學(xué)生安全教育之常見的簡單急救課件
- 癲癇專題知識培訓(xùn)ppt課件
- 牛津高中英語高一上課件M2U3Task
- 中小學(xué)英語公開課—《Childhood--Friends》課件
- 高一地理必修一21地球上的大氣人教版課件
- 振蕩器的設(shè)計解析ppt課件
- 誤差理論與數(shù)據(jù)處理 全套課件
- 直腸癌化療醫(yī)療護(hù)理查房培訓(xùn)ppt課件
- 模塊五-商務(wù)會面禮儀課件