編譯技術(shù)課件

1

編譯系統(tǒng)概述

21.1 程序設(shè)計語言的發(fā)展匯編語言(AssembleLanguage)機(jī)器語言(MachineLanguage)程序設(shè)計語言(ProgrammingLanguage)3

例計算表達(dá)式3*16+2的值，實(shí)現(xiàn)該計算的機(jī)器語言程序、匯編語言程序和程序設(shè)計語言（C語言）程序如下所示。目標(biāo)計算機(jī)的系統(tǒng)結(jié)構(gòu)和匯編語言的使用方法詳見本書第7章。22038210260261011000f000LoadR0,3MulR0,10LoadR1,2AddR0,R1WriteR0Haltvoidmain(void){cout<<3*16+2;}注：10表示164㈠機(jī)器語言機(jī)器指令集合稱為機(jī)器語言。機(jī)器指令即二進(jìn)制數(shù)，通常由若干字節(jié)構(gòu)成。①優(yōu)點(diǎn)計算機(jī)可直接識別執(zhí)行可充分利用硬件特性②缺點(diǎn)可讀性差指令系統(tǒng)隨機(jī)種而異由于機(jī)器指令直接或間接含有絕對地址，增加或減少一條指令，可能會引起多條指令的修改。編程者需協(xié)調(diào)內(nèi)存的使用所以，機(jī)器語言形式的程序編制和維護(hù)困難，限制了計算機(jī)的推廣和應(yīng)用。5㈡匯編語言用記憶符取代二進(jìn)制位，存儲地址和匯編語句的序號可用符號名表示。①優(yōu)點(diǎn)用符號取代二進(jìn)制數(shù)，提高了程序的可理解性。性能較好的匯編語言，可用符號名來表示存儲地址和匯編語句序號，這樣避免了在匯編語句中絕對地址的出現(xiàn)?？沙浞掷糜布匦运?，匯編語言在一定程度上降低了程序編制和維護(hù)的難度。②缺點(diǎn)匯編語句和機(jī)器指令基本上是一對一的，所以匯編語言的編程效率并沒有質(zhì)的提高。和機(jī)器語言一樣，匯編語言依附于目標(biāo)計算機(jī)。需匯編程序，將匯編語言譯成機(jī)器語言。6㈢程序設(shè)計語言程序設(shè)計語言又稱高級語言。程序設(shè)計語言接近于英語，相當(dāng)于工程語言。目前計算機(jī)系統(tǒng)一般含有多個程序設(shè)計語言的翻譯程序（例VC、VB等），甚至對同一個程序設(shè)計語言配備了多個不同性能的翻譯程序，供用戶選擇使用。①優(yōu)點(diǎn)獨(dú)立于具體計算機(jī)，面向過程（函數(shù)）或?qū)ο?。程序設(shè)計語言接近于英語，可理解性好。數(shù)據(jù)類型豐富，各種功能的語句齊備，一條語句至少相當(dāng)于幾十條匯編語句。所以，程序設(shè)計語言極大地提高了編程效率，大幅度地降低了編程難度。②缺點(diǎn)需翻譯程序，將高級語言譯成機(jī)器語言或匯編語言。對硬件操作困難，高級語言通常提供匯編語言接口。71.2基本術(shù)語解釋㈠源語言和源程序(SourceLanguageandSourceProgram)

用程序設(shè)計語言書寫的程序，稱為源程序，該程序設(shè)計語言稱為源語言。源程序通常用編緝程序輸入，用字符(ASCII碼)表示，以文本文件形式存儲。㈡文本文件(TextFile)

文本文件的內(nèi)容由94個圖形字符‘!’-‘~’(33-126)和4個控制字符換行(10)、回車(13)、空格(32)、TAB(9)構(gòu)成，文本文件又稱為ASCII碼文件，擴(kuò)展名通常為TXT，文件尾用控制字符EOF(26)指示。當(dāng)換行和回車二個控制字符從文本文件讀入內(nèi)存，在C語言中是用一個字符（換行）表示。8㈢目標(biāo)語言和目標(biāo)程序(TargetLanguageandTargetProgram)

目標(biāo)語言可以是機(jī)器語言(二進(jìn)制數(shù))，也可以是匯編語言(字符)，或者是其它中間語言(字符)，但最終結(jié)果必定是機(jī)器語言。機(jī)器語言程序用二進(jìn)制文件存儲，匯編語言或中間語言程序用文本文件存儲。目標(biāo)程序是經(jīng)翻譯程序加工后用目標(biāo)語言表示的程序。㈣二進(jìn)制文件(BinaryFile)

二進(jìn)制文件由機(jī)器指令即二進(jìn)制數(shù)構(gòu)成，因二進(jìn)制數(shù)可能是26(文件結(jié)束控制符)，故文件尾用文件長度(文件的字節(jié)數(shù))指示，擴(kuò)展名通常為EXE。9㈤翻譯程序(Translator)

將源程序譯成邏輯上等價的目標(biāo)程序的程序。翻譯程序有二種工作方式：編譯和解釋。解釋程序Interpreter

源程序結(jié)果輸入數(shù)據(jù)解釋、執(zhí)行

解釋方式主要特點(diǎn)是：用戶程序是消極的。用戶程序運(yùn)行時，控制點(diǎn)在解釋程序，即用戶程序的執(zhí)行離不開解釋程序。①解釋方式(Interpret)

以源程序作為輸入，輸入一句解釋執(zhí)行一句，不產(chǎn)生完整的目標(biāo)程序，相應(yīng)的翻譯程序稱為解釋程序(Interpreter)

。工作方式如下圖所示：10②編譯方式(Compile)

將源程序全部譯為目標(biāo)程序，該目標(biāo)程序可在操作系統(tǒng)環(huán)境下直接執(zhí)行，相應(yīng)的翻譯程序稱為編譯程序(Compiler)

，工作方式如下圖所示：編譯程序Compile連接程序Link裝入運(yùn)行Run編輯程序EditASCII碼二進(jìn)制(整體未定位)

二進(jìn)制(整體定位)

源程序結(jié)果輸入數(shù)據(jù)11編輯程序的工作結(jié)果是ASCII碼形式的源程序。編譯程序以ASCII碼形式的源程序?yàn)檩斎?，它的工作結(jié)果是二進(jìn)制形式的目標(biāo)程序，但并未包括用戶程序中所使用的系統(tǒng)函數(shù)的目標(biāo)代碼。從整體上來看，程序是不完整的，程序中的部分地址尚未確定（例系統(tǒng)函數(shù)的調(diào)用）。將二進(jìn)制形式的用戶程序和系統(tǒng)函數(shù)目標(biāo)代碼連接成一個程序，對未確定的地址進(jìn)行定位。由操作系統(tǒng)將用戶程序裝入內(nèi)存后運(yùn)行。程序在運(yùn)行過程中讀入數(shù)據(jù)，經(jīng)處理加工后輸出計算結(jié)果。

編譯方式主要特點(diǎn)是：用戶程序是積極的。用戶程序執(zhí)行時，控制點(diǎn)在用戶程序自身。除操作系統(tǒng)外，程序運(yùn)行無需其它支撐軟件。12③二種翻譯方式比較解釋方式和編譯方式的主要區(qū)別是：目標(biāo)代碼的執(zhí)行方式不同，基本原理和方法沒有本質(zhì)上的區(qū)別。1）解釋方式的優(yōu)點(diǎn)提供一種直接的交互調(diào)試功能，容易獲得較好的動態(tài)調(diào)試效果。使用變量可不預(yù)先定義。變量性質(zhì)可動態(tài)修改。2）解釋方式的缺點(diǎn)在執(zhí)行時需動態(tài)地對程序進(jìn)行分析翻譯，開銷大，其執(zhí)行速度相當(dāng)于編譯方式的1/10至1/100。解釋方式占用內(nèi)存大顯然解釋程序的優(yōu)點(diǎn)就是編譯程序的缺點(diǎn)，反之亦然，對于編譯程序的優(yōu)缺點(diǎn)不再重復(fù)敘述。④對任何一種高級語言，既可采用編譯方式，也可采用解釋方式，包括匯編語言在內(nèi)（MASM方式和DEBUG方式）。131.3 編譯過程概述

典型的編譯程序工作過程是：輸入源程序，對它進(jìn)行加工處理，最后輸出目標(biāo)程序（機(jī)器語言或匯編語言形式）。整個過程相當(dāng)復(fù)雜，從數(shù)據(jù)加工的角度來看，可將其分成4個邏輯階段，它們是：詞法分析語法分析語義分析（中間代碼產(chǎn)生）目標(biāo)代碼生成詞法分析語法分析語義分析(中間代碼產(chǎn)生)目標(biāo)代碼生成源程序目標(biāo)程序編譯程序基本上是按照這個流程來設(shè)計的。圖示如下：14

以算術(shù)表達(dá)式3+abc*128為例，來說明編譯程序工作過程。㈠詞法分析(LexicalAnalysis)

執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器。任務(wù)：字符串形式單詞

編碼形式單詞內(nèi)部碼（二元式）依據(jù)：語言的構(gòu)詞規(guī)則①二元式(Pair)(單詞種別,單詞值)單詞種別：用整數(shù)碼表示（為直觀起見用字符表示），語法分析時用。單詞值：在本書中用字符串表示，語義分析時用。當(dāng)一個單詞種別中可能有多個單詞時，單詞的值才有意義。為了便于輸入處理，無意義的單詞值用"NUL"表示。15②二元式編碼單詞單詞種別單詞值++NUL--NUL**NUL//NUL((NUL))NUL………標(biāo)識符i字符串形式符號名

整常數(shù)x字符串形式整常數(shù)實(shí)常數(shù)y字符串形式實(shí)常數(shù)………經(jīng)詞分析，算術(shù)表達(dá)式3+abc*128的單詞內(nèi)部碼（二元式）為：('x',"3")('+',"NUL")('i',"abc")('*',"NUL")('x',"128")16㈡語法分析(Parsing)

執(zhí)行語法分析任務(wù)的程序稱為語法分析器。任務(wù)：檢查源程序的語法結(jié)構(gòu)是否正確依據(jù)：語言的語法規(guī)則在語法分析時，算術(shù)表達(dá)式3+abc*128的語法結(jié)構(gòu)應(yīng)表示為x+i*x，語法分析器最終應(yīng)識別出這是一個算術(shù)表達(dá)式。識別過程相當(dāng)于建立一棵語法樹 <算術(shù)表達(dá)式> <算術(shù)表達(dá)式> + <項(xiàng)> <項(xiàng)> <項(xiàng)> * <因子> <因子> <因子> x(整常數(shù)) x(整常數(shù)) i(標(biāo)識符)17㈢語義分析(SemanticAnalysis)

執(zhí)行語義分析任務(wù)的程序稱為語義分析器或中間代碼產(chǎn)生器。任務(wù)：建立符號表和常數(shù)表，記錄源程序中標(biāo)識符屬性和常數(shù)值，根據(jù)語言的語義規(guī)定生成中間代碼。依據(jù)：語言的語義內(nèi)涵語義分析（中間代碼產(chǎn)生）主要工作為：語義正確性檢查語義翻譯①語義正確性檢查 例2：begin

realA;integerB;B=A+B;end

語法正確，不同的語言有不同的語義解釋。標(biāo)準(zhǔn)Fortran語言認(rèn)為是錯誤的，其不允許不同類型的量進(jìn)行混合運(yùn)算。C語言認(rèn)為是正確的，允許混合運(yùn)算，但需轉(zhuǎn)換成相同類型的量，然后再進(jìn)行運(yùn)算。Pascal語言認(rèn)為是錯誤的，雖允許混合運(yùn)算，但不允許將實(shí)型量賦值于整型量。begin

realA;

integerB;B=A+B;end18②語義翻譯

1)說明語句的翻譯 將標(biāo)識符及其屬性填入符號表。

2)執(zhí)行語句的翻譯 根據(jù)不同語句的語義，生成邏輯上等價的中間代碼。中間代碼結(jié)構(gòu)簡單、意義明確的記號系統(tǒng)，非常接近機(jī)器指令，又獨(dú)立于具體機(jī)器。常用的中間代碼有三元式和四元式。表達(dá)式3+abc*128可譯成如下四元式：

(*,&abc,&128,&T1) (+,&3,&T1,&T2)其中，

&abc表示標(biāo)識符abc在符號表中入口（即地址）；

T1和T2是在翻譯過程中由編譯程序引入的臨時變量，&T1和&T2分別表示T1和T2在符號表中入口；而&128表示常數(shù)128在常數(shù)表中的地址。19符號表(SymbolTable)

符號表用于記錄源程序中出現(xiàn)的標(biāo)識符(Identifier)，一個標(biāo)識符往往具有一系列的語義值，它包括標(biāo)識符的名稱、標(biāo)識符的種屬、標(biāo)識符的類型、標(biāo)識符值的存放地址等等。每個標(biāo)識符在符號表中有一項(xiàng)記錄，用于記錄標(biāo)識符的各種語義值，而在四元式中填寫的是標(biāo)識符在符號表中的記錄地址，通常稱為符號表入口。內(nèi)存地址符號名種屬類型…………未分配abc簡單變量整型未分配T1簡單變量整型未分配T2簡單變量整型…………符號表的結(jié)構(gòu)示意如下：20常數(shù)表(ConstantTable)

常數(shù)表用于記錄在源程序中出現(xiàn)的常數(shù)。假定，每個整常數(shù)在常數(shù)表中占2個字節(jié)，每個實(shí)常數(shù)在常數(shù)表中占4個字節(jié)。常數(shù)的二進(jìn)制值00000000-00000011（3）00000000-01000000（128）……常數(shù)表的結(jié)構(gòu)示意如下：21㈣目標(biāo)代碼生成(CodeGeneration)

執(zhí)行目標(biāo)代碼生成的程序稱為目標(biāo)代碼生成器。任務(wù)：中間代碼

目標(biāo)代碼（機(jī)器指令或匯編語言）依據(jù)：目標(biāo)機(jī)器的系統(tǒng)結(jié)構(gòu)假設(shè)模型機(jī)器的指令格式為：

opRi,M （Ri）op（M）→Ri

opRi,Rj （Ri）op（Rj）→Ri

opRi,C （Ri）opC→Ri

其中Ri表示寄存器，M表示內(nèi)存地址（可用符號表示），C表示常數(shù)。表達(dá)式3+abc*128最終形成的匯編語言程序示意如下：

LoadR0,abc MulR0,128 StoreR0,T1 LoadR0,3 AddR0,T1 StoreR0,T2//假設(shè)地址可以用符號名表示//暫且僅僅使用R022

編譯程序在工作過程中可發(fā)現(xiàn)源程序中各種錯誤，錯誤類型及錯誤處理對策簡述如下：㈠錯誤類型詞法錯誤（可在詞法分析階段發(fā)現(xiàn)）語法錯誤（可在語法分析階段發(fā)現(xiàn)）語義錯誤（可在語義分析階段發(fā)現(xiàn)）1.4 出錯處理(ErrorHandle)㈡出錯處理一旦發(fā)現(xiàn)錯誤，暫停編譯程序工作，指出錯誤的地點(diǎn)和類型。在發(fā)現(xiàn)錯誤后，不中斷編譯程序工作。采取某些措施（例錯誤局部化、錯誤校正等），使得源程序的編譯工作可繼續(xù)下去，盡可能發(fā)現(xiàn)源程序中比較多的錯誤。231.5 編譯程序的前端和后端

由于在編譯程序的內(nèi)部引入了中間代碼，這樣可將編譯程序分為二個相互獨(dú)立部分。㈠編譯程序前端(TheFrontEnd)

組成：詞法分析器、語法分析器和中間代碼產(chǎn)生器特點(diǎn)：依賴于被編譯的源語言，輸出結(jié)果用中間代碼描述，和目標(biāo)機(jī)器無關(guān)。㈡編譯程序后端(TheBackEnd)

組成：目標(biāo)代碼生成器特點(diǎn)：和源語言無關(guān)，以中間代碼形式的源程序?yàn)檩斎脒M(jìn)行處理，輸出結(jié)果依賴于目標(biāo)機(jī)器。

為一個源語言構(gòu)造好前端，若要在某一個特定計算機(jī)上構(gòu)造該源語言的編譯程序，只要構(gòu)造這個目標(biāo)機(jī)器的后端即可。相反，若已構(gòu)造了一個高質(zhì)量的后端，若要在同一臺目標(biāo)機(jī)器上為另一源語言構(gòu)造編譯程序時，只要構(gòu)造該源語言的前端即可。242.1詞法分析器的設(shè)計考慮及

手工構(gòu)造詞法分析任務(wù)：從文件讀入源程序，去除源程序中與編譯無關(guān)的編輯字符、注釋等，由字符拼接單詞。每當(dāng)識別出一個單詞，就用單詞的內(nèi)部碼（單詞二元式）替換。執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器。252.1.1單詞類型及二元式編碼㈠單詞類型任何程序設(shè)計語言的單詞都可將其分為5種類型，它們是：基本字 real、integer、……標(biāo)識符 通常為以字母開始的數(shù)字字母串（簡單變量、標(biāo)號、……）常數(shù) 整常數(shù)（123）、實(shí)常數(shù)（123.456）、……運(yùn)算符 +、*、/、……界符 ;、(、)、……㈡單詞的性質(zhì)基本字、運(yùn)算符和界符對于某一程序設(shè)計語言來說是確定的，而源程序中的標(biāo)識符和常數(shù)的個數(shù)是不確定的，隨源程序而異。有些單詞由單個字符構(gòu)成，而有些單詞由多個字符構(gòu)成。26㈢單詞二元式編碼經(jīng)詞法分析后，單詞用二元式(code,val)表示。code表示單詞的種別，用整數(shù)碼表示。單詞種別表示單詞的語法特性，在語法分析時使用。val表示單詞的值，在本書中用字符串表示。單詞值表示了單詞的語義特性，在語義分析時使用。㈣編碼原則通常將標(biāo)識符歸為一種，常數(shù)按類型分種，基本字、運(yùn)算符及界符采用一符一種。如果一個種別僅包含一個單詞，那么單詞種別就可代表該單詞，無需給出單詞值。為了輸入和處理的方便，無意義的單詞值用字符串"NUL"表示。若一個種別含有多個單詞，除給出種別外，還需給出它的值。27㈤實(shí)例設(shè)有某一程序設(shè)計語言，其部分單詞二元式編碼如下所示：單詞單詞種別單詞值integeraNULrealcNULbegin{NULend}NUL標(biāo)識符i字符串形式符號名無符號整常數(shù)x字符串形式數(shù)字無符號實(shí)常數(shù)y字符串形式數(shù)字==NUL**NUL++NUL((NUL))NUL,,NUL;;NUL

計算園柱體表面積的源程序（輸入輸出略）如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/Realr,h,s;s=2*3.14*r*(r+h)End

根據(jù)單詞二元式編碼，上述程序的單詞二元式序列應(yīng)為：

('{',"NUL") …………282.1.2源程序的輸入及預(yù)處理

㈠源程序的輸入

分段讀入處理（早期）全部讀入后處理

源程序以文件形式存于外存，首先要將其讀入內(nèi)存才可進(jìn)行詞法分析。早期計算機(jī)內(nèi)存較小，只能在內(nèi)存設(shè)置長度有限的緩沖區(qū)，分段讀入源程序進(jìn)行處理。在編制程序時，必須考慮由于源程序分段讀入所產(chǎn)生的問題。例如，由多個字符構(gòu)成的單詞有可能被緩沖區(qū)邊界所打斷（留作習(xí)題）。目前計算機(jī)所使用的的內(nèi)存已超過若干年前硬盤容量，計算機(jī)內(nèi)存足以容納源程序的全部，故源程序可一次全部讀入內(nèi)存進(jìn)行處理。29

設(shè)源程序如下所示，其中'\'為續(xù)行符。Begin/*S=2*3.14*R*R+2*3.14*R*H*/\n\tReal

r,h,s;\n\ts=2*3.\\n14*r*(r+h)\nEnd\n\0......\0源程序讀入后，輸入緩沖區(qū)的內(nèi)容如下所示：30㈡預(yù)處理詞法分析器通常由二個部分構(gòu)成： 預(yù)處理程序 掃描器（單詞識別程序）①分成二部分的理由目前使用的程序設(shè)計語言大都采用自由格式書寫，允許在單詞之間存在多余的空格、換行和制表符（TAB）。源程序通常帶有注釋，注釋不是程序的必要組成部分。有些語言還提供續(xù)行功能（例C語言中的續(xù)行符'\'），當(dāng)一個單詞過長（例字符串常數(shù)），可分多行列出。對于Fortran和Cobol之類語言，源程序還受到書寫格式的限制。

詞法分析器可在輸入緩沖區(qū)上直接識別單詞，但從程序設(shè)計的角度來看，若把源程序預(yù)處理一下，則單詞識別就比較容易。31②預(yù)處理主要工作刪除注釋刪除續(xù)行符，以及后續(xù)換行符(0AH)。換行符、TAB和空格具有界符作用，預(yù)處理時通常予以保留。在后面的分析中可以看到，它們的存在反而給后續(xù)的單詞識別帶來方便。為了簡化判斷，可在預(yù)處理時，將換行符和TAB統(tǒng)一替換為空格。大多數(shù)語言（除C語言）不區(qū)分大小寫，可在預(yù)處理時，將大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。對于受書寫格式限制的語言（例Fortran和Cobol），還應(yīng)識別標(biāo)號區(qū)，正確給出語句標(biāo)號。識別續(xù)行標(biāo)志，把相繼行捻接在一起，給出語句結(jié)束符。beginrealr,h,s;

s=2*3.14*r*(r+h)

end\0...\0上述源程序經(jīng)預(yù)處理后，掃描緩沖區(qū)中的內(nèi)容如下所示：32㈢預(yù)處理例用偽代碼編寫一個預(yù)處理程序，要求如下：去除源程序中注釋（源程序中的注釋用/*……*/標(biāo)記，不允許嵌套使用）去除源程序中續(xù)行符（\）將TAB和換行符替換為空格將大寫字母變換成小寫在源程序尾部添加字符'#'，這是編譯程序內(nèi)部的一個特殊的單詞，以示源程序結(jié)束。每調(diào)用一次，將經(jīng)預(yù)處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描器識別單詞。33①算法說明用偽代碼編寫預(yù)處理程序，輸入和預(yù)處理可同時進(jìn)行，無需輸入緩沖區(qū)，將讀入后經(jīng)預(yù)處理的源程序直接送掃描緩沖區(qū)buf[1..n]。定義布爾變量in_comment，記錄當(dāng)前處理字符是否處于注釋。若in_comment的值為false，則表示當(dāng)前讀入字符未處于注釋中，此時應(yīng)將當(dāng)前處理字符存入掃描緩沖區(qū)；若in_comment的值為true，則表示當(dāng)前處理字符處于注釋中，此時無需將該字符存入buf中，相當(dāng)于掉棄。當(dāng)讀入“/*”，布爾變量in_comment的值由false變?yōu)閠rue；當(dāng)讀入“*/”，布爾變量in_comment的值由true變?yōu)閒alse?？捎米兞縞ur_c記錄當(dāng)前正在處理的字符，用old_c記錄剛處理過的字符。 ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧin_comment:f………f/t…………t/f………f340.procedurepro_process() //掃描緩沖區(qū)buf[]和掃描緩沖區(qū)指針i1.old_c←‘\0’:in_comment←false:cur_c←文件第一個字符:i←12.whilenoteof(“source.txt”)do//文件尚未處理完3. ifnotin_commentthen//當(dāng)前字符未處于注釋中4. ifold_c='/'andcur_c='*'then//進(jìn)入注釋5. i←i-1:in_comment←true6. else7. ifold_c='\'andcur_c=換行符theni←i-1//是續(xù)行符8. else9. ifcur_c≥'A'andcur_c≤'Z'thencur_c←cur_c+3210. ifcur_c=制表符orcur_c=換行符thencur_c←空格11. i←i+1:buf[i]←cur_c //送入掃描緩沖區(qū)12. endif13. endif14. else//當(dāng)前字符處于注釋中15. ifold_c='*'andcur_c='/'thenin_comment←false //離開注釋16. endif 17. old_c←cur_c:cur_c←文件下一個字符18.endwhile19.i←i+1:buf[i]←'#'20.endprocedure352.1.3基本字的識別和超前搜索

程序設(shè)計語言單詞以基本字識別最為困難，原因如下：

①有些語言對基本字不加保護(hù)，用戶可用作普通標(biāo)識符。

②基本字、用戶定義的標(biāo)識符和常數(shù)之間可能沒有分隔符。

例標(biāo)準(zhǔn)Fortran對基本字不加保護(hù)，用戶可以把它們用作普通標(biāo)識符。讓我們來觀察下面三個Fortran語言語句。IF(5.EQ.M)GOTO55

邏輯IF，當(dāng)M等于5轉(zhuǎn)標(biāo)號為55的語句。IF(5)=55 IF為數(shù)組名，IF(5)為下標(biāo)變量IF(X+Y)110,120,130

算術(shù)IF，當(dāng)X+Y<0，轉(zhuǎn)標(biāo)號為110的語句；當(dāng)X+Y等于0，轉(zhuǎn)標(biāo)號為120的語句；當(dāng)X+Y>0，轉(zhuǎn)標(biāo)號為130的語句顯然僅根據(jù)IF無法判斷其為何種單詞，可能是基本字，也可能是標(biāo)識符。36

解決辦法是超前搜索，一直掃描到右括號后面的字符。若該字符為字母G或g，則為邏輯IF；若為數(shù)字，則為算術(shù)IF；若為=，則為標(biāo)識符。超前搜索導(dǎo)致詞法分析器實(shí)現(xiàn)困難。為了降低詞法分析器的復(fù)雜性，避免超前搜索，在實(shí)際實(shí)現(xiàn)中，大多數(shù)語言的編譯程序?qū)τ脩舨扇×硕l限制措施：

①所有基本字均為保留字，用戶不得使用它們作為標(biāo)識符。

②將空格、TAB和換行符視為界符。在基本字、用戶定義的標(biāo)識符和常數(shù)之間，若沒有運(yùn)算符或界符，則至少用一個空格（或TAB、換行符）加以分隔。

這樣空格、TAB和換行符不再是沒有意義的了，這也就是為什么在詞法分析預(yù)處理中將空格、TAB和換行符保留下來的原因。采用上述二條限制措施，對用戶來講是完全可接受的，并且已成為程序員進(jìn)行程序設(shè)計的慣例。詞法分析器對于所有單詞的識別，最多只要向前看一個字符就足夠了。372.1.4遍㈠遍的基本概念由外存獲得前一遍的工作結(jié)果(對于第一遍而言，從外存獲得源程序)，完成它所含的有關(guān)階段工作之后，再把結(jié)果存于外存。㈡遍引入的歷史背景早期的計算機(jī)內(nèi)存較小，編譯程序相對而言體積較大。使用遍技術(shù)的優(yōu)點(diǎn)在于，可根據(jù)當(dāng)前遍的工作，裝入相應(yīng)的工作程序。當(dāng)一遍工作完之后，內(nèi)存空間大部分被釋放。當(dāng)下一遍進(jìn)入后，幾乎可以使用全部存儲空間。遍數(shù)多一點(diǎn)還有一個好處，即整個編譯程序的邏輯結(jié)構(gòu)較為清晰。但是，遍數(shù)多勢必增加輸入輸出所耗費(fèi)的時間。㈢遍和編譯程序的結(jié)構(gòu)遍決定了編譯程序的結(jié)構(gòu)。在本書中，詞法分析器是以函數(shù)形式書寫的，函數(shù)的返回值是一個單詞的二元式。

①詞法分析不作為獨(dú)立一遍

②詞法分析作為獨(dú)立一遍（本書采用）382.1.5狀態(tài)轉(zhuǎn)換圖和詞法分析器手工構(gòu)造㈠引入狀態(tài)轉(zhuǎn)換圖的必要性若不考慮科學(xué)計數(shù)法形式，程序設(shè)計語言的無符號實(shí)型常數(shù)有三種書寫形式，它們是： 無小數(shù)部分形式 134.

無整數(shù)部分形式 .12

完全形式 3.14

如果考慮科學(xué)計數(shù)法形式，則無符號實(shí)型常數(shù)識別更復(fù)雜。直接編寫識別無符號實(shí)型常數(shù)的程序有一定難度，狀態(tài)轉(zhuǎn)換圖是構(gòu)造單詞識別程序（掃描器）的一種較好工具。㈡狀態(tài)轉(zhuǎn)換圖基本概念及應(yīng)用①狀態(tài)轉(zhuǎn)換圖是一個有向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用園圈表示。狀態(tài)之間用箭弧連接。箭弧上的標(biāo)記代表在射出結(jié)狀態(tài)下可能出現(xiàn)的合法的輸入字符。39②一個狀態(tài)轉(zhuǎn)換圖包含若干個狀態(tài)（結(jié)點(diǎn)），其中有一個是初態(tài)，用符號指示，是識別字符串的起點(diǎn)。狀態(tài)轉(zhuǎn)換圖至少有一個終態(tài)，表示已識別出一個字符串（單詞），終態(tài)用雙圈表示。例，識別標(biāo)識符的狀態(tài)轉(zhuǎn)換圖如下所示：其中0為初態(tài)，2為終態(tài)。40③若當(dāng)前狀態(tài)是1，只有當(dāng)輸入字符為非字母數(shù)字，才可能到達(dá)狀態(tài)2，顯然多讀了一個字符，這就是終態(tài)結(jié)2上星號‘*’的含義，它并不是正在識別的標(biāo)識符的組成部分。此時應(yīng)將其退回，下次識別單詞從該字符開始。

④單詞的尾部空格作為單詞的結(jié)束標(biāo)志，單詞的前導(dǎo)空格在識別單詞前濾去，所以在初態(tài)0有一個標(biāo)記為空格的自回路。在詞法分析預(yù)處理中，空格作為界符被保留下來。由于空格不是任何單詞的組成部分（除字符串常數(shù)），故在識別單詞前，應(yīng)將單詞的前導(dǎo)空格濾去。由于空格的特殊性，狀態(tài)轉(zhuǎn)換圖中用虛線表示（若當(dāng)前輸入字符是空格，重新進(jìn)入1狀態(tài)）。在識別標(biāo)識符的過程中，當(dāng)讀入的字符不是字母或數(shù)字，可能是空格，說明當(dāng)前正在識別的單詞已完全讀入。為程序處理方便起見，不管是什么字符，均將其退回。若退回的是空格，該空格將成為下一個單詞的前導(dǎo)空格。41⑤一個狀態(tài)轉(zhuǎn)換圖可用于識別單詞，從初態(tài)出發(fā)，經(jīng)一條通路到達(dá)某一終態(tài)，路徑上的標(biāo)記依次連接而成的字符串，即為狀態(tài)轉(zhuǎn)換圖識別出的單詞。例，識別實(shí)常數(shù)和整常數(shù)的狀態(tài)轉(zhuǎn)換圖如下所示：42設(shè)輸入串為"134.+……"，從初態(tài)0出發(fā)，經(jīng)路徑

到達(dá)終態(tài)5，路徑上標(biāo)記依次連接而成的字符串為"134.+"，退回多讀的字符'+'，識別出的字符串（單詞）為"134."。43⑥一個程序設(shè)計語言單詞的識別，可以用若干張狀態(tài)轉(zhuǎn)換圖予以描述，雖然用一張圖也可以，但用若干張圖，有時會有助于概念的清晰化。將上述三個圖合并視為一個圖，初始狀態(tài)為0。從初態(tài)0出發(fā)，若當(dāng)前輸入字符是字母，則進(jìn)入狀態(tài)1；若為數(shù)字，則進(jìn)入狀態(tài)3；若為小數(shù)點(diǎn)，則進(jìn)入狀態(tài)7。若為加號，則進(jìn)入狀態(tài)10。否則，或進(jìn)入其它單詞的識別（若有的話），或出錯（非法字符）。下圖是識別"#"、"+"和"++"的狀態(tài)轉(zhuǎn)換圖。44㈢利用狀態(tài)轉(zhuǎn)換圖識別單詞狀態(tài)轉(zhuǎn)換圖每次只能識別一個單詞，若源程序中有N個單詞，則需使用狀態(tài)轉(zhuǎn)換圖N次。設(shè)源程序?yàn)?x+++y#"（'#'是預(yù)處理程序添加的），單詞識別程序（掃描器）共使用狀態(tài)轉(zhuǎn)換圖5次。從初態(tài)0出發(fā)，讀入'x'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'+'，進(jìn)入終態(tài)2，識別出標(biāo)識符"x"，退回'+'；從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)10，在狀態(tài)10讀入'+'，進(jìn)入終態(tài)11，識別出運(yùn)算符"++"；從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)10，在狀態(tài)10讀入'y'，進(jìn)入終態(tài)12，識別出運(yùn)算符"+"，退回'y'；從初態(tài)0出發(fā)，讀入'y'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'#'，進(jìn)入終態(tài)2，識別出標(biāo)識符"y"，退回'#'；從初態(tài)0出發(fā)，讀入'#'進(jìn)入狀態(tài)13，識別出單詞"#"，識別出單詞"#"意味著整個源程序中字符處理完畢。45㈣根據(jù)狀態(tài)轉(zhuǎn)換圖編制程序狀態(tài)轉(zhuǎn)換圖就是程序控制流程圖，每個結(jié)點(diǎn)對應(yīng)一段程序。分叉結(jié)點(diǎn)：if語句或switch語句含自回路結(jié)點(diǎn)：while語句終態(tài)結(jié)點(diǎn)：return語句返回單詞的二元式。若終態(tài)結(jié)點(diǎn)帶有星號'*'，則緩沖區(qū)指針值不變；否則緩沖區(qū)指針值加1，指向下一字符。下面是根據(jù)識別標(biāo)識符的狀態(tài)轉(zhuǎn)換圖編制的部分掃描程序。

structcode_val{ //結(jié)構(gòu)用于存放單詞二元式

charcode;charval[20];};structcode_valscanner(char*buf);//單詞識別程序(掃描器)，每調(diào)用一次返回一個單詞的二元式。

voidconcat(chartoken[],charc); //拼接單詞函數(shù)

charreserve(chartoken[]); //查基本字表函數(shù)46structcode_val{ charcode;charval[20];};structcode_valscanner(char*buf)//每調(diào)用一次返回一個單詞的二元式{//buf為掃描緩沖區(qū)存放經(jīng)預(yù)處理的源程序。

staticinti=0; //靜態(tài)局部變量，掃描緩沖區(qū)指示器。

structcode_valt={'\0',"NUL"};//用于存放單詞二元式，識別前清空。

chartoken[20]=""; //用于拼接單詞的字符數(shù)組，識別前清空。

//去除前導(dǎo)空格

while(buf[i]=='')i++;//進(jìn)入標(biāo)識符或基本字的識別

if(buf[i]>='a'&&buf[i]<='z'){ while(buf[i]>='a'&&buf[i]<='z'||buf[i]>='0'&&buf[i]<='9') concat(token,buf[i++]); //拼接函數(shù)

t.code=reserve(token); //查基本字表函數(shù)

if(t.code=='i')strcpy(t.val,token); //是標(biāo)識符

returnt; //返回標(biāo)識符或基本字的二元式

} ………………… //其余單詞識別程序略}//endofscanner47①拼接函數(shù)concat(token[],ch)concat為拼接函數(shù)，它有二個參數(shù)。設(shè)在調(diào)用前token[]內(nèi)容為"beg",輸入字符ch為'i'，則調(diào)用拼接函數(shù)concat后，token的內(nèi)容為"begi"。voidconcat(chartoken[],charc){for(inti=0;token[i]!='\0';i++); //找到尾

token[i]=c;token[++i]='\0';}②查基本字表函數(shù)reserve(token[])基本字通常是由字母構(gòu)成，符合標(biāo)識符規(guī)則?？紤]簡化程序設(shè)計，將基本字作為一種特殊標(biāo)識符來處理。設(shè)置一個基本字表（包括相應(yīng)二元式編），當(dāng)狀態(tài)轉(zhuǎn)換圖識別出一個標(biāo)識符時，就去查對這張表，確定它是基本字還是標(biāo)識符。charreserve(chartoken[]){//基本字及編碼表

constchar*table[]={"begin","end","integer","real"};constcharcode[]={"{}ac"};for(inti=0;i<strlen(code);i++) if(strcmp(token,table[i])==0)returncode[i];return'i';//標(biāo)識符的單詞種別為'i'}begin}end{integerarealc0123482.2正規(guī)式、自動機(jī)及詞法分析器的自動生成492.2.1基本概念㈠有窮字母表∑

符號有限集，它的每個元素稱為字符。㈡字（字符串）

∑上字符所構(gòu)成的有限序列。①空字不包含任何字符的字，稱為空字，記為ε（空字相當(dāng)于高級語言中的空串“”）。

ε 空字

{} 空集

{ε} 集合僅有一個元素ε②∑*∑上所有字的全體，包括ε。例：∑={0，1} ∑*={ε，0，1，00，01，10，11，000，001，……}50③（集合的）積運(yùn)算定義：設(shè)U、V

∑*，U和V的積記為U

V（或UV）且定義為

UV={αβ|（α∈U）∧（β∈V）}積不滿足交換律 UV≠VU積滿足結(jié)合律 (UV)W=U(VW)證明見本書38頁積滿足分配律 X(Y∪Z)=XY∪XZ④（集合的）閉包設(shè)V

Σ*，V的閉包記為V*且定義為V自身的任意有限次積，即V*=V0∪V1∪V2∪……∪Vn，規(guī)定V0={ε}。設(shè)V={0,1}，則V*={ε,0,1,00,01,10,11,000,001,……}閉包V*中的每個字都是由V中的字經(jīng)有限次連接而成。⑤（集合的）正則閉包定義：設(shè)V

Σ*，V的正則閉包記為V+，且定義V+=VV*。根據(jù)定義可以證明V+=V1∪V2∪……∪Vn(詳見本書18頁)。設(shè)V={0,1}，則V+=V1∪V2∪……∪Vn={0,1,00,01,10,11,000,001,……}，V+可理解為二進(jìn)制數(shù)的全體。若V=U，則UV=VV=V2512.2.2正規(guī)式與正規(guī)集㈠正規(guī)式和正規(guī)集的定義：ε和Φ是∑上的正規(guī)式，相應(yīng)的正規(guī)集為{ε}、{}。若字符a∈∑，則字符a是正規(guī)式，相應(yīng)正規(guī)集為{a}。若α、β為正規(guī)式，相應(yīng)正規(guī)集分別記為L(α)和L(β)，則α|β是正規(guī)式，其相應(yīng)正規(guī)集記為L(α|β)，且令L(α|β)=L(α)∪L(β)。若α、β為正規(guī)式，相應(yīng)正規(guī)集分別記為L(α)和L(β)，則αβ(或α·β)是正規(guī)式，其相應(yīng)正規(guī)集記為L(αβ)，且令L(αβ)=L(α)L(β)。若α=β，則L(αβ)=L(αα)=

L(α2)=L(α)2。推廣到一般，正規(guī)式α自身的n次積αα…α是正規(guī)式，可記為αn，其相應(yīng)正規(guī)集記為L(αn)，顯然L(αn)=L(α)n。）若α為正規(guī)式，相應(yīng)正規(guī)集記為L(α)，則α*=α0|α1|α2|……|αn是正規(guī)式，規(guī)定α0=ε，其相應(yīng)正規(guī)集記為L(α*)，且令L(α*)=L(α)*。正規(guī)式運(yùn)算符優(yōu)先性依次為:*、·、︱,可用園括號改變運(yùn)算順序。例子詳見本書第21頁52㈡實(shí)際意義有窮字母表Σ是程序設(shè)計語言所使用的字符集的抽象正規(guī)集是程序設(shè)計語言單詞集的抽象正規(guī)式是程序設(shè)計語言構(gòu)詞規(guī)則的抽象㈢正規(guī)式相等原理二個正規(guī)式是相等的，當(dāng)且僅當(dāng)二個正規(guī)式所表示的正規(guī)集是相等的。例：設(shè)α是正規(guī)式，求證α|α=α。證： L(α|α)=L(α)∪L(α)=L(α) ∵L(α|α)=L(α) ∴α|α=α㈣正規(guī)式滿足下列關(guān)系①交換律：α|β=β|α②結(jié)合律：α|(β|γ)=(α|β)|γ，α(βγ)=(αβ)γ③分配律：α(β|γ)=αβ|αγ，(β|γ)α=βα|γα④εα=αε=α53㈤例設(shè)α=a|b|……|z，β=0|1|……|9。描述標(biāo)識符的正規(guī)式：

α(α|β)*

描述二進(jìn)制數(shù)的正規(guī)式：

(0|1)(0|1)*描述無符號整常數(shù)的正規(guī)式：

ββ*

描述無符號實(shí)常數(shù)的正規(guī)式：

ββ*.β*|.ββ*|(ββ*.β*|.ββ*|ββ*)(E|e)(+|-|ε)ββ*123.45 123.542.2.3確定有限自動機(jī)（DFA）㈠DFA定義一個確定有限自動機(jī)M是一個五元式

M=(S，Σ，f，s0，Z)S是一個有限集，它的每一個元素稱為狀態(tài)。Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。f是一個從S×Σ至S的映照，即f：S×Σ→S（單值函數(shù)）例f(si,a)=sj，表示當(dāng)現(xiàn)行狀態(tài)為si，若輸入字符為a，則轉(zhuǎn)移到下一狀態(tài)sj，sj稱為si的后繼狀態(tài)。s0∈S，是唯一的一個初態(tài)。Z

S，是一個終態(tài)集。例：一個識別二進(jìn)制數(shù)的確定有限自動機(jī)

M=（{0，1}，{'0','1'}，f，0，{1}）其中f的定義如下：

f(0,'0')=1、f(0,'1')=1、f(1,'0')=1、f(1,'1')=155㈡狀態(tài)轉(zhuǎn)換矩陣函數(shù)f可用矩陣表示，行表示狀態(tài)，列表示輸入字符，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。只要對初態(tài)和終態(tài)作適當(dāng)標(biāo)記，可用一個狀態(tài)轉(zhuǎn)換矩陣來表示DFA。㈢DFAM可用一個（確定的）狀態(tài)轉(zhuǎn)換圖表示例識別二進(jìn)制數(shù)的DFA可用（確定的）狀態(tài)轉(zhuǎn)換圖表示如下：狀態(tài)/字符'0''1'011111接上例56㈣字α可為DFAM識別對于一個字α，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的路徑，且路徑上的所有弧的標(biāo)記依序連接成的字為α，則稱α可為DFAM所識別或接受。若DFAM的初態(tài)結(jié)同時又是終態(tài)結(jié)，則稱空字ε可為DFAM所識別或接受。DFAM所識別的字全體記為L(M)。設(shè)α=1012=5

因從初態(tài)0出發(fā)，存在一條到終態(tài)1的路徑。路徑上的標(biāo)記依次連接為101，則稱α=101可為M所識別或接受。

L(M)={α|α為二進(jìn)制數(shù)}。572.2.4非確定有限自動機(jī)（NFA）㈠NFA定義一個非確定的有限自動機(jī)M是一個五元式

M=（S，Σ，f，S0，Z）S是一個有限集，它的每一個元素稱為狀態(tài)。Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。f是一個從S×Σ*到S的子集映照，即f：S×Σ*→2S（多值函數(shù)）2S表示冪集，若S={0，1}，則2S={{}，{0}，{1}，{0，1}}。S0

S，是一個非空初態(tài)集，即NFA的初態(tài)不一定唯一。Z

S，是一個終態(tài)集。DFA和NFA的主要區(qū)別為：映照f（函數(shù)），DFA的映照f是從"狀態(tài)×字符"映射到"狀態(tài)"，f為單值函數(shù)；而NFA的映照f是從"狀態(tài)×字"映射到"狀態(tài)子集"，f為多值函數(shù)。58例某一非確定有限自動機(jī)

M=（{1，2，3，4，5，6}，{a，b}，f，{1，2}，{3}）其中f的定義為：

f(1,"a")={4，5}、f(5，ε)={6}、f(6，ε)={2}、f(2，"ab")={3}其余情況f(si，α)={}（α∈Σ*，si∈S）㈡NFAM可用一個（非確定的）狀態(tài)轉(zhuǎn)換圖表示59㈢字α可為NFAM識別對于Σ*中的一個字α，若在NFAM中存在一條從某一初態(tài)到某一終態(tài)的路徑，且路徑上的所有標(biāo)記依序連接成的字為α，則稱α可為NFAM所識別或接受。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的ε道路，那么空字ε可為M所接受。非確定有限自動機(jī)M所識別的字全體記為L(M)。對于任何二個有限自動機(jī)M和M'，若L(M)=L(M')，則稱二個有限自動機(jī)M和M'等價。DFA是NFA的特例，對于每個NFAM存在一個DFAM'，使得L(M)=L(M')。602.2.5正規(guī)式與確定有限自動機(jī)的等價性

對于Σ上的每個正規(guī)式V，存在一個Σ上的確定有限自動機(jī)M，使得L(V)=L(M)。㈠V

NFA①將V表示成拓廣NFA②根據(jù)下面三條規(guī)則對V進(jìn)行分裂（規(guī)則基于識別的語言不變），直至每條弧上的標(biāo)記為Σ上的一個字符或ε。

V

61例，已知正規(guī)式(a|b)*(aa|bb)構(gòu)造它的NFA。62㈡NFA

DFA

為了便于描述NFA確定化算法，我們引進(jìn)二個概念。①I的ε閉包

I的ε閉包記為ε_CLOSURE(I)或CLOSURE(I)，設(shè)I是NFAM狀態(tài)集的一個子集，I的ε閉包定義為：若狀態(tài)s∈I，則s∈ε_CLOSURE(I)。若狀態(tài)s∈I，則從狀態(tài)s出發(fā)，經(jīng)一條或多條ε弧所能到達(dá)的狀態(tài)s'也屬于ε_CLOSURE(I)。②IaI NFAM狀態(tài)集的一個子集

Ja 從I出發(fā)經(jīng)一條a弧所能到達(dá)的狀態(tài)全體

Ia ε_CLOSURE(Ja)63設(shè)I={1}，則CLOSURE(I)=CLOSURE({1})={1,2}。設(shè)I={5,4,3}，則CLOSURE(I)=CLOSURE({5,4,3})={5,4,3,6,2,8,7}。接上例設(shè)I={1，2}，則

Ja={4,5}∪{3}={3,4,5}Ia=CLOSURE({3,4,5})={5,4,3,6,2,8,7}③NFA確定化算法IIa（a∈∑）Ib（b∈∑）CLOSURE({X})1）數(shù)據(jù)結(jié)構(gòu)及初始狀態(tài)手工計算642）算法描述0.procedureNFA_TO_DFA1. p_cur←1 //當(dāng)前指針，指示當(dāng)前處理的狀態(tài)子集。2. p_end←1 //表尾指針3. I[1]←CLOSURE({X})4. whilep_cur≤p_end5. fori←1ton //設(shè)∑={x1,x2,…,xn}6. ifIXi[p_cur]≠{}andIXi[p_cur]

I[1..p_end]then7. p_end←p_end+18. I[p_end]←IXi[p_cur]9. endif10. endfor11. p_cur←p_cur+112. endwhile13.endprocedure65IIaIb{X,1,2}{1,3,2}{1,4,2}{1,3,2}{1,3,Y,2}{1,4,2}{1,4,2}{1,3,2}{1,Y,4,2}{1,3,Y,2}{1,3,Y,2}{1,4,2}{1,Y,4,2}{1,3,2}{1,Y,4,2}

根據(jù)上述算法對NFAM進(jìn)行確定化。因NFAM具有6個狀態(tài)，狀態(tài)子集個數(shù)（包括空集）最多為64，故表的長度不會超過26-1=63，循環(huán)必然在有限步中結(jié)束。3）結(jié)果處理將I中的每個子集視為DFAM'的一個狀態(tài)。ε_CLOSURE({X})視為DFAM'的初態(tài)。將所有含有原NFA終態(tài)(即Y)的DFAM'狀態(tài)視為終態(tài)。將I、Ia、Ib、……視為DFAM’狀態(tài)轉(zhuǎn)換矩陣，即函數(shù)f。4）重新標(biāo)記狀態(tài)/字符ab0121322143324140是初態(tài)，3和4為終態(tài)。665）用（確定的）狀態(tài)轉(zhuǎn)換圖表示

構(gòu)造過程采用子集法，從字的識別角度來看，DFAM'和NFAM是等價的。672.3詞法分析器的自動生成

輸入正規(guī)式（構(gòu)詞規(guī)則），經(jīng)自動生成器加工，其結(jié)果為DFA。詞法分析器的自動生成器輸入正規(guī)式輸出DFA（狀態(tài)轉(zhuǎn)換矩陣）㈠自動生成過程概述①構(gòu)造描述每個單詞的正規(guī)式Pi(1≤i≤N)。②根據(jù)正規(guī)式Pi構(gòu)造NFAMi(1≤i≤N)，假定初態(tài)均為0。在構(gòu)造NFAMi的同時，逐步并且最終形成識別全部單詞的NFAM。③NFAM確定化④重新標(biāo)記，構(gòu)造DFAM'。68㈡實(shí)例（模型語言的詞法）①模型語言字符集{'a'..'z'，'0'..'9'，'+'，'='，'*'，','，';'，'('，')'，'#'}②模型語言單詞集基本字：begin、end、integer、real標(biāo)識符：以字母開始的數(shù)字字母串無符號整常數(shù)：數(shù)字串運(yùn)算符：+、*、++、=界符：,、;、(、)、#③單詞編碼基本字：begin('{',"NUL"}、end('}',"NUL")、integer('a',"NUL")、real('c',"NUL")標(biāo)識符：('i',字符串) 無符號整常數(shù)：('x',字符串)運(yùn)算符:=('=',"NUL")、+('+',"NUL")、*('*',"NUL")、++('$',"NUL")界符：,(',',"NUL")、;(';',"NUL")、(('(',"NUL")、)(')',"NUL")、#('#',"NUL")69②構(gòu)造NFAM實(shí)例解：①構(gòu)造正規(guī)式（令α=a|b|c|d|……|z、β=0|1|2|3|4|5|6|7|8|9）標(biāo)識符

α(α|β)*無符號整常數(shù)

ββ*運(yùn)算符 單詞本身（例'='的正規(guī)式為'='，"++"的正規(guī)式為"++"）界符 單詞本身（例';'的正規(guī)式為';'）基本字通常是由字母構(gòu)成，符合標(biāo)識符規(guī)則，將基本字作為一種特殊標(biāo)識符來處理（可設(shè)置保留字表，二者區(qū)分可通過查表）。70③NFAM確定化IIαIβI=I+I*I,I;I(I)I#{0}{1,12,13}{2,14,15}{3}{4,5}{6}{7}{8}{9}{10}{11}{1,12,13}{12,13}{12,13}{2,14,15}{14,15}{3}{4,5}{16}{6}{7}{8}{9}{10}{11}{12,13}{12,13}{12,13}{14,15}{14,15}{16}71④重新標(biāo)記，構(gòu)造DFAM'。狀態(tài)/字符αβ=+*,;()#0123456789101111121234135678910111111121213注：0為初態(tài)，其余均為終態(tài)。72㈢掃描器控制程序工作原理每次識別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進(jìn)入下一狀態(tài)，尋求最長匹配，直到無法前進(jìn)為止，這樣始終多讀一個字符。在狀態(tài)遷移過程中，需用Token數(shù)組保存讀入字符。在無法前進(jìn)時，若發(fā)現(xiàn)當(dāng)前狀態(tài)為終態(tài)，則認(rèn)為識別出一個單詞，反之出錯，即Token數(shù)組所保存的字符串不構(gòu)成一個單詞，而是源程序中的一個錯誤詞形。事先設(shè)置一個單詞二元式編碼表，它包括除標(biāo)識符和整常數(shù)以外的所有單詞（基本字、運(yùn)算符和界符）。當(dāng)DFA識別出一個單詞，就根據(jù)Token數(shù)組所保存的字符串去查表。若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標(biāo)識符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。首字符為字母的是標(biāo)識符，首字符為數(shù)字的是無符號整常數(shù)。73DFA每次只能識別一個單詞，需多次使用DFA來識別源程序中單詞，直到源程序中的字符全部處理完。由于構(gòu)造的方法不同，在DFA某一個終態(tài)中，有可能包含原NFA中的二個終態(tài)或更多，即在該狀態(tài)可識別出二個詞形相似的單詞，這就存在一個優(yōu)先匹配問題。此時，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過程，讓其先得到匹配。

設(shè)源程序?yàn)椤皒+++y#”（‘#’是預(yù)處理程序添加的），掃描器共使用確定有限自動機(jī)5次（見下頁）。74從初態(tài)0出發(fā)，讀入'x'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'+'，無法前進(jìn)。因當(dāng)前所處狀態(tài)1為終態(tài)，故識別出一個單詞。查表未果，由于首字符為字母，故單詞"x"為標(biāo)識符，返回單詞二元式編碼('i',"x")并退回'+'。從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)4，在狀態(tài)4讀入'+'，進(jìn)入終態(tài)13，在狀態(tài)13讀入'+'，無法前進(jìn)。因當(dāng)前所處狀態(tài)13為終態(tài)，故識別出一個單詞。查表，確認(rèn)識別出單詞為"++"，返回單詞二元式編碼('$',"NUL")并退回'+'。從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)4，在狀態(tài)4讀入'y'，無法前進(jìn)。因當(dāng)前所處狀態(tài)4為終態(tài)，故識別出一個單詞。查表，確認(rèn)識別出單詞為"+"，返回單詞二元式編碼('+',"NUL")并退回'y'；從初態(tài)0出發(fā)，讀入'y'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'#'，無法前進(jìn)。因當(dāng)前所處狀態(tài)1為終態(tài)，故識別出一個單詞。查表未果，由于首字符為字母，故單詞"y"為標(biāo)識符，返回單詞二元式編碼('i',"y")并退回'#'。從初態(tài)0出發(fā)，讀入'#'，進(jìn)入狀態(tài)10。由于無法再讀入字符，即查表，確認(rèn)識別出單詞為"#"，返回單詞二元式編碼('#',"NUL")。識別出單詞"#"意味著整個源程序中字符全部處理完畢。75㈣掃描器控制程序的實(shí)現(xiàn)⑴狀態(tài)轉(zhuǎn)換矩陣的數(shù)字化控制程序是根據(jù)DFA來工作的，首先要將狀態(tài)轉(zhuǎn)換矩陣數(shù)字化，空白用0表示。在預(yù)處理中，空格作為界符被保留下來。單詞的前導(dǎo)空格在識別一個單詞前被濾去，單詞的尾部空格用作單詞的終止標(biāo)志，故在狀態(tài)轉(zhuǎn)換矩陣中，應(yīng)增加空格列，該列每個元素的值均標(biāo)記為0。因26個字母作用相同，故可用一列表示。在查表時可將26個字母轉(zhuǎn)換成1個，例'a'。因10個數(shù)字作用相同，故可用一列表示。在查表時可將10個數(shù)字轉(zhuǎn)換成1個，例'0'。狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如下頁所示：76a0=+*,;()#空格012345678910011111000000000201200000000030000000000040001300000005000000000006000000000007000000000008000000000009000000000001000000000000111111000000000120120000000001300000000000狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如右所示：77⑵轉(zhuǎn)換函數(shù)0．procedureTra(c)1. ifc是字母thenc←'a'2. ifc是數(shù)字thenc←'0'3. returnc4.endprocedure單詞code單詞code1begin{8**2end}9，,3integera10;;4realc11((5==12))6++13##7++$14⑶DFA終態(tài)集Z={1,2,3,4,5,6,7,8,9,10,11,12,13}在上例中，除初態(tài)0外，其余狀態(tài)均為終態(tài)，故終態(tài)集可不設(shè)置。但此情況屬于特例，通常需設(shè)置終態(tài)集，供程序判斷。⑷單詞二元式編碼表780.procedurscanner()1. t.code←'':t.val←"Nul":Token[]←""2. i←i+1:c←buf[i]:當(dāng)前狀態(tài)←初態(tài)3． whileDFA[當(dāng)前狀態(tài),c]≠0do4. Token←Token,c //將Token中字符串拼接字符c后送Token5. 當(dāng)前狀態(tài)←DFA[當(dāng)前狀態(tài),Tra(c)]6. i←i+1 //指向下一字符7. ifbuf[i]為空thenbreak8. elsec←buf[i]9. endif10. endwhile11． ifnot(當(dāng)前狀態(tài)∈終態(tài)集)thenoutput"Error":exit12. t.code←根據(jù)Token[]查表的結(jié)果13. ift.code=‘?’then //?表示單詞二元式編碼表中無14. ifToken首字符是字母thent.code=‘i‘ //是標(biāo)識符15. ifToken首字符是數(shù)字thent.code=‘x‘ //是整常數(shù)16. t.val←Token[] //此時單詞有值17. endif18. returnt 19.endprocedure793.1

文法的引入3.2

上下文無關(guān)文法3.3文法舉例（略）

使用文法對程序設(shè)計語言的結(jié)構(gòu)進(jìn)行定義和描述。803.1文法的引入

先討論自然語言的文法。例：thebigelephentateabanana㈠語法樹根據(jù)英語的語法，上述句子的語法結(jié)構(gòu)可用圖（語法樹）表示如下：非葉結(jié)點(diǎn)稱為語法單位，在形式語言中稱為非終結(jié)符。處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱為開始符號。葉結(jié)點(diǎn)稱為單詞符號，在形式語言中稱為終結(jié)符。81㈡規(guī)則可以通過建立一組規(guī)則，來描述上述句子的語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。<句子>→<主語><謂語> <主語>→<冠詞><形容詞><名詞><冠詞>→the|a<形容詞>→big<名詞>→elephant|banana<謂語>→<動詞><直接賓語><直接賓語>→<冠詞><名詞><動詞>→ate㈢由規(guī)則推導(dǎo)句子可用規(guī)則來推導(dǎo)出句子。從開始符號出發(fā)，若能從規(guī)則推導(dǎo)出某符號串，則該符號串就是該文法的合法的句子，反之語法錯誤。上述英文句子可用下述規(guī)則來描述：82 <句子>

<主語><謂語>

<冠詞><形容詞><名詞><謂語>

the<形容詞><名詞><謂語>

thebig<名詞><謂語>

thebigelephant<謂語>

thebigelephant<動詞><直接賓語>

thebigelephantate<直接賓語>

thebigelephantate<冠詞><名詞>

thebigelephantatea<名詞>

thebigelephantateabanana

上述推導(dǎo)可簡單表示為：

<句子>

thebigelephantateabanana。值得注意的是用上述規(guī)則可推導(dǎo)出多個句子，因存在推導(dǎo)

<句子>

abigbananaatetheelephant

所以，abigbananaatetheelephant也是文法的一個合法的句子。但意義是荒謬的，也就是說句子的語義是錯誤的。一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進(jìn)行語法和語義兩方面檢查。綜上所述，語言結(jié)構(gòu)通常是用文法來定義和描述，文法是由終結(jié)符、非終結(jié)符、開始符號（特殊非終結(jié)符）及產(chǎn)生式四個要素構(gòu)成。從開始符號出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱為文法所規(guī)定的語言83㈣遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個重要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。例：U→xUy，通常用大寫字母表示非終結(jié)符，用小寫字母表示終結(jié)符。

⑴左遞歸規(guī)則：x=ε，U→Uy（ε表示空串）

⑵右遞歸規(guī)則：y=ε，U→xU③間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。例：V→Uy|Z，U→xV

因存在推導(dǎo)V

Uy

xVy，故存在間接遞歸。

⑴間接左遞歸：若x=ε，則V

Vy。

⑵間接右遞歸：若y=ε，則V

xU。④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱為遞歸文法。利用遞歸文法，可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。843.2 上下文無關(guān)文法

形式語言的奠基人喬姆斯基（Chomsky）將文法分為4種類型，它們是：短語文法（0型文法）上下文有關(guān)文法（1型文法）上下文無關(guān)文法（2型文法）正規(guī)文法（3型文法）這四種文法在形式語言中都有嚴(yán)格的定義。但對于程序設(shè)計語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計語言的語法結(jié)構(gòu)。以后，“文法”一詞若無特別說明，則指“上下文無關(guān)文法”。85㈠文法和語言一個文法G是一個四元式(VT,VN,S,P)，其中VT是一個終結(jié)符的非空有限集，終結(jié)符通常用小寫字母表示。VN是一個非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。S是一個特殊的非終結(jié)符（S∈VN），稱為開始符號。P是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。①終結(jié)符是語言的基本符號，即程序設(shè)計語言的單詞。語法分析時，終結(jié)符用單詞的種別表示。根據(jù)前面約定： 標(biāo)識符（簡單變量）： i

無符號整常數(shù)： x

無符號實(shí)常數(shù)： y

單字符單詞： 用單詞本身表示（例單詞“+”的 種別用+表示） 多字符單詞： 需特別指定（例“++”用$表示）86②非終結(jié)符表示抽象的語法單位.

例“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值語句”、“說明語句”和“程序”等。非終結(jié)符通常用大寫字母表示，也可以用帶尖括號的漢字表示。③開始符號是一個特殊的非終結(jié)符，它代表我們最感興趣的語法單位。例如討論算術(shù)表達(dá)式，那么描述算術(shù)表達(dá)式文法的開始符號就是<算術(shù)表達(dá)式>。在程序設(shè)計語言中，我們最感興趣的語法單位是<程序>。④產(chǎn)生式是定義語法單位的一種書寫規(guī)則。上下文無關(guān)文法產(chǎn)生式的左部必定是一個非終結(jié)符，該非終結(jié)符稱為左部符號。產(chǎn)生式的右部是終結(jié)符和非終結(jié)符經(jīng)有限次連接構(gòu)成的文法符號串，可以是空字ε。四種文法的區(qū)別主要是對產(chǎn)生式的左部和右部的限制不同。若干個左部符號相同的產(chǎn)生式，可合并為一個，例： A→α1|α2|……|αn，其中αi稱為A的候選式(1≤i≤n)。87

例1：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中

VT={+,-,*,/,i,x,y,(,)} VN={<算術(shù)表達(dá)式>,<項(xiàng)>,<因子>} S=<算術(shù)表達(dá)式> P={ <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>-<項(xiàng)> <算術(shù)表達(dá)式>→<項(xiàng)> <項(xiàng)>→<項(xiàng)>*<因子> <項(xiàng)>→<項(xiàng)>/<因子> <項(xiàng)>→<因子> <因子>→(<算術(shù)表達(dá)式>) <因子>→i //標(biāo)識符

<因子>→x //無符號整常數(shù)

<因子>→y //無符號實(shí)常數(shù)

}

根據(jù)上述文法，可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。88

因已約定非終結(jié)符和終結(jié)符的書寫方式，非終結(jié)符和終結(jié)符在產(chǎn)生式中一目了然，故終結(jié)符集VT