三下编译原理

编译原理

(PrinciplesofCompiling)1主讲：蒋宗礼办公室：二教205电话：67392690Email：答疑与考试安排答疑时间与地点二教205，6月9日(星期一)全天考试时间：6月10日3-4节(9:55-11:30)考试地点计算机实验班：一教209软件工程实验班：一教210一纸开卷期末80%，平时20%(实验+作业+课堂)2上次课主要内容编译优化机器相关：目标代码机器无关：中间代码基本块全局优化循环优化局部优化基本块内的优化3上次课主要内容基本块的入口语句代码序列的第一语句转移语句的目标语句转移语句的下一条语句定义基本块一入口语句到下一入口语句之前一入口语句到转移语句或停语句4上次课主要内容局部优化合并已知量重新命名临时变量公共子表达式删除无用(死)代码5循环优化代码外提强度削弱消除归纳变量上次课主要内容目标代码生成针对目标语言的特殊性，生成高性能的目标代码(机器相关)充分利用寄存器输入：中间代码序列输出：目标代码6总结7“编译原理”是一门非常好的课程AlfredV.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到8“编译原理”是一门非常好的课程最经典、最常用的问题求解和系统设计思想和方法9自顶向下自底向上逐步求精递归求解目标驱动抽象与形式化描述算法设计与实现数据结构的选择与使用系统构建模块化一些具体的表示和变换算法自动计算、类计算一个相当规模的系统的设计(含总体结构)“编译原理”是一门非常好的课程掌握“编译原理”中的基本概念、基本理论、基本方法，在系统级上再认识程序和算法，提升计算机问题求解的水平，增强系统能力，体验实现自动计算的乐趣实验情况递归子程序、LL(1)、LR、自动生成多种形式的输入词法分析器、语法分析器自动生成错误处理与续编译101绪论——翻译系统11RunSystemDataResultMLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResultCompilingSystem⊕1绪论——编译程序12中间代码目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码目标代码语法单位单词符号词法分析器源程序变成一个单词序列走向目标1一个平滑的字符流走向目标2走向目标3走向目标4走向目标5得到语法成分！更接近机器语言更高的效率达到目标1绪论——编译的遍(Pass)根据系统资源状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描，在每一遍扫描中，完成不同的任务遍与阶段的联系与区别131绪论——T形图表示语言翻译程序的T形图14源语言表示语言目标语言功能1)交叉编译/移植：用A机的C编译构造B机的C编译2)本机编译器利用：用A机的C编译构造A机的B编译3)自展技术/自编译技术4)自动生成技术2文法与语言字母表∑：非空有穷集合字母表的乘积∑1∑2={ab|a∈∑1，b∈∑2}∑*、∑+x∈∑*,L∑*,x∈Lε语句152文法与语言文法：Ｇ=(Ｖ，T，Ｐ，Ｓ)α→β∈PBNF：∷＝,[],{}lu,{}m候选式：α→β1|β2|…|βn推导(派生)：αAβαγβA→γ∈

Pαβ；αnβ；α*β；α+β句型：S*αα∈(Ｖ∪T)*句子：S*x，x∈T* ε162文法与语言最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型(右句型)α1α2α3……αiαi+1……αn最右推导对应最左归约(规范归约)172文法与语言语言：L(G)＝{x｜S*

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

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

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)同步记号：synch4自顶向下语法分析语法图每个非终结符对应一个语法图，边上标记语法符号化简语法图递归子程序法为每个语法变量编写一个处理子程序28简化的语法图29E→T(+T)*T→F(*F)*F→(E)|idET3+0T6ε10*7F13ε14F1516(Eid17)简单算术表达式的分析器Ｅ的子程序(E→T(+T)*)procedureE;beginT; T的过程调用

whilelookhead='+'do lookhead：当前符号begin 当前符号等于＋时

match(‘+’); 处理终结符＋

T T的过程调用

endend; 305自底向上语法分析思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误核心寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法方法算符优先分析法LR分析法31分析器结构32

id+

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

♁

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

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

Nnan#的最左素短语是满足下列条件的最左子串

NiaiNi+1ai+1…

NjajNj+1其中：ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+134LR分析法关键概念规范句型活前缀——规范句型(右句型)的不含句柄右边任何符号的前缀句柄形成情况的表示——LR(0)项目：A→α.β移进项目：A→α.aβ待约项目：A→α.Bβ归约项目：A→α.35LR分析器的总体结构36a1…ai…an#LR主控程序动作表action转移表goto产生式序列状态/符号栈输入缓冲区分析表SmSm-1……S1S0XmXm-1……X1#LR分析表状态动作表action转移表gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r237action[s,a]goto[s,X]LR分析表的构造拓广文法——给出分析开始和结束状态G=(V∪{S'},T,P∪{S'→S},S')S'V对应S'→.S(分析开始)和S'→S.(分析成功)识别CFGG的拓广文法的所有规范句型活前缀的DFA以项目集{S'→.S}的闭包为启动状态分析器的状态——某个项目集闭包后继项目项目集规范族——DFA的全部状态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产生式编号*id核心项目项目集I的相容归约—归约冲突移进—归约冲突LR(0)文法——G'的LR(0)项目集规范族中的所有项目集闭包是相容的40分析表的构造设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)=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)分析表的构造：仅当a∈FOLLOW(A)时执行关于A→α的归约(rj)

;解决部分冲突LR(1)的搜索符/展望符传播的/继承的自生的LALR(1)——同心集426属性文法与语法制导翻译语法制导翻译在完成语法分析的同时完成语义分析属性文法A=(G,V,F)——一种实现用属性表示一些语义值436属性文法与语法制导翻译综合属性A→X1X2…Xn A.s=f(c1,c2,…,ck)44Ax1x2xnA.sc1c2cnA.in固有属性6属性文法与语法制导翻译L继承属性A→X1X2…Xn Xi.in=f(c,c1,c2,…,ck)1≤k<i≤n45Ax1x2xnxk…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属性文法/定义包含综合属性和L继承属性的属性文法466属性文法与语法制导翻译翻译模式语义动作被嵌入到产生式右部的适当位置，在推导过程中完成语义处理属性文法与翻译模式属性文法将产生式和语义动作相关联翻译模式进一步指出动作执行的时机477语义分析和中间代码生成中间代码类型三地址代码(四元式)语法(结构)树(三元式)后缀式——逆波兰表示算术表达式的翻译E→E1+E2 E.code:=E1.code||E2.codegen(E.place’:=’E1.place’+’E2.place)E→id

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