第3章 詞法分析(1).ppt

1、1,第三章 詞法分析,2,文法和語(yǔ)言概述 字母表和符號(hào)串 文法和語(yǔ)言的形式定義 文法的類型 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 句型的分析 有關(guān)文法實(shí)用中的說(shuō)明,前章回顧,3,詞法分析,4,要求明確此階段的任務(wù); 理解單詞分類和構(gòu)詞規(guī)則; 會(huì)使用單詞的描述和識(shí)別機(jī)制; 掌握正規(guī)文法、狀態(tài)圖、自動(dòng)機(jī)（重點(diǎn)）、正規(guī)式和正規(guī)集的基本概念和它們之間的關(guān)系; 掌握詞法分析程序的實(shí)現(xiàn)方法。,詞法分析,5,詞法分析,詞法分析程序概述 正規(guī)文法與正規(guī)式 有窮自動(dòng)機(jī) 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性 正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性 一個(gè)簡(jiǎn)單的詞法分析器示例,6,（1）分析和識(shí)別單詞及屬性， 包括識(shí)別語(yǔ)言的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)

2、算符等； （2）跳過(guò)各種分隔符，如空格，回車，制表符等； （3）刪除注釋； （4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤； （5）建立符號(hào)表。,3.1 詞法分析概述,詞法分析的任務(wù),7,main( ) /*ADD*/ int x=10, y=20, sum; sum=x+y; ,main、(、)、int、x、=、10、，、y、=、20、，、sum、；、sum、=、x、+、y、；、,詞法分析,3.1 詞法分析概述,8,詞法分析的基本思路 將單詞符號(hào)的語(yǔ)法用有效的工具描述； 基于該描述建立單詞的識(shí)別機(jī)制； 設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序。,3.1 詞法分析概述,9,詞法分析程序的工作方式 相對(duì)獨(dú)立方式（單遍）：把

3、詞法分析程序作為語(yǔ)法分析程序的一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)時(shí)調(diào)用這個(gè)子程序。 完全獨(dú)立方式（多遍）：詞法分析程序作為單獨(dú)一趟來(lái)實(shí)現(xiàn)。詞法分析程序讀入整個(gè)源程序，它的輸出作為語(yǔ)法分析程序的輸入。,3.1 詞法分析概述,10,2.詞法分析單獨(dú)作為一遍,S.P.(字符串),優(yōu)點(diǎn): 結(jié)構(gòu)清晰、各遍功能單一 缺點(diǎn)：效率低,1.詞法分析程序作為語(yǔ)法程序的子程序,S.P.(字符串),詞法分 析程序,語(yǔ)法分 析程序,取單詞,單詞,3.1 詞法分析概述,11,源程序 字符串,詞 法 分 析 器,符號(hào)表,單詞符號(hào) 串程序,字符,單詞,詞法分析程序與語(yǔ)法分析程序的接口方式圖示,源程序 字符串,詞 法 分

4、析 器,符 號(hào) 表,語(yǔ) 法 分 析 器,字符,單詞,取下一單詞,詞法分析程序 作為獨(dú)立程序 （多遍）,詞法分析程序 作為語(yǔ)法分析程序的子程序 （單遍）,3.1 詞法分析概述,12,單詞的種類 （1）關(guān)鍵字：if、for、while （2）標(biāo)識(shí)符： （3） 常數(shù)： （4） 運(yùn)算符：+、-、* （5）分界符：, 、;、(、),詞法分析程序的輸出形式,3.1 詞法分析概述,13,3.1 詞法分析概述,詞法分析程序的輸出形式,單詞類別可以用整數(shù)編碼 表示:一類一種或一字一種,14,int x=10,y=20,sum;詞法分析的結(jié)果,3.1 詞法分析概述,15,詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.1 詞法分析

5、概述,（1）根據(jù)詞法規(guī)則寫出正規(guī)文法； （2）將正規(guī)文法轉(zhuǎn)換成狀態(tài)圖； （3）將狀態(tài)圖轉(zhuǎn)換成流程圖； （4）寫出詞法分析程序。,16,3.1 詞法分析概述,正規(guī)文法及其狀態(tài)圖,狀態(tài)圖：為識(shí)別單詞而專門設(shè)計(jì)的有向圖， 是設(shè)計(jì)詞法分析程序的一種好途徑。,結(jié)點(diǎn)代表狀態(tài)，用圓圈表示，為非終結(jié)符； 有向弧表示狀態(tài)轉(zhuǎn)移； 弧上的標(biāo)記表示在射出弧的結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符，為終結(jié)符。,一張狀態(tài)圖包含有窮個(gè)狀態(tài)，只能有一個(gè)初態(tài)，至少要有一個(gè)終態(tài)（用雙圈表示）。,17,例：某語(yǔ)言的標(biāo)識(shí)符可使用以下正規(guī)文法GS來(lái)定義：,SlA A|lA|dA la,b,z， d1,2,9 試構(gòu)造此文法的狀態(tài)圖。,3.1 詞法

6、分析概述,18,由正規(guī)文法構(gòu)造狀態(tài)圖,3.1 詞法分析概述,（1）對(duì)于右線性文法 步驟1 增加結(jié)點(diǎn)Z為終態(tài)； 步驟2 將每個(gè)非終結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)； 步驟3 對(duì)于Aa，引一條從A到Z的弧，弧上標(biāo)記為a； 而對(duì)于AaB，引一條從A到B的弧，弧上標(biāo)記為a。,SlA A|lA|dA,19,由正規(guī)文法構(gòu)造狀態(tài)圖,（1）對(duì)于左線性文法 步驟1 增加結(jié)點(diǎn)S為初態(tài)； 步驟2 將每個(gè)非終結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)； 步驟3 對(duì)于Aa，引一條從S到A的弧，弧上標(biāo)記為a； 而對(duì)于ABa，引一條從B到A的弧，弧上標(biāo)記為a。,3.1 詞法分析概述,Al|Al|Ad,SlA A|lA|dA,20,詞法分析程序的

7、設(shè)計(jì)與實(shí)現(xiàn),（1）根據(jù)詞法規(guī)則寫出正規(guī)文法； （2）將正規(guī)文法轉(zhuǎn)換成狀態(tài)圖； （3）將狀態(tài)圖轉(zhuǎn)換成流程圖； （4）寫出詞法分析程序。,3.1 詞法分析概述,21,標(biāo)識(shí)符 無(wú)符號(hào)整數(shù) 運(yùn)算符：+、*、= 分界符：，、；,【例】假設(shè)某種語(yǔ)言的單詞符號(hào)的子集有：,試構(gòu)造此語(yǔ)言子集的詞法分析程序。,3.1 詞法分析概述,22,（1）根據(jù)詞法規(guī)則寫出正規(guī)文法,字母 | 字母 | 數(shù)字） 數(shù)字 | 數(shù)字 + | * | = | =,3.1 詞法分析概述,23,出口,S,非字母數(shù)字,字母,字母、數(shù)字,出口,S,2,非數(shù)字,數(shù)字,數(shù)字,出口,S,3,其他字符,+ * = , ;,標(biāo)識(shí)符,無(wú)符號(hào)整數(shù),單字符分界

8、符,雙字符分界符,出口,S,4,其他字符,5,=,非 =,（2）將正規(guī)文法轉(zhuǎn)換成狀態(tài)圖,3.1 詞法分析概述,1,24,合并 將初始狀態(tài)合并為一個(gè)唯一的初態(tài)； 化簡(jiǎn)調(diào)整狀態(tài)沖突并對(duì)沖突狀態(tài)重新編號(hào)； 如有必要，增加出錯(cuò)狀態(tài)。,3.1 詞法分析概述,25,3.1 詞法分析概述,合并后的狀態(tài)圖,標(biāo)識(shí)符,無(wú)符號(hào)整數(shù),單界符,雙界符,26,（3）將狀態(tài)圖轉(zhuǎn)換成流程圖,（4）寫出詞法分析程序,3.1 詞法分析概述,27,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法,3型文法回顧;,（右線性）P： A:=a 或 A:=aB 其中 A、B VN a VT,3型語(yǔ)言：L3，又稱正則語(yǔ)言。,3型文法稱為正則文法。它是對(duì)2

9、型文法進(jìn)行進(jìn)一步限制。 左線性 和右線性文法是相互等價(jià)的,（左線性）P： A:=a 或 A:=Ba 其中 A、B VN a VT,多數(shù)程序設(shè)計(jì)語(yǔ)言的單詞語(yǔ)法都能用正規(guī)文法（3型文法）來(lái)描述。,28,3.2 正規(guī)文法與正規(guī)式,為何引入正規(guī)式？ 可以更好的表示單詞的構(gòu)成規(guī)則（形式化的規(guī)則）。 狀態(tài)轉(zhuǎn)換圖的形式化，便于詞法分析器的自動(dòng)生成。,正規(guī)式,29,3.2 正規(guī)文法與正規(guī)式,正規(guī)式和正規(guī)集的定義,(1) 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和。 (2) 對(duì)任一個(gè)a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a。 (3) 如果R和S是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(R) 和L(S)，則

10、： RS是上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)L(S)； RS是上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)L(S)； R*是上的正規(guī)式，它所表示的正規(guī)集為(L(R)*； (R)也是上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)。 (4) 僅由有限次使用規(guī)則(1)(3)得到的表示式是上的正規(guī)式，它 所表示的集合是上的正規(guī)集。,30,正規(guī)式中的運(yùn)算符： | 或（選擇） 連接 * 或 重復(fù) （） 括號(hào),運(yùn)算符的優(yōu)先級(jí)： 先 * , 后 , 最后 | 在正規(guī)式中可以省略。,正規(guī)式相等這兩個(gè)正規(guī)式表示的語(yǔ)言相等,3.2 正規(guī)文法與正規(guī)式,31,【例】設(shè)=a,b,正規(guī)式和正規(guī)集示例,3.2 正規(guī)文法與正規(guī)式,32,

11、標(biāo)識(shí)符 無(wú)符號(hào)整數(shù) 運(yùn)算符： +、*、= 分界符：，、；,【例】假設(shè)某種語(yǔ)言的單詞符號(hào)的子集有：,3.2 正規(guī)文法與正規(guī)式,使用正規(guī)式來(lái)表示相應(yīng)單詞符號(hào)。,33,字母 | 字母 | 數(shù)字） 數(shù)字 | 數(shù)字 + | * |=,標(biāo)識(shí)符： l(l|d)* 無(wú)符號(hào)整數(shù)： dd* 單界符： + | * | |, | ; 雙界符： =,3.2 正規(guī)文法與正規(guī)式,34,正規(guī)式：?jiǎn)卧~的詞型公式 正規(guī)集：符合詞型公式的單詞的集合，是符號(hào)集 運(yùn)算符：從高到低的優(yōu)先次序：* | 正規(guī)式的定義是一種遞歸定義 正規(guī)式等價(jià) 正規(guī)式R和S，如果L(R)=L(S),則RS,【例】 L(b(ab)*)=L(ba)*b)， b(

12、ab)*=(ba)*b L(a|b)*)=L(a)*(b)*)*), (a|b)*=(a)*(b)*)*,3.2 正規(guī)文法與正規(guī)式,正規(guī)式和正規(guī)集的說(shuō)明,35,(1) 交換律： RS = SR (2) 結(jié)合律： R(ST) = (RS)T R(ST) = (RS)T (3) 分配律： R(ST) = RSRT (RS)T = RTST (4) 同一律： R = R = R (5) 抽取律： r | r = r,3.2 正規(guī)文法與正規(guī)式,正規(guī)式的性質(zhì),交換律適合 運(yùn)算嗎？,36,【例】令=a,b，設(shè)R=a(ab)* 是上的正規(guī)式， 試求其表示的正規(guī)集。 【解答】L(R)=L(a(ab)*)=L(

13、a)L(ab)*) =L(a)(L(ab)*=L(a)(L(a)L(b)* =a(ab)*=aa,b* =a, a, b, aa, ab, ba, bb, aaa, =a, aa, ab, aaa, aab, aba, abb, aaaa, ,3.2 正規(guī)文法與正規(guī)式,37,【解答】 (1) (ab)*對(duì)應(yīng)的正規(guī)集：a、b可任意交替出現(xiàn)，如abbaaaba a*b*對(duì)應(yīng)的正規(guī)集：只可出現(xiàn)任意個(gè)a或者任意個(gè)b,(2) (ab)*對(duì)應(yīng)的正規(guī)集：任意個(gè)ab對(duì)，即ababab； a*b*對(duì)應(yīng)的正規(guī)集：先出現(xiàn)任意個(gè)a后接任意個(gè)b，即aabb；,(3) (ab)*對(duì)應(yīng)的正規(guī)集：a、b可任意交替出現(xiàn)，如aa

14、babbb； (a*b*)*可采用如下構(gòu)造方法得到字符串a(chǎn)ababbb： (a*b*)2=(a*b*)(a*b*)=(a2b1)(a1b3)=aababbb 反之，對(duì)(a*b*)*產(chǎn)生的任意字也可由(ab)*得到，即兩者是等價(jià)的。,【例】 判斷下述正規(guī)式之間是否等價(jià)： (1) (ab)*與a*b* (2) (ab)*與a*b* (3) (ab)*與(a*b*)*,3.2 正規(guī)文法與正規(guī)式,不等價(jià),不等價(jià),等價(jià),思考題：求證(ab)*與(a*b*)* 的等價(jià)性,38,【例】證明：設(shè)L(a+)=a*-，則有a+=aa*。 【證明】L(a+)=a*-=, a, a2, a3, - =a, a2, a

15、3, =a, a, a2 =aa*=L(a)L(a*)=L(aa*) 故：a+=aa*,3.2 正規(guī)文法與正規(guī)式,39,一個(gè)正規(guī)語(yǔ)言可以由正規(guī)文法定義，也可以由正規(guī)式定義。 對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)正規(guī)語(yǔ)言的正規(guī)式；反之，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法。,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法和正規(guī)式的等價(jià)性,40,(1)令S是文法G的開(kāi)始符號(hào)，首先形成Sr (2)對(duì)形成的形如Axy的正規(guī)產(chǎn)生式，重寫為：AxB，By (3)對(duì)形成的形如Ax*y的正規(guī)產(chǎn)生式，重寫為：AxA，Ay (4)對(duì)形成的形如Axy*的正規(guī)產(chǎn)生式，重寫為： Ax，AAy (5)對(duì)形如Ax|y的正規(guī)產(chǎn)

16、生式，重寫為：Ax，Ay (6)不斷利用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式都符合正規(guī)文法 的要求。,正規(guī)式轉(zhuǎn)換成正規(guī)文法,將上的正規(guī)式 r 轉(zhuǎn)換成文法G(VN,VT,S,P)方法如下：,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法和正規(guī)式的等價(jià)性,41,步驟1 構(gòu)造 Sr 步驟2 不斷利用下表的規(guī)則做變換,直到每個(gè)產(chǎn)生式 最多含有一個(gè)終結(jié)符為止。,3.2 正規(guī)文法與正規(guī)式,42,【例】求正規(guī)式(a|b)(a|b|0|1)*對(duì)應(yīng)的正規(guī)文法,S(a|b)(a|b|0|1)*,S(a|b),AaA|bA|0A|1A|,GS： SaA|bA AaA|bA|0A|1A|,A(a|b|0|1)*,3.2 正規(guī)文法與正規(guī)

17、式,43,下面是用正規(guī)式表示的變量聲明：(int|float)id(,id)* 請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫一個(gè)上下文無(wú)關(guān)文法， 它和該正規(guī)式等價(jià)。,(int | float ) id (, id )*,D( int | float )L L id (, id )*,D int L | float L L L, id | id,GD：Dint L | float L L L, id | id,3.2 正規(guī)文法與正規(guī)式,44,S a(a|d)*,【例】將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法,故，R=a(a|d)*轉(zhuǎn)換成 相應(yīng)的正規(guī)文法GS：,3.2 正規(guī)文法與正規(guī)式,課堂練習(xí),【解】令S

18、是文法的開(kāi)始符號(hào),45,將一個(gè)正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則： (1)AxB，By 正規(guī)式為： A=xy (2)AxA|y， 正規(guī)式為： A=x*y (3)Ax|Ay， 正規(guī)式為： A=xy* (4)Ax，Ay 正規(guī)式為： A=x|y,不斷收縮產(chǎn)生式規(guī)則，直到剩下一個(gè)開(kāi)始符號(hào)定 義的正規(guī)式，并且該產(chǎn)生式的右部不含非終結(jié)符。,AxA Ay,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法轉(zhuǎn)換成正規(guī)式,正規(guī)文法和正規(guī)式的等價(jià)性,Ax AAy,46,步驟1 將每條產(chǎn)生式改寫為正規(guī)式； 步驟2 用代入法解正規(guī)式方程組，最后只剩下一個(gè) 開(kāi)始符號(hào)定義的正規(guī)式，其中不含非終結(jié)符。,3.2 正規(guī)文法與正規(guī)式,AxB By|z,AxA|y|z,Axy|xz,Ax*y|x*z,47,【例】GS: SaA|a AdA|d,S=aA|a A= d*d,3.2 正規(guī)文法與正規(guī)式,48,SaA Sa AaA AdA Aa Ad,課堂練習(xí)：將文法GS轉(zhuǎn)換成正規(guī)式:,3.2 正規(guī)文法與正規(guī)式,49,3.2 正規(guī)文法與正規(guī)式,根據(jù)上述規(guī)則2， AxA|y 推出 A=x*y,SaA|a,SaA Sa AaA AdA Aa Ad,A=(aA|dA)|(a|d),將A代入SaA