1、編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表 格 管 理出 錯(cuò) 處 理中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器源程序例 一個(gè)語句的翻譯參見第8頁圖1-10第三章 詞法分析School of Computer Science & Technology Harbin Institute of Technology重點(diǎn)：詞法分析器的輸入、輸出， 用于識(shí)別符號(hào)的狀態(tài)轉(zhuǎn)移圖的構(gòu)造， 根據(jù)狀態(tài)轉(zhuǎn)移圖實(shí)現(xiàn)詞法分析器。 難點(diǎn)：詞法的正規(guī)文法表示、正規(guī)表達(dá)式表示、 狀態(tài)轉(zhuǎn)移圖表示，它們之間的轉(zhuǎn)換。 本章主要內(nèi)容3.1 詞法分析器(Scanner)的功能3.2 單詞的種類

2、和詞法分析器的輸出形式3.3 相關(guān)問題3.4 正規(guī)表達(dá)式3.5 狀態(tài)轉(zhuǎn)換圖3.6 詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)3.1 詞法分析（掃描）器的功能功能：輸入源程序，輸出單詞符號(hào)(token)。即：把構(gòu)成源程序的字符串轉(zhuǎn)換成單詞符號(hào)的序列根據(jù)詞法規(guī)則識(shí)別及組合單詞，進(jìn)行詞法檢查對(duì)數(shù)字常數(shù)完成數(shù)字字符串到二進(jìn)制數(shù)值的轉(zhuǎn)換刪去空格字符和注釋3.2 單詞的種類和詞法分析程序的輸出形式一、單詞的種類 1. 關(guān)鍵字：begin、end、for、do.2. 標(biāo)識(shí)符：由用戶定義，表示各種名字3. 常 數(shù)：無符號(hào)數(shù)、布爾常數(shù)、字符串常數(shù)等4.運(yùn)算符：算術(shù)運(yùn)算符、邏輯運(yùn)算符、關(guān)系運(yùn)算符5. 分界符：逗號(hào)、分號(hào)、括號(hào)等二、詞

3、法分析程序的輸出形式-單詞的內(nèi)部形式幾種常用的單詞內(nèi)部形式：1、按單詞種類分類2、保留字和分界符采用一符一類3、標(biāo)識(shí)符和常數(shù)的單詞值又為指示字（指針值）單詞類別 屬性值表示單詞的種類，可用整數(shù)編碼或記憶符表示不同的單詞不同的值單詞名稱標(biāo)識(shí)符無符號(hào)常數(shù)無符號(hào)浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值內(nèi)部字符串整數(shù)值數(shù)值0 或 1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼1、按單詞種類分類2、保留字和分界符采用一符一類單詞名稱標(biāo)識(shí)符無符號(hào)常數(shù)(整)無符號(hào)浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)BEGINENDFORDO:+*,(類別編碼12345678920212223單詞值內(nèi)部字符串整數(shù)值

4、數(shù)值0 或 1內(nèi)部字符串-例 3-1: 單詞符號(hào)序列while(*pointer!=0)pointer+; while (WHILE， _ )( (SLP， _ )* (FETCH， _ )pointer (IDN， 符號(hào)表入口指針)!= (RELOP， NE )0 (CONST， 0 )(SRP， _ ) (LP， _ )pointer (IDN， 符號(hào)表入口指針)+ (INC， _ ); (SEMI， _ ) (RP， _ ) 跟實(shí)現(xiàn)有關(guān)3.3 相關(guān)問題超前掃描雙字符運(yùn)算符（*, /*,:=,）DO 90 k=1,10DO 90 k=1.10 預(yù)處理問題剔除源程序中的無用符號(hào)、空格、換行、

5、注釋等1.詞法分析單獨(dú)作為一遍2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析S.P.(符號(hào)串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn): 結(jié)構(gòu)清晰、 各遍功能單一缺點(diǎn)：效率低S.P.(字符串)詞法分析程序語法分析程序取單詞單詞優(yōu)點(diǎn): 效率高3.3 相關(guān)問題-掃描器的運(yùn)行方式3.3 相關(guān)問題符號(hào)表的查填兼顧問題兼顧：token自身值作為符號(hào)表的入口Token串長(zhǎng)度統(tǒng)一，可放寬對(duì)標(biāo)識(shí)符的限制，但要增加額外負(fù)擔(dān)不兼顧： token自身值就是標(biāo)識(shí)符、常數(shù)本身的符號(hào)串速度快，但要限制標(biāo)識(shí)符的長(zhǎng)度詞法錯(cuò)誤的檢測(cè)行、列計(jì)數(shù)發(fā)現(xiàn)并定位詞法錯(cuò)誤一種符號(hào)表的數(shù)據(jù)結(jié)構(gòu)3.3 相關(guān)問題工作區(qū)(token)單詞開始指

6、針掃描指針正拼單詞輸入緩沖區(qū)每次移動(dòng)向前指針都需要做兩次測(cè)試3.3 相關(guān)問題雙緩沖區(qū)問題_超前掃描導(dǎo)致的效率問題？如何設(shè)計(jì)和實(shí)現(xiàn)掃描器大小問題128Byte*2|1024Byte*2|4096Byte*2if forward在緩沖區(qū)第一部分末尾 then begin重裝緩沖區(qū)第二部分;forward := forward +1endelse if forward在緩沖區(qū)第二部分末尾 then begin 重裝緩沖區(qū)第一部分; 將forward移到緩沖區(qū)第一部分開始endelse forward:= forward +1; forward := forward + 1;if forward= e

7、of then beginif forward在第一部分末尾 then begin 重裝第二部分; forward := forward +1endelse if forward在第二部分末尾 then begin 重裝第一部分; 將forward 移到第一部分開始endelse /* eof 在表示輸入結(jié)束 */ 終止詞法分析end 3.4 記號(hào)的描述_正規(guī)(表達(dá))式例：標(biāo)識(shí)符的文法描述約定：用digit表示數(shù)字：0,1,2,9; 用letter表示字母：A,B,Z,a,b,zG =(digit,letter, S, P, S)Sletter Lletter|letter TSS digit

8、TLetter T|letterSS letterTdigit T|digit左線性右線性表示集合：letterletter,digit* 1) 正規(guī)式：正規(guī)語言的另一種描述方法例3-2：標(biāo)識(shí)符的另一種表示letter(letter|digit)* | 表示或 * 表示Kleene閉包Letter和(letter|digit)*的并列表示兩者的連接正規(guī)式 r 表示正規(guī)集,相應(yīng)的正規(guī)集記為 L(r) 正規(guī)(表達(dá))式(Regular ExpressionRE)設(shè)是一個(gè)字母表， 是上的RE，L()=； 是上的RE，L()=； 對(duì)于a，a是RE，L(a)=a；如果r和s是RE，L(r)=R,L(s)=

9、S，則：r與s的“和” (r|s)是RE，L(r|s)=RS；r與s的“乘積” (rs)是RE，L(rs)=RS；r的克林閉包(r*)是RE，L(r*)=R*。 只有滿足、的才是RE。 運(yùn)算的優(yōu)先級(jí)運(yùn)算優(yōu)先級(jí)和結(jié)合性:*高于“連接” 和| ， “連接” 高于 |具有交換律、結(jié)合律“連接” 具有結(jié)合律、和對(duì)|的分配律( )指定優(yōu)先關(guān)系意義清楚時(shí)，括號(hào)可以省略例：L(a(a|b)*(|(.|_)(a|b)(a|b)*)aa,b*(.,_a,ba,b* )2) 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式等價(jià)對(duì)任何正規(guī)文法，存在定義同一語言的正規(guī)式對(duì)任何正規(guī)式，存在生成同一語言的正規(guī)文法例 3-3 標(biāo)識(shí)符定義的

10、轉(zhuǎn)換引入 S Sletter (letter|digit)*引入A消除閉包 Sletter A A(letter|digit)A|執(zhí)行連接對(duì)|的分配律 Sletter A Aletter A|digit A| 例3-4正規(guī)式到正規(guī)文法的轉(zhuǎn)換a(a|b)*(|(.|_)(a|b)(a|b)*)= a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*)=aA|aCA=aA|bA| C=aC|bC|.B|_BB=aA|bASaA|aC AaA|bA| CaC|bC|.B|_BBaA|bA正規(guī)式到正規(guī)文法的轉(zhuǎn)換按如下方法構(gòu)造正規(guī)定義式

11、，并逐步將其轉(zhuǎn)換成正則文法引入開始符號(hào)S，從如下正規(guī)定義式開始Sr對(duì)r中的形如r1|r2|rn的子串用產(chǎn)生式組A r1|r2|rn 表示正規(guī)式到正規(guī)文法的轉(zhuǎn)換對(duì)r中的形如r1*的子串用產(chǎn)生式組 A|r1A 表示對(duì)r中的形如r1+的子式子，用產(chǎn)生式組 A r1| r1A 表示執(zhí)行連接對(duì)|的分配律正規(guī)式到正規(guī)文法的轉(zhuǎn)換用到了正規(guī)定義式的概念。正規(guī)文法到正規(guī)式的轉(zhuǎn)換代入：對(duì)于 AxB, By，構(gòu)造 Axy遞歸：對(duì)于 AxA|y，構(gòu)造 Ax*y多候選式：對(duì)于 Ax，Ay，構(gòu)造Ax|yS0A A1B B2B|2C C3C|3S01B S012*2C S012*23*3=012+3+ 一個(gè)語言的文法描述不

12、是唯一的（文法的等價(jià)）3) 高級(jí)語言詞法的簡(jiǎn)單描述詞法單詞符號(hào)的文法，用來描述高級(jí)語言中的：標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分界符、關(guān)鍵字參考教材P6466，了解如何定義高級(jí)語言中的整數(shù)、實(shí)數(shù)等的相應(yīng)正則文法。例 3-5：某簡(jiǎn)易語言的詞法正規(guī)定義式 詞法規(guī)則 單詞種別 屬性(|)* IDN 符號(hào)表入口 ()* NUM 數(shù)值 := ASG 無 其它單詞字符本身 單詞名稱 無 變換為正規(guī)文法letter|letter|digitdigit | digit :=+=(其它：實(shí)數(shù)、算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、分號(hào)、括號(hào)等）問題：如何識(shí)別記號(hào)？3.5 記號(hào)的識(shí)別狀態(tài)轉(zhuǎn)換圖1 狀態(tài)轉(zhuǎn)換圖（有窮自動(dòng)機(jī) FA M=(Q，q

13、0，F(xiàn)) ）用來描述詞法分析器識(shí)別記號(hào)時(shí)要做的動(dòng)作結(jié)點(diǎn)：狀態(tài)用表示；終態(tài)用表示 有向弧 箭頭 弧標(biāo)記 輸入字符標(biāo)識(shí)符的狀態(tài)圖(|)* 123letterletter,digit其它開始終態(tài)初態(tài)例3-5的狀態(tài)圖letter,digitletter（IDN，入口）digitdigit(其它) (其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDNletter(letter|digit)*NUMdigit(digit)*ASG:=INC+利用狀態(tài)轉(zhuǎn)換圖識(shí)別單詞1. 從初態(tài)出發(fā)2. 讀入一字符3. 按當(dāng)前字符轉(zhuǎn)入下一狀態(tài)4. 重復(fù) 2,3 直到無法繼續(xù)轉(zhuǎn)移#. 在遇到讀入

14、的字符是Token的分割符時(shí)，若當(dāng)前狀態(tài)是終止?fàn)顟B(tài)，說明讀入的字符組成一單詞；否則，說明輸入不符合詞法規(guī)則。2、從正規(guī)文法出發(fā)，構(gòu)造狀態(tài)圖1.以每個(gè)非終結(jié)符為狀態(tài)結(jié)點(diǎn)，開始符號(hào)對(duì)應(yīng)初態(tài) S；2.增設(shè)一個(gè)終態(tài) T；3.對(duì)于規(guī)則 AaB，畫從狀態(tài) A 到 B 的弧，標(biāo)為 a；4.對(duì)于規(guī)則 Aa，畫從狀態(tài) A 到終態(tài) T 的弧，標(biāo)為 a。* 對(duì)于規(guī)則 Ars*，畫從狀態(tài) A 到狀態(tài) N 的弧，標(biāo)為 r和狀態(tài)N到N的標(biāo)記為s的弧AsrABaAa例 3-6 語言無符號(hào)整數(shù)的識(shí)別1、正規(guī)定義式描述八進(jìn)制數(shù): ( OCT，值 )oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十

15、進(jìn)制數(shù): ( DEC，值 )dec(1|.|9)(0|.|9)* |0十六進(jìn)制數(shù): ( HEX，值 )hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f |A|F)*2、識(shí)別不同進(jìn)制數(shù)的狀態(tài)圖342100-70-7(其它)56101-90-9 (其它)十進(jìn)制整數(shù)八進(jìn)制整數(shù)oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec(1|.|9)(0|.|9)* |02、識(shí)別不同進(jìn)制數(shù)的狀態(tài)圖910810 (其它)十六進(jìn)制整數(shù)7x0-9,a-f0-9,a-f狀態(tài)圖合并1、從開始狀態(tài)出發(fā)；2、選擇輸入符號(hào)，構(gòu)成目標(biāo)狀態(tài)集3、從新狀態(tài)集出發(fā)，重復(fù)1、2

16、hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f |A|F)*（HEX，值）（OCT，值）3、語言無符號(hào)整數(shù)識(shí)別的狀態(tài)圖9,10810其他2,6,7x0-9 ,a-f0-9,a-f 3,40-70-7其他51-90-9其他（DEC，值）其他3.6 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移圖教材P68狀態(tài)轉(zhuǎn)移圖的實(shí)現(xiàn)教材P68-72子程序 scan( )輸入：字符流輸出：Symbol:單詞種別Attr:屬性（全局變量）數(shù)據(jù)結(jié)構(gòu)與子例程數(shù)據(jù)結(jié)構(gòu)ch 當(dāng)前輸入字符token 輸入緩沖區(qū)(字符數(shù)組)symbol 單詞種別（子程序的返回值）attr 屬性（全局變量）子例程Lookup(

17、token):將 token 存入符號(hào)表，返回入口指針isKeyword(token):判別 token是關(guān)鍵字？返回關(guān)鍵字種別或 -1getchar():從輸入緩沖區(qū)中讀入一個(gè)字符放入chisLetter() isalpha() 例3-3的狀態(tài)圖的實(shí)現(xiàn)算法1. getchar()2. WHILE ch 是空格/跳過空格2.1 DO getchar();3. CASE ch OF4. isdigit(ch) :4.1 chtoken; getchar();4.2 WHILE isdigit(ch) DO chtoken; getchar();4.3 輸入指針回退一個(gè)字符；4.4 將token中

18、的字符串變成數(shù)值attr4.5 返回 NUM5. isalpha(ch) :5.1 chtoken; getchar();5.2 WHILE isalpha(ch) OR isdigit(ch) DO chtoken; getchar();5.3輸入指針回退一個(gè)字符;5.4 key = isKeyword(token);5.5 IF key0 THEN 返回 key5.6 Lookup(token)attr;5.7 返回 IDN6 : : getchar(); 6.1 IF ch等于= THEN 返回 ASG6.2 出錯(cuò)處理7 + : 返回 ADD8 - : 返回 SUB9 * : 返回 MU

19、L10 / : 返回 DIV11 = : 返回 EQ12 : 返回 GT13 : 返回 LT14 ( : 返回 LP15 ) : 返回 RP16 ; : 返回 SEMI17 其它 : 出錯(cuò)處理18 END OF CASE需要說明的問題緩沖區(qū)預(yù)處理，超前搜索關(guān)鍵字的處理，符號(hào)表的實(shí)現(xiàn)Lookup：查找效率，算法的優(yōu)化實(shí)現(xiàn)詞法錯(cuò)誤處理由于高級(jí)語言的詞組成的集合為3型語言，所以，這里討論的詞法分析技術(shù)可以用于處理所有的3型語言，也就是所有的可以用3型文法描述的語言。如：信息檢索系統(tǒng)的查詢語言、命令語言等3LEX簡(jiǎn)介：實(shí)現(xiàn)過程Lex源程序Lex.yy.cLex編譯器詞法分析器LLex.yy.cC編譯器

20、Token序列詞法分析器L輸入流LEX簡(jiǎn)介：Lex程序結(jié)構(gòu)聲明部分(正規(guī)定義式)%轉(zhuǎn)換規(guī)則(識(shí)別規(guī)則)%輔助過程%常量定義%正規(guī)定義掃描器的自動(dòng)生成：LEX簡(jiǎn)介1、正規(guī)定義式letterA|B|C|Z|a|b|c|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)* 2、識(shí)別規(guī)則正規(guī)式動(dòng)作描述token1action1token2action2tokennactionn%#include #include #include #define BEGIN 1#define END 2 #define IF 3#define

21、 THEN 4#define ELSE 5#define ID 6#define INT 7#define LT 8#define LE 9#define EQ 10#define NE 11#define GT 12#define GE 13%digit 0-9alpha a-zA-Zalnum a-zA-Z0-9%begin OUT(BEGIN,NULL); end OUT(END,NULL); if OUT(IF,NULL); then OUT(THEN,NULL); else OUT(ELSE,NULL); alphaalnum* OUT(ID,yytext); digit+ OUT(

22、INT,yytext); “” OUT(LT,NULL); “=” OUT(LE,NULL); “=” OUT(EQ,NULL); “” OUT(NE,NULL); “” OUT(GT,NULL); “=” OUT(GE,NULL); %OUT(int c, char *val)LEX二義性問題的兩條原則1.最長(zhǎng)匹配原則 在識(shí)別單詞過程中，有一字符串 x x x x x 根據(jù)最長(zhǎng)匹配原則，應(yīng)識(shí)別為這是 一個(gè)符合Pk規(guī)則的單詞， 而不是Pj和Pi規(guī)則的單詞。PjPiPk2.優(yōu)先匹配原則 如有一字符串，有兩條規(guī)則可以同時(shí)匹配時(shí)，那么用規(guī)則序列中位于前面的規(guī)則相匹配，所以排列在最前面的規(guī)則優(yōu)先權(quán)最高。如:begin:=LEX的功能是根據(jù)LEX源程序構(gòu)造一個(gè)詞法分析程序，該詞法分析器實(shí)質(zhì)上是一個(gè)有窮自動(dòng)機(jī)。LEX生成的詞法分析程