編譯原理-總結(jié)

總結(jié)1“編譯原理”是一門非常好的課程AlfredV.Aho：編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書中的原理和技術(shù)都會(huì)反復(fù)用到“自頂向下”和“自底向上”的系統(tǒng)設(shè)計(jì)方法（思想、方法、實(shí)現(xiàn)全方位討論）一些具體的表示和變換算法一個(gè)相當(dāng)規(guī)模的系統(tǒng)的設(shè)計(jì)（含總體結(jié)構(gòu)）2掌握“編譯原理”中的基本概念、基本理論、基本方法，在系統(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)、SLR(1)、LR(1)多種形式的輸入LR(1)分析表的自動(dòng)生成錯(cuò)誤處理與續(xù)編譯3“編譯原理”是一門非常好的課程1緒論——計(jì)算機(jī)語言的發(fā)展機(jī)器語言(MachineLanguage)與匯編語言(AssembleLanguage)高級(jí)語言(HighLevelLanguage)強(qiáng)制式語言(ImperativeLanguage)函數(shù)(應(yīng)用)式語言(FunctionalLanguage)邏輯式(基于規(guī)則)語言(LogicalLanguage)面向?qū)ο笳Z言(Object-OrientedLanguage)命令語言(Command)4翻譯系統(tǒng)—匯總ML MLP Assembler DisassemblerAL

ALP Translator Compiler DataHL HLP Interpreter ResultRunSystemDataResult編譯程序總體結(jié)構(gòu)目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理

出錯(cuò)處理中間代碼中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器源程序編譯的遍（Pass）根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求……等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描，在每一遍掃描中，完成不同的任務(wù)7Ｔ形圖表示語言翻譯的Ｔ形圖8源語言表示語言目標(biāo)語言功能1)交叉編譯/移植：用A機(jī)的C編譯構(gòu)造B機(jī)的C編譯2)本機(jī)編譯器利用：用A機(jī)的C編譯構(gòu)造A機(jī)的B編譯3)自展技術(shù)2文法與語言字母表∑：非空有窮集合字母表的乘積：∑1∑2={ab|a∈∑1，b∈∑2}∑*、∑+x∈∑*,L

∑*,x∈Lε語句9文法：Ｇ=(ＶT，ＶN，Ｐ，Ｓ)α→β∈PBNF：∷＝,[],{}lu,{}m候選式：α→β1|β2|…|βn推導(dǎo)（派生）：αＡβ

αγβ

Ａ→γ∈Pα

β；α

nβ；α

*β；α

+β句型：S

*αα∈(ＶT∪ＶN)*句子：S

*x，x∈ＶT*102文法與語言最左(Left-most)推導(dǎo)——最左分析左句型最左推導(dǎo)對(duì)應(yīng)最右歸約最右(Right-most)推導(dǎo)——最右分析規(guī)范推導(dǎo)、規(guī)范句型（右句型）最右推導(dǎo)對(duì)應(yīng)最左歸約（規(guī)范歸約）112文法與語言語言：Ｌ(Ｇ)＝{x｜Ｓ

*

x&x∈ＶT*}短語：如果S

*αＡβ

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

aBCS

aSBCCB

BCaB

dbB

bbbC

bcC

ccE→E+EE→E*EE→(E)E→idE→E-EE→E/E

S

aBCS

aSBCCB

BCaB

abbB

bbbC

bccC

ccS→a|bS→aT|bTT→a|bT→1|2T→aT|bTT→1T|2T15S→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è)有力的工具16詞法分析器的實(shí)現(xiàn)按狀態(tài)轉(zhuǎn)移圖設(shè)計(jì)主程序設(shè)計(jì)適當(dāng)?shù)淖映绦?7ABaAaAsr正規(guī)定義式FAA→rs*RGFAA→aBA→a3詞法分析4自頂向下語法分析語法分析方法分類回溯（虛假匹配）、左遞歸、二義性消除左遞歸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|…|βn18LL(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)194自頂向下語法分析LL(1)分析器系統(tǒng)結(jié)構(gòu)20LL(1)通用控制算法預(yù)測(cè)分析表的構(gòu)造算法

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

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)語法圖簡(jiǎn)化語法圖遞歸子程序法為每個(gè)語法變量編寫一個(gè)處理子程序224自頂向下語法分析23簡(jiǎn)化的語法圖+TE＊ＦＴidＥＦ

（）E→T(+T)*T→F(*F)*F→(E)|id簡(jiǎn)單算術(shù)表達(dá)式的分析器Ｅ的子程序(E→T(+T)*)procedureE;beginT; Ｔ的過程調(diào)用whilelookhead='+'do lookhead：當(dāng)前符號(hào)begin 當(dāng)前符號(hào)等于＋時(shí)match(‘+’); 處理終結(jié)符＋T Ｔ的過程調(diào)用endend; 245自底向上語法分析思想從輸入串出發(fā)，反復(fù)利用產(chǎn)生式進(jìn)行歸約，如果最后能得到文法的開始符號(hào)，則輸入串是句子，否則輸入串有語法錯(cuò)誤核心尋找句型中的當(dāng)前歸約對(duì)象——“句柄”進(jìn)行歸約,用不同的方法尋找句柄，就可獲得不同的分析方法方法算符優(yōu)先分析法LR分析法2526

id+

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

?

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

分析表分析器結(jié)構(gòu)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ò)27算符優(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+128LR分析法關(guān)鍵概念規(guī)范句型活前綴——規(guī)范句型（右句型）的不含句柄右邊任何符號(hào)的前綴句柄形成情況的表示——LR(0)項(xiàng)目：A→α.β移進(jìn)項(xiàng)目：A→α.aβ待約項(xiàng)目：A→α.Bβ歸約項(xiàng)目：A→α.2930LR分析器的總體結(jié)構(gòu)a1…ai…an#LR主控程序動(dòng)作表action轉(zhuǎn)移表goto產(chǎn)生式序列狀態(tài)/符號(hào)棧輸入緩沖區(qū)分析表SmSm-1………S1S0XmXm-1………X1#LR分析表：action[s,a]；goto[s,X]31

動(dòng)作表轉(zhuǎn)移表狀態(tài) action gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35 r1r1r16r2r2r2LR分析表的構(gòu)造拓廣文法——給出分析開始和結(jié)束狀態(tài)G=(VN∪{S’},VT,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)3233I0: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)*idSLR(1)分析法項(xiàng)目集I的相容歸約—?dú)w約沖突移進(jìn)—?dú)w約沖突LR(0)文法——G‘的項(xiàng)目集規(guī)范族中的所有項(xiàng)目集閉包是相容的SLR(1)分析法SLR(1)分析表的構(gòu)造：僅當(dāng)a∈FOLLOW(A)時(shí)執(zhí)行關(guān)于A→α的歸約（rj）

;

34分析表的構(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)=Ijthenaction[i,B]=sj;ifA→α.∈Iithen for

a∈VT∪{#}//FOLLOW(A)doaction[i,a]=rj

;ifS'→S.∈Iithenaction[i,#]=acc;3所有空格置error356屬性文法與語法制導(dǎo)翻譯語法制導(dǎo)翻譯在完成語法分析的同時(shí)完成語義分析屬性文法A=(G,V,F)——一種實(shí)現(xiàn)用屬性表示一些語義值36綜合屬性A→X1X2…Xn A.s=f(c1,c2,…,ck)37Ax1x2xnA.sc1c2cnA.in固有屬性6屬性文法與語法制導(dǎo)翻譯繼承屬性A→X1X2…Xn

Xi.in=f(c,c1,c2,…,ck)1≤k<i≤n38Ax1x2xnxk…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屬性文法包含綜合屬性和繼承屬性的屬性文法396屬性文法與語法制導(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ī)406屬性文法與語法制導(dǎo)翻譯7語義分析和中間代碼生成類型三地址代碼（四元式）語法(結(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=’’41變量說明的翻譯在符號(hào)表中記錄種別、類型、相對(duì)地址、作用域……等計(jì)算相對(duì)地址42說明語句的翻譯模式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}43數(shù)組數(shù)組說明的翻譯4445動(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]ofT46id[i1,i2,…,in]（ih相當(dāng)于Eh的值）P181S→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ù)值表示真假出口47S→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.code48C.codeS1.beginC.trueS.nextS1.codeC.falseS→ifCthenS1C.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.code49C.codeS1.beginC.trueS.nextS1.codeC.falsegotoS.nextS2.codeS2.beginS2.nextS1.nextS→ifCthenS1elseS2

if語句的翻譯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