編譯技術(shù)：第03章 詞法分析

1、第三章 詞法分析詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源源程程序序機器代碼機器代碼編譯的步驟2Zhou, ErqiangSchool of Information and Software Engineering詞法分析概述詞法分析功能詞法分析功能 掃描源程序掃描源程序 識別單詞符號識別單詞符號 發(fā)現(xiàn)發(fā)現(xiàn)詞法錯誤、詞法錯誤、輸出錯誤信息輸出錯誤信息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源程序中的源程序中的單詞符號單詞符號詞法記號（詞法記號（Token） 表示源程序中的一個表示源程序中的一個獨立單位獨立單位詞法分析舉例7Zhou, ErqiangSchool of Information and Software En

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

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

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

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

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

9、編碼整數(shù)常量的編碼，1010在常量表的位置在常量表的位置 ) (; (;的編碼，的編碼，0 0)詞法分析器的輸出形式16Zhou, ErqiangSchool of Information and Software Engineering詞法分析的難點C+C+中的嵌套的模板聲明中的嵌套的模板聲明 vector vector myVector vector vector myVectorPL/1PL/1中關(guān)鍵字可被用作標(biāo)識符中關(guān)鍵字可被用作標(biāo)識符 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如何識別給定語言的詞法符號？如何識別給定語言的詞法符號？ 標(biāo)識符、常數(shù)、運算符、界符等標(biāo)識符、常數(shù)、運算符、界符等根據(jù)語言的根據(jù)語言的詞法規(guī)則詞法規(guī)則 文法文法 轉(zhuǎn)換圖轉(zhuǎn)換圖/ /語法圖語法圖 （有限自動機）（有限自動機）思考18Zhou, ErqiangSchool of Information and Software Engineering獲取單詞符號獲取單詞符號 1 1）標(biāo)識符）標(biāo)識符 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è)計19Zhou, ErqiangSchool of Information and Software Engineering單詞符號編碼單詞符號編碼 參參p. p. xxxxxx 表表3-23-2詞法分析器的設(shè)計20Zhou, ErqiangSchool of Information and Software Engine

12、ering特定語言手動編碼方式特定語言手動編碼方式 手動手動實現(xiàn)實現(xiàn)識別單詞符號的有限自動機識別單詞符號的有限自動機 參參p. p. xxxxxx 圖圖3-43-4正則表達(dá)式方式正則表達(dá)式方式 自動自動將正則表達(dá)式轉(zhuǎn)化為有限自動機將正則表達(dá)式轉(zhuǎn)化為有限自動機詞法分析器的設(shè)計21Zhou, ErqiangSchool of Information and Software Engineering手動編碼方式手動編碼方式 詞法分析器的實現(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)傅淖址?即下一個要處理的字符即下一個要處理的字符

14、getc() 返回當(dāng)前指針?biāo)缸址祷禺?dāng)前指針?biāo)缸址?將指針移動到下一字符將指針移動到下一字符手動編碼方式手動編碼方式 詞法分析器的實現(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.詞法分析器的實現(xiàn)LexAnalyze()LexAnalyze()實現(xiàn)為一個函數(shù)實現(xiàn)為一個函數(shù)LexAnalyze()LexAnalyze()每執(zhí)行一次每執(zhí)行一次 識別出一個單詞符號識別出一個單詞

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

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

20、ol of Information and Software Engineering語言語言 給定字母表上一個任意的可數(shù)的串集合給定字母表上一個任意的可數(shù)的串集合正則表達(dá)式的遞歸定義正則表達(dá)式的遞歸定義 1 1） 是一個正則表達(dá)式是一個正則表達(dá)式 L() = ，即該語言只包含空串。，即該語言只包含空串。 2 2）如果）如果 a 是字母表是字母表上的一個符號上的一個符號 那么那么 a 是一個正則表達(dá)式，并且是一個正則表達(dá)式，并且L(a) = aR、R1、R2是正則表達(dá)式是正則表達(dá)式 R1R2 、 R1 | R2 、 R* 、（、（R）是正則表達(dá)式是正則表達(dá)式詞法分析器的實現(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詞法分析器的實現(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)成的所有串集詞法分析器的實現(xiàn)33Zhou, ErqiangSchool of Information and Software Engineering正則表達(dá)式方式正則表達(dá)式方式( (掌握掌握) ) 詞法規(guī)則：用正則表達(dá)式描述詞法規(guī)則：用正則表達(dá)式描述 程序讀入詞法規(guī)則程序讀入詞法規(guī)則 自動生成對應(yīng)的處理程序自動生成對應(yīng)的處理程序 flex flex 詞法分析器的實現(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); 詞法分析器的實現(xiàn)35Zhou, ErqiangSchool of Informa

24、tion and Software Engineering有限自動機有限自動機 確定的有限自動機（確定的有限自動機（DFAsDFAs） 非確定的有限自動機（非確定的有限自動機（NFAsNFAs）正則表達(dá)式的實現(xiàn)36Zhou, ErqiangSchool of Information and Software Engineering有限自動機開始開始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)（至少一個）若干終態(tài)（至少一個）37Zhou, ErqiangSchool of Information and

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