编译原理复习

《编译原理复习》由会员分享，可在线阅读，更多相关《编译原理复习（26页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,编译原理总复习,Click to edit Master title style,Click to edit Master te

2、xt styles,Second level,Third level,Fourth level,Fifth level,*,编译原理,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,编译原理总复习,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fif

3、th level,*,编译原理,期末总复习,考试题型,一单项选择,(2,10=20,),二简答题,(,6,3,=,18,),三自动机转换题,(15,),四中缀式转化后缀式和四元式,(,6,2=1,2,),五用,DAG,进行局部优化,(10,),六综合题,(25,),编译原理总复习,知识要点,第,1,章,编译程序:,compiler,能将一种计算机,高级语言,程序(,源语言,程序)转换成另一种等价的计算机,低级语言,程序(,目标语言,程序),编译原理总复习,编译程序工作过程的各个阶段：,词法分析器,语法分析器,语义分析器,源程序,中间代码生成器,代码优化器,目标代码生成器,目标程序,出错管理器,

4、符号表管理器,编译原理总复习,第,3,章,文法,G=,（,V,N,，,V,T,，,P,，,Z,）,V,N,：非终结符号集,V,T,：终结符号集,P,：产生式或规则的集合,Z,：开始符号（识别符号）,ZV,N,规范推导：,即最,右,推导,若符号串,中有两个以上的非终结符时，对推导的每一步坚持把,中的最右非终结符进行替换。,编译原理总复习,文法,GZ,所产生的,所有句子的集合,文法,GZ,（,1,）,句型,：,x,是句型,Z,x,且,x,V*,；,*,*,（,2,）,句子,：,x,是句子,Z,x,且,x,V,T,*,；,*,（,3,）,语言,：,L,（,GZ,）,=x|Z,x,，,x,V,T,*,

5、；,即：句型是由文法开始符号推导出来的,由终结符和非终结符组成的符号串。,即：句子是由文法开始符号推导出来的,由终结符组成的符号串。,编译原理总复习,给定文法，判断给定输入串是否为该文法的句子或句型。并指出该句子或句型的：,短语,简单短语,句柄,编译原理总复习,第,4,章,词法分析程序的主要任务：,对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符，按照构词规则切分成一个一个具有独立意义的单词，并识别其正确性，再交给下一阶段进行语法分析。,描述词法的机制是,正则表达式,识别机制是,有穷状态自动机,编译原理总复习,为正规式,(0|1),*,0(0|1),构造一个等价的有穷自动机。,将此

6、自动机转换为确定自动机,DFA,。,例：,编译原理总复习,S,A,B,C,Z,0,1,0,0,1,第,5,章,语法分析的主要工作：,识别由词法分析给出的单词序列是否为给定文法的正确句子（程序）。,语法分析常用的方法：,自顶向下的语法分析和自底向上的语法分析两大类。,编译原理总复习,三个重要集合：,First,集,Follow,集,Select,集,注：三,种集合均为,终结符集,编译原理总复习,SELECT(,A,)=,(FIRST(),),FOLLOW,(A),，,否则,FIRST(),，,当,时,*,确定的自顶向下语法分析：,要求文法必须是,LL(1),文法,LL(1),文法的判别,若非终结

7、符,A,的两个不同产生式，,A,A,；,满足：,SELECT(A,)SELECT(A,)=,编译原理总复习,第,7,章,LR,分析法,前缀：,一个符号串的前缀是指该串的任意首部（包括,）。,可归前缀：,是指规范句型的一个前缀，这种前缀,包含句柄且不含句柄之后的任何符号,。,活前缀：,可归前缀的任意首部。,编译原理总复习,移进项目：,A,.,b,其中,b,为终结符,，,可为,待约项目：,A,.,B,其中,B,为非终结符,，,可为,归约项目：,A,.,接受项目：,SS,.,LR(0),分析和,SLR(1),分析,编译原理总复习,分析法过程步骤：,拓广文法,G,：引起一个新的开始符号,S,，且将,S

8、,S,作为第,0,个产生式添加到文法,G,中，并对所有产生式进行编号。,构造识别活前缀的,DFA,。,判断是否存在,移进归约,冲突或,归约归约,冲突。,若无冲突，则为,LR(0),文法，构造,LR(0),分析表；,若有冲突，判断是否为,SLR(1),文法,编译原理总复习,SLR(1),文法判定：,存在如下项目集,(,状态,)I:,I=,X,.,b,A,.,B,.,其中,bV,T,I,中含有,移进归约,和,归约归约,冲突。,若满足：,FOLLOW(A),FOLLOW,(B)b=,则为,SLR(1),文法。,编译原理总复习,SLR(1),分析表的构造规则：,(1),项目集,Ii,中若有形如,A.X

9、,的项目，且有,GO(,Ii,X,),=Ij,若,X,为一终结符号,a,时，则置,ACTION,I,a,=Sj,;,若,X,为一非终结符号时，则置,GOTO,i,X,=j,；,(2),若有归约项目,A,.,属于,Ii,设,A,为文法第,j,个行产生式，则对任何,属于,FOLLOW(A),的,输入符号,a,，置,ACTION,i,a,=Rj,；,(3),若有接受项目,SS,.,属于,Ii,则置,ACTIONi,#,=acc,。,(4),在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。,编译原理总复习,第,8,章,语义分析的任务,对于所写的源程序，在词法分析和语法分析的基础上，进一步分析

10、其含义，在理解含义的基础上，为生成相应的目标代码做好准备或直接生成目标代码。,语义描述方法,属性文法,语义的处理方法,语法制导翻译,编译原理总复习,属性文法,属性文法形式的定义为一个三元组,AG,，,AG=,（,G,，,V,，,E,）。其中,G,为一个上下文无关文法；,V,为属性的有穷集；,E,为一组语义规则。,语法制导翻译,语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。,属性分为两类：综合属性和继承属性,综合属性,：,如果,b,是,A,的属性，,c,1,c,2,c,k,是产生式右部文法符号的属性或,A,的其它属性。

11、,继承属性,：如果,b,是产生式右部某个文法符号,X,的属性。,编译原理总复习,给定文法,S,及相应翻译方案为：,(0),S,S,print:“a,”,(1),S,r,D,print:“b,”,(2),D,D,i,print:“c,”,(3),D,i,print:“d,”,1.,符号串,ri,i,i,是不是该文法的一个句子，请证实。,2.,若是句子，写出其所有的短语、简单短语，以及句柄。,3.,构造识别该文法的活前缀的,DFA,，并判断该文法是,LR(0),还是,SLR(1),。,4.,对于,ri,i,i,这个输入符号串，该翻译方案的输出是什么？,编译原理总复习,例：,S,r,S,D,D,i,

12、，,i,D,i,，,中间代码的形式,几种常用的中间表示,：,后缀表示：逆波兰记号,三地址代码：三元式、四元式,图形表示：树形表示,编译原理总复习,（,b*cd/c)*a,a,cc,+e,d,例：,第,9,章,符号表的作用和地位,语义检查的依据,目标代码生成阶段地址分配的依据,编译原理总复习,第,11,章,基本块,：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。,基本块的,DAG,：,无环路有向图,编译原理总复习,t1,S,R,t2,S,R,A,t1*t2,B,A,t3,S,R,t4,t2*t3,B,t4,(1),画出,DAG,图；,(2),假设基本块出口时只有,A,、,B,还被引用，请写出优化后的三地址代码序列。,编译原理总复习,有基本块：,例：,编译原理总复习,1.,编译程序的主要组成部分有哪些？,2.,词法分析的主要任务是什么？,3.,简述,DFA,与,NFA,有何区别？,4.,自底向上的语法分析方法的基本思想是什么,?,5.,何谓语法制导翻译？,6.,常用的中间语言表示形式有哪些？（至少写出三种）,简答题,