《編譯原理之詞法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理之詞法分析.ppt（96頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第4章 詞法分析,本章將討論詞法分析程序的設(shè)計(jì)原則，單 詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析程序 的自動(dòng)構(gòu)造原理。 4.1 詞法分析程序的設(shè)計(jì) 4.2 單詞的描述工具（正規(guī)式和正規(guī)文法） 4.3 有窮自動(dòng)機(jī)(單詞的識(shí)別機(jī)制) 4.4 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 4.5 正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換 4.6 詞法分析程序的自動(dòng)構(gòu)造,本章重點(diǎn),單詞的描述工具 單詞的識(shí)別系統(tǒng) 設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序 首先需要描述和刻畫程序設(shè)計(jì)語言中的原子單位單詞，其次需要識(shí)別單詞和執(zhí)行某些相關(guān)的動(dòng)作。 描述程序設(shè)計(jì)語言的詞法的機(jī)制是正則表達(dá)式，識(shí)別機(jī)制是有窮狀態(tài)自動(dòng)機(jī)。,回顧 什么是詞法分析程序,實(shí)現(xiàn)詞法分析（lexi

2、cal analysis）的程序 逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。 詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行 。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。,詞法分析程序的功能,詞法分析程序的功能是讀入源程序，輸出 單詞符號(hào)。 源程序 單詞符號(hào) “詞法” “分析程序” “的” “功能” 假如你沒有中文分詞的概念，你會(huì)明白中文句子的含義嗎？,詞法分析器,,,詞法分析程序的功能,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è)計(jì),源程序,詞法分析程序,語法分析程序,,,Token,,get token,4.1.2 詞法分析程序的輸出,程序語言單詞的分類： 1關(guān)鍵字(保留字或基本字)：begin,end 2標(biāo)識(shí)符：用來表示各種名字 3字面常數(shù)：256，3 .14，true,abc 4 運(yùn)算符：如，、、*、/ 等等 5分界符：如逗號(hào)，分

4、號(hào)，冒號(hào)等,4.1.2 詞法分析程序的輸出,詞法分析程序所輸出的單詞符號(hào)常常用以 下二元式表示： （單詞種別，單詞自身的值） 單詞的種別是語法分析需要的信息，而單 詞的值則是編譯其它階段需要的信息。 例如：在PASCAL的語句const i=25; yes=1; 中的單詞25和1的種別是常數(shù)，常數(shù)的值是25和1。,4.1.3 將詞法分析工作分離的考慮,簡(jiǎn)化設(shè)計(jì) 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性,4.2 單詞的描述工具,程序設(shè)計(jì)語言中的單詞是基本語法成分。 單詞符號(hào)的語法可以用有效的工具加以描 述。 基于描述工具，實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造。,4.2.1 正規(guī)文法,多數(shù)程序設(shè)計(jì)語言的單詞的語

5、法都能用正規(guī)文法或3型文法來描述。 程序設(shè)計(jì)語言中的幾類單詞可用下述規(guī)則 來描述： L|L L|d|L ,, d|d| +|-|*|/|=|=| ,|;|(|)|....... 其中L表示az中的任何一英文字母，d表 示09中的任一數(shù)字。,例4.1 無符號(hào)數(shù)的正規(guī)文法, d|.|e d|.| e| d e|d| d|s d d| 其中s表示正或負(fù)號(hào)+，-。,4.2.2 正規(guī)式,正規(guī)式也稱正則表達(dá)式,正規(guī)表達(dá)式 （regular expression）是說明單詞的模 式(pattern)的一種重要的表示法（記號(hào)） ，是定義正規(guī)集的數(shù)學(xué)工具。我們用以描 述單詞符號(hào)。下面是正規(guī)式和它

6、所表示的 正規(guī)集的遞歸定義。,正規(guī)式和它所表示的正規(guī)集,定義（正規(guī)式和它所表示的正規(guī)集）： 設(shè)字母表為，輔助字母表=，，，，，，。 1.和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ； 2. 任何a ，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a；,正規(guī)式和它所表示的正規(guī)集,3. 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1))。 4. 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的

7、集合才是上的正規(guī)集。,正規(guī)式和它所表示的正規(guī)集,其中的“”讀為“或”（也有使用“+”代 替 “” 的）；“ ”讀為“連接”；“” 讀為“閉包”（即，任意有限次的自重復(fù)連 接）。在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算 符的優(yōu)先順序?yàn)椤啊?、?”、“” 。連 接符“ ”一般可省略不寫?！啊?、“ ” 和“” 都是左結(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, 任意個(gè)a的串,正規(guī)式 正規(guī)集 (ab) ,a,b,aa,ab 所有由a 和b組成的串 (ab)(aabb)(a

8、b) 上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串,例4.3 =d，.，e，+，-, 則上的正規(guī)式 d(.dd)(e(+-)dd) 表示的是無符號(hào)數(shù)的集合。其中d為0-9的數(shù)字。,例:令=l，d，則上的正規(guī)式r=l(ld)定義的正規(guī)集為:l,ll,ld,ldd,,其中l(wèi)代表字母,d代表數(shù)字, 正規(guī)式即是字母(字母|數(shù)字) ,它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法規(guī)則。 含義： 上所有由字母開頭的串。 字母打頭的后跟字母和數(shù)字任意組合的串,若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價(jià),寫作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ī)式的等價(jià)性,一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一

10、個(gè)語言的正規(guī)式； 反之，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一個(gè)語言的正規(guī)文法。,一、將上的一個(gè)正規(guī)式轉(zhuǎn)換成正規(guī)文法,將上的一個(gè)正規(guī)式r轉(zhuǎn)換成文法G=（VN，VT，S，P）。令其中的VT= ，確定產(chǎn)生式和VN用如下辦法： 對(duì)任何正規(guī)式r，選擇一個(gè)非終結(jié)符S生成產(chǎn)生式Sr，并將S定為G的識(shí)別符號(hào)。 若x和y都是正規(guī)式，對(duì)形如Axy的產(chǎn)生式，重寫成：A xB, B y兩產(chǎn)生式，其中B是新選擇的非終結(jié)符，即BVN,對(duì)已轉(zhuǎn)換的文法中的形如A x*y的產(chǎn)生式，重寫為：A xBA yB xBB y其中B為一新非終結(jié)符。 對(duì)形如A x|y的產(chǎn)生式，重寫為：A xA y 不斷利用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式最多含有

11、一個(gè)終結(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ī)式,基本上是上述過程的逆過程，最后只剩下 一個(gè)開始符號(hào)定義的產(chǎn)生式，并且該產(chǎn)生 式的右部不含非終結(jié)符。,例4.5 文法GS，求該文法對(duì)應(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 有窮自動(dòng)機(jī),有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。 有窮自動(dòng)機(jī)分為兩類： 確定的有窮自動(dòng)機(jī)(Deterministic Finite Automata) -- DFA 不確定的有窮自動(dòng)機(jī)(Nondeterministic Finite Automata) -- NFA,關(guān)于有窮自動(dòng)機(jī)我們將討論如下題目,確定的有窮自動(dòng)機(jī)DFA 不確定的有窮自動(dòng)機(jī)NFA NFA的確定化 DFA的最小化,4.3.1 確定

13、的有窮自動(dòng)機(jī)DFA,DFA定義： 一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，，f，S，Z）其中 1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； （狀態(tài)集） 2.是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)表；,DFA定義,3.f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如f（ki，a）=kj，（kiK，kjK）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)； 4.SK是唯一的一個(gè)初態(tài)； 5.Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。,一個(gè)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,一個(gè)DFA可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài) 轉(zhuǎn)換圖)。假定DFA M含有m個(gè)狀態(tài)，n個(gè)輸入字 符，那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最 多有n個(gè)弧射出，整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn) 和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“”或 標(biāo)以“-”，終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“+”，若 f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)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,一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣 的行表示狀態(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如何作為一種識(shí)別機(jī)制,我們還要理解下面的定義,*上的符號(hào)串t在DFA M上運(yùn)行 一個(gè)輸入符號(hào)串t，（將它表示成Tt1的形式， 其中T，t1 *）在DFA M=（K，， f，S，Z）上運(yùn)行的定義為： f（Q， Tt1）=f（f（Q，T），

16、t1） 其中QK 擴(kuò)充轉(zhuǎn)換函數(shù)f為 K*K上的映射，且： f（ki，）= ki,*上的符號(hào)串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所接受（識(shí)別）.,,例：證明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所能接受的符號(hào)串的全體記為L(zhǎng)(M).對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M，如果L(M)=L(M

17、 )，則稱M與M是等價(jià)的. 結(jié)論： 上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有窮自動(dòng)機(jī)M，使得V=L(M)。,DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個(gè)單值函數(shù)，也就是說，對(duì)任何狀態(tài)kK，和輸入符號(hào)a，f(k,a)唯一地確定了下一個(gè)狀態(tài)。 從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。,4.3.2 不確定的有窮自動(dòng)機(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, 對(duì)NFA M=K，，f，S，Z也有如下定義,*上的符號(hào)串t在NFA M上運(yùn)行.. 一個(gè)輸入符號(hào)串t，（我們將它表示成Tt1的形式，其 中T，t1 *）在NFA M上運(yùn)行的定義為： f（Q， Tt1）=f（f（Q，T），t1） 其中QK. *上的符號(hào)串t被NFA M接受 若t *，f(S0，t)=P，其中S0 S，P Z， 則稱t為NFA M所接受（識(shí)別）,*上的符號(hào)串t被NFA M接受也可以這樣理解,對(duì)

19、于中的任何一個(gè)串t，若存在一條從 某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上 所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo) 記為的弧)等于t，則稱t可為NFA M所識(shí)別(讀出 或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)， 或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路, 其上所有弧的標(biāo)記均為，那么空字可為M所接受。,4.3.3 NFADFA的轉(zhuǎn)換,從NFA的矩陣表示中可以看出，表項(xiàng)通常 是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造 的基本思路是： DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài).,D

20、FA是NFA的特例.對(duì)每個(gè)NFA N一定存在一個(gè)DFA ，使得L(M)=L(N)。對(duì)每個(gè)NFA N存在著與之等價(jià)的DFA M 有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法. 與某一NFA等價(jià)的DFA不唯一.,定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yù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、運(yùn)算的例子,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)造 一個(gè)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ī)則排列的，即對(duì)于子集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 每個(gè)輸入字母a do U:= -closure(move(T,a))； if U不在C中 then 將U作為未標(biāo)記的子集加在C中,例4.8 對(duì)圖4.4的NFA N確定化。,,NFA確定化為DFA的過程如下所示,Ia= -closure(move(I,a)) Ib= -closure(move(I,b)),DFA M 如圖4.6所示,,,4.3.4 確定有窮自動(dòng)機(jī)的化簡(jiǎn),1 什么是多余狀態(tài)？ 所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入

24、串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。,4.3.4 確定有窮自動(dòng)機(jī)的化簡(jiǎn),2 什么是等價(jià)狀態(tài)？ 兩個(gè)狀態(tài)s和t等價(jià)：滿足 兼容性(一致性條件)同是終態(tài)或同是非終態(tài) 傳播性（蔓延性條件）對(duì)于所有輸入符號(hào)，狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。,一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。 說一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。,DFA的最小化就是尋求最小狀態(tài)DFA,最小狀態(tài)DFA的含義: 沒有多余狀態(tài)(死狀態(tài)) 沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）,C和D同是終態(tài),讀入a到達(dá)C和F, C和F同是終態(tài)

25、, C和F讀入a都到達(dá)C,讀入b都到達(dá)E. C和D等價(jià),,最小狀態(tài)DFA,對(duì)于一個(gè)DFA M =（K,,f, k0,,kt)，存在一個(gè)最小狀態(tài)DFA M =（K,,f, k0,,kt)，,使L(M)=L(M).,“分割法”,DFA的最小化算法的核心 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 算法假定每個(gè)狀態(tài)射出的弧都是完全的,否則,引入一個(gè)新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對(duì)所有輸入，該狀態(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ī)式和有窮自動(dòng)機(jī)DFA的等價(jià)性,1有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性 對(duì)于上的一個(gè)NFA M，可以構(gòu)造 一個(gè)上的正規(guī)式R,使得L(R)=L(M)。 對(duì)于上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)上的NFA M，使的L(M)=L(R)。,2有窮自動(dòng)機(jī) NFA正規(guī)式,為M添加兩個(gè)結(jié)點(diǎn)的X,Y，X用連接到M的所有

27、初態(tài)，Y用連接到M的所有終態(tài)。 利用下面三條規(guī)則： 反復(fù)三條規(guī)則，最后X,Y間的標(biāo)記就是所求的正規(guī)式R。,3.正規(guī)式有窮自動(dòng)機(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).對(duì)于正規(guī)式r, r= r1|r2構(gòu)造的NFA,,(3).對(duì)于正規(guī)式r, r=r1r2構(gòu)造的NFA,4. 對(duì)于正規(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é)點(diǎn)，分別用弧連接到初態(tài)和

28、終態(tài). 如圖4.9(a)所示M,Step 2. 逐步消去M中的結(jié)點(diǎn), 消去1,3之后如圖4.9(b).,Step 3. 逐步消去M中的結(jié)點(diǎn), 消去2,4之后如圖4.9(c).,Step 4. 逐步消去M中的結(jié)點(diǎn), 消去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ī)文法和有窮自動(dòng)機(jī)的等價(jià)性,(一) 正規(guī)文法NFA M，L(M)=L(G). M的字母表與G的終結(jié)符集相同, =VT 為G中的每個(gè)非終結(jié)符生成一個(gè)同名狀態(tài)，G的開始符號(hào)S是開始狀態(tài). 增加一個(gè)新狀

29、態(tài)Z作為NFA的終態(tài). 對(duì)G中的形如A tB的規(guī)則(其中t為終結(jié)符或, A,B為非終結(jié)符的產(chǎn)生式)，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B. 對(duì)G中形如A t的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z.,例4.12 與文法GS等價(jià)的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). 對(duì)轉(zhuǎn)換函數(shù)f(A,t)=B,可寫成一產(chǎn)生式：AtB. 對(duì)可接受狀態(tài)Z，增加一產(chǎn)生式： Z.,

30、4.6 詞法分析程序的自動(dòng)構(gòu)造,正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡(jiǎn) 潔方便。而把一個(gè)正規(guī)式編譯(或稱轉(zhuǎn)換) 為一個(gè)NFA進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA，這個(gè) NFA或DFA正是識(shí)別該正規(guī)式所表示的語言 的句子的識(shí)別器?；谶@種方法來構(gòu)造詞 法分析程序,詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介,一.原理 單詞的結(jié)構(gòu)用正規(guī)式描述 正規(guī)式 NFA DFA min DFA 二.用LEX建立詞法分析程序的過程,三.lex源程序 lex源程序由三部分組成 聲明 %% 翻譯規(guī)則 %% 輔助過程,聲明包括變量，顯明常量和正規(guī)定義式。 翻譯規(guī)則的形式為： p1 動(dòng)作1 p2 動(dòng)作2

31、 p n 動(dòng)作n,每個(gè)pi是正規(guī)定義式的名子，每個(gè)動(dòng)作i是正規(guī)定義式pi識(shí)別某類單詞時(shí)，詞法分析器應(yīng)執(zhí)行動(dòng)作的程序段。用C書寫。 輔助過程是動(dòng)作需要的，這些過程用C書寫，可以分別編譯。 詞法分析器返回給語法分析器一個(gè)單詞, ,把單詞的屬性值存放于全程變量yylval中。,作業(yè)：P72,1.（1） 5,本章小結(jié),詞法分析程序是編譯第一階段的工作，它 讀入字符流的源程序，按照詞法規(guī)則識(shí)別 單詞，交由語法分析程序接下去。 本章講述了詞法分析程序設(shè)計(jì)原則，并介紹了分 別作為正規(guī)集的描述機(jī)制和識(shí)別機(jī)制的正規(guī)式和 有窮自動(dòng)機(jī)。在此基礎(chǔ)上給出了詞法分析程序自動(dòng) 構(gòu)造工具，如LEX的原理。,