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

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

2、算符等； （2）跳過各種分隔符，如空格，回車，制表符等； （3）刪除注釋； （4）進行詞法檢查，報告所發(fā)現(xiàn)的錯誤； （5）建立符號表。,3.1 詞法分析概述,詞法分析的任務,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,詞法分析的基本思路 將單詞符號的語法用有效的工具描述； 基于該描述建立單詞的識別機制； 設計和實現(xiàn)詞法分析程序。,3.1 詞法分析概述,9,詞法分析程序的工作方式 相對獨立方式（單遍）：把

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

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

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

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

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

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

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

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

11、標識符 無符號整數(shù) 運算符： +、*、= 分界符：，、；,【例】假設某種語言的單詞符號的子集有：,3.2 正規(guī)文法與正規(guī)式,使用正規(guī)式來表示相應單詞符號。,33,字母 | 字母 | 數(shù)字） 數(shù)字 | 數(shù)字 + | * |=,標識符： l(l|d)* 無符號整數(shù)： dd* 單界符： + | * | |, | ; 雙界符： =,3.2 正規(guī)文法與正規(guī)式,34,正規(guī)式：單詞的詞型公式 正規(guī)集：符合詞型公式的單詞的集合，是符號集 運算符：從高到低的優(yōu)先次序：* | 正規(guī)式的定義是一種遞歸定義 正規(guī)式等價 正規(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ī)集的說明,35,(1) 交換律： RS = SR (2) 結合律： 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ī)式的性質,交換律適合 運算嗎？,36,【例】令=a,b，設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)*對應的正規(guī)集：a、b可任意交替出現(xiàn)，如abbaaaba a*b*對應的正規(guī)集：只可出現(xiàn)任意個a或者任意個b,(2) (ab)*對應的正規(guī)集：任意個ab對，即ababab； a*b*對應的正規(guī)集：先出現(xiàn)任意個a后接任意個b，即aabb；,(3) (ab)*對應的正規(guī)集：a、b可任意交替出現(xiàn)，如aa

14、babbb； (a*b*)*可采用如下構造方法得到字符串aababbb： (a*b*)2=(a*b*)(a*b*)=(a2b1)(a1b3)=aababbb 反之，對(a*b*)*產生的任意字也可由(ab)*得到，即兩者是等價的。,【例】 判斷下述正規(guī)式之間是否等價： (1) (ab)*與a*b* (2) (ab)*與a*b* (3) (ab)*與(a*b*)*,3.2 正規(guī)文法與正規(guī)式,不等價,不等價,等價,思考題：求證(ab)*與(a*b*)* 的等價性,38,【例】證明：設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,一個正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義。 對任意一個正規(guī)文法，存在一個定義同一個正規(guī)語言的正規(guī)式；反之，對每個正規(guī)式，存在一個生成同一語言的正規(guī)文法。,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法和正規(guī)式的等價性,40,(1)令S是文法G的開始符號，首先形成Sr (2)對形成的形如Axy的正規(guī)產生式，重寫為：AxB，By (3)對形成的形如Ax*y的正規(guī)產生式，重寫為：AxA，Ay (4)對形成的形如Axy*的正規(guī)產生式，重寫為： Ax，AAy (5)對形如Ax|y的正規(guī)產

16、生式，重寫為：Ax，Ay (6)不斷利用上述規(guī)則做變換，直到每個產生式都符合正規(guī)文法 的要求。,正規(guī)式轉換成正規(guī)文法,將上的正規(guī)式 r 轉換成文法G(VN,VT,S,P)方法如下：,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法和正規(guī)式的等價性,41,步驟1 構造 Sr 步驟2 不斷利用下表的規(guī)則做變換,直到每個產生式 最多含有一個終結符為止。,3.2 正規(guī)文法與正規(guī)式,42,【例】求正規(guī)式(a|b)(a|b|0|1)*對應的正規(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)* 請改用上下文無關文法表示，也就是寫一個上下文無關文法， 它和該正規(guī)式等價。,(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)*轉換成相應的正規(guī)文法,故，R=a(a|d)*轉換成 相應的正規(guī)文法GS：,3.2 正規(guī)文法與正規(guī)式,課堂練習,【解】令S

18、是文法的開始符號,45,將一個正規(guī)文法轉換為正規(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,不斷收縮產生式規(guī)則，直到剩下一個開始符號定 義的正規(guī)式，并且該產生式的右部不含非終結符。,AxA Ay,3.2 正規(guī)文法與正規(guī)式,正規(guī)文法轉換成正規(guī)式,正規(guī)文法和正規(guī)式的等價性,Ax AAy,46,步驟1 將每條產生式改寫為正規(guī)式； 步驟2 用代入法解正規(guī)式方程組，最后只剩下一個 開始符號定義的正規(guī)式，其中不含非終結符。,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,課堂練習：將文法GS轉換成正規(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