1、第三章 詞法分析詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源源程程序序機(jī)器代碼機(jī)器代碼編譯的步驟2Zhou, ErqiangSchool of Information and Software Engineering詞法分析概述詞法分析功能詞法分析功能 掃描源程序掃描源程序 識(shí)別單詞符號(hào)識(shí)別單詞符號(hào) 發(fā)現(xiàn)發(fā)現(xiàn)詞法錯(cuò)誤、詞法錯(cuò)誤、輸出錯(cuò)誤信息輸出錯(cuò)誤信息3Zhou, ErqiangSchool of Information and Software Engineering詞法分析舉例while

2、(ip z)while (ip z) +ip; +ip;while(ipz)nt+ip;T_WhileT_IdentT_IdentT_Ident()+ipzip4Zhou, ErqiangSchool of Information and Software Engineeringwhile (ip z)while (ip z) +ip; +ip;while(ipz)nt+ip;T_WhileT_IdentT_IdentT_Ident()+ipzipipT_IdentzT_IdentipT_Ident+While5Zhou, ErqiangSchool of Information and So

3、ftware Engineeringdo for = new 0;do for = new 0;dofor =new 0;T_DoT_ForT_NewT_IntConst=0詞法分析舉例6Zhou, ErqiangSchool of Information and Software Engineeringwhile(137i)n t+i;whileT_While源程序中的源程序中的單詞符號(hào)單詞符號(hào)詞法記號(hào)（詞法記號(hào)（Token） 表示源程序中的一個(gè)表示源程序中的一個(gè)獨(dú)立單位獨(dú)立單位詞法分析舉例7Zhou, ErqiangSchool of Information and Software En

4、gineeringwhile(137i)n t+i;whileT_While是否需要記錄？是否需要記錄？ 無(wú)實(shí)際含義的單詞符號(hào)無(wú)實(shí)際含義的單詞符號(hào) 不用記錄不用記錄詞法分析舉例8Zhou, ErqiangSchool of Information and Software Engineeringwhile(137i)n t+i;whileT_While(137T_IntConst137有些詞法記號(hào)會(huì)有有些詞法記號(hào)會(huì)有屬性屬性本例中屬性為本例中屬性為整數(shù)的值整數(shù)的值屬性信息需要記錄屬性信息需要記錄詞法分析舉例9Zhou, ErqiangSchool of Information and Soft

5、ware Engineering（1 1）詞法分析作為單獨(dú)的一遍）詞法分析作為單獨(dú)的一遍語(yǔ)法分析器語(yǔ)法分析器詞法分析器詞法分析器輸入串輸入串單詞流單詞流符號(hào)表符號(hào)表詞法分析器和語(yǔ)法分析器的關(guān)系10Zhou, ErqiangSchool of Information and Software Engineering（2 2）詞法分析作為子程序）詞法分析作為子程序詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器符號(hào)表符號(hào)表輸入串輸入串取下一單詞取下一單詞返回一個(gè)單詞返回一個(gè)單詞詞法分析器和語(yǔ)法分析器的關(guān)系11Zhou, ErqiangSchool of Information and Software E

6、ngineering1. 1. 單詞的種類單詞的種類 (1)(1)標(biāo)識(shí)符標(biāo)識(shí)符: :變量、函數(shù)、過(guò)程、標(biāo)號(hào)等變量、函數(shù)、過(guò)程、標(biāo)號(hào)等 (2)(2)基本字基本字( (關(guān)鍵字關(guān)鍵字): ): 如如ifif、whilewhile等等 (3)(3)常數(shù)常數(shù): :各種類型的常數(shù)各種類型的常數(shù) (4)(4)運(yùn)算符運(yùn)算符: :如如+ +、- -、* *、/ /等等 (5)(5)界符界符: :如如 ; ; : : 等等單詞符號(hào)的類別12Zhou, ErqiangSchool of Information and Software Engineering 二元式二元式 ( (單詞類別，單詞屬性單詞類別，單詞屬性

7、) )區(qū)分單詞所屬的類區(qū)分單詞所屬的類( (整數(shù)編碼整數(shù)編碼) ) 單詞的屬性值單詞的屬性值詞法分析器的輸出形式T_IntConst13713Zhou, ErqiangSchool of Information and Software Engineering單詞的編碼單詞的編碼 基本字、運(yùn)算符、界符基本字、運(yùn)算符、界符一字一碼一字一碼 標(biāo)識(shí)符統(tǒng)一用標(biāo)識(shí)符統(tǒng)一用一個(gè)一個(gè)編碼編碼 常數(shù)常數(shù)一種類型一種類型對(duì)應(yīng)對(duì)應(yīng)一個(gè)編碼一個(gè)編碼詞法分析器的輸出形式14Zhou, ErqiangSchool of Information and Software Engineering單詞的屬性單詞的屬性 基本字

8、、運(yùn)算符、界符：基本字、運(yùn)算符、界符：可省可省 標(biāo)識(shí)符：在標(biāo)識(shí)符：在符號(hào)表符號(hào)表中的位置中的位置 常數(shù)：常數(shù)： 在在常數(shù)表常數(shù)表中的位置中的位置詞法分析器的輸出形式15Zhou, ErqiangSchool of Information and Software Engineering語(yǔ)句語(yǔ)句“A := B50 + 10;”的詞法輸出形式的詞法輸出形式 ( (標(biāo)識(shí)符的編碼，標(biāo)識(shí)符的編碼，A A在符號(hào)表中的位置在符號(hào)表中的位置) (:= (:=的編碼，的編碼，0 0） ( (標(biāo)識(shí)符的編碼標(biāo)識(shí)符的編碼，B50B50在符號(hào)表中的位置在符號(hào)表中的位置) ( (的編碼，的編碼，0 0) ( (整數(shù)常量的

9、編碼整數(shù)常量的編碼，1010在常量表的位置在常量表的位置 ) (; (;的編碼，的編碼，0 0)詞法分析器的輸出形式16Zhou, ErqiangSchool of Information and Software Engineering詞法分析的難點(diǎn)C+C+中的嵌套的模板聲明中的嵌套的模板聲明 vector vector myVector vector vector myVectorPL/1PL/1中關(guān)鍵字可被用作標(biāo)識(shí)符中關(guān)鍵字可被用作標(biāo)識(shí)符 IF THEN THEN THEN = ELSE; ELSE ELSE = IF IF THEN THEN THEN = ELSE; ELSE ELS

10、E = IF 17Zhou, ErqiangSchool of Information and Software Engineering如何識(shí)別給定語(yǔ)言的詞法符號(hào)？如何識(shí)別給定語(yǔ)言的詞法符號(hào)？ 標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符等標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符等根據(jù)語(yǔ)言的根據(jù)語(yǔ)言的詞法規(guī)則詞法規(guī)則 文法文法 轉(zhuǎn)換圖轉(zhuǎn)換圖/ /語(yǔ)法圖語(yǔ)法圖 （有限自動(dòng)機(jī)）（有限自動(dòng)機(jī)）思考18Zhou, ErqiangSchool of Information and Software Engineering獲取單詞符號(hào)獲取單詞符號(hào) 1 1）標(biāo)識(shí)符）標(biāo)識(shí)符 2 2）關(guān)鍵字：）關(guān)鍵字：beginbegin、endend、in

11、tegerinteger、ifif、 then then、elseelse、functionfunction、readread、writewrite 3 3）整型常量整型常量 4 4）- -、* *、 、=、= =、 、=、:=:= 5 5）；、（、）；、（、）詞法分析器的設(shè)計(jì)19Zhou, ErqiangSchool of Information and Software Engineering單詞符號(hào)編碼單詞符號(hào)編碼 參參p. p. xxxxxx 表表3-23-2詞法分析器的設(shè)計(jì)20Zhou, ErqiangSchool of Information and Software Engine

12、ering特定語(yǔ)言手動(dòng)編碼方式特定語(yǔ)言手動(dòng)編碼方式 手動(dòng)手動(dòng)實(shí)現(xiàn)實(shí)現(xiàn)識(shí)別單詞符號(hào)的有限自動(dòng)機(jī)識(shí)別單詞符號(hào)的有限自動(dòng)機(jī) 參參p. p. xxxxxx 圖圖3-43-4正則表達(dá)式方式正則表達(dá)式方式 自動(dòng)自動(dòng)將正則表達(dá)式轉(zhuǎn)化為有限自動(dòng)機(jī)將正則表達(dá)式轉(zhuǎn)化為有限自動(dòng)機(jī)詞法分析器的設(shè)計(jì)21Zhou, ErqiangSchool of Information and Software Engineering手動(dòng)編碼方式手動(dòng)編碼方式 詞法分析器的實(shí)現(xiàn)22Zhou, ErqiangSchool of Information and Software Engineeringdefdef tokenise(): t

13、okenise():symbolList = symbolList = whilewhile notnot eof(): eof():# process next chars until end of symbol# process next chars until end of symbol# add symbol to symbolList# add symbol to symbolList. . . . .returnreturn symbolList symbolListsource codenextc 為當(dāng)前指針?biāo)傅淖址麨楫?dāng)前指針?biāo)傅淖址?即下一個(gè)要處理的字符即下一個(gè)要處理的字符

14、getc() 返回當(dāng)前指針?biāo)缸址祷禺?dāng)前指針?biāo)缸址?將指針移動(dòng)到下一字符將指針移動(dòng)到下一字符手動(dòng)編碼方式手動(dòng)編碼方式 詞法分析器的實(shí)現(xiàn)23Zhou, ErqiangSchool of Information and Software Engineeringdef tokenise():def tokenise():symbolList = symbolList = while not eof():while not eof():. . . . .return symbolListreturn symbolListswitchswitch ( type(nextc): ( type(next

15、c):casecase WHITESPACE: WHITESPACE:.casecase ALPHABET: ALPHABET:.casecase DIGIT: DIGIT:.etc.etc.def type (char):if char in “a-zA-z_”:return ALPHABET;ALPHABET;if char in “0-9”:return DIGIT;DIGIT;if char in “ tn”:return WHITESPACEWHITESPACEif char in “;,”:return SEPCHAR;SEPCHAR;if char in “ + - * * /

16、/symbol = “” + getc()symbol = “” + getc()if nextc = =:if nextc = =: symbol += getc() symbol += getc()symbolList.append(symbol)symbolList.append(symbol)casecase SEPCHAR: SEPCHAR: # ; :# ; :symbol = “” + getc()symbol = “” + getc()symbolList.append(symbol)symbolList.append(symbol)defaultdefault: print

17、“ERROR: Unknown Char: ”+getc(): print “ERROR: Unknown Char: ”+getc()switchswitch ( type(nextc): ( type(nextc):casecase WHITESPACE: WHITESPACE:.casecase ALPHABET: ALPHABET:.casecase DIGIT: DIGIT:.etc.etc.詞法分析器的實(shí)現(xiàn)LexAnalyze()LexAnalyze()實(shí)現(xiàn)為一個(gè)函數(shù)實(shí)現(xiàn)為一個(gè)函數(shù)LexAnalyze()LexAnalyze()每執(zhí)行一次每執(zhí)行一次 識(shí)別出一個(gè)單詞符號(hào)識(shí)別出一個(gè)單詞

18、符號(hào) 返回相應(yīng)的二元式返回相應(yīng)的二元式LexAnalyze()LexAnalyze()的兩種的兩種使用使用方法方法 獨(dú)立使用獨(dú)立使用 作為語(yǔ)法分析的子程序使用作為語(yǔ)法分析的子程序使用28Zhou, ErqiangSchool of Information and Software Engineering特定語(yǔ)言手動(dòng)編碼方式特定語(yǔ)言手動(dòng)編碼方式 手動(dòng)實(shí)現(xiàn)識(shí)別單詞符號(hào)的有限自動(dòng)機(jī)手動(dòng)實(shí)現(xiàn)識(shí)別單詞符號(hào)的有限自動(dòng)機(jī) 參參p. 190 p. 190 圖圖8-58-5正則表達(dá)式方式正則表達(dá)式方式( (掌握掌握) ) 自動(dòng)自動(dòng)將正則表達(dá)式轉(zhuǎn)化為有限自動(dòng)機(jī)將正則表達(dá)式轉(zhuǎn)化為有限自動(dòng)機(jī)詞法分析器的設(shè)計(jì)29Zho

19、u, ErqiangSchool of Information and Software Engineering正則表達(dá)式正則表達(dá)式 一種用來(lái)描述字符串集合的工具一種用來(lái)描述字符串集合的工具字母表字母表 一個(gè)有限的符號(hào)集合一個(gè)有限的符號(hào)集合 集合集合0, 1是二進(jìn)制字母表是二進(jìn)制字母表字母表上的一個(gè)字母表上的一個(gè)“串串”或或“句子句子” 字母表中符號(hào)的一個(gè)有窮序列字母表中符號(hào)的一個(gè)有窮序列 串串s s的長(zhǎng)度，記作的長(zhǎng)度，記作 |s| |s|，指，指s s中符號(hào)出現(xiàn)的次數(shù)中符號(hào)出現(xiàn)的次數(shù) 空串是長(zhǎng)度為空串是長(zhǎng)度為0 0的串，用的串，用表示表示詞法分析器的實(shí)現(xiàn)30Zhou, ErqiangScho

20、ol of Information and Software Engineering語(yǔ)言語(yǔ)言 給定字母表上一個(gè)任意的可數(shù)的串集合給定字母表上一個(gè)任意的可數(shù)的串集合正則表達(dá)式的遞歸定義正則表達(dá)式的遞歸定義 1 1） 是一個(gè)正則表達(dá)式是一個(gè)正則表達(dá)式 L() = ，即該語(yǔ)言只包含空串。，即該語(yǔ)言只包含空串。 2 2）如果）如果 a 是字母表是字母表上的一個(gè)符號(hào)上的一個(gè)符號(hào) 那么那么 a 是一個(gè)正則表達(dá)式，并且是一個(gè)正則表達(dá)式，并且L(a) = aR、R1、R2是正則表達(dá)式是正則表達(dá)式 R1R2 、 R1 | R2 、 R* 、（、（R）是正則表達(dá)式是正則表達(dá)式詞法分析器的實(shí)現(xiàn)31Zhou, Erq

21、iangSchool of Information and Software Engineering正則表達(dá)式正則表達(dá)式的例子的例子 (0|1)* 00 (0|1)* 所有包含所有包含0000的由的由0 0、1 1組成的串組成的串(0|1)(0|1)(0|1)(0|1) 0000、1010、1111、1000、.(0|1)4詞法分析器的實(shí)現(xiàn)32Zhou, ErqiangSchool of Information and Software Engineering正則表達(dá)式正則表達(dá)式的例子的例子 = a, b a|b a, b(a|b)(a|b) aa, ab, ba, bbaa|ab|ba|bb

22、 aa, ab, ba, bb a* 由字母由字母a a構(gòu)成的所有串集構(gòu)成的所有串集(a|b)* 由由a a和和b b構(gòu)成的所有串集構(gòu)成的所有串集詞法分析器的實(shí)現(xiàn)33Zhou, ErqiangSchool of Information and Software Engineering正則表達(dá)式方式正則表達(dá)式方式( (掌握掌握) ) 詞法規(guī)則：用正則表達(dá)式描述詞法規(guī)則：用正則表達(dá)式描述 程序讀入詞法規(guī)則程序讀入詞法規(guī)則 自動(dòng)生成對(duì)應(yīng)的處理程序自動(dòng)生成對(duì)應(yīng)的處理程序 flex flex 詞法分析器的實(shí)現(xiàn)34Zhou, ErqiangSchool of Information and Softwar

23、e EngineeringFlexFlex的規(guī)則舉例的規(guī)則舉例( (掌握掌握) )DIGIT 0-9DIGIT 0-9ID a-za-z0-9ID a-za-z0-9* *DIGIT+ DIGIT+ printf( “ (integer, %s) , yytext); printf( “ (integer, %s) , yytext); DIGIT+.DIGITDIGIT+.DIGIT* * printf( “(float, %s), yytext); printf( “(float, %s), yytext); 詞法分析器的實(shí)現(xiàn)35Zhou, ErqiangSchool of Informa

24、tion and Software Engineering有限自動(dòng)機(jī)有限自動(dòng)機(jī) 確定的有限自動(dòng)機(jī)（確定的有限自動(dòng)機(jī)（DFAsDFAs） 非確定的有限自動(dòng)機(jī)（非確定的有限自動(dòng)機(jī)（NFAsNFAs）正則表達(dá)式的實(shí)現(xiàn)36Zhou, ErqiangSchool of Information and Software Engineering有限自動(dòng)機(jī)開始開始A,B,C,ZA,B,C,Z有限的有向圖有限的有向圖初態(tài)唯一初態(tài)唯一有向邊上標(biāo)記字符，表示狀態(tài)轉(zhuǎn)換有向邊上標(biāo)記字符，表示狀態(tài)轉(zhuǎn)換若干終態(tài)（至少一個(gè)）若干終態(tài)（至少一個(gè)）37Zhou, ErqiangSchool of Information and

25、Software Engineering有限自動(dòng)機(jī)開始開始A,B,C,Z H E Y A 以一個(gè)字符串作為輸入以一個(gè)字符串作為輸入決定接受或者拒絕該串決定接受或者拒絕該串38Zhou, ErqiangSchool of Information and Software Engineering有限自動(dòng)機(jī)開始開始A,B,C,Z H E Y A 39Zhou, ErqiangSchool of Information and Software Engineering有限自動(dòng)機(jī)開始開始A,B,C,Z H E 沒(méi)有相應(yīng)的沒(méi)有相應(yīng)的轉(zhuǎn)換，轉(zhuǎn)換，停機(jī)停機(jī)拒絕輸入串拒絕輸入串40Zhou, ErqiangSchool of Information and Software Engineering有限自動(dòng)機(jī)開始開始A,B,C,Z H E Y A A不是接受狀態(tài)不是接受狀態(tài)拒絕輸入串拒絕輸入串41Zhou, ErqiangSchool of Information and Software Engineeri