ch4詞法分析(張素琴)

《ch4詞法分析(張素琴)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、詞法分析程序的設(shè)計(jì)單詞的描述工具單詞的識(shí)別系統(tǒng)實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造第4章詞法分析4.1詞法分析(lexicalanalysis)程序設(shè)計(jì)逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留關(guān)鍵字、標(biāo)識(shí)符、常量、運(yùn)算符、標(biāo)點(diǎn)符號(hào)、分界符等。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。也可和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。4.1.1詞法分析程序和語(yǔ)法分析程序的關(guān)系源程序詞法分析程序語(yǔ)法分析程序Tokeng

2、ettoken….4.1.2詞法分析程序的主要任務(wù)及輸出讀源程序，產(chǎn)生用二元組表示的單詞符號(hào)(單詞種類，單詞自身的值)。單詞種類是語(yǔ)法分析需要的信息，單詞自身的值是語(yǔ)義分析和代碼生成階段需要的信息。如consti=25,yes=1;兩個(gè)單詞種類是常數(shù)，常數(shù)值分別為25,1.濾掉空格，跳過(guò)注釋、換行符記錄源程序的行號(hào)，以便出錯(cuò)處理程序準(zhǔn)確定位源程序的錯(cuò)誤宏展開(kāi)等……詞法分析程序的主要任務(wù)讀源程序，產(chǎn)生用二元組表示的單詞符號(hào)(單詞種別，單詞自身的值)。對(duì)某些單詞來(lái)說(shuō)，不僅僅需要它的值，還需要其它信息以方便代碼生成

3、。如標(biāo)識(shí)符還需要記載它的層次，類別(整形、實(shí)形、布爾等)，這些屬性都收集到一個(gè)符號(hào)表中?？梢詫⒃~法分析輸出的單詞二元表示設(shè)計(jì)成(標(biāo)識(shí)符,指向該標(biāo)示符所在符號(hào)表中位置指針)。6界符和運(yùn)算符:常數(shù)可統(tǒng)歸一類，也可按類型（整型、實(shí)型、布爾型等），每個(gè)類型的常數(shù)劃分成一類。一類型一碼。所有的標(biāo)識(shí)符分為一類。一類一碼。詞類編碼原則:一字一碼。7表1單詞詞類編碼8對(duì)于關(guān)鍵字、界符、運(yùn)算符來(lái)說(shuō)，它們的詞類編碼就可以表示其完整的信息，故對(duì)于這類單詞，其單詞自身的屬性值通常為空對(duì)于標(biāo)識(shí)符，詞類編碼所反映的信息不夠充分，標(biāo)識(shí)符的

4、具體特性還要通過(guò)單詞自身的屬性進(jìn)行互相區(qū)分。標(biāo)識(shí)符的單詞自身的屬性常用其在符號(hào)表中的入口指針來(lái)表示對(duì)于常數(shù)，其單詞自身的屬性常用其在常數(shù)表中的入口指針來(lái)表示4.1.3詞法分析工作分離的考慮簡(jiǎn)化設(shè)計(jì)改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性10詞法分析的設(shè)計(jì)形式(1)設(shè)計(jì)成一個(gè)獨(dú)立程序，完成詞法分析的任務(wù)，結(jié)果以文件的形式組織，做為語(yǔ)法分析的輸入源程序詞法分析符號(hào)表TOKEN字錯(cuò)誤信息11詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼生成源程序中間代碼符號(hào)表管理錯(cuò)誤的診查處理(2)作為語(yǔ)法分析和語(yǔ)義分析的子程序用正規(guī)文法或者正則表

5、達(dá)式描述單詞符號(hào)的詞法構(gòu)成4.2.1正規(guī)文法正規(guī)(3型)文法G=(VN,VT,P,S),其中P中的產(chǎn)生式的形式為A→?B或者A→?，其中A和B是非終結(jié)符號(hào)，??VT*。高級(jí)語(yǔ)言中幾類單詞的3型文法描述：標(biāo)識(shí)符、無(wú)符號(hào)整數(shù)、運(yùn)算符、標(biāo)點(diǎn)符號(hào)、關(guān)鍵詞、無(wú)符號(hào)實(shí)數(shù)等。4.2單詞的描述工具124.2.2正規(guī)式正規(guī)式也稱正則表達(dá)式,是描述單詞的構(gòu)成語(yǔ)法的有效工具，是定義正規(guī)集的數(shù)學(xué)工具。正規(guī)表達(dá)式（regularexpression）是說(shuō)明單詞的模式(pattern)的一種重要的表示法（記號(hào)），用以描述單詞符號(hào)。正規(guī)式

6、的遞歸定義(1)?和?都是字母表?上的正規(guī)式，對(duì)應(yīng)正規(guī)集為{?}和?；(2)任何a??,a是?上的一個(gè)正規(guī)式，表示的正規(guī)集分別為{a}；(3)假設(shè)e1和e2都是?上的正規(guī)式，表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，則(e1),e1

7、e2,e1.e2,e1*都是?上的正規(guī)式,它們表示的正規(guī)集分別為L(zhǎng)(e1)，L(e1)?L(e2),L(e1)L(e2),(L(e1))*；(4)僅由有限次使用上述三步驟定義的表達(dá)式才是?上的正規(guī)式，僅有這些正規(guī)式表示的子集才是?上的正規(guī)集。*.

8、三個(gè)符號(hào)的優(yōu)先級(jí)一次降低，都是左

9、結(jié)合的正規(guī)式等價(jià)：如果它們所表示的正規(guī)集相同，稱兩個(gè)正規(guī)式等價(jià)正規(guī)式服從的代數(shù)規(guī)律：或交換律或的可結(jié)合律連接的可結(jié)合律分配律或的抽取律存在連接的恒等元素?教科書p53例1.?={a，b}，?上的正規(guī)式和相應(yīng)的正規(guī)集aa?bab(a?b)(a?b)a?(a?b)?(a?b)?(aa?bb)(a?b)?{a}{a,b}{ab}{aa,ab,ba,bb}{?,a,aa,……任意個(gè)a的串}{?,a,b,aa,ab,bb……所有由a和b組成的串}{??上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}例2.令?={l，d}

10、，則?上的正規(guī)式r=l(l?d)?定義的正規(guī)集為:{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式即是字母(字母

11、數(shù)字)?,它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,就是程序設(shè)計(jì)語(yǔ)言允許的標(biāo)識(shí)符詞法規(guī)則.例3.?={d，.，e，+，-},則?上的正規(guī)式d?(.dd???)(e(+?-??)dd???)表示的是無(wú)符號(hào)數(shù)的集合。其中d為0~9的數(shù)字。4.2.3正規(guī)文