编译原理总复习串讲

单击此处编辑母版标题样式,*单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,总复习串讲,1、复习范围。,2、习题讲解。,3、模拟题讲解。,教材,编译原理 陈意云 ， 高教京,。,参考书籍：,编译原理陈火旺国防工业出版社,编译原理及实践,Louden, K.C.,机械工业出版社,编译原理和技术陈意云 中国科技大学出版社,编译原理，吕映芝等，清华大学出版社，1998年1月第1版或第2版。,章节,第一章 概述,第三章 文法和语言,第四章 词法分析,第五章 自顶向下语法分析,LL（1）,文法,第六章 自底向上优先语法分析,第七章 自底向上语法分析,LR,分析法,第八章 语法制导翻译和中 间代码生成,第十一章 代码优化,一、概论主要内容,编译程序的实现策略,T,型图,交叉编译,自展,编译程序总体结构,8项功能、8个模块,书写语言,目标语言,源语言,编译程序的结构,二、文法分类主要内容,文法的定义：,=(,T,，,N,，,，),推导与归约：,最左推导（左句型、最右归约）,最右推导（右句型、规范句型、规范（最左）归约）,语法树,（,CFG,的分析树）,二义性（定义）,文法的分类,PSG、CSG、CFG、,RG,（,短语、上下文有关、上下文无关、正规 文法）,PSL、CSL、CFL、RL,三、词法分析,1、三型语言（,RL）,的等价描述,1),RG、RE、FA(DFA、NFA 、,-NFA),2) RG,RE,例：,S0A|1B A1S|1B0S|0,3) RE,RG(,正规定义式),例：1|0 100 0,*,(100),*,2(1|0),+,|0,*,4),RG,FA(FA,RG、RE,FA、FA,RE),AaB: a,Aa： a T,主要内容,2、,扫描器的设计与实现,1) 输入(,Character,字符流),2) 输出(,Token,符号,二元组流),3) 缓冲区,4) 状态图的实现,3、,Lex,四、自顶向下 语法分析,1、左递归按转换规范完成变换,将,AA|,替换为,AA,和,A,A,|,一般地：,用产生式组,A,1,B|,2,B,|,n,B,B,1,B|,2,B,|,n,B|,替换产生式组,A,A,1,|A,2,|A,n,|,1,|,2,|,m,其中：,B,为新变量，相当于,A,四、自顶向下 语法分析,2、自顶向下：递归子程序、预测分析(,LL),核心寻找最左推导,关键技术：根据当前输入符号确定候选式,FIRST(),集与,FOLLOW(A),集,对于,(,T,N,),*,定义:,的首符号集,FIRST()=a|,*,a，a,T,*,P70,对于,A,N,定义,A,的后续符号集,：,P71,FOLLOW(A)=a|,S,*,Aa,，a,T,五、自底向上语法分析,自底向上：算符优先、,LR(0)、SLR(1)、LR(1)、LALR,项目：,A,x.by,A,x.By,A,x.,A,.,项目集闭包与求法,移进归约分析,核心：在句型中寻找句柄进行归约,算符优先关系表、,LR,分析表（动作表和状态转移表）,六、语义分析和中间代码生成,属性文法,定义、属性分类、属性文法分类,简单算术表达式,中间代码：三元式、四元式、逆波兰,七、代码优化,1、基本概念,2、,DAG,图,第三章 练习参考答案,第,1,题,(1),允许,0,开头的偶正整数集合的文法,解：,E-NT|D,T-NT|D,N-D|1|3|5|7|9,D-0|2|4|6|8,(2),不允许,0,开头的偶正整数集合的文法,解：,E-NT|D,T-FT|G,N-D|1|3|5|7|9,D-2|4|6|8,F-N|0,G-D|0,第三章练习参考答案,第,2,题,可,为句子,a+a*a,构造两个不同的最右推导,:,解：,最右推导,1,表达式,表达式运算符表达式,表达式运算符,a,表达式*,a,表达式运算符表达式*,a,表达式运算符,a * a,表达式+,a * a,a + a * a,最右推导,2,表达式,表达式运算符表达式,表达式运算符表达式运算符表达式,表达式运算符表达式运算符,a,表达式运算符表达式 *,a,表达式运算符,a * a,表达式+,a * a,a + a * a,第三章练习参考答案,第,3,题，,GE,为,:,E-E+T|E-T,T-T*F|T/F|F,F-(E)|I,解：,因为存在推导序列,:,E,E+T,E + T * F,句型,E+T*F,的,短语有,:,E+T*F,T*F,直接短语有,:,T*F,句柄为,:,T*F,第三章练习参考答案,第,4,题,（,1,）,a,n,b,n,a,m,b,m,| n,，,m=0 (2) 1,n,0,m,1,m,0,n,| n,，,m=0,S-AA S-1S0|A,A-,aAb,|,A-0A1|,第,5,题，,(1),a,n,b,m,|n,m=1 ,的三型文法为：,S-,aA,A-,aA,|B,B-,bB,|b,(2),a,n,b,m,c,k,|n,m,k=0 ,的三型文法为,:,A-,aA,|B,B-,bB,|C,C-,cC,|,第四章 作业及答案,1.,构造正规式1(0|1)*101相应的,DFA,.(P66),确定化,（子集法）,0,1,X,A,A,A,AB,AB,AC,AB,AC,A,ABY,ABY,AC,AB,重新命名，令,AB,为,B,、,AC,为,C,、,ABY,为,D,0,1,X,A,A,A,B,B,C,B,C,A,D,D,C,B,DFA,：,第五章 练习及答案,7、对于一个文法消除左递归，提取左公共因子。构造,LL（1）,分析表。,练习7（2）,（2） 文法：,A-aABe|a,B-Bb|d,改写文法为：,0),A-a N,1) N-A B e,2) N-,3) B-d M,4) M-b M,5) M-,计算,FIRST 、 FOLLOW,集,=,| |,FIRST | FOLLOW |,+-+-+-+,| A | a | #,d |,+-+-+-+,| B | d | e |,+-+-+-+,| M | b, | e |,+-+-+-+,| N | ,a | #,d |,=,（,预测分析表,Predicting Analysis Table,）,=,| |,a | e | b | d | # |,+-+-+-+-+-+-+,| A |-a N | | | | |,+-+-+-+-+-+-+,| B | | | |-d M | |,+-+-+-+-+-+-+,| M | |- |-b M | | |,+-+-+-+-+-+-+,| N |-A B e | | |- |- |,=,由预测分析表中无多重入口判定文法是,LL(1),的。,第六章 例题,文法,G：,(0) S,S,(1) S,rD,(2) D D,i(3) D i,文法,G：,(0) S,S,(1) S,rD,(2) D D,i(3) D i,I,0,:S,SS,rD,I,2,: S, r,DD,D,i,D,i,I,3,: S,rD,D,D,i,I,4,:,D, i,I,5,: D, D,i,I,1,:,S,S,I,6,:,D,D,i,S,r,i,D,i,LR(0),分析表,一、单项选择题1、设,r=(a|b|c)(x|y|z),则,L（r）,中元素为 个（ ）,A9 B6 C18 D27 2、,正则集合,L=a,n,|n0,相应的正则表达式是（ ）,Aa* Ba+ C,aa,* D,aa,+,3、如果一个文法的产生式形式为：,A,Ba,或,A,a,，,其中,A,、,B,N,，,a,，,则称此文法是左,线性的。对每一个,左,线性文法,G1,_,一个,右,线性文法,G2,和其等价,。（ ）,A,都存在,B,不存在,C,不一定存在,D,无法判定,4、,xab,+,cde,-*f/+:=,是赋值语句（） 相应的后缀式,A,x:=a+b+c*d-e/f,B,x:=a+(b+c)*d-e/f,C,x:=a+b+c*(d-e)/,f,Dx:=a+b+c+(c*d)-e/f,5、设文法,G（S,为其开始符号）产生式如下：,S,aSb,|,ab,|,则,G,是一个（ ）,ALR（1）,文法,BSLR（1）,文法,C,三型文法,D,二型文法,6、上下文无关文法其能力相当于(),A、,线性有界自动机,B、,下推自动机,C、,图灵机,D、,有限自动机,二、判断题1、,局部优化是局限于一个基本块范围内的优化。（ ）,2、对任意的,LR（1）,文法,G，,都存在,DFA M，,满足,L（M）=L（G）。（ ）3、,对任何一个正则集合,L，,都有下正则表达式,r，,满足,L（r）=L。（ ）4、,任何2型文法的任何句子的句柄都是唯一的。（ )5、,LL（1）,文法一定是无二义性的。（ ）,总复习串讲结束！,谢谢大家！,