课程总结PPT课件

.,1,编译原理,第1章编译程序概论第2章PL/0编译程序的实现第3章文法和语言第4章词法分析第5章自顶向下语法分析方法第7章自底向上语法分析-LR分析第8章语法制导翻译和中间代码生成第9章符号表第10章目标程序运行时的存储分配第13章编译程序的开发途径（课件）,.,2,第1章编译程序概论,基本概念,1.2典型的编译程序可划分为几部分？各部分的主要功能是什么？每部分都是必不可少的吗？1.3解释方式和编译方式的区别是什么？1.4论述多遍扫描编译程序的优缺点。1.5解释下列名词：源程序、目标程序、翻译程序、汇编程序、编译程序、遍,.,3,第2章PL/0编译程序的实现,本章目的：对编译程序的实现建立起整体概念,.,4,第3章文法和语言,主要内容：1文法和语言的形式定义2文法的分类3上下文无关文法及其语法树4对实用文法的限制与扩充,.,5,GS：SABAaA|aBbB|b或GS：SaS|aBBbB|b语言属于3型语言。（可写成正则式：aa*bb*）,写出生成下述语言的文法，并指出该语言属于型还是型语言。,.,6,L=ambn|mn=0解：SaS|aBBaBb|或者SABAaA|aBaBb|2型文法，语言属于型语言,.,7,L=ambcm|m=1anbncmdm|m,n=1解：GS：SD|ABDaDc|abcAaAb|abBcBd|cd2型文法，语言属于型语言,.,8,给出下面文法GS所产生的语言SaS|bA|AaS|a解：代入：SaS|b(aS|a)|即SaS|baS|ba|S(a|ba)S|(ba|)所以S=(a|ba)*(ba|),.,9,2设有正规文法GS，GS：SaAAaA|bS|a（1）试构造一确定的有穷自动机M，使L（M）=L（G）；（2）求一正规式，恰好是该文法所定义的语言。解：(1)有穷自动机状态图：,.,10,GS：SaAAaA|bS|a,.,11,(2)根据文法，可得：AS|bS|a，代入SSa(S|bS|a)SaS|abS|aaS=(a|ab)*aa即为所求或a（a*ba）*a*a,GS：SaAAaA|bS|a,.,12,文法的分类,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)*VN(VNVT)*，(VNVT)*1型文法：对任一产生式，都有|(|表示串长)2型文法：对任一产生式，都有VN3型文法：任一产生式的形式都为（1）AaB或Aa：G为右线性文法；（2）ABa或Aa：G为左线性文法；（都为3型文法）其中AVN，BVN，aVT*,.,13,四类文法之间的逐级“包含”关系,L3（T3）L2（T2）L1（T1）L0（T0）,上述定义的4类文法在描述语法的能力上是从0型开始依次减弱（但规则的限制逐步增强）。,.,14,第4章词法分析,词法分析器的设计技术，即有穷状态自动机技术和正则式技术正则文法、正则式、非确定的有穷状态自动机（NFA）、确定的有穷状态自动机（DFA）之间的等价性及相互变换的方法。,.,15,解：NFAM构造如下：,1：构造NFA，识别语言x|x为非负偶整数，不允许0开头,对应正规文法：SD1A|2|4|6|8D11|2|3|4|5|6|7|8|9AD1A|0A|0|2|4|6|8,.,16,例2：识别由偶数个0和偶数个1组成的串。解：构造FA的状态转换图,GS:S0A|1B|A0S|1CB0C|1SC1A|0B,.,17,例：奇偶测试器（串中1的个数的奇偶性）语言：含有奇数个1的0、1串,.,18,根据正则文法来构造FA,已知：G=(VN，VT，P，S)是正则文法，不失一般性，假定规则是右线性，用文法的非终极符作为状态，开始符号作为开始状态。再增加一个新的符号R，作为终止状态。若文法中有：qiaqj则f(qi,a)=qjqja则f(qj,a)=RA则A也作为终止状态,.,19,根据FA来构造正则文法,已知FA=(Q,q0,F)，构造正则文法（VN，Vt，P，S）对转换函数(A,t)=B可写一产生式AtB可接受状态z，增加一产生式z此外，S=q0，VT=（FA的字母表）,根据FAM，可以构造出如下的正则文法：GS:S0S|1AA0A|1S|,.,20,例：文法G：SaS|aBBbCCaC|a求正则式。解：由得C=a*a代入得B=ba*a代入：SaS|aba*a所以S=a*aba*a即S=aibaj|i,j=1,.,21,例：已知正则式r=1(01)*(0*|1*)0，构造等价的NFAM。解：根据正则式定义语言的特征，可以使NFAM的状态图更简化。,.,22,第5章自顶向下语法分析方法,5.1语法分析器的功能5.2自顶向下分析面临的问题5.3LL分析法（预测分析法）5.4递归子程序法,.,23,第5章自顶向下语法分析方法,六.（13分）已知文法GS：SAB|aAbX|BYe|XcX|dYdY|1（4分）求每一非终结符的FIRST集和FOLLOW集,并将计算结果填入下表。2.（9分）填写该文法的LL（1）分析表。3（2分）该文法是否是LL(1)文法？请解释你的回答。,.,24,第7章自底向上语法分析-LR分析,本章内容预备知识:自底向上语法分析概述7.1LR分析器概述7.2LR(0)分析7.3SLR(1)分析*7.4LR(1)分析,复习：所有的课上例题，课后作业,.,25,七.（16分）已知文法GS：（1）（2分）求出S,A,B的first集和follow集。（2）（5分）求该文法的LR（0）项目集规范族。（3）（9分）该文法是否为LR（0）文法？是否为SLR（1）文法？说明理由，并构造出相应的SLR（1）分析表。,.,26,第8章语法制导翻译和中间代码生成,8.1语义分析概述8.2属性文法8.3S-属性文法的自下而上翻译8.4L-属性文法的自上而下翻译8.5中间代码的形式8.6简单赋值语句的翻译8.7控制结构的翻译,本章内容,.,27,第8章语法制导翻译和中间代码生成,8.1-8.4基本概念为主8.5中间代码的形式8.6简单赋值语句的翻译8.7控制结构的翻译后3节：对于给定的程序语言的语句,求翻译后的四元式目标代码。（参见课件上的习题）,复习重点,.,28,将下列语句翻译成四元式代码:IFabORcdTHENs:=aELSEs:=c+d（设当前四元式编号从10开始）。解：（10）（j，a，b，14）真(11)(j，_，_，12)(12)(j，c，d，14)真(13)(j，_，_，16)假(14)(:=，a，_，s)(15)(j，_，_，18)(16)(+，c，d，T1)(17)(:=，T1，_，s)(18),.,29,符号表的作用保存各类标识符的属性检查上下文语义的正确性作为目标代码生成阶段地址分配的依据,第9章符号表管理技术,.,30,第章目标程序运行时的存储组织,根据程序的生命周期（编译和运行），编译中存储分配策略分为：静态存储分配栈式动态存储分配堆式动态存储分配,编译程序采用的存储分配策略与它所编译的源语言有关。,.,31,采用静态存储分配的语言必须满足下列条件：（1）不允许过程有递归调用。（2）不允许有可变大小的数据项，如可变数组或可变字符串。（3）不允许用户动态建立数据实体。静态存储分配策略实际上是把内存看成一个一维数组。其特点是：如果编译时将一个存储单元分配给某个变量，那么在整个程序运行期间，该单元就一直被这个变量所占用。这种策略对FORTRAN语言是一种合适的策略，但对块结构语言显然不是很好的。,第章目标程序运行时的存储组织,.,32,栈式动态存储分配,栈式动态存储分配策略是将整个程序的数据空间设计为一个栈(称为运行时栈)。（一）每当程序调用一个过程（进入一个块）时，就在栈顶为被调过程分配一个新的数据空间；即：保留块的开始地址：基地址寄存器（BASE，或用sp）。为当前块分配存储：在栈顶留出相应单元，作为当前数据区。为每个局部量分配相对地址，填入符号表（adr属性）中。相对地址为相对于该块数据区开始地址的位移量。块内变量x的运行时地址：BASE+offset（x）,.,33,10.3栈式动态存储分配,栈式动态存储分配策略是将整个程序的数据空间设计为一个栈。（二）当被调过程结束时（退出块），则释放栈顶的这部分空间；即：恢复当前块的开始地址。top=sp-1sp=老sp,栈式动态存储分配策略适合于块结构语言。如C、PASCAL等语言即采用这种存储分配方式。,top,sp,.,34,何时采用堆式动态存储分配：如果源语言提供自由地申请与释放数据空间的机制，未必服从“先申请后释放，后申请先释放”的原则时，不适宜用栈，应该采用堆式动态存储分配。堆式动态存储分配特点：1局部名的值在活动结束时必须被保存。2.被调用者的活动生存期超过调用者。new(p);dispose(p);,第章目标程序运行时的存储组织,.,35,第3章编译程序的开发途径,编译程序的型图：任何一个编译程序涉及到