编译原理--总复习

编译原理总复习认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分应该是基本概念题，但也会有一些综合性的题目。自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”。复习内容包括核心算法和重要概念（不再详细点出）：复习：什么是语言，什么是文法？掌握由文法求语言和由语言求文法，重点复习课本的几道例子和课后作业的几个习题请问“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生请问下列是否是句子：我是大学生、王明是大学生、王明学习英语、他学习英语、你是工人复习：学会求闭包，正闭包：•符号串集合：若集合A中一切元素都是某字母表S上的符号串，则称A为字母表S上的符号串集合。•两个符号串集合A和B的乘积定义为AB={xy|x属于A且y属于B}若集合A={a,b}B={c,d}则AB={ac,ad,bc,bd}{ε}A=A{ε}=A(∵εx=xε=x)•使用S*表示S上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。•从S*中除去ε得到的集合记为S+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：设Σ={0,1}，则Σ*={ε,0,1,00,01,10,11,000,001,010,…}例：设Σ={a,b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}复习：弄清楚什么是正规式、什么是正规文法、什么是语言、什么是正规集正规式和正规文法的互换，请看课本例题（1）将正规式转换成正规文法•例求正规式a(a|d)*的正规文法解：分析过程如下：S--A--*A--A→εB--(a|d)BB→ε所以最终的正规文法为：SaAA-(a|d)B|εB-(a|d)B|ε例子2：已知正规文法G1的产生式，求出它所定义的正规式。产生式为：S→aS|aBB→bB|bAA→cA|c解：（1）S=aS|aBB=bB|bAA=cA|c(2)根据定理2由S=aS|aB得S=a*aB=a+B同理由B=bB|bA得B=b+A由A=cA|c得A=c+代入得B=b+c+,S=a+b+c+。故正规式为S=a+b+c+。例3：考虑文法G[S]：S→aSbS|bSaS|ε(1)试用最左推导说明此文法的二义性。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么？解答：(1)句子abab有如下两个不同的最左推导：S=aSbS=abS=abaSbS=ababS=ababS=aSbS=abSaSbS=abaSbS=ababS=abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：（推导过程请不要偷工减料）S=aSbS=aSbaSbS=aSbaSb=aSbab=ababS=aSbS=aSb=abSaSb=abSab=abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串复习：识别二义文法，懂得转换二义文法为无二义文法判断一个语法是否为二义文法（重点）若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。•判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。•二义文法改造为无二义文法（重点）G[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE→(E)注意：必须规定优先顺序和结合律复习：大家要理解DFA和NFA的含义，两者之间的区别和联系，以及两者怎样转化；最后应该理解描述一个词法的DFA是否是唯一的，怎样把他化为最简的DFA等几个问题。懂得求解NFADFA，也就是NFA的确定化、最小化懂得根据正规式画出DFA，请看课本例子例子一：G[E]为:E-E+T|E-TT-T*F|T/F|FF-(E)|I请问文法G[E]是否存在句型E+T*F？如果存在，请写出该句型E+T*F的所有短语、直接短语、句柄。（提醒，大家需要掌握素短语、最左素短语）解答：因为存在推导序列:EE+TE+T*F所以E+T*F是句型句型E+T*F的短语有:E+T*F,T*F直接短语有:T*F句柄为:T*F素短语和最左素短语呢？扩展复习：需要掌握知识点：消除左递归、消除回溯文法G(E):E→E＋T|TT→T*F|FF→(E)|i经消去直接左递归后变成：E→TEE→+TE|T→FTT→*FT|F→(E)|i假定有文法G(S):(1)S→xAy(2)A→**|*请消除它的回溯。消除方法：提取候选式前面相同的部分。因为A→**|*的两个候选式前面字符串相同，所以存在回溯，解答方法：提取相同部分：A→*(*|)消除后为：A→*BB→*|例子二：请构造如下文法的LL（1）分析表，并且写出输入串#a+a#的分析过程解答：需求first和follow集合，上图中的表格就是解题的答案复习：对每一文法符号XVT∪VN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若XVT，则FIRST(X)＝{X}。2.若XVN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→也是一条产生式，则把也加到FIRST(X)中。3.若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1…Yi-1)，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j＝1，2，…，k，则把加到FIRST(X)中。对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每},|{)(*TVaAaSaAFOLLOW个FOLLOW不再增大为止：1.对于文法的开始符号S，置＃于FOLLOW(S)中；2.若A→B是一个产生式，则把FIRST()\{}加至FOLLOW(B)中；3.若A→B是一个产生式，或AB是一个产生式而(即FIRST())，则把FOLLOW(A)加至FOLLOW(B)中。First和follow的求解方法请按照平时上课讲解的求解方法例子：求表达式文法的语法符号的FIRST集和FOLLOW集表达式文法:E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id解：FIRST(F)={(,id}FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)={(,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(()={(}FIRST())={)}FIRST(id)={id}FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+,),#}FOLLOW(T')=FOLLOW(T)={+,},#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={*,+,},#}构造LL(1)分析表的方法：在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。1.对文法G的每个产生式A→执行第2步和第3步；2.对每个终结符aFIRST()，把A→加至M[A，a]中；3.若FIRST()，则对任何bFOLLOW(A)把A→加至M[A，b]中。4.把所有无定义的M[A，a]标上“出错标志”懂得构造LR(0)SLR(1)LR(1)的分析表，并且能写出字符串归约分析过程。例:G[S]:SaAcBe[1]Ab[2]AAb[3]Bd[4]请构造出LR(0)分析表，同时写出字符串abbcde#的归约过程ＬＲ分析器模型：ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1解：Stepstates.Syms.Therestofinputactiongoto10#abbcde#s2202#abbcde#s43024#abbcde#r2goto(2,A)4023#aAs650236#aAbcde#r36023#aAs570235#aAcde#s8802358#aAcde#r4902357#aAcBs910023579#aAcBe#r11101#Sacc复习如何求firstVT和lastVT分析算符优先的字符串归约过程三、中间代码的形成中间代码的常见形式：1．逆波兰记号（后缀式）•将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。三元式和抽象语法树表示格式：(算符,第一运算对象,第二运算对象)如：a=b*c+b*d(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2))(4)(=,(3),a)3.四元式（1）格式：(算符,第一运算对象,第二运算对象,结果)如：a=b*c+b*d(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(=,t3,-,a)四、简单赋值语句的翻译四元式形式:t:=arg1oparg2语义属性：id.name,E.placeE.place:值E的位置函数：lookup(id.name);返回指向id的指针过程：emit(t:=arg1oparg2);输出四元式newtemp;生成临时变量产生式和语义描述：(1)Sid:=E{P:=lookup(id.name);ifPnilthenemit(P“:=”E.place)elseerror}(2)EE1+E2{E.place:=newtemp;emit(E.place“:=”E1.place“+”E2.place)}(3)E-E1{E.place:=newtemp;emit(E.place“:=”“uminus”E1.place)}(4)E(E1){E.place:=E1.place}(5)E{E.place:=newtemp;P:=lookup(id.name);elseerror}=a+**bcbd段考最后一道题目的答案：3．文法G[S]的产生式如下：S→SbEa|EE→a（1）请判断该文法是不是LR(1)文法？如果是，填写下面的LR(1)分析表。（2）给出输入串abaa归约分析过程。（20分）