编译原理--总复习.doc

编译原理总复习认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分应该是基本概念题，但也会有一些综合性的题目。自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”。复习内容包括核心算法和重要概念（不再详细点出）：复习：什么是语言，什么是文法？掌握由文法求语言和由语言求文法，重点复习课本的几道例子和课后作业的几个习题请问“我是大学生”是否是该语言的句子？句子:= 主语谓语主语:= 代词|名词代词:= 你 | 我 | 他名词:= 王明 | 大学生 | 工人 | 英语谓语:= 动词直接宾语动词:= 是 | 学习直接宾语:= 代词|名词句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生请问下列是否是句子：我是大学生、王明是大学生、王明学习英语、他学习英语、你是工人复习：学会求闭包，正闭包：符号串集合：若集合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-aAA-(a|d)*A-(a|d)B AB-(a|d)B B所以最终的正规文法为： SaA A-(a|d)B | B-(a|d)B|例子2：已知正规文法G1的产生式，求出它所定义的正规式。 产生式为：SaS|aB BbB|bA AcA|c 解：（1）S=aS|aB B=bB|bA A=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：考虑文法GS：SaSbS|bSaS|(1)试用最左推导说明此文法的二义性。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么？解答：(1) 句子abab有如下两个不同的最左推导：S = aSbS = abS =abaSbS = ababS = abab S = aSbS = abSaSbS = abaSbS = ababS = abab 所以此文法是二义性的。(2) 句子abab的两个相应的最右推导：（推导过程请不要偷工减料） S = aSbS = aSbaSbS = aSbaSb = aSbab = abab S = aSbS = aSb = abSaSb = abSab = abab(3) 句子abab的两棵分析树： (a)(b)(4) 此文法产生的语言是：在a，b上由相同个数的a和b组成的字符串复习：识别二义文法，懂得转换二义文法为无二义文法判断一个语法是否为二义文法（重点）若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。二义文法改造为无二义文法（重点）GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 注意：必须规定优先顺序和结合律复习：大家要理解DFA和NFA的含义，两者之间的区别和联系，以及两者怎样转化；最后应该理解描述一个词法的DFA是否是唯一的，怎样把他化为最简的DFA等几个问题。懂得求解NFADFA，也就是NFA的确定化、最小化懂得根据正规式画出DFA，请看课本例子例子一：GE为: E-E+T|E-T T-T*F|T/F|F F-(E)|I请问文法GE是否存在句型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):EET | TTT*F | FF(E) | i经消去直接左递归后变成： ETE E+TE | e TFT T*FT | e F(E) | i假定有文法G(S): (1) SxAy (2) A*|*请消除它的回溯。消除方法：提取候选式前面相同的部分。 因为A*|* 的两个候选式前面字符串相同，所以存在回溯，解答方法：提取相同部分： A*(*|e) 消除后为： A*B B*|e例子二：请构造如下文法的LL（1）分析表，并且写出输入串#a+a#的分析过程解答：需求first和follow集合，上图中的表格就是解题的答案复习：对每一文法符号XVTVN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1. 若XVT，则FIRST(X)X。2. 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若Xe也是一条产生式，则把e也加到FIRST(X)中。3. 若XY是一个产生式且YVN，则把FIRST(Y)中的所有非e-元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有e(即Y1Yi-1e)， 则把FIRST(Yi)中的所有非e-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有e，j1，2，k，则把e加到FIRST(X)中。对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1. 对于文法的开始符号S，置于FOLLOW(S)中；2. 若AaBb是一个产生式，则把FIRST(b)e加至FOLLOW(B)中；3. 若AaB是一个产生式，或AaBb是一个产生式而b e (即eFIRST(b)， 则把FOLLOW(A)加至FOLLOW(B)中。First 和 follow的求解方法请按照平时上课讲解的求解方法例子：求表达式文法的语法符号的 FIRST 集和FOLLOW 集表达式文法:ETE E+TE| TFT T*FT| F(E)|id解：FIRST(F)=(,idFIRST(T)=FIRST(F)=(,id FIRST(E)=FIRST(T)=(,id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST( ( )=(FIRST( ) )=)FIRST(id)=idFOLLOW(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及其任意候选a都构造出FIRST(a)和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。1. 对文法G的每个产生式Aa执行第2步和第3步；2. 对每个终结符a FIRST(a)，把Aa加至MA，a中；3. 若eFIRST(a)，则对任何bFOLLOW(A)把Aa加至MA，b中。4. 把所有无定义的MA，a标上“出错标志”懂得构造 LR(0) SLR(1) LR(1)的分析表 ，并且能写出字符串归约分析过程。例:GS: S a A c B e 1 A b 2 A Ab 3 B d 4请构造出LR(0)分析表，同时写出字符串abbcde# 的归约过程分析器模型：ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1解：Step states. Syms. The rest of inputaction goto1 0 # abbcde# s22 02 #a bbcde# s43 024 #ab bcde# r2 goto(2,A)4 023 #aA s65 0236 #aAb cde# r36 023 #aA s57 0235 #aAc de# s88 02358 #aAcd e# r4 9 02357 #aAcB s910 023579#aAcBe # r111 01 #S acc复习如何求firstVT和lastVT分析算符优先的字符串归约过程三、中间代码的形成中间代码的常见形式：1 逆波兰记号 （后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。=a+*bcbd三元式和抽象语法树表示格式：(算符, 第一运算对象, 第二运算对象)如：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 :=arg1 op arg2语义属性：, E.place E.place:值E的位置函数：lookup() ; 返回指向id的指针过程：emit(t := arg1 op arg2); 输出四元式newtemp; 生成临时变量产生式和语义描述：(1) S id := E P:=lookup () ;if Pnil then emit( P“:=”E.place)else error (2) EE1+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)Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error段考最后一道题目的答案：3文法GS的产生式如下： SSbEa|EEa（1）请判断该文法是不是LR(1)文法？如果是，填写下面的LR(1)分析表。（2）给出输入串abaa归约分析过程。（20分）文法的LR(1)分析表状态 ACTION GOTOab#SE1拓广文法：(1)SS(2)SSbEa(3)SE(4)Ea