工學(xué)第三章詞法分析

工學(xué)第三章詞法分析詞法：描述語言的單詞符號的文法。語言的種類很多，因此需要用不同的詞法來描述他們。例如描述某一語言標(biāo)識符的文法也稱為詞法。3.1詞法分析與詞法分析程序思考：詞法是哪類文法？詞法分析的任務(wù)：對輸入的字符串形式的源程序按順序進行掃描，根據(jù)源程序的詞法規(guī)則識別具有獨立意義的單詞（符號），并產(chǎn)生與其等價的屬性字流作為輸出。詞法分析程序定義：編譯程序中完成詞法分析任務(wù)的程序段，又稱詞法分析器或掃描器（scanner）。

詞法分析程序的功能識別出單詞（內(nèi)部表示）；詞法分析器（scanner）源程序?qū)傩宰至鱈1While(i!=j)doif(i＞j)i＝i-j;//求i,j的差值詞法分析器‘while’，‘(’，‘i’，‘!=’，‘j’，‘)’，‘do’，‘if’，‘(’，‘i’，‘＞’，‘j’,‘)’，'i','=’,'i',’-’,'j',‘;'3.2詞法分析程序設(shè)計與實現(xiàn)詞法分析程序的輸入與輸出源程序的輸入與預(yù)處理單詞的識別詞法分析程序與詞法分析程序的接口詞法分析器的設(shè)計與實現(xiàn)單詞是語言中具有獨立意義的最小語法單位.單詞的種類

1.關(guān)鍵字（保留字）：while、class、for、do2.標(biāo)識符：a、m_a3.常數(shù)：無符號數(shù)、布爾常數(shù)、字符串常數(shù)等4.運算符：+、-、*5.界限符：逗號，分號，括號和引號種類的劃分是根據(jù)編譯的目標(biāo)和方便設(shè)定的單詞常用的單詞內(nèi)部形式：1、按單詞種類分類2、保留字和分界符采用一符一類3、標(biāo)識符和常數(shù)的單詞屬性值為符號表入口指針（標(biāo)識符、常數(shù)相關(guān)屬性很多）（單詞屬性，單詞值）屬性字：詞法分析程序的輸出形式-----單詞的內(nèi)部形式單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值符號表入口指針整數(shù)值數(shù)值0或1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼1、按單詞種類分類2、保留字和分界符采用一符一類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點數(shù)布爾常數(shù)字符串常數(shù)BEGINENDFORDO………:+*,(類別編碼123456789…….20212223…….單詞值符號表入口指針整數(shù)值數(shù)值0或1內(nèi)部字符串----…..-----3.2.2源程序的輸入與預(yù)處理詞法分析器工作的第一步是接受輸入源程序。通常是把輸入的源程序引導(dǎo)至一個輸入緩沖區(qū)，并對輸入串進行預(yù)處理，然后才交付掃描器進行處理。S.P.(字符串)詞法分析程序輸入緩沖區(qū)的處理？輸入緩沖區(qū)的處理？顯然，無論緩沖區(qū)設(shè)定為多大，都不能保證單詞不會被它的邊界打斷，若有標(biāo)識符TEST123，可能在緩沖區(qū)中成為：………….TES在這種情況下，即使讀到緩沖區(qū)的最后一個字符，但仍不能找到該單詞的右邊界，這時，若從外存上再讀一部分源程序進入緩沖區(qū)，則會將沒有處理過的字符(TES)沖掉。兩個半?yún)^(qū)互補使用為此，我們可將緩沖區(qū)分成相等的兩個區(qū)域：掃描緩沖區(qū)一分為二，互補使用。搜索指針從單詞起點開始搜索，如果遇到半?yún)^(qū)域的邊界，但尚未到達單詞的終點時，則可將后續(xù)的輸入字符裝入該緩沖區(qū)的另一半。單詞起點

搜索指針I(yè)fFatendoffirsthalf{reloadsecondhalf;F++;}ElseifFatendofsecondhalf{ reloadfirsthalf;moveFtobeginningoffirsthalf}ElseF++;輸入緩沖區(qū)兩個半?yún)^(qū)互補功能的實現(xiàn)算法源程序的預(yù)處理為了減輕詞法分析器實質(zhì)性處理的負(fù)擔(dān)，因此源程序從輸入緩沖區(qū)進入詞法分析器之前，要先對源程序進行預(yù)處理，預(yù)處理子程序一般完成的主要功能是：過濾掉源程序中的注釋；剔除源程序中無用字符；進行宏替換；實現(xiàn)文件包含的嵌入和條件編譯的嵌入等。具有兩個緩沖區(qū)的詞法分析器結(jié)構(gòu)源程序L輸入緩沖區(qū)X預(yù)處理子程序掃描緩沖區(qū)X1詞法分析器源程序L的屬性字流實現(xiàn)方案（編譯程序中實現(xiàn)方式）：基本上有兩種1.詞法分析單獨作為一遍2.詞法分析程序作為單獨的子程序S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點:結(jié)構(gòu)清晰、各遍功能單一缺點：生成中間文件，效率低S.P.(字符串)詞法分析程序語法分析程序取單詞單詞★詞法分析程序的設(shè)計與實現(xiàn)詞法規(guī)則正規(guī)表達式狀態(tài)轉(zhuǎn)換圖（最小DFA）1.構(gòu)造識別單詞的狀態(tài)轉(zhuǎn)換圖(1)對程序語言的單詞按種類分別構(gòu)造對應(yīng)的狀態(tài)轉(zhuǎn)換圖.(2)對各類轉(zhuǎn)換圖合并，構(gòu)成一個能識別語言所有單詞的狀態(tài)轉(zhuǎn)換圖.2.編程實現(xiàn)狀態(tài)轉(zhuǎn)換圖1.詞法及其狀態(tài)轉(zhuǎn)換圖例1假定語言X的字母表∑={A-Z,a-z,0-9,;,=}單詞符號定義如下： 1、標(biāo)識符：字母打頭的字母數(shù)字串 2、無符號整數(shù)：無符號數(shù)字串 3、分界符：； 4、運算符：=標(biāo)識符出口S1非字母數(shù)字字母字母、數(shù)字無符號整數(shù)出口S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字分界符出口S；運算符出口S=標(biāo)識符無符號整數(shù)分界符S1非字母數(shù)字*字母字母、數(shù)字2非數(shù)字*數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符==80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;1,‘Line’3,‘=’2,‘80’4,‘;’數(shù)字?jǐn)?shù)字字母字母11==0003;;1輸入輸出2.狀態(tài)轉(zhuǎn)換圖的實現(xiàn)——構(gòu)造詞法分析程序標(biāo)識符無符號整數(shù)分界符運算符<1，標(biāo)識符名字><2，整數(shù)值><3，“;”><4，“=”>例1假定語言X的字母表∑={A-Z,a-z,0-9,;,=}單詞符號定義如下： 1、標(biāo)識符：字母打頭的字母數(shù)字串 2、無符號整數(shù)：無符號數(shù)字串 3、分界符：； 4、運算符：=標(biāo)識符S1非字母數(shù)字字母字母、數(shù)字無符號整數(shù)S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字分界符出口S；運算符S=出口出口出口標(biāo)識符出口S1非字母數(shù)字字母字母、數(shù)字If(ISLETTER){WHILE(ISLETTERORISDIGIT)DO{

當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR；//從緩沖區(qū)取下一字符};UNGETCH；//回退一字符OUTPUT(1，標(biāo)識符名字)；}；=80;eniLLine=80;==;;無符號整數(shù)出口S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字If(ISDIGIT){WHILEISDIGITDO{

當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR；//從緩沖區(qū)取下一字符};UNGETCH；//回退一字符OUTPUT(2,整數(shù))；};=80;eniLLine=80;==;;分界符出口S；If(CH==‘;’)OUTPUT(3,“;”)；If(CH==‘=’)OUTPUT(4,“=”)；運算符S=出口標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=例1程序語言的詞法分析程序GETNEXTCHAR()；SWITCH(CHCODE);{CASE1:{WHILE(ISLETTERORISDIGIT)DO{SAVE();//當(dāng)前字符放入一臨時字符數(shù)組；GETNEXTCHAR()；//從緩沖區(qū)取下一字符};UNGETCH；//回退一字符OUTPUT(1，標(biāo)識符名字)；}；BREAK;CASE2:{WHILEISDIGITDO{SAVE();//當(dāng)前字符放入一臨時字符數(shù)組；GETNEXTCHAR；//從緩沖區(qū)取下一字符};UNGETCH；//回退一字符OUTPUT(2,整數(shù))；};BREAK;CASE3:OUTPUT(3,“;”)；BREAK;CASE4:OUTPUT(4,“=”)；BREAK;DEFAULT:Error();};標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=采用面向?qū)ο蟮姆椒ㄔO(shè)計詞法分析器標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=詞法規(guī)則正規(guī)表達式狀態(tài)轉(zhuǎn)換圖（最小DFA）合并狀態(tài)轉(zhuǎn)換圖編程實現(xiàn)狀態(tài)轉(zhuǎn)換圖合并狀態(tài)轉(zhuǎn)換圖文法、正規(guī)表達式、有限自動機有限自動機(最小化？)3.3

詞法分析程序的自動生成器—LEX（LEXICALAnalyzerGenerator）LEX是1972年在貝爾實驗室的UNIX上首先實現(xiàn)FLEX是1984年GNU工程推出，是LEX的擴充，并兼容LEX原理：LEX源程序(lex.l)S.P.字符串LEX編譯器詞法分析程序L(lex.yy.c)S.P.單詞字符串C編譯器可執(zhí)行L詞法分析程序L(lex.yy.c)可執(zhí)行L1.LEX源程序的結(jié)構(gòu)一個LEX源程序具有如下形式:聲明部分%%識別規(guī)則%%輔助函數(shù)各部分之間用%%隔開，同時%%在最左邊.一、聲明部分

D1R1

D2R2∶∶DnRn

其中：R1,R2，……，Rn為正則表達式。D1,D2，……，Dn為正則表達式名字

例：C++標(biāo)識符letterA|B|¨¨¨|Z|_

digit0|1|¨¨¨|9

idletter(letter|digit)*二、識別規(guī)則：是一串如下形式的LEX語句：

模式{動作}P1{A1}P2{A2}∶∶Pm{Am}Pi：定義在Σ∪{D1,D2,¨¨Dn}上的正規(guī)表達式，也稱模式。{Ai}：Ai為語句序列，它指出，在識別出模式為Pi的單詞以后，詞法分析器所應(yīng)作的動作。其基本動作是返回單詞的類別編碼和其屬性。三、輔助函數(shù)定義模式動作需要的函數(shù)在這三部分中一和三為可選項，但是二是必須的

一對特殊的符號%{和%}：出現(xiàn)在括號內(nèi)的所有內(nèi)容都被復(fù)制到文件中，它們不會被當(dāng)作正則定義處理。下面是識別某語言單詞符號的LEX源程序：例：LEX源程序AUXILIARYDEFINITIONS/*聲明部分*/letter[A—z]digit[0—9]%%RECOGNIYIONRULES/*識別規(guī)則*/“BEGIN”“END”“FOR”{RETURN(1,─)}{RETURN(2,─)}{RETURN(3,─)}RETURN是LEX過程，該過程將單詞傳給語法分析程序RETURN（C，LEXVAL）其中C為單詞類別編碼LEXVAL：標(biāo)識符：TOKEN（字符數(shù)組）整常數(shù)：DTB（數(shù)值轉(zhuǎn)換函數(shù)，將TOKEN中的數(shù)字串轉(zhuǎn)換二進制值）其他單詞：無定義。“THEN”“ELSE”{