编译原理复习总结_东北大学.ppt

单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,编译方法,2013,年,12,月,复习,.,总结,第一部分,考试范围,一,.,概念部分,概念词语解释,(,简单明确,),概念词语填空,(,不求全，只求准,),二,.,形式语言基础,简单文法构造,自己总结。,如：给定一符号串集合，,构造文法,。,主要语法成分的识别,给定一文法和一个符号串,，证明 是句型,(,句子,),，并画,语法树,求短语、简单短语和,句柄,。,(,接上页,),简单文法变换技术,如 消除文法的直接左递归！主要是三种常用的文法变换方法,圆括号,、,方括号,和,花括号,。,三,.,自动机基础,简单有限,自动机的构造,如 给定一符号串集合,(,或正规式或正规文法,),，构造有限自动机（,DFA,）,求一个有限,自动机所定义的语言,(,符号串集合,),。,(,接上页,),四,.,词法分析,1.,2,个实验,。,五,.,语法分析,给定文法，,构造递归子程序,（框图）,判断一个文法是否是,LL(1),文法,；,(1),消除,边，,NFA=DFA,(2),NFA=DFA,。,5.,有限自动机的实现,有限自动机的,确定化,。,4.,确定的有限自动机的,最小化,。,2.,会写,TOKEN,序列；,3.,词法分析技术应用,；,(,接上页,),七,.,中间代码生成,会写常用语句的中间代码,(,逆波兰式,，,四元式,),；,会构造常用语法成分的,翻译文法,；,给定翻译文法和,动作序列,，会走,翻译过程,。,给定文法，,构造,LL(1),分析表，,LR(0),文法的判断和相应,分析表的构造,。,六,.,符号表组织,符号表结构以及填写。,5.,简单优先,文法的判断和相应,分析表的构造,。,6.,语法分析器的构造,。,4.,语法制导翻译技术的应用。,(,接上页,),九,.,目标代码生成,1.,会写常用语句在,单寄存器下的目标代码生成过程,；,八,.,优化处理,3.,基本块内四元式的优化。,1.,基本块的划分。,2.,局部优化的几种常见方法。,1.,编译程序,(,compiler,),目标语言,词法,分析,源,语言,语法,分析,语义,分析,优化,处理,代码,生成,错 误 处 理,符 号 表 管 理,2.,编译程序结构,五个阶段,第二部分 基本概念总结,是一种语言,翻译程序,，它特指把,某种,高级程序设计语言,翻译成具体计算机上的,低级程序设计语言,。,4.,文法,(,上下文无关文法,),(,接上页,),3.,形式语言,所有,符号串,之,集合,；其中的每个符号串称为,句子。,G(Z)=(V,N,V,T,S,P),V,N,:,非终结符集（定义的对象集，如：语法成分等,),；,例：,G(E),E-E+T|E,T|T,T-T*F|T/F|F,F-i|(E),简单,算术表达式,文法,其中：,V,N,=,E,T,F,;,VT,=,i,+,-,*,/,(,),;,Z,=,E,;,P,：,可用,四元组表示：,V,T,:,终结符集（字母表）；,S:,开始符号（研究范畴中，最大的定义对象）；,P:,规则集（又称产生式集）；,字母表,上的符号，按一定的,规则,组成的,是定义语言的,规则集，,(,接上页,),5.,有限自动机,(finite automata,）,FA,是一种,数学模型，,用于描述,正规语言,FA=(Q,S,F,),：,变换（二元函数）：,Q,(,有限状态集,);,F,(,结束状态集,F,Q,）；,S,(,开始状态集,S,Q,）,；,(,字母表,),；,i,j,a,或,(i,a,）,=j,确定的有限自动机DFA),特征,：,开始状态唯一,;,变换函数单值；,不带,边。,非确定的有限自动机,(NFA),带有,边的,非确定的有限,自动机,(,NFA),不带有,边的,非确定的有限,自动机,(NFA),-,不能全部具备上述特征者！,6.,有限自动机的分类,其中,可定义为,五元组：,(,接上页,),(1),识别单词,从用户的源程序中把单词分离出来,;,(2),翻译单词,把单词转换成机内表示，便于后续处理。,7.,词法分析任务,标识符,(i),，常数,(c),，关键字,(k),，界符,(p),。,8.,单词的分类,9.,有限自动机作为单词识别器,+,-,-,#,l,d,-,d,I|d,标识符,|,关键字,无符号整数,界符,注,如何区别标识符,|,关键字？,通过查,关键字表,决定之：,若表中存在，则视为,关键字,；否则视为,标识符,！,滤掉回车换行、空格！,(,接上页,),形式上说，语法分析是指对给定的符号串（,），判定其是否是某文法,G(S),的句子。即,10.,语法分析,语法分析主要功能是识别短语和句型，,Z,成立吗,?,=,+,1.,自顶向下法,（,推导法,）,2.,自底向上法,（,归约法,）,11.,语法分析方法分类,12.,四种实用分析方法及相应文法,适应于自顶向下的分析法,-,LL(1),文法,是指文法中，,具有相同左部的各产生式，其选择集合不相交,。,适应于自底向上的分析法,-LR(0),文法,是指文法的,句柄识别器,(,有限自动机,),无冲突项目,。,(,接上页,),13.,标识符,的,语义信息：,名字、类型、种类、地址。,14.,语法制导翻译技术,通俗地说，所谓,语法制导翻译技术,，是指：,语法分析技术 翻译文法构造技术,+,15.,优化处理,优化处理,是指,产生更高效的目标代码,所做的工作。,或者说 为,提高目标程序质量,所做的工作。,第三部分 基本运算总结,1.,判定一个符号串是否是某文法的句子：,A-d B b|c,B-B b|,G(S):S-a A B|a A c,哪个符号串是句子？,adbb abc,如：设有文法,【,解,】,adbb?,S,=adBbb,+,S=adbb,=aAB,也可以用 语法树证明：,S,a A B,d B b,B b,=adBb,=adbb,adbb,是句子,abc?,S=aAB,=adBbB=?,=acB=?,又,S=aAc,=adBbc=?,=Acc=?,abc,不是句子。,也可以用 语法树证明：,a A c,S,d,?,a A B,S,c,?,a A B,S,d,?,a A c,S,c,?,(,接上页,),2.,简单的文法构造：,设有符号串集合：,L=a,ba,n,c|n0 ,构造上下文无关文法；,构造正规文法。,解：,构造上下文无关文法；,(2),构造正规文法。,G(S):,S-a|b A c,A-a A|G(S):,S-a|b A,A-a A|,c,3.,求解一个句型的短语和句柄：,如：,已知文法,G(S):,A-a A c|b,试指出句型,abAb,的短语和句柄：,【,解,】,首先画该句型的语法树：,S,a S A,b A,b,句柄,是,一个句型的,最左简单短语。,短语,是一个句型,任一子树的树叶全体。,简单短语,是一个句型,任一简单子树的树叶全体。,根据语法树确认短语和句柄：,短语：,abAb,bA,b,简单短语：,bA,b,句柄,：,bA,S-b A|a S A,【,解,】,S-a A b|a,(,首符号相同,),变换后得：,S-a,A b,或,S-a S;S-A b|,A-A b|d直接左递归）,变换后得：,A-d,b,或,A-d A;A-b A|,4.,简单的文法变换：,如：有文法,G(S):S-a A b|a,A-A b|d,(1),具有相同左部的各产生式，其首符号不相同；,试进行文法变换，使其满足以下两个条件：,(2),消除文法的左递归,.,变换后的文法,G(S):,S-a,A b,A-d,b,5.,有限自动机的构造：,如：已知符号串集合：,A=,a,n,ba,n,|n0,试构造有限自动机。,【,解,】,a,+,1,b,-,此集合有两种句型（还包含一个空串,）,分别构造之：,2,-,+,1,2,+,-,a,合成为一个：,b,-,2,+,1,-,a,a,错误,3,b,正确,+,1,-,a,a,2,-,a,-,6.,有限自动机的确定化：,如,把下述,NFA,转换为,DFA:(,消,边,DFA,最小化,略,),A1,，,2,b,a,+,a,b,a,b,+,-,+,C2,3,B2,C2,3,C2,3,B2,C2,3,B2,-,a,a,b,+,-,DFA1:,A,B,C,b,b,a,b,a,b,+,-,A1,b,a,+,B2,3,B2,3,B2,3,-,a,b,+,-,DFA2:,A,B,7.,正规语言,的三种表示方法：,(2),有限自动机：,+,-,a,b,c,c,设有正规语言：,L=ac,n,bc,m,|n0,m0,(1),正规式：,e=ac,*,|bc,3),正规文法：,G(S):,S-a A|b B,A-c A|,B-c A,S,A,B,S,A,B,令,3,5,y,a,x,8.,已知源程序片断,写出词法分析后的,TOKEN,序列,:,如：,if(x 5)y=3*x,a;,1,float,2,for,3,if,4,int,5,struct,6,while,7,1,+,2,-,3,*,4,/,5,=,6,aASb|Bd;A-cS|,;B-bB|d,遇终结符，判定之；,遇非终结符，调用之；,遇,，直接出口。,算法,入口,c,NEXT(w),出口,遇,时,n,y,S,A,子程序,b,NEXT(w),出口,n,y,B,d,NEXT(w),err3,y,n,入口,B,子程序,11.,会判定,LL(1),文法和构造,LL(1),分析表,如 已知文法,G(S),：,S-a A S b|B d A-c S|,B-b B|d,（,1,）求选择集合；证明是,LL(1),文法；,select()=,select()=,select()=,select()=,select()=,select()=,=,【,解,】,（,1,）求选择集合,a,b,d,c,follow(A),a,b,d,b,d,（,2,）,LL(1),分析表,:,三对选择集合两两不相交,!,G(S),是,LL(1),文法,!,d,B,A,S,c,b,a,（,2,）构造,LL(1),分析表。,如,12.,会判定,LR(0),文法和构造,LR(0),分析表,G(Z):Z-aBAd,A-bc|,c,B-bB|c,B-c,9,Z-Z,1,(0),Z,-a,2,B,3,A,4,d,5,(1),A-b,6,c,7,(2),|,c,8,(,3),扩展文法,LR,（）分析表：,Z,A,0,d,#,B,c,b,a,a,2,Z,1,1,A,4,OK,r,(1),r,(1),r,(1),r,(1),r,(1),d,5,r,(3),r,(3),r,(3),r,(3),r,(3),r,(2),r,(2),r,(2),r,(2),r,(2),c,8,b,6,B,3,c,9,5,4,8,6,7,3,2,9,r,(4),r,(4),r,(4),r,(4),r,(4),c,7,分析表中无冲突项目，是,LR(0),文法！,0,【,例,】,G(S):,S,aAeB|b,，,A,Sb|e,，,B,aA,S,A,B,a,b,e,S,A,B,a,e,S,A,B,FIRSTVT,a,b,S,e,a,b,a,LASTVT,B,b,A,e,b,e,A,b,e,头符号集合,尾符号集合,优先矩阵,表项,=,空,表示两个符号不可能相临。,13.,会判定简单优先文法和构造简单优先分析表,14.,会写,表达式,的,逆波兰式,例：求下述表达式的逆波兰式：,=,pos,(,a+b/d,),e,*,pos,(,(a+b/d)*e,),=,pos,(,(a+b/d),),pos,(,e,),*,=,pos,(,a,),pos,(,b/d,)+,e*,=,a bd/+e*,pos,(,(a+b/d)*e,),=a b d/+e*,(a+b/d)*e,pos()?,脱括号,a,b,d,/,+,e,*,注,根据逆波兰式特点：,运算对象顺序不变；,运算符紧跟运算对象之后。,可直接写出：,算术表达式,四元式翻译文法：,15.,会,构造常见语法成分,的,四元式,翻译文法,【,例,】,算术表达式,逆波兰式翻译文法：,E-T|E+T,“,PUSH(+),”,T-F|T*F,“,PUSH(*),”,F-i,“,PUSH(i),”,|(E),其中,:,PUSH(x),-,把,x,压入分析栈；,QUAT(+),QUAT(*),16.,会走翻译过程的,动作序列,：,符号串,a*(b+c),的分析,(,翻译,),过程,(,推导法,):,E,=T,=T*F,*,=F*F,*,=a,a,*F,*,=a,a,*(E),*,=a,a,*(E+T,+,),*,=a,i,*(T+T,+,),*,a,a,*(b,b,+c,c,+,),*,=,+,【,例,】,算术表达式,逆波兰式翻译文法,a:,动作符号；,含义：,输出,(,a,),E-T|E+T,+,|E-T,-,T-F|T*F,*,|T/F,/,F-i,i,|(E),G(E),abc+*,动作序列的执行结果：,相应的,四元式,动作序列：,PUSH(a)PUSH(b)PUSH(c)GEQ(+)GEQ(*),执行的,过程,、,结果,如何,?!,G(S),：,S-a|,|(T),T-T,S|S,【,例,:,】,给定文法如下：,(,(a,),a),变换为,(,+(a+)+a),1.,给出翻译文法,统计符号串中,a,的个数和,的个数；,给定的符号串有如：,=(a,),a),17.,语法制导翻译技术应用：,2.,给出翻译文法,进行符号串变换；,如,:,【,解,:1,】,G(S),：,S-a,“,a1,”,|,“,a2,”,|(T),T-T,S|S,其中,:,a1:num1+;,a2:num2+;,19.,会填写单寄存器下,从,四元式,=,目标语言,的生成表,:,如,设有语句序列：,If(a+b10)x=(a*b)/(i+(a*b);y=x;,18.,基本块划分和优化,1.,写出四元式序列,;,2.,进行基本块划分,;,3.,进行必要的优化,;,4.,写出目标代码,.,放映结束！,