編譯原理課件

編譯原理編譯原理1概論詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成優(yōu)化目標(biāo)代碼生成概論2一.概論1.1翻譯程序

匯編程序：源語(yǔ)言為匯編語(yǔ)言，目標(biāo)語(yǔ)言為

機(jī)器語(yǔ)言

編譯程序：源語(yǔ)言為高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言為

某臺(tái)計(jì)算機(jī)上的匯編語(yǔ)言或機(jī)器 語(yǔ)言

解釋程序：能夠按源程序的動(dòng)態(tài)順序逐句進(jìn) 行分析解釋，根據(jù)語(yǔ)句功能翻譯 成與該語(yǔ)句相應(yīng)的機(jī)器指令序 列，并立即執(zhí)行，直至結(jié)束。翻譯程序源程序目標(biāo)程序翻譯程序一.概論1.1翻譯程序翻譯程序源程序目標(biāo)程序翻31.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）編譯途徑即是將一份源程序從頭至尾翻譯成某臺(tái)計(jì)算機(jī)上的機(jī)器語(yǔ)言表示的目標(biāo)程序，然后執(zhí)行該目標(biāo)程序得到運(yùn)行結(jié)果，并允許重復(fù)執(zhí)行若干次。編譯的轉(zhuǎn)換過(guò)程兩階段轉(zhuǎn)換：編譯——運(yùn)行源程序編譯程序目標(biāo)代碼編譯時(shí)初始數(shù)據(jù)運(yùn)行子程序目標(biāo)代碼計(jì)算結(jié)果運(yùn)行時(shí)1.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）編譯途徑即是將41.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）解釋途徑即是對(duì)于源程序的一個(gè)語(yǔ)句，把它翻譯成相應(yīng)的機(jī)器語(yǔ)言，并讓計(jì)算機(jī)立即執(zhí)行。如果需要數(shù)據(jù)時(shí)，則提示用戶輸入初始數(shù)據(jù)，并立即進(jìn)行處理。解釋途徑就是邊解釋邊執(zhí)行，直至源程序動(dòng)態(tài)處理完畢為止。當(dāng)用高級(jí)語(yǔ)言編寫的源程序輸入計(jì)算機(jī)后，鍵入運(yùn)行程序命令，則解釋程序就對(duì)源程序逐條翻譯，翻譯一條立即執(zhí)行一條。該途徑不產(chǎn)生目標(biāo)代碼程序，故占用內(nèi)存較少，但執(zhí)行速度要慢些。解釋程序源程序結(jié)果初始數(shù)據(jù)1.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）解釋途徑即是對(duì)51.4編譯程序的結(jié)構(gòu)

詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代碼生成優(yōu)化目標(biāo)代碼生成源程序目標(biāo)代碼表格管理出錯(cuò)處理1.4編譯程序的結(jié)構(gòu)

詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代6二.詞法分析2.1任務(wù)輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞及其有關(guān)屬性，并轉(zhuǎn)換成屬性字，這也就是詞法分析的輸出。2.2單詞是高級(jí)語(yǔ)言中有實(shí)在意義的最小語(yǔ)法單位，它由字符構(gòu)成。2.3屬性字指單詞的一種機(jī)內(nèi)表示單詞類別單詞屬性值二.詞法分析2.1任務(wù)單詞類別單詞屬性值72.4詞法分析程序與語(yǔ)法分析程序的接口方式 詞法分析程序是編譯第一階段的工作。詞法分析工作可以是獨(dú)立的一遍，把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上，這個(gè)文件做為語(yǔ)法分析程序的輸入而繼續(xù)編譯過(guò)程。 而更一般的情況，常將詞法分析程序設(shè)計(jì)成一個(gè)子程序，每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)，則調(diào)用該子程序。詞法程序每得到一次調(diào)用，便從源程序文件中賭徒一些字符，直到識(shí)別出一個(gè)單詞，或者直到下一單詞的第一個(gè)字符為止。這中設(shè)計(jì)方案中，詞法分析程序和語(yǔ)法分析程序放在同一遍里，而省掉了中間文件。2.4詞法分析程序與語(yǔ)法分析程序的接口方式8字符串表示的源程序詞法分析器字符單詞符號(hào)取下一個(gè)單詞符號(hào)語(yǔ)法分析器字符串詞字符單詞符號(hào)取下一個(gè)語(yǔ)9編譯原理課件102.語(yǔ)法分析2.1任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，逐一分析詞法分析時(shí)得到的屬性字，檢查語(yǔ)法錯(cuò)誤，若沒(méi)有錯(cuò)誤，則給出正確的語(yǔ)法結(jié)構(gòu)（如短語(yǔ)、子句、句子、程序段、程序等）。2.2語(yǔ)法規(guī)則：語(yǔ)言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語(yǔ)、語(yǔ)句、過(guò)程和程序。2.語(yǔ)法分析2.1任務(wù)：112.3語(yǔ)法分析的方法2.3.1自下而上分析法(Bottom-up)基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直到文法的開(kāi)始符號(hào)。即從樹(shù)末端開(kāi)始，構(gòu)造語(yǔ)法樹(shù)。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語(yǔ)法分析。適合分析表達(dá)式。LR分析法：規(guī)范歸約2.3語(yǔ)法分析的方法2.3.1自下而上分析法(Bottom12G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEEG(E)：Ei|E+E|E-E|E*E|132.3.2自上而下分析法(Top-down)基本思想：它從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。遞歸下降分析法：對(duì)每一語(yǔ)法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語(yǔ)法單位，通過(guò)子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。預(yù)測(cè)分析程序優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。2.3.2自上而下分析法(Top-down)14自上而下分析面臨的問(wèn)題要消除文法的左遞歸性克服回溯例：下列文法含有直接左遞歸： S→Sa S→b 所能產(chǎn)生的語(yǔ)言L={|n0}，對(duì)輸入串baaaa#是該語(yǔ)言的句子，但用自頂向下分析時(shí)可看出當(dāng)輸入符為b時(shí)，為與b匹配應(yīng)選用S→b來(lái)推導(dǎo)，這樣就推不出后面部分，若用S→Sa則無(wú)法確定到什么時(shí)候才用S→b替換。n自上而下分析面臨的問(wèn)題n15左遞歸的消除對(duì)上例的直接左遞歸可改寫為右遞歸，如對(duì)上例的文法可改寫為：改寫后的文法和原文法產(chǎn)生的語(yǔ)言相同。左遞歸的消除對(duì)上例的直接左遞歸可改寫為右遞歸，如對(duì)上例的文法16回溯的消除為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無(wú)疑的?；厮莸南秊榱讼厮菥捅仨毐ＷC：對(duì)文法的任何非終結(jié)符，當(dāng)要17提取公共左因子:假定關(guān)于A的規(guī)則是A→1|2|…|n|1|2|…|m (其中，每個(gè)

不以開(kāi)頭)那么，可以把這些規(guī)則改寫成A→A|1|2|…|mA→1|2|…|n經(jīng)過(guò)反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。提取公共左因子:182.4LL(1)文法的判斷

當(dāng)需要選用自頂向下分析技術(shù)時(shí)，首先必須判別所給文法是否是LL(1)文法。因而我們對(duì)任給文法需計(jì)算FIRST,FOLLOW,SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L(1)文法。實(shí)質(zhì):對(duì)于文法G[S],其每個(gè)非終結(jié)符號(hào)的不同規(guī)則具有不相交的可選集Select,則稱該文法為L(zhǎng)L(1)文法.A→X1︱X2︱…︱XnSelect(A→Xi)∩Select(A→Xj)=(空集)(i≠j)2.4LL(1)文法的判斷 當(dāng)需要選用自頂向下分析技19FIRST集合定義令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選定義它的終結(jié)首符集FIRST()為：

特別是，若，則規(guī)定FIRST()。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選i和jFIRST(i)∩FIRST(j)＝當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。FIRST集合定義令G是一個(gè)不含左遞歸的文法，對(duì)G的所20FOLLOW集合定義假定S是文法G的開(kāi)始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定＃FOLLOW(A)FOLLOW集合定義假定S是文法G的開(kāi)始符號(hào)，對(duì)于G的任何非21可選集Select設(shè)文法G[S],并有規(guī)則A→（為符號(hào)串）則該規(guī)則的可選集為

定義Select（A→）=｛Follow(A)First()，當(dāng)為空符號(hào)串First()，當(dāng)不為空符號(hào)串可選集Select設(shè)文法G[S],并有規(guī)則A→（為符號(hào)22例：文法G[E]E→E+T︱TT→T*F︱FF→（E）︱iSellect（E→T）=First（T）=｛（，i｝Sellect（F→（E））=First（（E））=｛（｝Sellect（E→E+T）=First（E+T）=｛（，i｝Sellect（T→T*F）=First（T*F）=｛（，i｝Sellect（T→F）=First（F）=｛（，i｝例：文法G[E]E→E+T︱TSellect（E→T）=23構(gòu)造預(yù)測(cè)分析表 對(duì)每個(gè)終結(jié)符或#號(hào)用a表示。若則把放入M[A,a]中。把所有無(wú)定義的M[A,a]標(biāo)上出錯(cuò)標(biāo)記。構(gòu)造預(yù)測(cè)分析表 對(duì)每個(gè)終結(jié)符或#號(hào)用a表示。24例：對(duì)于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測(cè)分析：例：對(duì)于文法G(E)25步驟

符號(hào)棧

輸入串

所用產(chǎn)生式0 #E i1*i2+i3#1 #ET i1*i2+i3# E→TE2 #ETF i1*i2+i3# T→FT3 #ETi i1*i2+i3# F→i步驟 符號(hào)棧 輸入串 所用產(chǎn)生式26步驟

符號(hào)棧

輸入串

所用產(chǎn)生式3 #ETi i1*i2+i3# F→i4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i步驟 符號(hào)棧 輸入串 所用產(chǎn)生式27步驟

符號(hào)棧

輸入串

所用產(chǎn)生7 #ETi i2+i3#F→i8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#步驟 符號(hào)棧 輸入串 所用產(chǎn)生28步驟

符號(hào)棧

輸入串

所用產(chǎn)生11 #ET i3#12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→步驟 符號(hào)棧 輸入串 所用產(chǎn)生293.語(yǔ)義分析任務(wù)對(duì)語(yǔ)法分析識(shí)別出的各類語(yǔ)法范疇，分析其含義，進(jìn)行和初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間的一種代碼。分為兩階段工作對(duì)每種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查若語(yǔ)義正確，就進(jìn)行中間代碼的翻譯中間代碼形式四元式、三元式、逆波蘭式3.語(yǔ)義分析任務(wù)30“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。這種記號(hào)系統(tǒng)或者與現(xiàn)代計(jì)算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算機(jī)的機(jī)器指令?！胺g”工作僅僅在這里才開(kāi)始涉及到。常用的中間代碼如：三元式、四元式、逆波蘭式

算符左操作數(shù)右操作數(shù)

結(jié)果“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)“翻譯”工作僅僅在31例如x=2*a+b三元式(*,2,a)(2)(+,(1),b)(3)(=,(2),x)四元式(*,2,a,t1)(2)(+,t1,b,t2)(3)(=,t2,/,x)例如x=2*a+b三元式四元式32如上述源程序經(jīng)語(yǔ)義分析得到下列中間代碼程序Voidjisuan(){floatr,s,c;s=3.14*r*r;c=2*3.14*r;}（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，3.14）（5）（*，（4），r）（6）（：=，（5），c）如上述源程序經(jīng)語(yǔ)義分析得到下列中間代碼程序Voidji33如上述源程序經(jīng)代碼優(yōu)化得到下列中間代碼程序Voidjisuan(){floatr,s,c;s=3.14*r*r;c=2*3.14*r;}（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，3.14）（5）（*，（4），r）（6）（：=，（5），c）（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，（1））（5）（：=，（4），c）如上述源程序經(jīng)代碼優(yōu)化得到下列中間代碼程序Voidji344.優(yōu)化任務(wù)對(duì)前面產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生更為高效的目標(biāo)代碼。原則：等價(jià)變換主要方面公共子表達(dá)式的提取、合并已知量、刪除無(wú)用語(yǔ)句、循環(huán)優(yōu)化等。4.優(yōu)化任務(wù)354.1合并常量運(yùn)算當(dāng)運(yùn)算分量為常量時(shí)，立即計(jì)算出運(yùn)算結(jié)果，而不生成目標(biāo)代碼。i:=10;j:=2*i+5;k:=2*i+j

優(yōu)化前(:=,10,i)(2)(*,2,i)(3)(+,5,(2))(4)(:=,(3),j)(5)(*,2,i)(6)(+,(5),(4))(7)(:=,(6),k)優(yōu)化后(1)(:=,10,i)(2)(:=,25,j)(3)(:=,45,k)4.1合并常量運(yùn)算當(dāng)運(yùn)算分量為常量時(shí)，立即計(jì)算出i:=10;364.2外提循環(huán)中的不變表達(dá)式指該表達(dá)式中的所有運(yùn)算分量是常量或者是關(guān)于該循環(huán)的區(qū)域常量。fori:=1to100dobegina:=(x+y)*i;b:=(x-y)*i;s:=a*b;end

t1:=x+y;t2:=x-y;fori:=1to100dobegina:=t1*i;b:=t2*i;s:=a*b;end

x+y和x-y是不變表達(dá)式，被重復(fù)執(zhí)行100次4.2外提循環(huán)中的不變表達(dá)式指該表達(dá)式中的所有運(yùn)算分量是常374.3削減運(yùn)算強(qiáng)度把強(qiáng)度大的運(yùn)算改為強(qiáng)度小的運(yùn)算如*/改為+-fori:=1to100dos:=i*b;

執(zhí)行100次*s:=0;fori:=1to100dos:=s+b;

執(zhí)行100次+4.3削減運(yùn)算強(qiáng)度把強(qiáng)度大的運(yùn)算改為強(qiáng)度小的運(yùn)算如*/改385.目標(biāo)代碼生成任務(wù)把經(jīng)過(guò)優(yōu)化的中間代碼轉(zhuǎn)化成特定機(jī)器上的低級(jí)語(yǔ)言代碼目標(biāo)代碼的形式絕對(duì)指令代碼:可立即執(zhí)行的目標(biāo)代碼。匯編指令代碼：匯編語(yǔ)言程序，需要通過(guò)匯編程序匯編后才能運(yùn)行。可重定位指令代碼：先將各目標(biāo)模塊連接起來(lái)，確定變量、常數(shù)在主存中的位置，裝入主存后才能成為可以運(yùn)行的絕對(duì)指令代碼。5.目標(biāo)代碼生成任務(wù)39一個(gè)實(shí)例通過(guò)設(shè)計(jì)和實(shí)現(xiàn)能夠正確對(duì)IF-THEN-ELSE的語(yǔ)句進(jìn)行詞法，語(yǔ)法及語(yǔ)義分析的程序，加深對(duì)整個(gè)編譯過(guò)程的理解。一個(gè)實(shí)例通過(guò)設(shè)計(jì)和實(shí)現(xiàn)能夠正確對(duì)IF-THEN-E40（1）詞法分析1.1.詞法分析器的輸入和輸出 輸入：所給文法的源程序字符串 輸出：二元組（單詞種別，單詞符號(hào)屬性值）構(gòu)成的序列。1.2.待分析單詞的詞法 模擬程序語(yǔ)言的單詞符號(hào)分為以下五種 關(guān)鍵字：{,},if,else,then,while,> 運(yùn)算符：+,-,*,/,=（1）詞法分析1.1.詞法分析器的輸入和輸出41界符:逗號(hào)，分號(hào)，左圓括號(hào)，右圓括號(hào)

常數(shù):這里我們只涉及int型常數(shù)

其它單詞是標(biāo)識(shí)符（ID）和整型常數(shù)(NUM),可以通過(guò)一下

正規(guī)式定義:

ID=letter(letter|digit)*

NUM=digitdigit*

制表符，換行符，空格在詞法分析階段就會(huì)過(guò)濾掉。

1.3.各種單詞的種別碼

界符:逗號(hào)，分號(hào)，左圓括號(hào)，右圓括號(hào)

常42單詞符號(hào)種別碼單詞符號(hào)種別碼{*}/if=else,then;while(>)+letter(letter|digit)*-digitdigit*單詞符號(hào)種別碼單詞符號(hào)種別碼{*}/if=else,then43（2）語(yǔ)法分析 2.1根據(jù)需求設(shè)計(jì)如下文法：G=(VN,VT,S,P),VN={S,E,B,N},VT={if,then,else,>,a,b,x},P有下列產(chǎn)生式組成:S->ifEthenB1elseB2E->id1Nid2B->id1NnumN->>此文法中a,b,x指的是程序中的變量（2）語(yǔ)法分析 2.1根據(jù)需求設(shè)計(jì)如下文法：44結(jié)束語(yǔ)當(dāng)你盡了自己的最大努力時(shí)，失敗也是偉大的，所以不要放棄，堅(jiān)持就是正確的。WhenYouDoYourBest,FailureIsGreat,SoDon'TGiveUp,StickToTheEnd結(jié)束語(yǔ)45謝謝大家榮幸這一路，與你同行It'SAnHonorToWalkWithYouAllTheWay演講人：XXXXXX時(shí)間：XX年XX月XX日

謝謝大家演講人：XXXXXX46編譯原理編譯原理47概論詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成優(yōu)化目標(biāo)代碼生成概論48一.概論1.1翻譯程序

匯編程序：源語(yǔ)言為匯編語(yǔ)言，目標(biāo)語(yǔ)言為

機(jī)器語(yǔ)言

編譯程序：源語(yǔ)言為高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言為

某臺(tái)計(jì)算機(jī)上的匯編語(yǔ)言或機(jī)器 語(yǔ)言

解釋程序：能夠按源程序的動(dòng)態(tài)順序逐句進(jìn) 行分析解釋，根據(jù)語(yǔ)句功能翻譯 成與該語(yǔ)句相應(yīng)的機(jī)器指令序 列，并立即執(zhí)行，直至結(jié)束。翻譯程序源程序目標(biāo)程序翻譯程序一.概論1.1翻譯程序翻譯程序源程序目標(biāo)程序翻491.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）編譯途徑即是將一份源程序從頭至尾翻譯成某臺(tái)計(jì)算機(jī)上的機(jī)器語(yǔ)言表示的目標(biāo)程序，然后執(zhí)行該目標(biāo)程序得到運(yùn)行結(jié)果，并允許重復(fù)執(zhí)行若干次。編譯的轉(zhuǎn)換過(guò)程兩階段轉(zhuǎn)換：編譯——運(yùn)行源程序編譯程序目標(biāo)代碼編譯時(shí)初始數(shù)據(jù)運(yùn)行子程序目標(biāo)代碼計(jì)算結(jié)果運(yùn)行時(shí)1.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）編譯途徑即是將501.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）解釋途徑即是對(duì)于源程序的一個(gè)語(yǔ)句，把它翻譯成相應(yīng)的機(jī)器語(yǔ)言，并讓計(jì)算機(jī)立即執(zhí)行。如果需要數(shù)據(jù)時(shí)，則提示用戶輸入初始數(shù)據(jù)，并立即進(jìn)行處理。解釋途徑就是邊解釋邊執(zhí)行，直至源程序動(dòng)態(tài)處理完畢為止。當(dāng)用高級(jí)語(yǔ)言編寫的源程序輸入計(jì)算機(jī)后，鍵入運(yùn)行程序命令，則解釋程序就對(duì)源程序逐條翻譯，翻譯一條立即執(zhí)行一條。該途徑不產(chǎn)生目標(biāo)代碼程序，故占用內(nèi)存較少，但執(zhí)行速度要慢些。解釋程序源程序結(jié)果初始數(shù)據(jù)1.2源程序執(zhí)行的途徑（編譯途徑、解釋途徑）解釋途徑即是對(duì)511.4編譯程序的結(jié)構(gòu)

詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代碼生成優(yōu)化目標(biāo)代碼生成源程序目標(biāo)代碼表格管理出錯(cuò)處理1.4編譯程序的結(jié)構(gòu)

詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代52二.詞法分析2.1任務(wù)輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞及其有關(guān)屬性，并轉(zhuǎn)換成屬性字，這也就是詞法分析的輸出。2.2單詞是高級(jí)語(yǔ)言中有實(shí)在意義的最小語(yǔ)法單位，它由字符構(gòu)成。2.3屬性字指單詞的一種機(jī)內(nèi)表示單詞類別單詞屬性值二.詞法分析2.1任務(wù)單詞類別單詞屬性值532.4詞法分析程序與語(yǔ)法分析程序的接口方式 詞法分析程序是編譯第一階段的工作。詞法分析工作可以是獨(dú)立的一遍，把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上，這個(gè)文件做為語(yǔ)法分析程序的輸入而繼續(xù)編譯過(guò)程。 而更一般的情況，常將詞法分析程序設(shè)計(jì)成一個(gè)子程序，每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)，則調(diào)用該子程序。詞法程序每得到一次調(diào)用，便從源程序文件中賭徒一些字符，直到識(shí)別出一個(gè)單詞，或者直到下一單詞的第一個(gè)字符為止。這中設(shè)計(jì)方案中，詞法分析程序和語(yǔ)法分析程序放在同一遍里，而省掉了中間文件。2.4詞法分析程序與語(yǔ)法分析程序的接口方式54字符串表示的源程序詞法分析器字符單詞符號(hào)取下一個(gè)單詞符號(hào)語(yǔ)法分析器字符串詞字符單詞符號(hào)取下一個(gè)語(yǔ)55編譯原理課件562.語(yǔ)法分析2.1任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，逐一分析詞法分析時(shí)得到的屬性字，檢查語(yǔ)法錯(cuò)誤，若沒(méi)有錯(cuò)誤，則給出正確的語(yǔ)法結(jié)構(gòu)（如短語(yǔ)、子句、句子、程序段、程序等）。2.2語(yǔ)法規(guī)則：語(yǔ)言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語(yǔ)、語(yǔ)句、過(guò)程和程序。2.語(yǔ)法分析2.1任務(wù)：572.3語(yǔ)法分析的方法2.3.1自下而上分析法(Bottom-up)基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直到文法的開(kāi)始符號(hào)。即從樹(shù)末端開(kāi)始，構(gòu)造語(yǔ)法樹(shù)。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語(yǔ)法分析。適合分析表達(dá)式。LR分析法：規(guī)范歸約2.3語(yǔ)法分析的方法2.3.1自下而上分析法(Bottom58G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEEG(E)：Ei|E+E|E-E|E*E|592.3.2自上而下分析法(Top-down)基本思想：它從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。遞歸下降分析法：對(duì)每一語(yǔ)法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語(yǔ)法單位，通過(guò)子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。預(yù)測(cè)分析程序優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。2.3.2自上而下分析法(Top-down)60自上而下分析面臨的問(wèn)題要消除文法的左遞歸性克服回溯例：下列文法含有直接左遞歸： S→Sa S→b 所能產(chǎn)生的語(yǔ)言L={|n0}，對(duì)輸入串baaaa#是該語(yǔ)言的句子，但用自頂向下分析時(shí)可看出當(dāng)輸入符為b時(shí)，為與b匹配應(yīng)選用S→b來(lái)推導(dǎo)，這樣就推不出后面部分，若用S→Sa則無(wú)法確定到什么時(shí)候才用S→b替換。n自上而下分析面臨的問(wèn)題n61左遞歸的消除對(duì)上例的直接左遞歸可改寫為右遞歸，如對(duì)上例的文法可改寫為：改寫后的文法和原文法產(chǎn)生的語(yǔ)言相同。左遞歸的消除對(duì)上例的直接左遞歸可改寫為右遞歸，如對(duì)上例的文法62回溯的消除為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無(wú)疑的。回溯的消除為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要63提取公共左因子:假定關(guān)于A的規(guī)則是A→1|2|…|n|1|2|…|m (其中，每個(gè)

不以開(kāi)頭)那么，可以把這些規(guī)則改寫成A→A|1|2|…|mA→1|2|…|n經(jīng)過(guò)反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。提取公共左因子:642.4LL(1)文法的判斷

當(dāng)需要選用自頂向下分析技術(shù)時(shí)，首先必須判別所給文法是否是LL(1)文法。因而我們對(duì)任給文法需計(jì)算FIRST,FOLLOW,SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L(1)文法。實(shí)質(zhì):對(duì)于文法G[S],其每個(gè)非終結(jié)符號(hào)的不同規(guī)則具有不相交的可選集Select,則稱該文法為L(zhǎng)L(1)文法.A→X1︱X2︱…︱XnSelect(A→Xi)∩Select(A→Xj)=(空集)(i≠j)2.4LL(1)文法的判斷 當(dāng)需要選用自頂向下分析技65FIRST集合定義令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選定義它的終結(jié)首符集FIRST()為：

特別是，若，則規(guī)定FIRST()。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選i和jFIRST(i)∩FIRST(j)＝當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。FIRST集合定義令G是一個(gè)不含左遞歸的文法，對(duì)G的所66FOLLOW集合定義假定S是文法G的開(kāi)始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定＃FOLLOW(A)FOLLOW集合定義假定S是文法G的開(kāi)始符號(hào)，對(duì)于G的任何非67可選集Select設(shè)文法G[S],并有規(guī)則A→（為符號(hào)串）則該規(guī)則的可選集為

定義Select（A→）=｛Follow(A)First()，當(dāng)為空符號(hào)串First()，當(dāng)不為空符號(hào)串可選集Select設(shè)文法G[S],并有規(guī)則A→（為符號(hào)68例：文法G[E]E→E+T︱TT→T*F︱FF→（E）︱iSellect（E→T）=First（T）=｛（，i｝Sellect（F→（E））=First（（E））=｛（｝Sellect（E→E+T）=First（E+T）=｛（，i｝Sellect（T→T*F）=First（T*F）=｛（，i｝Sellect（T→F）=First（F）=｛（，i｝例：文法G[E]E→E+T︱TSellect（E→T）=69構(gòu)造預(yù)測(cè)分析表 對(duì)每個(gè)終結(jié)符或#號(hào)用a表示。若則把放入M[A,a]中。把所有無(wú)定義的M[A,a]標(biāo)上出錯(cuò)標(biāo)記。構(gòu)造預(yù)測(cè)分析表 對(duì)每個(gè)終結(jié)符或#號(hào)用a表示。70例：對(duì)于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測(cè)分析：例：對(duì)于文法G(E)71步驟

符號(hào)棧

輸入串

所用產(chǎn)生式0 #E i1*i2+i3#1 #ET i1*i2+i3# E→TE2 #ETF i1*i2+i3# T→FT3 #ETi i1*i2+i3# F→i步驟 符號(hào)棧 輸入串 所用產(chǎn)生式72步驟

符號(hào)棧

輸入串

所用產(chǎn)生式3 #ETi i1*i2+i3# F→i4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i步驟 符號(hào)棧 輸入串 所用產(chǎn)生式73步驟

符號(hào)棧

輸入串

所用產(chǎn)生7 #ETi i2+i3#F→i8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#步驟 符號(hào)棧 輸入串 所用產(chǎn)生74步驟

符號(hào)棧

輸入串

所用產(chǎn)生11 #ET i3#12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→步驟 符號(hào)棧 輸入串 所用產(chǎn)生753.語(yǔ)義分析任務(wù)對(duì)語(yǔ)法分析識(shí)別出的各類語(yǔ)法范疇，分析其含義，進(jìn)行和初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間的一種代碼。分為兩階段工作對(duì)每種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查若語(yǔ)義正確，就進(jìn)行中間代碼的翻譯中間代碼形式四元式、三元式、逆波蘭式3.語(yǔ)義分析任務(wù)76“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。這種記號(hào)系統(tǒng)或者與現(xiàn)代計(jì)算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算機(jī)的機(jī)器指令?！胺g”工作僅僅在這里才開(kāi)始涉及到。常用的中間代碼如：三元式、四元式、逆波蘭式

算符左操作數(shù)右操作數(shù)

結(jié)果“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)“翻譯”工作僅僅在77例如x=2*a+b三元式(*,2,a)(2)(+,(1),b)(3)(=,(2),x)四元式(*,2,a,t1)(2)(+,t1,b,t2)(3)(=,t2,/,x)例如x=2*a+b三元式四元式78如上述源程序經(jīng)語(yǔ)義分析得到下列中間代碼程序Voidjisuan(){floatr,s,c;s=3.14*r*r;c=2*3.14*r;}（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，3.14）（5）（*，（4），r）（6）（：=，（5），c）如上述源程序經(jīng)語(yǔ)義分析得到下列中間代碼程序Voidji79如上述源程序經(jīng)代碼優(yōu)化得到下列中間代碼程序Voidjisuan(){floatr,s,c;s=3.14*r*r;c=2*3.14*r;}（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，3.14）（5）（*，（4），r）（6）（：=，（5），c）（1）（*，3.14，r）（2）（*，（1），r）（3）（：=，（2），s）（4）（*，2，（1））（5）（：=，（4），c）如上述源程序經(jīng)代碼優(yōu)化得到下列中間代碼程序Voidji804.優(yōu)化任務(wù)對(duì)前面產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生更為高效的目標(biāo)代碼。原則：等價(jià)變換主要方面公共子表達(dá)式的提取、合并已知量、刪除無(wú)用語(yǔ)句、循環(huán)優(yōu)化等。4.優(yōu)化任務(wù)814.1合并常量運(yùn)算當(dāng)運(yùn)算分量為常量時(shí)，立即計(jì)算出運(yùn)算結(jié)果，而不生成目標(biāo)代碼。i:=10;j:=2*i+5;k:=2*i+j

優(yōu)化前(:=,10,i)(2)(*,2,i)(3)(+,5,(2))(4)(:=,(3),j)(5)(*,2,i)(6)(+,(5),(4))(7)(:=,(6),k)優(yōu)化后(1)(:=,10,i)(2)(:=,25,j)(3)(:=,45,k)4.1合并常量運(yùn)算當(dāng)運(yùn)算分量為常量時(shí)，立即計(jì)算出i:=10;824.2外提循環(huán)中的不變表達(dá)式指該表達(dá)式中的所有運(yùn)算分量是常量或者是關(guān)于該循環(huán)的區(qū)域常量。fori:=1to100dobegina:=(x+y)*i;b:=(x-y)*i;s:=a*b;end

t1:=x+y;t2:=x-y;for