山东理工大学《编译原理》考试

第一章引论1．高级程序设计语言的翻译主要有两种方式：和，二者的根本区别在于。答：解释编译是否生成目标程序。2．编译程序决大多数时间是花在方面。A词法分析B语法分析C语义分析D代码生成E中间代码生成F代码优化G表格管理H出错管理答：G3．什么是遍？是否任何一种高级语言都能通过一遍扫描完成编译？答：遍是对源程序或源程序的中间表示从头到尾地扫描一次，并做相关的处理工作，生成新的源程序的中间形式或目标文件。并非所有的语言都能通过一遍扫描完成编译。如果该语言结构复杂，那么必须通过多次扫描才能真正完成编译工作。影响编译遍的次数的主要因素有：源语言；机器目（标机）；编译方法。第二章高级语言及其语法描述1．巴科斯—瑙尔范式（EBNF）是一种广泛采用的工具。A描述规则B描述语言C描述文法D描述句子答：C2．由文法的开始符号经0步或多步推导产生的文法符号序列是。A短语B句柄C句型D句子答：C3．请给出描述语言L={a2m+1bm+1|m>=0}∪{a2m+1bm+2|m>=0}的文法。解答：将语言句子的描述稍做变形，得：a2mabbm和a2mabbbm于是，得到文法如下：G[Z]:Z→aaZb|ab|bb4.文法G[S]:S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc它是乔姆斯基哪一型文法？它生成的语言是什么？答：从规则形式上可以看出，文法G是乔姆斯基1型文法，即上下文有关文法。它生成的语言是L={anbncn|n>=1}。第三章词法分析1.不是NFA的成分。A有穷字母表B初始状态集合C终止状态集合D有限状态集合答：B。2．构造一个DFA，其输入字母表是{0，1}，它能接受以0开始以1结尾的所有序列，要求写出正规式。答：r=0(0|1)1*NFA为：10，12εε0131xy确定化II0I1{x}{1,2，3}{1,2,3}{2,3}Φ{2,3,y}{2,3}{2,3}{2,3,y}{2,3}{2,3,y}{2,3,y}重命名011+22Φ44433334-确定化后的DFA如图：0301110201化简：{1，2,3}{4}4{1，2,3}0={2,3}{2，3}1={4}{1}1=Φ分两组{2，3}{1}{2,3}不可再分留2删3得化简后的DFA为：10021014第四章语法分析——自上而下分析1．自顶向下语法分析方法会遇到的主要问题有和。答：左递归回溯2.LL（1）分析法中，第一个L的含义是，第二个L的含义是，“1”的含义是。答：从左到右扫描输入串最左推导分析时每一步只需向前查看一个符号23.下列文法是左递归文法，试消除其左递归。G[S]：S→SaA|bBA→aB|cB→Bb|d解答：S→bBS’S’→aAS’|εA→aB|cB→dB’B’→bB’|ε4.考虑下面的文法G：S→a|∧|(T)T→T,S|S⑴消去G的左递归；⑵经改写后的文法是否是LL（1）的？给出它的预测分析表。解答：⑴按照T，S的顺序消除左递归，得到文法：G,[S]：S→a|∧|(T)T→ST,T,→,ST|ε,⑵首先计算每个非终结符的FIRST集合和FOLLOW集合：FIRST（S）={a,∧,(}FOLLOW(S)={,,),#}FIRST（T）={a,∧,(}FOLLOW(T)={)}FIRST（T,）={,,ε}FOLLOW(T,)={)}构造预测分析表如下表所示：A∧(),#SS→aS→∧S→(T)TT→ST,T→ST,T→ST,T,T,→εT,→,ST,从表中可以看出没有多重入口，所以改造后的文法是LL（1）文法。第五章语法分析——自下而上分析1．自下而上语法分析的基本思想是：从待输入的符号串出发，利用文法的产生式步步向上，试图到文法的。答：直接归约，归约开始符号2．规范归约每次归约的是当前句型的，算符优先文法每次归约，二者都是不断移进输入符号，直到符号栈的栈顶出的是当前句型的现的尾，再向前找到的头，然后归约。答：句柄最左素短语可归约串可归约串3．对下列文法G[S′]：（1）计算文法中每个非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表；（3）给出输入串cadbc的算符优先分析过程。文法G[S]：S′→#S#S→SaF|F3F→FbP|PP→c|d解答：(1)FIRSTVT(S)={a,b,c,d}LASTVT(S)={a,b,c,d}FIRSTVT(F)={b,c,d}LASTVT(F)={b,c,d}FIRSTVT(P)={c,d}LASTVT(P)={c,d}FIRSTVT(S’)={#}LASTVT(S’)={#}(2)文法G的优先关系表abcd#a><<<>b><<<>c>>d>>>#<<<<=c⑶分析过程步骤符号栈输入串动作0#cadbc##<a,移进1#cadbc#c>a,归约P→c2#Padbc##<a,移进3#Padbc#a<d,移进4#Padbc#d>b,归约P→d5#PaPbc#a<b,移进6#PaPbc#b<c#,移进7#PaPbc#c>#,规约P→c8#PaPbP#b>#,规约F→FbP9#PaF#a>#,规约S→SaF10#S#接受4．已知文法G[A]：A→(A)|a(1)请构造该文法的以LR(0)项日集为状态的识别活前缀的DFA。(2)构造该文法的LR(0)分析表，并回答该文法是LR(O)文法吗?(3)构造该文法的SLR(1)分析表，并回答该文法是SLR(1)文法吗？(4)构造该文法的以LR(1)项目集为状态的识别活前缀的DFA。(5)构造该文法的LR（1）分析表。(6)构造该文法的LALR(1)分析表。解答：(1)首先构造拓广文法如下：0A’→A4l2A→(A)A→a构造该文法的以LR(0)项日集为状态的识别活前缀的DFA如图所示文法的以LR[0]项目集为状态的识别活前缀的DFA(2)构造文法的LR(0)分析表如表所示。表中无多重定义，所以该文法是LR(0)文法。文法的LR(0)分析表)(3)因为FOLLOW(A)＝{，#}，所以得到文法的SLR(1)分析表如表所示。表中无多重定义，所以该文法是SLR(1)文法。文法的SLR(l)分析表5(4)构造该文法的以LR(1)顶目集为状态的识别活前缀的DFA如图所示(5)构造该文法的LR(1)分析表如表所示。6(6)状态I3和I6、I2和I5、I4利I8、I7和I9，是同心状态，将它们分别合并后不产生冲突，所以得到该文法的LALR(1)分析表如表所示。第六章属性文法和语法制导翻译1．在属性文法中，属性用于“自下而上”传递信息，而属性用于“自上而下”传递信息。2.下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：SLL|LLLB|BB0|1试设计求Sval的属性文法，其中，已知B的综合属性val，给出由B产生的二进位的7结果值。例如，输入101.101时，Sval＝5.625，其中第一个二进位的值是4，最后一个二进位的值时是0.125解答：语义动作子程序如下：产生式语义动作S，S{print(Sval)}SLL{Sval:=Lval+Lval/2}L2length121SL{Sval:=Lval}2LLB{Lval:=Lval*2+Bval11Llength:=Llength+1}1LB{Lval:=Bval;Llength:=1}B0{Bval:=0}B1{Bval:=1}第七章语义分析和中间代码生成1.⑴给出下列表达式的逆波兰表示（后缀式）：a+b*ca<=b+c∧a>d∨a+b≠e⑵写出下列语句的逆波兰表示（后缀式）：<变量>：＝<表达式>IF<表达式>THEN<语句1>ELSE<语句2>⑶写出算术表达式A+B*(C-D)+E/(C-D)**N的四元式，三元式和间接三元式序列。解答：⑴abc*+abc+<=ad>∧ab+e≠∨⑵<变量><表达式>：＝<表达式>p1BZ<语句1>p2BR<语句2>↑p1↑p2⑶四元式序列：⑴（-,C,D,T1）⑵(*,B,T1,T2)⑶(+,A,T2,T3)⑷(-,C,D,T4)⑸(**,T4,N,T5)⑹(/,E,T5,T6)⑺(+,T3,T6,T7)三元式序列：⑴（-,C,D）⑵(*,B,⑴)⑶(+,A,⑵)⑷(-,C,D)⑸(**,⑷,N)⑹(/,E,⑸)⑺(+,⑶,⑹)8

间接三元式序列：间接码表三元式表⑴⑴（-,C,D）⑵⑵(*,B,⑴)⑶⑶(+,A,⑵)⑴⑷(**,⑴,N)⑷⑸(/,E,⑷)⑸⑹(+,⑶,⑸)⑹2.将下列语句翻译成四元式序列。while(a>b)doif(c<d)thenx:=y*zelsex:=y+z解答：100(j>,a,b,102)106(j,_,_,100)101(j,_,_,110)107(+,y,z,T2)102(j<,c,d,104)108(:=,T2,_,x)103(j,_,_,107)109(j,_,_,100)104(*,y,z,T1)110105(:=,T1,_,x)第八章符号表1．在语义分析阶段，符号表所登记的信息将用于和，在目标代码生成阶段，符号表是的依据。答：语义检查，产生中间代码，地址分配2．编译过程中，每当扫描识别出一个名字后，编译程序就查阅，看该名字是否在其中，如果该名字是一个新名字就将它填进里。答：符号表符号表3．判断题：⑴名字就是标识符，标识符就是名字。（）⑵对每个过程指定顺序号，目的是为了确定过程中名字的作用域。（）⑶符号表的内容在词法分析阶段填进并在以后各个阶段得到使用。（）⑷编译开始时，符号表都是空的。（）⑸编译工作的相当一大部分时间是花费在查填符号表上。（）⑹程序在运时行发现的错误能够反映它在源程序中的确切位置。（）⑺“运算符与运算对象类型不符”属于语法错误。（）解答：⑴错⑵对⑶错⑷错⑸对⑹错⑺错第九章运时行存储空间组织1．在PASCAL语言中，为了在过程的嵌套调用过程中实现对非局部名字的访问，可以采用和活动纪录，或和活动纪录的方式。答：静态链过程嵌套层次表2．编译程序中常用的存储分配策略包括、和堆式动态存储分配策略。答：静态存储分配策略栈式动态存储分配策略93．如下示意的Pascal源程序：programmain;vara,b,c:integer;procedureX(i,j:integer);vard,e:real;procedureY;varf,g:real;begin„end;{Y}procedureZ(k:integer);varh,i,j:real;begin„end;{Z}begin„10:Y;„11:Z;„end;{X}begin„(a,b);„end.{main}并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和Display的内容。⑴已开始而尚未执行完毕标号为10的语句；⑵已开始而尚未执行完毕标号为11的语句。解答：15e（局）26j（局）14d（局）24g（局）23f（局）136XDisplay表25i（局）24h（局）1202216YDisplay表11j(形参)2316ZDisplay表226216109i（形参）2(形参个数)2(全局Display)200YDisplay表190(形参个数)210ZDisplay表20k(形参)81812(全局Display)7返回地址191(形参个数)1812(全局Display)17返回地址17返回地址16Y6（老SP）6X0（老SP）5Mainc（局）4b（局）16Z6（老SP）3a（局）20（Display）1返回地址0Main0（老SP）(1)已开始而尚未执行完毕标号为10的语句时运行栈的内容0－15和左侧表16－24右侧表20-22是Display表的内容10（2）已开始而尚未执行完毕标号为11的语句时运行栈的内容是中间表0－15右侧表16－26的内容，右侧表20－22的内容是此时Display表的内容。第十章优化1.在循环中可采用、和删除归纳变量三种优化措施。答：代码外提，强度削弱2.根据优化所涉及的范围，可将优化可分为，和循环优化。答：局部优化，全局优化3.试对以下基本块构造其DAG图，分别利用DAG图对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G，L，M在基本块后面还要被引用；（2）假设只有L在基本块后面还要被引用。B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L解答：该基本块的DAG图：L,Mn9n7G*+F,Jn1B3n6n8K15+D,Hn5E,In4*+n2A0n3C0(1)假设只有G，L，M在基本块后面还要被引用，该基本块优化后的四元式序列为：D:=A+CE:=A*CF:=D+EG:=3*FL:=15+FM:=L(2)假设只有L在基本块后面还要被引用,该基本块优化后的四元式序列为:D:=A+CE:=A*C11F:=D+EL:=15+F第十一章目标代码生成1.指令的执行代价定义为+.答:该指令访问内存的次数1(取该指令访问内存的次数)2.设有基本块PT0:=3T1:=8/T0T2:=S–CT3:=S+CR:=T0*T3H:=RT4:=10/T1T5:=S+CT6:=T4*T5H:=T6/T2(1)构造其DAG图，写出用DAG图优化后的三地址代码序列；(2)假定只有R，H在基本块出口是活跃的，试写出优化后的三地址代码序列；(3)假