三下編譯原理

編譯原理

(PrinciplesofCompiling)1主講：蔣宗禮辦公室：二教205電話：67392690Email：答疑與考試安排答疑時(shí)間與地點(diǎn)二教205，6月9日(星期一)全天考試時(shí)間：6月10日3-4節(jié)(9:55-11:30)考試地點(diǎn)計(jì)算機(jī)實(shí)驗(yàn)班：一教209軟件工程實(shí)驗(yàn)班：一教210一紙開卷期末80%，平時(shí)20%(實(shí)驗(yàn)+作業(yè)+課堂)2上次課主要內(nèi)容編譯優(yōu)化機(jī)器相關(guān)：目標(biāo)代碼機(jī)器無關(guān)：中間代碼基本塊全局優(yōu)化循環(huán)優(yōu)化局部?jī)?yōu)化基本塊內(nèi)的優(yōu)化3上次課主要內(nèi)容基本塊的入口語句代碼序列的第一語句轉(zhuǎn)移語句的目標(biāo)語句轉(zhuǎn)移語句的下一條語句定義基本塊一入口語句到下一入口語句之前一入口語句到轉(zhuǎn)移語句或停語句4上次課主要內(nèi)容局部?jī)?yōu)化合并已知量重新命名臨時(shí)變量公共子表達(dá)式刪除無用(死)代碼5循環(huán)優(yōu)化代碼外提強(qiáng)度削弱消除歸納變量上次課主要內(nèi)容目標(biāo)代碼生成針對(duì)目標(biāo)語言的特殊性，生成高性能的目標(biāo)代碼(機(jī)器相關(guān))充分利用寄存器輸入：中間代碼序列輸出：目標(biāo)代碼6總結(jié)7“編譯原理”是一門非常好的課程AlfredV.Aho：編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書中的原理和技術(shù)都會(huì)反復(fù)用到8“編譯原理”是一門非常好的課程最經(jīng)典、最常用的問題求解和系統(tǒng)設(shè)計(jì)思想和方法9自頂向下自底向上逐步求精遞歸求解目標(biāo)驅(qū)動(dòng)抽象與形式化描述算法設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的選擇與使用系統(tǒng)構(gòu)建模塊化一些具體的表示和變換算法自動(dòng)計(jì)算、類計(jì)算一個(gè)相當(dāng)規(guī)模的系統(tǒng)的設(shè)計(jì)(含總體結(jié)構(gòu))“編譯原理”是一門非常好的課程掌握“編譯原理”中的基本概念、基本理論、基本方法，在系統(tǒng)級(jí)上再認(rèn)識(shí)程序和算法，提升計(jì)算機(jī)問題求解的水平，增強(qiáng)系統(tǒng)能力，體驗(yàn)實(shí)現(xiàn)自動(dòng)計(jì)算的樂趣實(shí)驗(yàn)情況遞歸子程序、LL(1)、LR、自動(dòng)生成多種形式的輸入詞法分析器、語法分析器自動(dòng)生成錯(cuò)誤處理與續(xù)編譯101緒論——翻譯系統(tǒng)11RunSystemDataResultMLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResultCompilingSystem⊕1緒論——編譯程序12中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理出錯(cuò)處理中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器源程序變成一個(gè)單詞序列走向目標(biāo)1一個(gè)平滑的字符流走向目標(biāo)2走向目標(biāo)3走向目標(biāo)4走向目標(biāo)5得到語法成分！更接近機(jī)器語言更高的效率達(dá)到目標(biāo)1緒論——編譯的遍(Pass)根據(jù)系統(tǒng)資源狀況、運(yùn)行目標(biāo)的要求……等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描，在每一遍掃描中，完成不同的任務(wù)遍與階段的聯(lián)系與區(qū)別131緒論——T形圖表示語言翻譯程序的T形圖14源語言表示語言目標(biāo)語言功能1)交叉編譯/移植：用A機(jī)的C編譯構(gòu)造B機(jī)的C編譯2)本機(jī)編譯器利用：用A機(jī)的C編譯構(gòu)造A機(jī)的B編譯3)自展技術(shù)/自編譯技術(shù)4)自動(dòng)生成技術(shù)2文法與語言字母表∑：非空有窮集合字母表的乘積∑1∑2={ab|a∈∑1，b∈∑2}∑*、∑+x∈∑*,L∑*,x∈Lε語句152文法與語言文法：Ｇ=(Ｖ，T，Ｐ，Ｓ)α→β∈PBNF：∷＝,[],{}lu,{}m候選式：α→β1|β2|…|βn推導(dǎo)(派生)：αAβαγβA→γ∈

Pαβ；αnβ；α*β；α+β句型：S*αα∈(Ｖ∪T)*句子：S*x，x∈T* ε162文法與語言最左(Left-most)推導(dǎo)——最左分析左句型最左推導(dǎo)對(duì)應(yīng)最右歸約最右(Right-most)推導(dǎo)——最右分析規(guī)范推導(dǎo)、規(guī)范句型(右句型)α1α2α3……αiαi+1……αn最右推導(dǎo)對(duì)應(yīng)最左歸約(規(guī)范歸約)172文法與語言語言：L(G)＝{x｜S*

x&x∈T*}短語：如果S*αAβ+αγβ直接短語、句柄18語法(分析)樹用樹的形式表示句型的生成/結(jié)構(gòu)+id3id1id2*(語法)結(jié)構(gòu)樹/抽象語法樹去掉對(duì)(中間)代碼生成不必要的信息EE+EEEid1*id3id22文法與語言19EE*Eid3EE+id2id1二義性推導(dǎo)：兩個(gè)不同的最左推導(dǎo)；兩個(gè)不同的最右推導(dǎo)語法樹：兩棵不同的語法樹EE+EEEid1*id3id22文法與語言有的文法的二義性可以消除語言可以用不同文法產(chǎn)生20算術(shù)表達(dá)式文法2E→E+T|TT→T*F|FF→(E)|id算術(shù)表達(dá)式文法1E→E+E|E*E|(E)|id2文法與語言SaBCSaSBCCBBCaBdbBbbbCbcCccE→E+EE→E*EE→(E)E→idE→E-EE→E/E

SaBCSaSBCCBBCaBabbBbbbCbccCccS→a|bS→aT|bTT→a|bT→1|2T→aT|bTT→1T|2T21S→a|bS→Ha|HbS→H1|H2H→Ha|HbH→H1|H2H→a|b0型文法(PSG)1型文法(CSG)2型文法(CFG)3型文法(RG)3型文法(RG)文法的Chomsky體系3詞法分析詞法分析器的功能,在編譯程序中的“位置”緩沖區(qū)設(shè)計(jì)(雙緩沖)正規(guī)(表達(dá))式a|(a|b)*cc(a|b)+((0|1)(0|1))*=(00|01|10|11)*正規(guī)定義式S→((0|1)(0|1))*正規(guī)式(表達(dá)式)與正規(guī)文法等價(jià)FA(狀態(tài)轉(zhuǎn)移圖)是一個(gè)有力的工具223詞法分析詞法分析器的實(shí)現(xiàn)按狀態(tài)轉(zhuǎn)移圖設(shè)計(jì)主程序設(shè)計(jì)適當(dāng)?shù)淖映绦?3ABaAaAsr正規(guī)定義式FAA→rs*RGFAA→aBA→a4自頂向下語法分析語法分析方法分類回溯(虛假匹配)、左遞歸、二義性消除左遞歸A→Aα1|Aα2|…|Aαn|β1|β2|…|βmAβ1B|β2B

|…|βnBBα1B|α2B

|…|αnB|ε提取公共左因子A→αβ1|αβ2|…|αβn|γ1|γ2|…|γmA→αA'|γ1|γ2|…|γm和A'→β1|β2|…|βn244自頂向下語法分析LL(1)文法A→α1|α2|…|αnFIRST(αi)∩FIRST(αj)=Φi≠j當(dāng)ε∈FIRST(αj)時(shí)，F(xiàn)OLLOW(A)∩FIRST(αi)=Φ求FIRST(α)的算法α=X1X2…Xn求FOLLOW(B)的算法#∈FOLLOW(S)A→αBβ當(dāng)ε∈FIRST(β)時(shí)FOLLOW(B)=FOLLOW(B)∪(FIRST(β)–{ε})∪FOLLOW(A)254自頂向下語法分析LL(1)分析器系統(tǒng)結(jié)構(gòu)26LL(1)通用控制算法預(yù)測(cè)分析表的構(gòu)造算法

輸入緩沖區(qū)(符號(hào)序列)?？刂瞥绦騊77預(yù)測(cè)分析表M輸出的產(chǎn)生式序列表達(dá)式文法的預(yù)測(cè)分析表語法變量終極符號(hào)id+*()#EE'TT'F27E→TE'E'

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)同步記號(hào)：synch4自頂向下語法分析語法圖每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)語法圖，邊上標(biāo)記語法符號(hào)化簡(jiǎn)語法圖遞歸子程序法為每個(gè)語法變量編寫一個(gè)處理子程序28簡(jiǎn)化的語法圖29E→T(+T)*T→F(*F)*F→(E)|idET3+0T6ε10*7F13ε14F1516(Eid17)簡(jiǎn)單算術(shù)表達(dá)式的分析器Ｅ的子程序(E→T(+T)*)procedureE;beginT; T的過程調(diào)用

whilelookhead='+'do lookhead：當(dāng)前符號(hào)begin 當(dāng)前符號(hào)等于＋時(shí)

match(‘+’); 處理終結(jié)符＋

T T的過程調(diào)用

endend; 305自底向上語法分析思想從輸入串出發(fā)，反復(fù)利用產(chǎn)生式進(jìn)行歸約，如果最后能得到文法的開始符號(hào)，則輸入串是句子，否則輸入串有語法錯(cuò)誤核心尋找句型中的當(dāng)前歸約對(duì)象——“句柄”進(jìn)行歸約,用不同的方法尋找句柄，就可獲得不同的分析方法方法算符優(yōu)先分析法LR分析法31分析器結(jié)構(gòu)32

id+

id＊id#＋E#移進(jìn)歸約控制程序輸出產(chǎn)生式序列棧內(nèi)容

?

輸入緩沖區(qū)內(nèi)容＝#“當(dāng)前句型”#？LL(1)分析法棧輸入緩沖區(qū)

分析表4種操作：移進(jìn)、歸約、接受、出錯(cuò)算符優(yōu)先分析法根據(jù)當(dāng)前輸入符號(hào)a與棧頂符號(hào)b的優(yōu)先級(jí)確定動(dòng)作ifb≮athen移進(jìn)——?dú)w約對(duì)象未形成ifb≡athen移進(jìn)——?dú)w約對(duì)象未形成ifb≯athen歸約——?dú)w約對(duì)象已形成ifa=b=#then接受——分析成功Ifa與b無優(yōu)先關(guān)系then出錯(cuò)33算符優(yōu)先分析法算符文法(不含形如A→αBCβ的產(chǎn)生式)算符優(yōu)先級(jí)棧內(nèi)棧外、優(yōu)先函數(shù)算符優(yōu)先文法素短語和最左素短語句型#N1a1N2a2…

Nnan#的最左素短語是滿足下列條件的最左子串

NiaiNi+1ai+1…

NjajNj+1其中：ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+134LR分析法關(guān)鍵概念規(guī)范句型活前綴——規(guī)范句型(右句型)的不含句柄右邊任何符號(hào)的前綴句柄形成情況的表示——LR(0)項(xiàng)目：A→α.β移進(jìn)項(xiàng)目：A→α.aβ待約項(xiàng)目：A→α.Bβ歸約項(xiàng)目：A→α.35LR分析器的總體結(jié)構(gòu)36a1…ai…an#LR主控程序動(dòng)作表action轉(zhuǎn)移表goto產(chǎn)生式序列狀態(tài)/符號(hào)棧輸入緩沖區(qū)分析表SmSm-1……S1S0XmXm-1……X1#LR分析表狀態(tài)動(dòng)作表action轉(zhuǎn)移表gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r237action[s,a]goto[s,X]LR分析表的構(gòu)造拓廣文法——給出分析開始和結(jié)束狀態(tài)G=(V∪{S'},T,P∪{S'→S},S')S'V對(duì)應(yīng)S'→.S(分析開始)和S'→S.(分析成功)識(shí)別CFGG的拓廣文法的所有規(guī)范句型活前綴的DFA以項(xiàng)目集{S'→.S}的閉包為啟動(dòng)狀態(tài)分析器的狀態(tài)——某個(gè)項(xiàng)目集閉包后繼項(xiàng)目項(xiàng)目集規(guī)范族——DFA的全部狀態(tài)38I0:S'→.SS→.L=RS→.RL→.*RL→.idR→.LI1:S'→S.I2:S→L.=RR→L.LI3:S→R.RI4:L→*.RR→.LL→.*RL→.idI5:L→id.*idI6:S→L=.RR→.LL→.*RL→.id=I7:L→*R.RI8:R→L.LI9:S→L=R.R*LidSS→L=RS→RL→*RL→idR→L產(chǎn)生式編號(hào)*id核心項(xiàng)目項(xiàng)目集I的相容歸約—?dú)w約沖突移進(jìn)—?dú)w約沖突LR(0)文法——G'的LR(0)項(xiàng)目集規(guī)范族中的所有項(xiàng)目集閉包是相容的40分析表的構(gòu)造設(shè)G'的LR(0)項(xiàng)目集規(guī)范族：{I0,I1,…,In}用i表示閉包Ii對(duì)應(yīng)的分析器狀態(tài)(即相應(yīng)的DFA狀態(tài))10為開始狀態(tài)2對(duì)Ii∈C：

ifA→α.aβ∈Iiandgo(Ii,a)=Ijthenaction[i,a]=sj;ifA→α.Bβ∈Iiandgo(Ii,B)=Ijthengoto[i,B]=j;ifA→α.∈Iithen

fora∈T∪{#}

doaction[i,a]=rj

;

ifS'→S.∈Iithenaction[i,#]=acc;3所有空格置error41FOLLOW(A)doaction[i,a]=rj;

SLR(1)分析法SLR(1)分析法SLR(1)分析表的構(gòu)造：僅當(dāng)a∈FOLLOW(A)時(shí)執(zhí)行關(guān)于A→α的歸約(rj)

;解決部分沖突LR(1)的搜索符/展望符傳播的/繼承的自生的LALR(1)——同心集426屬性文法與語法制導(dǎo)翻譯語法制導(dǎo)翻譯在完成語法分析的同時(shí)完成語義分析屬性文法A=(G,V,F)——一種實(shí)現(xiàn)用屬性表示一些語義值436屬性文法與語法制導(dǎo)翻譯綜合屬性A→X1X2…Xn A.s=f(c1,c2,…,ck)44Ax1x2xnA.sc1c2cnA.in固有屬性6屬性文法與語法制導(dǎo)翻譯L繼承屬性A→X1X2…Xn Xi.in=f(c,c1,c2,…,ck)1≤k<i≤n45Ax1x2xnxk…Xi.inc1c2ckcnc6屬性文法與語法制導(dǎo)翻譯S屬性文法/定義:只含綜合屬性的屬性文法產(chǎn)生式 屬性(計(jì)算)規(guī)則/語義規(guī)則E→E1+E2 E.val:=E1.val+E2.valE→E1*E2 E.val:=E1.val*E2.valE→(E1) E.val:=E1.valE→id E.val:=id.valL屬性文法/定義包含綜合屬性和L繼承屬性的屬性文法466屬性文法與語法制導(dǎo)翻譯翻譯模式語義動(dòng)作被嵌入到產(chǎn)生式右部的適當(dāng)位置，在推導(dǎo)過程中完成語義處理屬性文法與翻譯模式屬性文法將產(chǎn)生式和語義動(dòng)作相關(guān)聯(lián)翻譯模式進(jìn)一步指出動(dòng)作執(zhí)行的時(shí)機(jī)477語義分析和中間代碼生成中間代碼類型三地址代碼(四元式)語法(結(jié)構(gòu))樹(三元式)后綴式——逆波蘭表示算術(shù)表達(dá)式的翻譯E→E1+E2 E.code:=E1.code||E2.codegen(E.place’:=’E1.place’+’E2.place)E→id

E.place:=id.placeE.code=’’48變量說明的翻譯在符號(hào)表中記錄種別、類型、相對(duì)地址、作用域……等計(jì)算相對(duì)地址49說明語句的翻譯模式P→{offset:=0}DD→D;DD→id:T{enter(,T.type,offset);

offset:=offset+T.width}T→integer{T.type:=integer;T.width:=4}T→real{T.type:=real;T.width:=8}T→array[num]ofT1

{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}T→↑T1{T.type:=pointer(T1.type);

T.width:=4}50數(shù)組數(shù)組說明的翻譯5152動(dòng)態(tài)分配方案下數(shù)組說明的代碼結(jié)構(gòu)D→id:array[low1:up1,……,lown:upn]ofTlow1.code送工作單元W1up1.code送工作單元W2……lown.code送工作單元W2n-1upn.code送工作單元W2n動(dòng)態(tài)分配子程序其它參數(shù)(n,type)轉(zhuǎn)動(dòng)態(tài)分配子程序入口?D→id:array[num]ofTid[i1,i2,…,in](ih相當(dāng)于Eh的值，P270中L=left，place=addr)S→L:=E {ifL.offset=nullthengen(L.place’:=’E.place) elsegen(L.place[L.offset]’:=’E.place}E→L {ifL.offset=nullthenE.place:=L.placeelse {E.place:=newtemp;gen(E.place’:=’L.place[L.offset]}}L→id {L.place:=id.place;L.offset:=null}L→Elist] {L.place:=newtemp;L.offset:=newtemp; gen(L.place’:=’c);gen(L.offset’:=’Elist.place*w)}

Elist→id[E {Elist.place:=E.place;

Elist.ndim:=1;

Elist.array:=id.place}Elist→Elist1,E{t:=newtemp;

m:=Elist1.ndim+1;

gen(t’:=’Elist1.place’*’limit(Elist.array,m); gen(t’:=’t’+’E.place);

Elist.array:=Elist1.array; Elist.place:=t;

Elist.ndim:=m}Addr(A[i1,i2,i3,i4])=c+(((i1*n1+i2)*n2+i3)*n3+i4)*w賦值語句的翻譯布爾表達(dá)式的翻譯數(shù)值表示：與算術(shù)表達(dá)式處理類似真假出口：E.true，E.false54S→id:=ES.code:=E.code||gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code||E2.code||gen(E.place':='E1.place'+'E2.place) ……if語句的翻譯C.true:=newlabel;S1.next:=S.next;S.code:=C.code||gen(C.true':')||S1.code55C.codeS1.beginC.trueS.nextS1.codeC.falseS→ifCthenS1if語句的翻譯C.true:=newlabel;C.false:=newlabel;S1.next:=S2.next:=S.next;S.code:=C.code||gen(C.true':')||S1.code||gen('goto'S.next)|| gen(C.false':')||S2.code56C.codeS1.beginC.trueS.nextS1.codeC.falsegotoS.nextS2.codeS2.beginS2.nextS1.nextS→ifCthenS1elseS2

while語句的翻譯S.begin:=S1.next:=newlabel;C.true:=S1.begin:=newlabel;C.false:=S.next;S.code:=gen(S.begin':')|| C.code|| gen(C.true':')|| S1.code|| gen('goto'S.begin)57C.codeS1.codegotoS.beginC.trueS1.beginC.falseS.nextS.beginS→whi