编译原理复习

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,编译原理,复习,如何让计算机,认识,、理解 和 执行,高级程序设计语言,？,1,课程基本框架,1,、基础知识：文法,2,、词法分析,理论模型,正规文法与有限自动机,实现,词法分析程序,3,、语法分析,理论模型：,自上而下分析,自下而上分析,4,、中间代码生成,语法制导翻译,5,、运行时数据区的管理,6,、中间代码,优化,：局部优化、循环优化、全局优化,7,、目标代码生成,2,复习范围,复习范围,：第,15,章、,7-8,章、,911,章,复习方法,：,1,、认真理解书中的基本概念、基本原理与基本算法；,2,、弄懂书中的例题与习题；,3,、在看书时或理解例题时，一定要划出相应的细节变化过程，通过画图来加深理解；,4,、在理解的基础上记忆。,3,第,1,章,引论,词法,分析,语法,分析,语义分析和中间代码生成,目标,代码,生成,源,代码,目标代码,错 误 处 理,符 号 表 管 理,优化,处理,编译程序总体结构,掌握编译程序的,五个阶段，,及每个阶段的输入和输出,单词符号,语法单位,中间代码,中间代码,4,第,1,章,掌握基本概念,：,遍,(,趟,),：,编译程序对源程序或源程序的中间结果从头至尾扫描的次数。,编译前端和后端：,编译前端：由与源语言有关但与目标机无关的部分组成，通常包括词法分析、语法分析、语义分析与中间代码生成。,编译后端：由编译程序中与目标机有关的部分组成，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。,5,第,2,章,形式语言基础,文法,：,描述语言的语法结构的形式规则。,上下文无关文法：,上下文无关文法是这样一种文法，它所定义的语法范畴（过语法单位）是完全独立于这种范畴可能出现的环境的。,上下文无关文法的组成,：,一个上下文无关文法,G,是一个四元式,(V,T,V,N,S,P),，其中,V,T,是一个非空有限集，它的每个元素称为终结符号；,V,N,是一个非空有限集，它的每个元素称为非终结符号；,S,是一个非终结符号，称为开始符号；,P,是一个产生式集合，每个产生式的形式是,P,。,6,第,2,章,例如，,考虑上下文无关文法：,E,i|EAE,A,+|*,其中，,E,、,A,是非终结符号，而,i,、,+,和*是终结符。,注意几个符号：,：定义为,=,：推导,*,：表示定义符号串的全体,|,：表示“或”,：空字。,7,第,2,章,要求掌握最左推导,并画出语法树,：,最左推导：任何一步推导,=,都是对,中的最左终结符进行替换的。如文法,E E+E|E*,E|(E)|i,，推导句子,(,i+i,),：,E(E)(E+E)(,i+E,)(,i+i,),句子和句型,假定,G,是一个文法，,S,是它的开始符号。如果,S,=,，则称,是一个句型。仅含终结符的句型是一个句子。,8,第,3,章,词法分析,要求：掌握将正规式构造为最小,DFA,的过程。,步骤,：,1.,构造其,NFA,；,2.,将构造的,NFA,确定化；,3.,将确定的,NFA(DFA),最小化。,i,j,AB,i,j,A,B,i,j,A,|,B,i,j,A*,i,j,i,j,A,B,A,9,第,3,章,例：,正则表达式,A(A|B)*B,的,NFA,构造过程,X,Y,A(A|B)*B,X,Y,A,(A|B)*,X,1,2,Y,A,B,A,B,B,3,10,2.,将构造的,NFA,确定化,注意,：遇到空字,(,),需要忽略该转移状态。确定化后得到新的转移转换矩阵。,理解书上的例子：（,a|b,)*(,aa|bb)(a|b,)*,对应的,DFA,。,4,Y,3,2,6,1,5,X,a,a,a,a,b,b,b,b,Ia,Ib,X,5,1,5,3,1,5,4,1,5,3,1,5,3,1,2,6,Y,5,4,1,5,4,1,5,3,1,5,4,1,2,6,Y,5,3,1,2,6,Y,5,3,1,2,6,Y,5,4,1,6,Y,5,4,1,6,Y,5,3,1,6,Y,5,4,1,2,6,Y,5,4,1,2,6,Y,5,3,1,6,Y,5,4,1,2,6,Y,5,3,1,6,Y,5,3,1,2,6,Y,5,4,1,6,Y,0,1,2,1,3,2,2,1,4,3,3,5,4,6,4,5,6,4,6,3,5,11,第,3,章,3.,最小化,把一个,DFA,的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。,化简过程：将状态分为两组,(,终态组和非终态组,),，分别将两组进行状态转换，如果转换后的状态属于确定组，则该组状态不可再划分（归结到一组）。,12,第,4,章,自上而下语法分析,判断某给定文法是否为,LL(1),文法其条件为,：,(1),文法不含左递归。,(2),对于文法中每个非终结符,A,的各个产生式的候选首符集两两不相交。即，若,A,1|2|,。,|n,则：,FIRST(i,),FIRST(j,),=,（,i j),(3),对文法中每一个终结符,A,，若它存在某个候选首符集包含，则,FIRST(A)FLLOW(A)=,一个文法若满足以上条件，则称该文法,G,为,LL(1),文法,.,13,第,4,章,1.,消除左递归,假定关于非终结符,P,的规则为,P,P|,其中,不以,P,开头,则,P,的规则可改为下面的非直接左递归形式：,P,P PP|,一般而言，假定,P,关于的全部产生式是,P,P,1,|P,2,|,P,m,|,1,|,2,|,n,其中，每个,都不等于，而每个都不以,P,开头，那末，消除,P,的直接左递归性就是把这些规则改写成：,P|,1,P|,2,P|,n,P,P,1,P|,2,P|,m,P,|,例子，将文法,SS+aB|aB|+aB,B,*,aB,|*a,消除左递归？,S,aBS|+aBS,S+,aBS,|,14,第,4,章,2.,消除回溯,(,提左公因子,),如，对上例,提取公共左因子，将产生式改写成：,B,*,aC,C,B|,3.,求,first,集合和,follow,集合,求,follow,集方法：,1),对文法开始符号,S,，将,#,加入到,Follow(S,),中；,2),若,B,A,是文法,G,的一个产生式，则将,First(,)-,加入到,Follow(A,),中,;,3),若,B,A,是文法,G,的一个产生式,或,B,A,是文法,G,的一个产生式,且,，则将,Follow(B,),加入到,Follow(A,),中；,15,第,4,章,4.,构造预测分析表,：,先求出,first,集和,follow,集，,1,）假定,A,是一个产生式，,a,First(,),那么当,A,是栈顶符号且将读入,a,时，,A,就应作为选用的侯选式，,A,应填入,MA,a,中。,2,）若,A,，而,First(,),对每个,a,Follow(A,),在,MA,a,元素中应填,A,(,一般填,A,).,16,第,4,章,5.,掌握输入串的分析过程,熟悉书上例子的预测分析过程。,41,注意：反向进栈,17,第,5,章,自下而上语法分析,给定文法，要求掌握：证明给定符号串是该文法的一个句型，并指出这个句型的短语、直接短语和句柄（,通过语法树确定,）。,短语：一颗子树的树叶全体；,简单短语：一颗简单子树的树叶全体；,句柄：最左边的简单短语。,要求掌握算符优先文法。,18,第,5,章,句型：,E+F-T/F*i,短语,:,E+F-T/F*i,，,E+F,，,F,，,T/F*i,，,T/F,，,i,简单短语,:F,，,T/F,，,i,句柄,:F,E,E -T,E +T T *F,F T /F i,E+F-T/F*I,的语法树,注：先由给定的句型画出语法树,19,第,5,章,求各非终结符,P,的首终结符集和尾终结符集,通过检查,G,的每个产生式的每个候选式，可以找出满足,a=b,的终结符对。为了找出所有满足关系,的终结符对，我们需要对,G,的每个非终结符,P,构造两个集合,首终结符集,FIRSTVT(P),和,尾终结符集,LASTVT(P):,FIRSTVT(P)=a|,P,+,a,或,P,+,Qa,aV,T,而,Q V,N,LASTVT(P)=a|,P,+,a,或,P,+,aQ,aV,T,而,Q V,N,有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系,的所有终结符对。例如：假定有个产生式的一个候选式为,aP,那么，对任何,bFISTVT(P,),我们有,ab.,20,算符优先分析,例,：构造下面文法的算符优先表。,S,if,E,b,then E else E E,E+T|T,T,T*F|F F,i,E,b,b,解：,1,）求各非终结符的首终结符集和尾终结符集。为了考虑语句的开始和结束符号“”，对文法拓广，加一个产生式,S,S,FIRSTVT(S)=if LASTVT(S)=else,+,*,i,FIRSTVT(E)=+,*,i LASTVT(E)=+,*,i,FIRSTVT(T)=*,i LASTVT(T)=*,i,FIRSTVT(F)=i LASTVT(F)=i,FIRSTVT(E,b,)=b,LASTVT(E,b,)=b,21,算符优先分析,2),填写算符优先表,#,b,i,*,+,else,then,if,#,b,i,*,+,else,then,if,左 右,22,第,7,章,语义分析和中间代码,掌握概念：,语法制导翻译的概念,语法制导翻译,：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构得到翻译结果的处理方法称为语法制导翻译。,23,第,7,章,要求掌握：写出表达式的后缀式、三元式、四元式、间接三元式。,24,第,9,章,运行时存储空间组织,写出程序段运行结果：,参数传递的方式分别采用传值、传地址、传结果、传名。,1),传地址：把实在参数的地址传递给相应的形式参数。,2),传值：把实在参数的值计算出来传递给相应的形式参数。,3),传名：把形参替换为相应的实参。,4),传结果：每个形参有两个单元，第一个单元存放实参地址，第二个单元存放实参的值。在过程体中对形参的引用看成是对第二个单元的直接访问，但在工作完成返回前必须把第二个单元的内容存放到第一个单元所指的实参单元中。,25,第,9,章,值结果传递与地址传递的唯一区别在于别名的表现不同。例如，在以下的代码中：,void p(,int,x,int,y),+x;,+y;,main(),int,a=1;,p(a,a,);,return 0;,在调用,p,之后，若使用了地址传递，则,a,的值为,3,；若使用了得结果传递，则,a,的值为,2,。,26,第,9,章,掌握概念：静态链和动态链,(P259),静态链：从一个过程的当前活动记录指向其直接外层的最新活动记录的地址（指针）。,动态链：指向当前正在活动的过程的活动记录的基地址，即指向调用该过程前正在运行的过程的最新活动记录的基地址。,27,第,10,章,优化,优化分类,1,、局部优化,1,）含义：局部优化是针对一段顺序执行语句序列的优化。,2,）主要方法,合并已知量,删除公共子表达式,变量传播与无用赋值删除,2,、循环优化,1,）含义：对程序中可能反复执行的代码序列的优化,2,）主要方法：,代码外提；,(,哪些情况下可以外提？,P290),强度削弱；,删除归纳变量,28,第,10,章,哪些情况下循环中的代码可以外提？,对于循环,L,中的每一不变运算,(,运算结果不改变,)s,：,A:=B op C,或,A:=B,，检查是否满足两个条件,P290,，,则代码,s,可以外提。,29,第,10,章,要求掌握基本块的,DAG,图的构造：,理解讲过的例子,例如,：为下列四元式程序段构造,DAG.,(1)T0:=3.14,(2)T1:=2*T0,(3)T2:=,R+r,(4)A:=T1*T2,(5