編譯原理實(shí)用教程 楊德芳 第3章 詞法分析

《編譯原理實(shí)用教程 楊德芳 第3章 詞法分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第三章詞法分析本章學(xué)習(xí)目標(biāo)詞法分析程序的主要任務(wù)是對(duì)源程序進(jìn)行掃描，從中識(shí)別出單詞。它是編譯程序的第一步，也是編譯過(guò)程中不可缺少的部分。本章的主要內(nèi)容是：正則表達(dá)式和有限自動(dòng)機(jī)文法、正規(guī)表達(dá)式、正規(guī)集及自動(dòng)機(jī)的相互轉(zhuǎn)換詞法分析器的C語(yǔ)言實(shí)現(xiàn)詞法分析器的自動(dòng)生成3.1詞法分析器與單詞符號(hào)3.1.1詞法分析詞法分析是編譯過(guò)程的第一個(gè)階段。這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)一個(gè)的單詞。編譯程序中完成詞法分析任務(wù)的程序段，稱為詞法分析程序。詞法

2、分析程序?qū)υ闯绦蜻M(jìn)行掃描，從中識(shí)別出一個(gè)個(gè)的單詞符號(hào)，因此，詞法分析程序又稱為詞法分析器，又稱掃描器。詞法分析器作為編譯程序的一部分，它與語(yǔ)法分析程序之間接口方式有兩種。一種方式是詞法分析程序獨(dú)立工作，把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上，這個(gè)文件稱為語(yǔ)法分析程序的輸入而繼續(xù)編譯，如圖3-1所示就是將詞法分析單獨(dú)作為一遍的接口方式。源程序詞法分析程序單詞序列圖3-1詞法分析單獨(dú)作為一遍取符號(hào)源程序詞法分析程序語(yǔ)法分析程序圖3-2詞法分析作為語(yǔ)法分析子程序送符號(hào)另一種方法，也是常用的一種方法就

3、是把詞法分析程序設(shè)計(jì)成一個(gè)子程序，每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)，就調(diào)用該程序。詞法分析程序每得到一次調(diào)用，就從源程序文件中讀入一個(gè)字符，直到識(shí)別出一個(gè)單詞為止。這種方法省去了中間文件。源程序詞法分析程序單詞序列圖3-1詞法分析單獨(dú)作為一遍取符號(hào)源程序詞法分析程序語(yǔ)法分析程序圖3-2詞法分析作為語(yǔ)法分析子程序送符號(hào)3.1.2單詞符號(hào)單詞符號(hào)是程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法單位和最小語(yǔ)義單位。單詞符號(hào)一般分為五類。（1）關(guān)鍵字（又稱保留字或基本字）如if，then，else，while，do，begin和end。（

4、2）標(biāo)識(shí)符，用于表示變量名、過(guò)程名等。（3）常數(shù)，如123，實(shí)數(shù)型45.67等。（4）運(yùn)算符，如+，-，*，/，<，=等。（5）界限符，如逗號(hào)、分號(hào)和括號(hào)等。程序設(shè)計(jì)語(yǔ)言中的關(guān)鍵字、運(yùn)算符和界限符的數(shù)量都是確定的。而常數(shù)和標(biāo)識(shí)符的數(shù)量是不確定的。1．單詞類別的表示單詞類別表示單詞的種類，它是語(yǔ)法分析所需要的信息。一個(gè)語(yǔ)言的單詞符號(hào)如何劃分種類、分為幾種，如何編碼都屬于技術(shù)性的問(wèn)題，主要取決于處理上的方便。單詞符號(hào)有5個(gè)類別：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符和界限符，可以用1、2、3、4、5來(lái)表示。也可以用一字

5、符一類別碼的編碼形式，如保留字可以采用一字一類別。分界符也可以采用一字一類別。對(duì)于一字一類別的單詞，單詞的類型就是單詞的自身值，詞法分析程序就不必輸出其值了。常數(shù)的自身值是其自身的二進(jìn)制。2．單詞的自身值單詞自身的值是編譯程序中其他階段所需要的信息。對(duì)于單詞符號(hào)來(lái)說(shuō)，如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么這個(gè)單詞符號(hào)，其種別就安全地代表了它的自身值。如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)該給出單詞符號(hào)自身的值，以便把同一種單詞區(qū)別開(kāi)來(lái)。注意，標(biāo)識(shí)符自身的值就是標(biāo)識(shí)

6、符自身的字符串。而常數(shù)自身的值是常數(shù)本身的二進(jìn)制數(shù)值。3.1.3一個(gè)簡(jiǎn)單的詞法分析程序的設(shè)計(jì)1．預(yù)處理詞法分析器在識(shí)別單詞符號(hào)之前，需要對(duì)輸入?yún)^(qū)的源程序進(jìn)行預(yù)處理。預(yù)處理包括刪除無(wú)用的空格、跳格、回車和換行等編輯性字符以及注釋部分。每一次對(duì)一串定長(zhǎng)的輸入字符進(jìn)行預(yù)處理，并裝進(jìn)一個(gè)指定的緩沖區(qū)。2．狀態(tài)轉(zhuǎn)換圖利用狀態(tài)轉(zhuǎn)換圖可以設(shè)計(jì)詞法分析器。狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖，僅包含有限個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一個(gè)狀態(tài)，其中有一個(gè)初始結(jié)點(diǎn)，至少有一個(gè)終態(tài)結(jié)點(diǎn)，結(jié)點(diǎn)間弧的標(biāo)記是輸入字符或字符類。例3.2有狀態(tài)轉(zhuǎn)換圖3-4所示

7、，其中，0結(jié)點(diǎn)用‘S’標(biāo)記，表示初態(tài)結(jié)點(diǎn)；2結(jié)點(diǎn)用‘E’標(biāo)記，表示終態(tài)結(jié)點(diǎn)。從初態(tài)結(jié)點(diǎn)出發(fā)到某一終態(tài)結(jié)點(diǎn)所經(jīng)過(guò)的路徑，稱為能為該狀態(tài)轉(zhuǎn)換圖所接受的符號(hào)串。012SE字母其它字符圖3-4掃描緩沖區(qū)字母或數(shù)字012SE字母非字母、數(shù)字35678146174E數(shù)字?jǐn)?shù)字+——*—=—（）；/其他EEEEEEE11109非數(shù)字126136166156EEEE非**=—非=圖3-6識(shí)別各類單詞符號(hào)的狀態(tài)集合字母或數(shù)字—+++++++++++E+詞法分析程序的構(gòu)造如下：初始化：arr：=′′;getch;getnbc;

8、casechof′a′‥′z′:beginwhileletterordigitdobeginconcat;getchend;retract;c:=reserve;ifc=0thenreturn(1，arr);elsereturn(c,);end;′0′‥′9′:beginwhiledigitdobeginconcat;getch;end;retract;return(2,dtb);end;′+′:return(31,);′－′