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

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

詞法分析程序的功能識(shí)別出單詞（內(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è)計(jì)與實(shí)現(xiàn)詞法分析程序的輸入與輸出源程序的輸入與預(yù)處理單詞的識(shí)別詞法分析程序與詞法分析程序的接口詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)單詞是語言中具有獨(dú)立意義的最小語法單位.單詞的種類

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

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

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

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

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

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

詞法分析程序的自動(dòng)生成器—LEX（LEXICALAnalyzerGenerator）LEX是1972年在貝爾實(shí)驗(yàn)室的UNIX上首先實(shí)現(xiàn)FLEX是1984年GNU工程推出，是LEX的擴(kuò)充，并兼容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)一個(gè)LEX源程序具有如下形式:聲明部分%%識(shí)別規(guī)則%%輔助函數(shù)各部分之間用%%隔開，同時(shí)%%在最左邊.一、聲明部分

D1R1

D2R2∶∶DnRn

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

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

digit0|1|¨¨¨|9

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

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

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