1、第3章 詞法分析,2020年7月28日,1,內(nèi)容提要,1、詞法分析的功能 2、詞法分析結(jié)果表示 3、正則文法及狀態(tài)圖 4、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),2020年7月28日,2,3.1詞法分析的功能,（1）分析和識(shí)別單詞及屬性，包括識(shí)別語(yǔ)言的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等； （2）跳過(guò)各種分隔符，如空格，回車，制表符等； （3）刪除注釋； （4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤； （5）建立符號(hào)表。,main( )/*ADD*/ int x=10,y=20,sum; sum=x+y; ,2020年7月28日,3,實(shí)現(xiàn)方案：基本上有兩種,1.詞法分析單獨(dú)作為一遍,2.詞法分析程序作為語(yǔ)法分析的子程序,

2、S.P.(字符串),詞法分析,S.P.(單詞串),語(yǔ)法分析,第一遍,第二遍,單詞串,優(yōu)點(diǎn): 結(jié)構(gòu)清晰、各遍功能單一 缺點(diǎn)：效率低,2020年7月28日,4,3.2 詞法分析結(jié)果表示,詞法分析的輸出常采用二元組。 單詞類別用一個(gè)整數(shù)類碼或單詞記號(hào)表示。 單詞記號(hào)比整數(shù)碼含義明確。例如，保留字for，可直接用字符串for作為單詞記號(hào)來(lái)表示 整數(shù)類碼，含義不直觀。 單詞類別如何分類、分成幾類、怎樣編碼，主要取決于技術(shù)處理上的方便。標(biāo)識(shí)符一般歸為一類，常數(shù)則按類型（整數(shù)、實(shí)數(shù)等）分類。保留字即可將全體定為一類，也可一字一類。分界符可單獨(dú)作為一類，也可采用一符一類的分法。,2020年7月28日,5,3.

3、3 正則文法及狀態(tài)圖,程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)可用正則文法來(lái)描述。 正則文法所描述的語(yǔ)言可用有窮自動(dòng)機(jī)來(lái)識(shí)別。 自動(dòng)機(jī)的非形式表示，即狀態(tài)圖。 為識(shí)別單詞而專門設(shè)計(jì)的有向圖，是設(shè)計(jì)詞法分析程序的一種好途徑。,2020年7月28日,6,狀態(tài)圖 狀態(tài)圖是一張有窮的有向圖。結(jié)點(diǎn)代表狀態(tài)，用圓圈表示，狀態(tài)間用有向弧連接，弧上有標(biāo)記符號(hào)，表示在弧線射出端的狀態(tài)下，讀入弧上標(biāo)記的符號(hào)可轉(zhuǎn)換到弧指向的狀態(tài)。 狀態(tài)圖只有有窮個(gè)狀態(tài)，其中只有一個(gè)開始狀態(tài)，至少有一個(gè)結(jié)束狀態(tài)，結(jié)束狀態(tài)常用雙圈表示。,2020年7月28日,7,由正則文法構(gòu)造狀態(tài)圖,（1）對(duì)于右線性文法 步驟1 增加結(jié)點(diǎn)Z為終態(tài)； 步驟2 將每個(gè)非終

4、結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)；將開始符號(hào)作為初態(tài)。 步驟3 對(duì)于Aa，引一條從A到Z的弧，弧上標(biāo)記為a；而對(duì)于AaB，引一條從A到B的弧，弧上標(biāo)記為a。,SlA A|lA|dA,2020年7月28日,8,（2）對(duì)于左線性文法 步驟1 增加結(jié)點(diǎn)S為初態(tài)； 步驟2 將每個(gè)非終結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)；文法中的開始符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)為終結(jié)狀態(tài) 步驟3 對(duì)于Aa，引一條從S到A的弧，弧上標(biāo)記為a；而對(duì)于ABa，引一條從B到A的弧，弧上標(biāo)記為a。,Al|Al|Ad,2020年7月28日,9,例3.1，設(shè)有正則文法GZ： ZU0|V1 UZ1|1 VZ0|0 畫出該文法對(duì)應(yīng)的狀態(tài)圖。,解：1、根據(jù)正則文法是左

5、線性還是右線性以及非終結(jié)符的數(shù)量，確定狀態(tài)圖的結(jié)點(diǎn)數(shù)量以及開始狀態(tài)和結(jié)束狀態(tài)。 2、根據(jù)產(chǎn)生式畫狀態(tài)圖。 思考：該文法確定的語(yǔ)言是什么？,S,U,V,Z,0,0,0,1,1,1,2020年7月28日,10,3.3.2 狀態(tài)圖的用法,利用狀態(tài)圖可分析和識(shí)別字符串，其方法如下： 1.設(shè)初始狀態(tài)S為當(dāng)前狀態(tài)。從輸入串的最左字符開始重復(fù)步驟2，直到到達(dá)輸入串的右端為止。 2.掃描輸入串的下一個(gè)字符，在當(dāng)前狀態(tài)所射出的弧中，找出標(biāo)記有該字符的弧，并沿此弧前進(jìn)，過(guò)渡到下一個(gè)狀態(tài)。 如果找不到標(biāo)記有該字符的弧，則說(shuō)明輸入串不合法，分析過(guò)程失敗結(jié)束； 如果掃描輸入串的最后一個(gè)字符，并從當(dāng)前狀態(tài)出發(fā)沿著標(biāo)記有該

6、字符的弧到達(dá)終結(jié)狀態(tài)，則表示輸入串合法，識(shí)別過(guò)程成功結(jié)束； 如果掃描輸入串的最后一個(gè)符號(hào)后到達(dá)的狀態(tài)不是狀態(tài)圖的終結(jié)狀態(tài)，則表示輸入串不合法，識(shí)別過(guò)程失敗結(jié)束。,2020年7月28日,11,3.3.2 狀態(tài)圖的用法,例3.2，對(duì)句子0110進(jìn)行分析。,Z,U,0,Z,1,V,1,0,3.5（a）輸入串0110分析過(guò)程,圖3.5（b）輸入串0110的語(yǔ)法樹,正則文法GZ： （1）ZU0|V1 （2）UZ1|1 （3）VZ0|0,2020年7月28日,12,利用狀態(tài)圖（由左線性文法構(gòu)造）識(shí)別句子的方法是一種自底向上的分析方法。 開始時(shí)，處于開始狀態(tài)，此時(shí)句柄是隨后掃描的字符，即輸入串的的第一個(gè)符號(hào)

7、，所要?dú)w約的符號(hào)就是從開始狀態(tài)經(jīng)過(guò)標(biāo)記有句柄符號(hào)的弧到達(dá)的下一個(gè)狀態(tài)的名字。 以后每一步（除第一步外）的句柄是當(dāng)前狀態(tài)的名字和隨后掃描的字符，而句柄所要?dú)w約的符號(hào)就是下一個(gè)狀態(tài)的名字。 問(wèn)題：右線性文法構(gòu)造的狀態(tài)圖？,2020年7月28日,13,狀態(tài)圖的應(yīng)用,問(wèn)題： 一個(gè)人帶著狼、山羊和白菜在一條河的左岸，有一條船，大小正好能裝下這個(gè)人和其它3件東西中的一件。人和他的隨行物都要過(guò)到河的右岸。人每次只能將一件東西擺渡過(guò)河。但若人將狼和羊留在同一岸而無(wú)人照顧的話，狼將把羊吃掉，類似的，羊也可能會(huì)吃掉白菜。請(qǐng)問(wèn)是否有可能擺渡過(guò)河，并使得羊和白菜都不會(huì)被吃掉？,2020年7月28日,14,分析：人和物

8、件在左右岸的組合構(gòu)成問(wèn)題的所有狀態(tài)。狀態(tài)表示：左岸組合，右岸組合，令M = 人，W= 狼，G = 山羊，C = 白菜,則所有狀態(tài)為： C(4,0): M,W,G,C, ; ,M,W,G,C ; C(4,1): W,G,C,M; M,G,C,W; M,W,C,G ; M,W,G,C; M, W,G,C; W,M,G,C; G , M,W,C; C , M,W,G; C(4,2): M,G,W,C ; M, C,W,G ; M,W,G,C ; W,G,M,C ; W,C, M,G; G,C, M,W; 去除不安全狀態(tài)，剩下10有用狀態(tài)，畫出狀態(tài)圖。 問(wèn)題：如何編程求出所有狀態(tài)？ 問(wèn)題等價(jià)于求集合的

9、冪集,2020年7月28日,15,由狀態(tài)圖可知有兩種渡河方案,2020年7月28日,16,2020年7月28日,3.4 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),（1）根據(jù)詞法規(guī)則寫出正則文法； （2）將正則文法轉(zhuǎn)換成狀態(tài)圖； （3）將狀態(tài)圖轉(zhuǎn)換成流程圖。,17,2020年7月28日,標(biāo)識(shí)符:由字母打頭的字母數(shù)字組合 關(guān)鍵字：標(biāo)識(shí)符的子集 無(wú)符號(hào)整數(shù)：任意數(shù)字組合 運(yùn)算符： +、*、= 分界符：,、;,例：假設(shè)某語(yǔ)言的單詞符號(hào)的子集有：,構(gòu)造此語(yǔ)言子集的詞法分析程序。,18,2020年7月28日,（1）根據(jù)詞法規(guī)則寫出正則文法,| | + | * | 0|1|2|3|4|5|6|7|8|9 a|b|c|z|A

10、|B|C|Z,19,標(biāo)識(shí)符:由字母打頭的字母數(shù)字組合 關(guān)鍵字：標(biāo)識(shí)符的子集 無(wú)符號(hào)整數(shù)：任意數(shù)字組合 運(yùn)算符： +、*、= 分界符：,、;,2020年7月28日,20,| | | + | * | 0|1|2|3|4|5|6|7|8|9 a|b|c|z|A|B|C|Z, a|b|c|z|A|B|C|Z|a|z |A|Z|0|9 0|1|2|3|4|5|6|7|8|9| 0|9 + | * | =,2020年7月28日,（2）將正則文法轉(zhuǎn)換成狀態(tài)圖,21, a|b|c|z|A|B|C|Z| a|z |A|Z|0|9 0|1|2|3|4|5|6|7|8|9| 0|9 + | * | =,2020年7

11、月28日,合并 將初始狀態(tài)合并為一個(gè)唯一的初態(tài)； 化簡(jiǎn)調(diào)整狀態(tài)沖突并對(duì)沖突狀態(tài)重新編號(hào)； 如有必要，增加出錯(cuò)狀態(tài)。,22,2020年7月28日,（3）將狀態(tài)圖轉(zhuǎn)換成流程圖,寫出詞法分析程序,23,含有分支或回路的狀態(tài)示意 (a) 含分支的狀態(tài)i； (b) 含回路的狀態(tài)i,2020年7月28日,24,2020年7月28日,不含回路的分支狀態(tài)可對(duì)應(yīng)一個(gè)switch( )語(yǔ)句或一組if-else語(yǔ)句。例如，上圖(a)的狀態(tài)i所對(duì)應(yīng)的switch語(yǔ)句如下：,s=getchar ( ); switch (s) case a: case b: case z: ; /*實(shí)現(xiàn)狀態(tài)j功能的語(yǔ)句*/ case 0: case 1: