1

編譯系統(tǒng)概述

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

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

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

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

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

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

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

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

解釋方式主要特點(diǎn)是：用戶程序是消極的。用戶程序運(yùn)行時(shí)，控制點(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)檩斎耄墓ぷ鹘Y(jié)果是二進(jìn)制形式的目標(biāo)程序，但并未包括用戶程序中所使用的系統(tǒng)函數(shù)的目標(biāo)代碼。從整體上來(lái)看，程序是不完整的，程序中的部分地址尚未確定（例系統(tǒng)函數(shù)的調(diào)用）。將二進(jìn)制形式的用戶程序和系統(tǒng)函數(shù)目標(biāo)代碼連接成一個(gè)程序，對(duì)未確定的地址進(jìn)行定位。由操作系統(tǒng)將用戶程序裝入內(nèi)存后運(yùn)行。程序在運(yùn)行過(guò)程中讀入數(shù)據(jù)，經(jīng)處理加工后輸出計(jì)算結(jié)果。

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

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

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

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

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

整常數(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㈡語(yǔ)法分析(Parsing)

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

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

realA;integerB;B=A+B;end

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

realA;

integerB;B=A+B;end18②語(yǔ)義翻譯

1)說(shuō)明語(yǔ)句的翻譯 將標(biāo)識(shí)符及其屬性填入符號(hào)表。

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

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

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

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

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

常數(shù)表用于記錄在源程序中出現(xiàn)的常數(shù)。假定，每個(gè)整常數(shù)在常數(shù)表中占2個(gè)字節(jié)，每個(gè)實(shí)常數(shù)在常數(shù)表中占4個(gè)字節(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ī)器指令或匯編語(yǔ)言）依據(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)存地址（可用符號(hào)表示），C表示常數(shù)。表達(dá)式3+abc*128最終形成的匯編語(yǔ)言程序示意如下：

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

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

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

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

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

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

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

計(jì)算園柱體表面積的源程序（輸入輸出略）如下所示：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ì)算機(jī)內(nèi)存較小，只能在內(nèi)存設(shè)置長(zhǎng)度有限的緩沖區(qū)，分段讀入源程序進(jìn)行處理。在編制程序時(shí)，必須考慮由于源程序分段讀入所產(chǎn)生的問(wèn)題。例如，由多個(gè)字符構(gòu)成的單詞有可能被緩沖區(qū)邊界所打斷（留作習(xí)題）。目前計(jì)算機(jī)所使用的的內(nèi)存已超過(guò)若干年前硬盤容量，計(jì)算機(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è)部分構(gòu)成： 預(yù)處理程序 掃描器（單詞識(shí)別程序）①分成二部分的理由目前使用的程序設(shè)計(jì)語(yǔ)言大都采用自由格式書寫，允許在單詞之間存在多余的空格、換行和制表符（TAB）。源程序通常帶有注釋，注釋不是程序的必要組成部分。有些語(yǔ)言還提供續(xù)行功能（例C語(yǔ)言中的續(xù)行符'\'），當(dāng)一個(gè)單詞過(guò)長(zhǎng)（例字符串常數(shù)），可分多行列出。對(duì)于Fortran和Cobol之類語(yǔ)言，源程序還受到書寫格式的限制。

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

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

end\0...\0上述源程序經(jīng)預(yù)處理后，掃描緩沖區(qū)中的內(nèi)容如下所示：32㈢預(yù)處理例用偽代碼編寫一個(gè)預(yù)處理程序，要求如下：去除源程序中注釋（源程序中的注釋用/*……*/標(biāo)記，不允許嵌套使用）去除源程序中續(xù)行符（\）將TAB和換行符替換為空格將大寫字母變換成小寫在源程序尾部添加字符'#'，這是編譯程序內(nèi)部的一個(gè)特殊的單詞，以示源程序結(jié)束。每調(diào)用一次，將經(jīng)預(yù)處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描器識(shí)別單詞。33①算法說(shuō)明用偽代碼編寫預(yù)處理程序，輸入和預(yù)處理可同時(shí)進(jìn)行，無(wú)需輸入緩沖區(qū)，將讀入后經(jīng)預(yù)處理的源程序直接送掃描緩沖區(qū)buf[1..n]。定義布爾變量in_comment，記錄當(dāng)前處理字符是否處于注釋。若in_comment的值為false，則表示當(dāng)前讀入字符未處于注釋中，此時(shí)應(yīng)將當(dāng)前處理字符存入掃描緩沖區(qū)；若in_comment的值為true，則表示當(dāng)前處理字符處于注釋中，此時(shí)無(wú)需將該字符存入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記錄剛處理過(guò)的字符。 ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧin_comment:f………f/t…………t/f………f340.procedurepro_process() //掃描緩沖區(qū)buf[]和掃描緩沖區(qū)指針i1.old_c←‘\0’:in_comment←false:cur_c←文件第一個(gè)字符: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←文件下一個(gè)字符18.endwhile19.i←i+1:buf[i]←'#'20.endprocedure352.1.3基本字的識(shí)別和超前搜索

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

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

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

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

邏輯IF，當(dāng)M等于5轉(zhuǎn)標(biāo)號(hào)為55的語(yǔ)句。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)號(hào)為110的語(yǔ)句；當(dāng)X+Y等于0，轉(zhuǎn)標(biāo)號(hào)為120的語(yǔ)句；當(dāng)X+Y>0，轉(zhuǎn)標(biāo)號(hào)為130的語(yǔ)句顯然僅根據(jù)IF無(wú)法判斷其為何種單詞，可能是基本字，也可能是標(biāo)識(shí)符。36

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

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

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

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

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

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

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

完全形式 3.14

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

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

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

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

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

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

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

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

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

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

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

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

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)識(shí)符

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

} ………………… //其余單詞識(shí)別程序略}//endofscanner47①拼接函數(shù)concat(token[],ch)concat為拼接函數(shù)，它有二個(gè)參數(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)識(shí)符規(guī)則。考慮簡(jiǎn)化程序設(shè)計(jì)，將基本字作為一種特殊標(biāo)識(shí)符來(lái)處理。設(shè)置一個(gè)基本字表（包括相應(yīng)二元式編），當(dāng)狀態(tài)轉(zhuǎn)換圖識(shí)別出一個(gè)標(biāo)識(shí)符時(shí)，就去查對(duì)這張表，確定它是基本字還是標(biāo)識(shí)符。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)識(shí)符的單詞種別為'i'}begin}end{integerarealc0123482.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成492.2.1基本概念㈠有窮字母表∑

符號(hào)有限集，它的每個(gè)元素稱為字符。㈡字（字符串）

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

ε 空字

{} 空集

{ε} 集合僅有一個(gè)元素ε②∑*∑上所有字的全體，包括ε。例：∑={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)證明見(jiàn)本書38頁(yè)積滿足分配律 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*中的每個(gè)字都是由V中的字經(jīng)有限次連接而成。⑤（集合的）正則閉包定義：設(shè)V

Σ*，V的正則閉包記為V+，且定義V+=VV*。根據(jù)定義可以證明V+=V1∪V2∪……∪Vn(詳見(jiàn)本書18頁(yè))。設(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(zhǎng)(α)和L(β)，則α|β是正規(guī)式，其相應(yīng)正規(guī)集記為L(zhǎng)(α|β)，且令L(α|β)=L(α)∪L(β)。若α、β為正規(guī)式，相應(yīng)正規(guī)集分別記為L(zhǎng)(α)和L(β)，則αβ(或α·β)是正規(guī)式，其相應(yīng)正規(guī)集記為L(zhǎng)(αβ)，且令L(αβ)=L(α)L(β)。若α=β，則L(αβ)=L(αα)=

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

α(α|β)*

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

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

ββ*

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

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

M=(S，Σ，f，s0，Z)S是一個(gè)有限集，它的每一個(gè)元素稱為狀態(tài)。Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。f是一個(gè)從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，是唯一的一個(gè)初態(tài)。Z

S，是一個(gè)終態(tài)集。例：一個(gè)識(shí)別二進(jìn)制數(shù)的確定有限自動(dòng)機(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)換矩陣。只要對(duì)初態(tài)和終態(tài)作適當(dāng)標(biāo)記，可用一個(gè)狀態(tài)轉(zhuǎn)換矩陣來(lái)表示DFA。㈢DFAM可用一個(gè)（確定的）狀態(tài)轉(zhuǎn)換圖表示例識(shí)別二進(jìn)制數(shù)的DFA可用（確定的）狀態(tài)轉(zhuǎn)換圖表示如下：狀態(tài)/字符'0''1'011111接上例56㈣字α可為DFAM識(shí)別對(duì)于一個(gè)字α，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的路徑，且路徑上的所有弧的標(biāo)記依序連接成的字為α，則稱α可為DFAM所識(shí)別或接受。若DFAM的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則稱空字ε可為DFAM所識(shí)別或接受。DFAM所識(shí)別的字全體記為L(zhǎng)(M)。設(shè)α=1012=5

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

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

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

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

S，是一個(gè)終態(tài)集。DFA和NFA的主要區(qū)別為：映照f(shuō)（函數(shù)），DFA的映照f(shuō)是從"狀態(tài)×字符"映射到"狀態(tài)"，f為單值函數(shù)；而NFA的映照f(shuō)是從"狀態(tài)×字"映射到"狀態(tài)子集"，f為多值函數(shù)。58例某一非確定有限自動(dòng)機(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可用一個(gè)（非確定的）狀態(tài)轉(zhuǎn)換圖表示59㈢字α可為NFAM識(shí)別對(duì)于Σ*中的一個(gè)字α，若在NFAM中存在一條從某一初態(tài)到某一終態(tài)的路徑，且路徑上的所有標(biāo)記依序連接成的字為α，則稱α可為NFAM所識(shí)別或接受。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的ε道路，那么空字ε可為M所接受。非確定有限自動(dòng)機(jī)M所識(shí)別的字全體記為L(zhǎng)(M)。對(duì)于任何二個(gè)有限自動(dòng)機(jī)M和M'，若L(M)=L(M')，則稱二個(gè)有限自動(dòng)機(jī)M和M'等價(jià)。DFA是NFA的特例，對(duì)于每個(gè)NFAM存在一個(gè)DFAM'，使得L(M)=L(M')。602.2.5正規(guī)式與確定有限自動(dòng)機(jī)的等價(jià)性

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

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

V

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

DFA

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

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

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

Ia ε_(tái)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)手工計(jì)算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ù)上述算法對(duì)NFAM進(jìn)行確定化。因NFAM具有6個(gè)狀態(tài)，狀態(tài)子集個(gè)數(shù)（包括空集）最多為64，故表的長(zhǎng)度不會(huì)超過(guò)26-1=63，循環(huán)必然在有限步中結(jié)束。3）結(jié)果處理將I中的每個(gè)子集視為DFAM'的一個(gè)狀態(tài)。ε_(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)造過(guò)程采用子集法，從字的識(shí)別角度來(lái)看，DFAM'和NFAM是等價(jià)的。672.3詞法分析器的自動(dòng)生成

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

α(α|β)*無(wú)符號(hào)整常數(shù)

ββ*運(yùn)算符 單詞本身（例'='的正規(guī)式為'='，"++"的正規(guī)式為"++"）界符 單詞本身（例';'的正規(guī)式為';'）基本字通常是由字母構(gòu)成，符合標(biāo)識(shí)符規(guī)則，將基本字作為一種特殊標(biāo)識(shí)符來(lái)處理（可設(shè)置保留字表，二者區(qū)分可通過(guò)查表）。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㈢掃描器控制程序工作原理每次識(shí)別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進(jìn)入下一狀態(tài)，尋求最長(zhǎng)匹配，直到無(wú)法前進(jìn)為止，這樣始終多讀一個(gè)字符。在狀態(tài)遷移過(guò)程中，需用Token數(shù)組保存讀入字符。在無(wú)法前進(jìn)時(shí)，若發(fā)現(xiàn)當(dāng)前狀態(tài)為終態(tài)，則認(rèn)為識(shí)別出一個(gè)單詞，反之出錯(cuò)，即Token數(shù)組所保存的字符串不構(gòu)成一個(gè)單詞，而是源程序中的一個(gè)錯(cuò)誤詞形。事先設(shè)置一個(gè)單詞二元式編碼表，它包括除標(biāo)識(shí)符和整常數(shù)以外的所有單詞（基本字、運(yùn)算符和界符）。當(dāng)DFA識(shí)別出一個(gè)單詞，就根據(jù)Token數(shù)組所保存的字符串去查表。若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標(biāo)識(shí)符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。首字符為字母的是標(biāo)識(shí)符，首字符為數(shù)字的是無(wú)符號(hào)整常數(shù)。73DFA每次只能識(shí)別一個(gè)單詞，需多次使用DFA來(lái)識(shí)別源程序中單詞，直到源程序中的字符全部處理完。由于構(gòu)造的方法不同，在DFA某一個(gè)終態(tài)中，有可能包含原NFA中的二個(gè)終態(tài)或更多，即在該狀態(tài)可識(shí)別出二個(gè)詞形相似的單詞，這就存在一個(gè)優(yōu)先匹配問(wèn)題。此時(shí)，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過(guò)程，讓其先得到匹配。

設(shè)源程序?yàn)椤皒+++y#”（‘#’是預(yù)處理程序添加的），掃描器共使用確定有限自動(dòng)機(jī)5次（見(jiàn)下頁(yè)）。74從初態(tài)0出發(fā)，讀入'x'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'+'，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài)1為終態(tài)，故識(shí)別出一個(gè)單詞。查表未果，由于首字符為字母，故單詞"x"為標(biāo)識(shí)符，返回單詞二元式編碼('i',"x")并退回'+'。從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)4，在狀態(tài)4讀入'+'，進(jìn)入終態(tài)13，在狀態(tài)13讀入'+'，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài)13為終態(tài)，故識(shí)別出一個(gè)單詞。查表，確認(rèn)識(shí)別出單詞為"++"，返回單詞二元式編碼('$',"NUL")并退回'+'。從初態(tài)0出發(fā)，讀入'+'進(jìn)入狀態(tài)4，在狀態(tài)4讀入'y'，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài)4為終態(tài)，故識(shí)別出一個(gè)單詞。查表，確認(rèn)識(shí)別出單詞為"+"，返回單詞二元式編碼('+',"NUL")并退回'y'；從初態(tài)0出發(fā)，讀入'y'進(jìn)入狀態(tài)1，在狀態(tài)1讀入'#'，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài)1為終態(tài)，故識(shí)別出一個(gè)單詞。查表未果，由于首字符為字母，故單詞"y"為標(biāo)識(shí)符，返回單詞二元式編碼('i',"y")并退回'#'。從初態(tài)0出發(fā)，讀入'#'，進(jìn)入狀態(tài)10。由于無(wú)法再讀入字符，即查表，確認(rèn)識(shí)別出單詞為"#"，返回單詞二元式編碼('#',"NUL")。識(shí)別出單詞"#"意味著整個(gè)源程序中字符全部處理完畢。75㈣掃描器控制程序的實(shí)現(xiàn)⑴狀態(tài)轉(zhuǎn)換矩陣的數(shù)字化控制程序是根據(jù)DFA來(lái)工作的，首先要將狀態(tài)轉(zhuǎn)換矩陣數(shù)字化，空白用0表示。在預(yù)處理中，空格作為界符被保留下來(lái)。單詞的前導(dǎo)空格在識(shí)別一個(gè)單詞前被濾去，單詞的尾部空格用作單詞的終止標(biāo)志，故在狀態(tài)轉(zhuǎn)換矩陣中，應(yīng)增加空格列，該列每個(gè)元素的值均標(biāo)記為0。因26個(gè)字母作用相同，故可用一列表示。在查表時(shí)可將26個(gè)字母轉(zhuǎn)換成1個(gè)，例'a'。因10個(gè)數(shù)字作用相同，故可用一列表示。在查表時(shí)可將10個(gè)數(shù)字轉(zhuǎn)換成1個(gè)，例'0'。狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如下頁(yè)所示：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 //?表示單詞二元式編碼表中無(wú)14. ifToken首字符是字母thent.code=‘i‘ //是標(biāo)識(shí)符15. ifToken首字符是數(shù)字thent.code=‘x‘ //是整常數(shù)16. t.val←Token[] //此時(shí)單詞有值17. endif18. returnt 19.endprocedure793.1

文法的引入3.2

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

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

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

<主語(yǔ)><謂語(yǔ)>

<冠詞><形容詞><名詞><謂語(yǔ)>

the<形容詞><名詞><謂語(yǔ)>

thebig<名詞><謂語(yǔ)>

thebigelephant<謂語(yǔ)>

thebigelephant<動(dòng)詞><直接賓語(yǔ)>

thebigelephantate<直接賓語(yǔ)>

thebigelephantate<冠詞><名詞>

thebigelephantatea<名詞>

thebigelephantateabanana

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

<句子>

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

<句子>

abigbananaatetheelephant

所以，abigbananaatetheelephant也是文法的一個(gè)合法的句子。但意義是荒謬的，也就是說(shuō)句子的語(yǔ)義是錯(cuò)誤的。一個(gè)語(yǔ)法正確的句子不能保證其語(yǔ)義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語(yǔ)法和語(yǔ)義兩方面檢查。綜上所述，語(yǔ)言結(jié)構(gòu)通常是用文法來(lái)定義和描述，文法是由終結(jié)符、非終結(jié)符、開始符號(hào)（特殊非終結(jié)符）及產(chǎn)生式四個(gè)要素構(gòu)成。從開始符號(hào)出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱為文法所規(guī)定的語(yǔ)言83㈣遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個(gè)重要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規(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ī)則來(lái)描述無(wú)窮的語(yǔ)言，這不但解決了語(yǔ)言的定義問(wèn)題，而且使得對(duì)語(yǔ)言的語(yǔ)法檢查成為可能。843.2 上下文無(wú)關(guān)文法

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

無(wú)符號(hào)整常數(shù)： x

無(wú)符號(hào)實(shí)常數(shù)： y

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

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

<因子>→x //無(wú)符號(hào)整常數(shù)

<因子>→y //無(wú)符號(hào)實(shí)常數(shù)

}

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

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