工大編譯原理課件-chapter3詞法分析

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

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

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

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

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

6、針掃描指針正拼單詞輸入緩沖區(qū)每次移動向前指針都需要做兩次測試3.3 相關問題雙緩沖區(qū)問題_超前掃描導致的效率問題？如何設計和實現(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 在表示輸入結束 */ 終止詞法分析end 3.4 記號的描述_正規(guī)(表達)式例：標識符的文法描述約定：用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：標識符的另一種表示letter(letter|digit)* | 表示或 * 表示Kleene閉包Letter和(letter|digit)*的并列表示兩者的連接正規(guī)式 r 表示正規(guī)集,相應的正規(guī)集記為 L(r) 正規(guī)(表達)式(Regular ExpressionRE)設是一個字母表， 是上的RE，L()=； 是上的RE，L()=； 對于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ōu)先級運算優(yōu)先級和結合性:*高于“連接” 和| ， “連接” 高于 |具有交換律、結合律“連接” 具有結合律、和對|的分配律( )指定優(yōu)先關系意義清楚時，括號可以省略例：L(a(a|b)*(|(.|_)(a|b)(a|b)*)aa,b*(.,_a,ba,b* )2) 正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式等價對任何正規(guī)文法，存在定義同一語言的正規(guī)式對任何正規(guī)式，存在生成同一語言的正規(guī)文法例 3-3 標識符定義的

10、轉換引入 S Sletter (letter|digit)*引入A消除閉包 Sletter A A(letter|digit)A|執(zhí)行連接對|的分配律 Sletter A Aletter A|digit A| 例3-4正規(guī)式到正規(guī)文法的轉換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ī)文法的轉換按如下方法構造正規(guī)定義式

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

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

13、0，F(xiàn)) ）用來描述詞法分析器識別記號時要做的動作結點：狀態(tài)用表示；終態(tài)用表示 有向弧 箭頭 弧標記 輸入字符標識符的狀態(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)轉換圖識別單詞1. 從初態(tài)出發(fā)2. 讀入一字符3. 按當前字符轉入下一狀態(tài)4. 重復 2,3 直到無法繼續(xù)轉移#. 在遇到讀入

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

15、進制數(shù): ( DEC，值 )dec(1|.|9)(0|.|9)* |0十六進制數(shù): ( HEX，值 )hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f |A|F)*2、識別不同進制數(shù)的狀態(tài)圖342100-70-7(其它)56101-90-9 (其它)十進制整數(shù)八進制整數(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ù)的狀態(tài)圖910810 (其它)十六進制整數(shù)7x0-9,a-f0-9,a-f狀態(tài)圖合并1、從開始狀態(tài)出發(fā)；2、選擇輸入符號，構成目標狀態(tài)集3、從新狀態(tài)集出發(fā)，重復1、2

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

17、token):將 token 存入符號表，返回入口指針isKeyword(token):判別 token是關鍵字？返回關鍵字種別或 -1getchar():從輸入緩沖區(qū)中讀入一個字符放入chisLetter() isalpha() 例3-3的狀態(tài)圖的實現(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 輸入指針回退一個字符；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輸入指針回退一個字符;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 出錯處理7 + : 返回 ADD8 - : 返回 SUB9 * : 返回 MU

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

20、Token序列詞法分析器L輸入流LEX簡介：Lex程序結構聲明部分(正規(guī)定義式)%轉換規(guī)則(識別規(guī)則)%輔助過程%常量定義%正規(guī)定義掃描器的自動生成：LEX簡介1、正規(guī)定義式letterA|B|C|Z|a|b|c|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)* 2、識別規(guī)則正規(guī)式動作描述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.最長匹配原則 在識別單詞過程中，有一字符串 x x x x x 根據(jù)最長匹配原則，應識別為這是 一個符合Pk規(guī)則的單詞， 而不是Pj和Pi規(guī)則的單詞。PjPiPk2.優(yōu)先匹配原則 如有一字符串，有兩條規(guī)則可以同時匹配時，那么用規(guī)則序列中位于前面的規(guī)則相匹配，所以排列在最前面的規(guī)則優(yōu)先權最高。如:begin:=LEX的功能是根據(jù)LEX源程序構造一個詞法分析程序，該詞法分析器實質上是一個有窮自動機。LEX生成的詞法分析程