《编译原理总复习》课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1 题型及分值,一、判断题（15=5）,二、填空题（11,0,=1,0,）,三、选择题（25=10）,四、简答题（本题共,35,分）,:,其中包括两个名词解释。,五、计算题（10+15+15=,40,）,编译原理,2 教材各章知识点概览,编译程序概论,1,文法和语言,2,词法分析与有限自动机,3,自上而下语法分析方法,4,自下而上语法分析方法,5,语法制导翻译和语义分析,6,符号表,7,代码优化,8,编译原理,1、编译程序概论,（1）基本概念,翻译程序,，,编译程序,（2）编译过程的五个阶段，各阶段的任务及其依循的规则、描述工具分别是什么？除了这个5个阶段之外，还应该有哪两个重要内容？,五个逻辑阶段：,词法分析,、,语法分析,、,语义分析和中间代码产生,、,代码优化,和,目标代码生成,。除了这五个阶段之外，编译程序的每个阶段都涉及到,表格管理,和,错误处理,这两个重要内容。,编译原理,1、编译程序概论,（3）编译错误的种类,从编译程序的角度来看，源程序中的错误主要分为：,语法错误,和,语义错误,两类错误。,（4）高级程序设计语言翻译的两种方式以及它们的区别,高级程序设计语言的翻译主要有两种方式：,编译方式,和,解释方式,。,区别：,是否生成目标代码,。,编译原理,2、文法和语言,（1）基本概念,文法,、,推导,、,最左推导,、,最右推导,、,句型,、,句子,、,语言,、,文法的二义性,（2）对文法G，能够给出给定句型或句子的最左推导及最右推导序列，并画出其对应的语法分析树。,（3）能够计算某文法的语言。,（4）理解文法的二义性，能够说明一个文法是二义的。,编译原理,2、文法和语言,（5）形式语言分类(chomsky,1956),0型 普通（短语）文法,1型 上下文有关文法,2型 上下文无关文法,3型 线性（正规、正则）文法,3型2型1型0型,编译原理,3、词法分析与有限自动机,（1）基本概念,状态等价,、,DFA的化简,（2）词法分析器的任务及其输出形式,任务,：自左至右逐个字符地对源程序进行扫描，按语言的构词规则识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序。,输出形式,：二元式 （单词种别，单词符号的属性值）,（3）单词符号的种类,关键字,、,标识符,、,常数,、,运算符,、,界符,编译原理,3、词法分析与有限自动机,（4）正规文法、正规式、有限自动机之间的相互等价性定理,（5）正规式 NFA DFA 最小化DFA,（,注意：状态函数定义不完整之情形,）,（6）状态转换图的构造(标识符、整数),编译原理,4、自上而下语法分析方法,（1）语法分析的方法,根据,语法分析树建立方向,的不同，将语法分析分成两类：,自上而下语法分析方法,和,自下而上语法分析方法,。,（2）自上而下分析的基本思想,穷举试探法,（3）自上而下分析面临的两个最主要的问题,左递归,、,回溯,（4）自上而下分析的基本方法,LL（1）分析法,、,递归下降分析器,编译原理,4、自上而下语法分析方法,（5）左递归（直接、间接）和回溯的消除,直接左递归的消除,间接左递归的消除,排序,代入及消除左递归,化简,编译原理,4、自上而下语法分析方法,（5）左递归（直接、间接）和回溯的消除,回溯的消除：提左公因子,编译原理,4、自上而下语法分析方法,（6）LL(1)的含义,LL(1)中的第一个L表示,从左至右扫描输入串,，第二个L表示,最左推导,，1表示,分析时每一步只需向前查看一个符号,。,（7）LL(1)分析器的组成部分,输入缓冲区,、,分析栈,、,分析表,、,总控程序,（8）LL(1)分析的四种动作,成功,、,匹配,、,推导,、,报错,编译原理,4、自上而下语法分析方法,（9）LL(1)文法的判定条件,文法不含,左递归,。,文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，,若,则,对文法中的每个非终结符A，若它存在某个候选首符集包含，则,如果一个文法G满足以上条件，则称该文法G为,LL(1)文法,。,编译原理,4、自上而下语法分析方法,（10）LL(1)分析方法,假设要用非终结符A进行匹配，面临的输入符号为a，关于A的所有产生式为,则LL(1)分析算法如下：,若 ，则指派 去执行匹配任务。,若a不属于任何一个候选首符集，则,若属于某个 且 ，则让A与自动匹配；,否则，a的出现是一种语法错误,。,根据LL(1)文法的条件，每一步这样的工作都是确信无疑的。,编译原理,4、自上而下语法分析方法,（11）FIRST集和FOLLOW集的构造,（12）预测分析表的构造,编译原理,5、自下而上语法分析方法,（1）基本概念,短语,、,直接短语,、,句柄,、,素短语,、,最左素短语,、,算符文法,、,算符优先文法,、,LR（0）项目,、,活前缀,、,可归前缀,（2）自下而上分析的基本思想及其核心,基本思想,：移进-归约,核心问题,：可归约串的界定,（3）自下而上分析的基本方法,算符优先分析法：以,最左素短语,作为可归约串，非规范归约,LR分析法：以,句柄,作为可归约串，规范归约,编译原理,5、自下而上语法分析方法,（4）给定一个文法的句型，找出其短语、直接短语、句柄、素短语和最左素短语,方法：首先画出句型的语法分析树，然后根据语法树寻找。,每棵子树的叶子结点自左至右排列构成一个相对于子树根的短语。,每棵简单子树（只有父子两代）的叶子结点自左至右排列构成一个直接短语。,最左简单子树的叶子结点自左至右排列构成一个句柄。,将所有短语中至少含一个终结符的短语，按长度从小到大排列，长度最短的认定为素短语，然后考察其余长度较大的，若不包含更小的素短语，则也为素短语。位于句型中最左边的素短语即为最左素短语。,5、自下而上语法分析方法,（5）算符文法与算符优先文法,算符文法,：任意产生式右部不含两个连续的非终结符，（.QR.）,算符优先文法,：算符文法中任意两个终结符之间至多只含,“,”,、,“,”,、,“,=,”,三种关系之一。,算符优先文法一定是算符文法,。,算符优先关系是有序的，但不满足对称性和传递性，即对于文法G的终结符a、b和c：,如果aa；,如果存在a=b和b=c，不一定有b=a或a=c；,如果存在ab和bc，也不能得出ac。,5、自下而上语法分析方法,（6）FIRSTVT集与LASTVT集的计算,FIRSTVT,规则一,：若有产生式Pa,或 PQa,，则aFIRSTVT(P)；,规则二,：若aFIRSTVT(Q)且有产生式 PQ,，则aFIRSTVT(P)；,规则三,：反复使用以上两条规则，直到FIRSTVT(P)不再增大为止。,LASTVT,规则一,：若有产生式P,a或 P,aQ，则aLASTVT(P)；,规则二,：若aLASTVT(Q)且有产生式 P,Q，则aLASTVT(P)；,规则三,：反复使用以上两条规则，直到LASTVT(P)不再增大为止。,5、自下而上语法分析方法,（7）算符优先关系表的构造,规则一,：对形如P,ab,或P,aQb,的产生式，有a=b；,规则二,：对形如P,aR,的产生式，若有bFIRSTVT(R)，则ab；,规则四,：对于语句括号#，有#=#，且若aFIRSTVT(S)和bLASTVT(S)，则有#。,5、自下而上语法分析方法,（8）优先表与优先函数之间的关系,对应一个优先关系表的优先函数f和g,不唯一,，只要存在一对，就存在,无穷多对,。也有许多优先关系表,不存在,对应的优先函数。,（9）算符优先分析算法,最左素短语的寻找依据：,5、自下而上语法分析方法,（9）算符优先分析算法,算符优先分析的特点：,算符优先分析一般并不等价于规范归约,无法使用单非产生式(如：TF)进行归约。,算符优先分析比规范归约过程要快，跳过了所有的单非产生式。,可能将本来不是句子的输入串误认为是句子。,（10）LR分析器的基本思想及其组成部分,基本思想,：,记住历史,、,展望未来,、,定夺现在,组成部分,：,输入缓冲区,、,分析栈,（状态、符号）、,分析表,（动作、转换）、,总控程序,5、自下而上语法分析方法,（11）四类LR分析表,LR分析表是LR分析器的核心，主要有以下几种分析表：,LR(0)表,、,SLR(1)表,（即简单LR表）、,LR(1)表,（即规范LR表）、,LALR表,（即向前LR表）。其中，L代表,自左至右扫描输入串,，R代表,构建最右推导的逆过程,，1代表,分析时每一步至多向前查看一个符号,，S,代表简单的,。,（12）LR分析器的四种动作,移进,、,归约,、,接受,、,报错,（13）LR分析器的两种冲突,移进,归约,冲突 和,归约,归约,冲突,5、自下而上语法分析方法,（14）四类不同的项目,项目类型,形 式,说 明,归约项目,A,这类项目表示句柄,恰好包含在栈顶中，即当前栈中符号正好为可归前缀，应按,A,进行归约。,接受项目,S,S,是文法唯一的开始符号。这类项目实际是特殊的归约项目，即按,S,进行归约，可直接归约到文法开始符号，表示分析成功。,移进项目,A,a,aV,T,，这类项目表示当前栈中符号串为不完全包含句柄的活前缀，为构成可归前缀，需将a移进分析栈。,待约项目,A,B,BV,N,，这类项目表示当前栈中符号串为不完全包含句柄的活前缀，为构成可归前缀，应先把当前输入字符串中的相应内容先归约到,B,。,5、自下而上语法分析方法,（15）四类LR分析表的构造,拓广文法,构造LR(0)（LR(0)和SLR分析表）或LR(1)（LR(1)和LALR分析表）项目集规范簇,构造相应分析表,（16）LR文法的特点,LR文法肯定是无二义的，一个二义文法决不会是LR文法。,LR分析法比预测分析法更加一般化。,LR(0)文法一定是SLR文法，SLR文法和LALR文法一定是LR(1)文法。,6、语法制导翻译和语义分析,（1）基本概念,S,属性文法,、,L,属性文法,（2）属性分类,综合属性,：用于,“,自下而上,”,地传递信息。,继承属性,：用于,“,自上而下,”,地传递信息。,终结符号只有,综合属性,，由,词法分析器,提供。,非终结符既可有综合属性也可有继承属性，文法开始符号的所有,继承属性,作为属性计算前的初始值。,（3）语义规则的表示,6、语法制导翻译和语义分析,（4）常见的中间代码的几种形式,后缀式,（逆波兰表示式）,图表示法,抽象语法树,DAG图,三地址代码,四元式,三元式,间接三元式,6、语法制导翻译和语义分析,（5）后缀式（逆波兰式）的表示,把运算量（操作数）写在前面，把运算符写在后面（后缀）的一种表达式表示方法。其归纳定义如下：,如果E是一个变量或常数，则E的后缀式是E自身。,如果E是E1 op E2 形式的表达式，op是二元操作符，则E的后缀式为E1E2op，其中E1，E2分别是E1和E2的后缀式。,若E是（E1）形式的表达式，则E的后缀式就是E1的后缀式。,6、语法制导翻译和语义分析,（6）将以下语句翻译为四元式序列,表达式（算术及布尔）,赋值语句,数组,IF语句,WHILE语句,（7）参数传递的几种方式,传地址,、,传值,、,传名,、,得结果,7、符号表,（1）符号表的重要性,合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。,（2）符号表的基本组成、基本操作,组成,：一张符号表的每一项入口包含：,名字栏,和,信息栏,操作,：,查表,、,填表,、,访表,、,更新,、,删除,（3）符号表的组织方式,按照处理对象的特点，符号表的组织方式一般可分为,直接方式,和,间接方式,。也按,标识符的种属,分别建立不同的符号表。,7、符号表,（4）符号表的构造和处理方法,符号表主要有三种构造和处理方式：,线性表,、,二叉树,、,杂凑（哈希）,。,（5）内情向量的基本表项,在编译过程中，碰到数组的说明时，通常将数组的有关信息记录在一个,内情向量表,中，这些信息包括：,维数,、,首地址,、,各维界差,、,各维上界,、,各