复习题().doc

选择题：1.将编译程序分成若干个“遍”是为了 。 a提高程序的执行效率 b使程序的结构更加清晰 c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2.构造编译程序应掌握。 a源程序b目标语言 c编译方法d以上三项都是3、变量应当。 a持有左值b持有右值 c既持有左值又持有右值d既不持有左值也不持有右值 4、编译程序绝大多数时间花在 上。 a出错处理b词法分析 c目标代码生成d管理表格5、 不可能是目标代码。 a汇编指令代码b可重定位指令代码 c绝对指令代码d中间代码6、使用 可以定义一个程序的意义。 a语义规则b词法规则 c产生规则d词法规则7、词法分析器的输入是 。 a单词符号串b源程序 c语法单位d目标程序8、中间代码生成时所遵循的是- 。 a语法规则b词法规则 c语义规则d等价变换规则9、编译程序是对 。 a汇编程序的翻译b高级语言程序的解释执行 c机器语言的执行d高级语言的翻译10、编译程序各阶段的工作都涉及到 。 a语法分析b表格管理c出错处理 d语义分析e词法分析11、编译程序工作时，通常有 阶段。 a词法分析b语法分析c中间代码生成 d语义检查e目标代码生成12、文法G：SxSx|y所识别的语言是。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*13、文法G描述的语言L(G)是指 。a. L(G)=|S+ , VT*b. L(G)=|S*, VT*c. L(G)=|S*,(VTVN*)d. L(G)=|S+ , (VTVN*)14、有限状态自动机能识别 。a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法15、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。a. 若f(a)g(b)，则abb.若f(a)g(b)，则aE+T|TT-T*F|FF-(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：短语: E+T*F, T*F,直接短语: T*F句柄: T*F例如2：令文法为（1） 给出i+i*i、i*(i+i)的最左推导和最右推导；（2） 给出i+i+i、i+i*i、i-i-i的语法树。最左推导:最右推导:语法树：i+i+i i+i*i i-i-i例如3：考虑文法G(E):EE+T | TTT*F | FF(E) | i（1）给出句型E+F*F的语法树；（2）给出以上句型的的短语、直接短语、句柄。E =E+T=E+T*F=E+F*F 由上图知：短语：F,F*F,E+F*F直接短语：F句柄：FSBbBSab对于文法GS：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄。 A短语：a ba Sb baSb直接短语：a Sb句柄：a素短语：a Sb 最左素短语：a9. lex / yacc： Lex是一个词法分析器生成器，用于自动生成程序设计语言的词法分析器；Yacc是一个语法分析器生成器，用于自动生成程序设计语言的语法分析器。10. 什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。 L-属性文法要求对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1） 产生式Xj的左边符号X1,X2Xj-1的属性；（2） A的继承属性。 S-属性文法是L-属性文法的特例。四、词法分析：1.给出下述文法对应的正规式S 0A| 1BA1S | 1B0S | 02.文法GS为： S-Ac|aB A-ab B-bc （3分）写出GS的所有句子。3.求1(0|1)*00的状态最少的DFA。解：1)得到NFA 2） NFA转换成DFA状态转换矩阵为： I I0 I1X-111,211,21,2,Y11,2,Y1,2,Y1重新命名后为： S010-11212313314.设计一个DFA,其输入字母表是0，1，它能接受以0开始，以1结尾的所有序列5. 设计一个DFA，它能接受以01结尾的二进制数串。6.将下图最小化032 b b a a b a a b541 b a a a最小化：021 b b a a b五、自上而下的语法分析1.设有文法GS：SaBc|bABAaAb|bBb|构造其LL(1)分析表，First(S)=a,bFirst(A)=a,bFirst(B)= b, Follow(S)=#Follow(B)=#,cFollow(A)=b，#abc#SS-aBcS-bABAA-aAbA-bBB-bB-B-表中空白表示出错并分析符号串baabbb是否是该文法的句子. S-bAB-baAbB-baaAbbB-baabbbB-baabbb所以baabbb是该文法的句子2. 给定文法 GS ： S AB A aB | bS | c B AS | d 1)请给出每一个非终结符号的 First 集； 2)请给出每一个非终结符号的 Follow 集； 3)什么是 LL(1) 文法？该文法是 LL(1) 文法吗？ （ 1 ） First(S) = a, b, c First(A) = a，b,c First(B) = a, b, c,d （ 2 ） Follow(S) = #, a, b, c, d Follow(A) = a, b, c, d Follow(B) = #, a, b, c, d （ 3 ）对于文法 G 的每一个非终结符 P 的产生式 U 1 | 2 | n ， 文法不含左递归如果 first( i) first( j)不相交，（ ij, i,j=1, 2, , n ），若first(U), first(U) follow(U)为空 则文法 G 是一个 LL(1) 文法。该文法是 LL(1) 文法。 3.对文法G(V): VN|NE EV|V+E Ni要求：1）消除回溯（公共左因子）；2）求出各非终结符的first集和follow集；3)判断改造后的方法是否是LL（1）文法。解：1）LL（1）文法的基本条件是不含左递归和回溯，而文法G中含在回溯，所以先消除回溯得到文法G(V)： VNV V|E EVE E|+E Ni2）求的first和follow集：（8分）First(V)= , First(E)= , +First（N）=iFirst(V)=iFirst(E)= iFollow(V)=#, ,+ Follow(N)= ,#, ,+Follow(V)在follow(V)中=,follow(V)=#, ,+Follow(E)= Follow(E)= First(N)=First(V)=first(E)=i;First(V)=, ;First(E)=+, ;Follow(V)=#，+Follow(V)=#,+Follow(E)= Follow(N)= ，#，+Follow(E)= 3）改造后的文法是LL（1）文法。 （2分）4）构造其预测分析表+i#VV-NVNN-iVV-EV-V-V-EV-NVEE -E-+E五、自下而上的语法分析设文法G(S)：(S,i) (S,i)(A,+) (A,+)(B,) (B,*)(B,() (B,() FirstVT(B)= (,)firstVT(A)= (,+,)firstVT(S)= (,+,),iLastVT(B)= (,*LastVT(A)= (,*,+LastVT(S)= i, (,*,+,1)构造各非终结符的FIRSTVT和LASTVT集合；2)构造优先关系表。4、解： (6分)FIRSTVT(S)= i，+，)，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 优先关系表: (5分)i+()*i()六给出下面表达式的逆波兰表示（后缀式）a+b*(c+d/e) 答案：abcde/+*+ 七1将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式序列:(1) +, a, b(2) uminus，(1)(3) +, c, d(4) *, (2), (3)(5) +, a, b(6) +, (5), c(7) -, (4), (6)间接三元式序列:三元式表：(1) +, a, b(2) uminus，(1)(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1) +, a, b, (2) uminus, ,-, (3) +, c, d, (4) *, , , (5) +, a, b, (6) +, , c, (7) -, , , 2. 赋值语句x:=(a+b)*(a+b)（1）写出其后缀式、三元式、四元式（2）画出语法树和DAG图 后缀式xab+ab+*:=三元式(1) (+,a,b )(2) (+,a,b)(3) (*,(1),(2)(4)(:=,x,(3)四元式(1) (+, a, b,T1 ) (2) (+, a, b,T2 ) (3) (*,T1,T2,T3 ) (4) (:=,x,T3,T4)画出语法树和DAG图（5分）算术表达式a*（- (b+c)）为a) 一棵语法树 b) 后缀式 c) 三地址代码d) 语法树： b) 后缀式: （3分）a b c + uminus * 4） c)三地址代码: t1 := b + c ;t2 := - t1; t3 := a * t2(1) (+, b, c)(2) (uminus,(1)(3) (*,a,(2)回填技术的应用已知文法的翻译模式，用回填法给出语句ab and cd or ef的四元式序列，要求给出简单过程。(1)EE1 and M E2 backpatch(E1truelist,M.quad);E.truelist:=,E2.truelist)E.falselist:=merge(E1.falselist, E2.falselist ) (2) EE1 or M E2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist)E.falselist:=E2.falselist (3)E1id1 relop id2 E.truelist:= makelist(nextquad);E.falselist:=makelist(nextquad+1);Emit(j relop.op , id1.place , id2.place , 0 );Emit(j,-,-,0)(4)M M.quad:=nextquad四元式序列为：（6分）100 （j，a，b，102）101 （j，-，-，104）102 (j，c，d，0)103 （j，-，-，104）104 (j，e，f，0)105 (j，-，-，0）九试把以下程序划分为基本块并作出其程序流图。1、划分基本块的算法： （1）先求出四元式程序中各个基本块的入口： 程序的第一条语句；能由条件转移语句或无条件转移语句转移到的语句；紧跟在条件转移语句后面的语句。 （2）对以上求出的每一入口语句，构造其所属的基本块。它是由该入口语句到另一入口语句，或到一转移语句，或到一停语句之间的语句序列组成的。 （3）凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，可把它们从程序中删除。Read CA:=0B:=1L1: A:=A+BIf BC goto L2B:=B+1Goto L1L2: write Ahalt2.调用R0和R1是两个可使用的寄存器，T4是基本块出口之后的活跃变量。将下面基本块的中间代码序列生成目标代码。T1:=A+BT2:=C+DT3:=E-T2T4:=T1-T3首先画出DAG图，对DAG图节点执行顺序进行排序，调整语句执行顺序 T2：=C+D T3：=E-T2T1：=A+B T4：=T1-T3然后进行翻译，目标代码序列为：LD R0,CADD R0,DLD R1,ESUB R1,R0LD R0, AADD R0,BSUB R0,R1ST R0,T4注意寄存器的选择要求利用变量的待用信息来决定。3.用DAG图对下面的基本块进行优化(假定出基本块后只有A、G、L是活跃的)(10分)A=B*CD=B/CE=2*3F=E+2G=B*CK=E+FG=K*KL=B/C解： A=B*C G=196 L=B/C 4.已知现在寄存器R，其中A是活跃变量，试将以下三地址代码翻译成汇编代码的形式。 T1：=A+B T2：=T1*C A：=T2+D目标代码序列为：LD R,AADD R,BMUL R,CADD R,DST R,A4. 假设可用寄存器为R0和R1，试写出下列四元式序列对应的目标代码。（10分）T1=B-CT2=A*T1T3=D+1 T4=E-FT5=T3*T4十、课后习题讲解：P81 1,2,3 p133 1,2,3 p164 1,2 31.S-a|(T)T-T,S|S(1)消去G1的左递归，然后对每个非终结符号，写出不带回溯的递归子程序。解1：分析：从产生式S-a|(T)可以看出，不会形成间接递归，运用消除直接递归的方法，如下：S-a|(T)T-STT-,S T|其不带回溯的递归子程序如下：Procedure SIf sym=athen Advance;Else if sym= then Advance;Else if sym=( then BeginAdvance;T;If sym=) then advance;Else error;EndElse error;Procedure TBeginS,TEndProcedure TIf sym=,then BeginAdvance;S,T;end解2：运用递归消除算法对S,T排序，首先消掉S（第一个非终结符）的直接左递归，这里没有，故缺省，得到S-a|(T)然后，一次消掉后面非终结符号的左递归，对T-T,S|S中的T-S等价代换，得到T-T,S| a|(T)再消掉上面式子的直接左递归，得到T-aT|T|(T)TT-,ST|这样，消除左递归后的产生式为S-a|(T)T-aT|T|(T)TT-,ST|该产生式的递归下降子程序我们参考上面的进行书写即可。上述两种方法都是正确的求解方法，第二种方法繁琐一些，但容易寻找到其first和follow集（2）判断是否是LL(1)，给出其预测分析表先求解其first集First(S)=a, , ( follow(S)=#, )First(T)= a, , (follow(T)= )First(T)=, , follow(T)= )可见first(T)与follow(T)没有交集每个产生式的候选的first集没有交集，因此这是一个LL(1)文法。假定我们选用第一种方法得到的产生式S-a|(T)T-STT-,S T|a(),#SS-aS-S-(TT-STT-STT-STT-TT-,S T第七章 题目训练1.题目1：已知文法的翻译模式，用回填法给出语句ab and cd or ef的四元式序列，要求给出简单过程。(1)EE1 and M E2 backpatch(E1truelist,M.quad);/将M.quad填入E1truelist中四元式的第四分量E.truelist:=,E2.truelist)E.falselist:=merge(E1.falselist, E2.falselist ) (2) EE1 or M E2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist)E.falselist:=E2.falselist (3)E1id1 relop id2 E.truelist:= makelist(nextquad);E.falselist:=makelist(nextquad+1);Emit(j relop.op , id1.place , id2.place , 0 );Emit(j,-,-,0)(4)M M.quad:=nextquad具体知识点：1.掌握条件控制语句的三地址代码翻译形式：每一个条件语句都可以看做图7.15，都有两个出口。1）if ab then s1 else s2翻译为If ab and cd then s1 else s2翻译为if ab goto L1Goto L2L1：If cd goto L3Goto L2L1：代表cd的三地址代码序列L2：代表S2程序块的三地址代码序列L3: 代表S1程序块的三地址代码序列接下来，我们将每个关系式E对应的两个出口，分别记为E.true和E.false，避免上述使用标号的随意性。2.掌握两遍扫描的翻译方法依据为表7.71)if ab or cd and eab的翻译得到if acd的翻译if cef的翻译if eE21 and E22的翻译E21.true=newlabel L1E21.false=E2.falseE22.true=E2.trueE22.false=E2.false此时E2的属性并不知道此时需要建立三地址代码 E21的三地址代码 L1: E22的三地址代码,如下：if cd goto L1Goto E2.flaseL1:if eE1 or E2的翻译E1.true=E.trueE1.false=newlabel L2E2.true=E.trueE2.false=E.false此时E的属性并不知道此时需要建立三地址代码 E1的三地址代码 E1.flase: E2的三地址代码,如下：if ab goto E.trueGoto L2L2: if cd goto E21.trueGoto E.flaseL1:if ef goto E.trueGoto E.flase作业：二遍翻译if ab and cd or eE1 or E2E1为真时应跳转到E为真时的出口E2为真时应跳转到E为真时的出口则E.truelist列表中就包含E1为真时和E2为真时的两条跳转指令。P191书，先建立一个语法树，然后从下向上规约。首先对E1-ab翻译，假定开始时标号指示器nextquad为100，每用emit产生一个四元式，n