编译原理-总结

总结1“编译原理”是一门非常好的课程AlfredV.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到“自顶向下”和“自底向上”的系统设计方法（思想、方法、实现全方位讨论）一些具体的表示和变换算法一个相当规模的系统的设计（含总体结构）2掌握“编译原理”中的基本概念、基本理论、基本方法，在系统级上再认识程序和算法，提升计算机问题求解的水平，增强系统能力，体验实现自动计算的乐趣实验情况递归子程序、LL(1)、SLR(1)、LR(1)多种形式的输入LR(1)分析表的自动生成错误处理与续编译3“编译原理”是一门非常好的课程1绪论——计算机语言的发展机器语言(MachineLanguage)与汇编语言(AssembleLanguage)高级语言(HighLevelLanguage)强制式语言(ImperativeLanguage)函数(应用)式语言(FunctionalLanguage)逻辑式(基于规则)语言(LogicalLanguage)面向对象语言(Object-OrientedLanguage)命令语言(Command)4翻译系统—汇总ML MLP Assembler DisassemblerAL

ALP Translator Compiler DataHL HLP Interpreter ResultRunSystemDataResult编译程序总体结构目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理

出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序编译的遍（Pass）根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描，在每一遍扫描中，完成不同的任务7Ｔ形图表示语言翻译的Ｔ形图8源语言表示语言目标语言功能1)交叉编译/移植：用A机的C编译构造B机的C编译2)本机编译器利用：用A机的C编译构造A机的B编译3)自展技术2文法与语言字母表∑：非空有穷集合字母表的乘积：∑1∑2={ab|a∈∑1，b∈∑2}∑*、∑+x∈∑*,L

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

αγβ

Ａ→γ∈Pα

β；α

nβ；α

*β；α

+β句型：S

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

*x，x∈ＶT*102文法与语言最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）112文法与语言语言：Ｌ(Ｇ)＝{x｜Ｓ

*

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

*αＡβ

+αγβ直接短语、句柄语法（分析）树用树的形式表示句型的生成/结构+id3id1id2*（抽象）语法树去掉对翻译不必要的信息EE+EEEid1*id3id22文法与语言13EE*Eid3EE+id2id1二义性推导：两个不同的最左推导；两个不同的最右推导语法树：两棵不同的语法树EE+EEEid1*id3id22文法与语言有的文法的二义性是可以消除的语言可以用不同文法产生14算术表达式文法2E→E+T|TT→T*F|FF→(E)|id算术表达式文法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词法分析词法分析器的功能,在编译程序中的“位置”缓冲区设计（双缓冲）正规(表达)式a|(a|b)*cc(a|b)+((0|1)(0|1))*(00|01|10|11)*正规定义式S→((0|1)(0|1))*正规式(表达式)与正规文法等价FA（状态转移图）是一个有力的工具16词法分析器的实现按状态转移图设计主程序设计适当的子程序17ABaAaAsr正规定义式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当ε∈FIRST(αj)时，FOLLOW(A)∩FIRST(αi)=Φ求FIRST(α)的算法α=X1X2…Xn求FOLLOW(B)的算法#∈FOLLOW(S)A→αBβ当ε∈FIRST(β)时FOLLOW(B)=FOLLOW(B)∪(FIRST(β)–{ε})∪FOLLOW(A)194自顶向下语法分析LL(1)分析器系统结构20LL(1)通用控制算法预测分析表的构造算法

输入缓冲区(符号序列)栈控制程序P77预测分析表M输出的产生式序列4自顶向下语法分析表达式文法的预测分析表语法变量终极符号id+*()#EE'TT'F21E→TE'E'

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)语法图简化语法图递归子程序法为每个语法变量编写一个处理子程序224自顶向下语法分析23简化的语法图+TE＊ＦＴidＥＦ

（）E→T(+T)*T→F(*F)*F→(E)|id简单算术表达式的分析器Ｅ的子程序(E→T(+T)*)procedureE;beginT; Ｔ的过程调用whilelookhead='+'do lookhead：当前符号begin 当前符号等于＋时match(‘+’); 处理终结符＋T Ｔ的过程调用endend; 245自底向上语法分析思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误核心寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法方法算符优先分析法LR分析法2526

id+

id＊id#＋Ｅ#移进归约控制程序输出产生式序列栈内容

♁

输入缓冲区内容＝#“当前句型”#？？LL(1)分析法栈输入缓冲区

分析表分析器结构4种操作：移进、归约、接受、出错算符优先分析法根据当前输入符号a与栈顶符号b的优先级确定动作：ifb≮athen移进——归约对象未形成ifb≡athen移进——归约对象未形成ifb≯athen归约——归约对象已形成ifa=b=#then接受——分析成功Ifa与b无优先关系then出错27算符优先分析法算符文法（不含形如A→αBCβ的产生式）算符优先级栈内栈外、优先函数算符优先文法素短语和最左素短语句型#N1a1N2a2…

Nnan#的最左素短语是满足下列条件的最左子串 NiaiNi+1ai+1…

NjajNj+1其中：ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+128LR分析法关键概念规范句型活前缀——规范句型（右句型）的不含句柄右边任何符号的前缀句柄形成情况的表示——LR(0)项目：A→α.β移进项目：A→α.aβ待约项目：A→α.Bβ归约项目：A→α.2930LR分析器的总体结构a1…ai…an#LR主控程序动作表action转移表goto产生式序列状态/符号栈输入缓冲区分析表SmSm-1………S1S0XmXm-1………X1#LR分析表：action[s,a]；goto[s,X]31

动作表转移表状态 action gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35 r1r1r16r2r2r2LR分析表的构造拓广文法——给出分析开始和结束状态G=(VN∪{S’},VT,P∪{S’→S},S’)S’

V对应S’→.S（分析开始）和S’→S.（分析成功）识别CFGG的拓广文法的所有规范句型活前缀的DFA以项目集{S’→.S}的闭包为启动状态分析器的状态——某个项目集闭包后继项目项目集规范族——DFA的全部状态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产生式编号*idSLR(1)分析法项目集I的相容归约—归约冲突移进—归约冲突LR(0)文法——G‘的项目集规范族中的所有项目集闭包是相容的SLR(1)分析法SLR(1)分析表的构造：仅当a∈FOLLOW(A)时执行关于A→α的归约（rj）

;

34分析表的构造设G’的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应的分析器状态(即相应的DFA状态)10为开始状态2对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属性文法与语法制导翻译语法制导翻译在完成语法分析的同时完成语义分析属性文法A=(G,V,F)——一种实现用属性表示一些语义值36综合属性A→X1X2…Xn A.s=f(c1,c2,…,ck)37Ax1x2xnA.sc1c2cnA.in固有属性6属性文法与语法制导翻译继承属性A→X1X2…Xn

Xi.in=f(c,c1,c2,…,ck)1≤k<i≤n38Ax1x2xnxk…Xi.inc1c2ckcnc6属性文法与语法制导翻译S属性文法:只含综合属性的属性文法产生式

属性（计算）规则/语义规则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属性文法与语法制导翻译翻译模式语义动作被嵌入到产生式右部的适当位置，在推导过程中完成语义处理属性文法与翻译模式属性文法将产生式和语义动作相关联翻译模式进一步指出动作执行的时机406属性文法与语法制导翻译7语义分析和中间代码生成类型三地址代码（四元式）语法(结构)树（三元式）后缀式——逆波兰表示算术表达式的翻译E→E1+E2 E.code:=E1.code||E2.codegen(E.place’:=’E1.place’+’E2.place)E→id

E.place:=id.placeE.code=’’41变量说明的翻译在符号表中记录种别、类型、相对地址、作用域……等计算相对地址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数组数组说明的翻译4445动态分配方案下数组说明的代码结构D→id:array[low1:up1,……,lown:upn]ofTlow1.code送工作单元W1up1.code送工作单元W2……lown.code送工作单元W2n-1upn.code送工作单元W2n动态分配子程序其它参数(n,type)转动态分配子程序入口?D→id:array[num]ofT46id[i1,i2,…,in]（ih相当于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赋值语句的翻译布尔表达式的翻译数值表示真假出口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