西电软院编译原理

模拟试题1、填空题1.1以阶段划分的编译器中，阶段以记号流为输入，阶段以语法树为输入。1.2设有正规式P=a|b和Q=cd，则L(QP)=，L((P|Q)Q)=。1.3有两个因素使得有限自动机是不确定的，一个是，另一个是。1.4词法分析器有四个作用，请给出其中的任意两个：。1.5一个定义正确的上下文无关文法，非终结符集合和终结符集合的交集为空，所有出现在产生式左部的文法符号均是，仅出现在产生式右部的文法符号均是。1.6编译源程序的过程中，发现函数定义末尾缺少花括号，该情况是错误；发现除数为0，该情况是错误。1.7推导S=?H=?FTP=?FTc=?Fbc=?abc是推导。1.8产生式F→A*F|A提取左因子的结果为。1.9对于算术表达式“a*b+c”，当采用预测分析方法时，接受格局中的“当前剩余输入”应该是，初始格局中的“当前剩余输入”应该是。1.10最左归约是的逆过程，每步直接归约均是用替换右句型中的，直到归约为文法开始符号。1.11在引用调用的参数传递方式中，调用时传递的是实参的，要求实参必须是，过程内部对形参的修改等价于。1.12假定运算+与*都是左结合的，且运算*比运算+优先级高，则算术表达式x+y*(u+v)的后缀式是。1.13拉链-回填技术是语法制导翻译过程中使用的一种基本技术，其基本思想是当三地址码中的转向不确定时，而一旦所转向的地址被确定，则。2、简答题2.1简述语言的语法和语义，并举一个实际的例子加以说明。2.2如果一个集合中的元素都是长度不小于1且均不以ab开始的a、b串，请给出描述该集合的正规式。2.3语法分析器在编译器中应完成什么任务？2.4给定文法G：C→ChT|TT→TaF|FF→v请给出该文法的终结符集合、非终结符集合，并指出文法的开始符号。2.5给出下图中的树对应的三地址码序列。+/T3a+/T1b*/T2xy2.6假设数组下标从0开始，对于有5行6列的数组a[5][6]，已知该数组的存储空间首地址为a，每个元素占用存储空间大小为w，请给出数组以行为主存放时元素a[2][3]的地址。3、计算题3.1给定正规式R=a(a|b)*1用Thompson算法构造识别L(R)的NFAN；2用“子集法”把N确定化（写出完整过程），得到识别L(R)的DFAD；3如果D不是最简DFA，请找出最简DFAD’。3.2给定文法G：B→B&C|CC→EE|EE→~E|n和右句型“B&n~n”。1画出该句型对应的分析树；2指出句型中的所有短语、直接短语和句柄。3.3给定文法G的拓广文法如下:S’→SS→E$E→idE→id(E)E→E+id1构造识别G所有活前缀的DFA；2G是SLR(1)文法吗？为什么？3G是LL(1)文法吗？为什么？若不是，请改写为等价的LL(1)文法。3.4已知布尔运算的符号为and、or和not，其中and、or是左结合，not是右结合，优先级从高到低依次为not、and、or，布尔表达式及对布尔变量赋值的产生式集合、语义规则如下表所示，设全局变量nextstat的初始值为1，对于赋值句x:=notaandborc1请给出其注释分析树；2写出其三地码序列。序号产生式语义规则(1)A→id:=Ebackpatch(E.tc,nextstat);backpatch(E.fc,nextstat+2);emit(id.place‘:=true’);emit(‘goto’,nextstat+2);emit(id.place‘:=false’);(2)M→εM.stat:=nextstat;(3)E→E1andME2backpatch(E1.tc,M.stat);E.fc:=merge(E1.fc,E2.fc);E.tc:=E2.tc:(4)E→E1orME2backpatch(E1.fc,M.stat);E.tc:=merge(E1.tc,E2.tc);E.fc:=E2.fc:(5)E→notE1E.tc:=E1.fc;E.fc=E1.tc;(6)E→idE.tc:=mkchain(nextstat);E.fc:=mkchain(nextstat+1);emit('if'id.place'goto-');emit('goto-');3.5忽略过程参数的快排序的部分Pascal声明代码如下：programsort;vara:array[10]ofinteger;x:integer;procedurequicksort;vari,v:integer;functionpartition:integer;vari,j:integer;1给出上述代码中三个过程（sort、quicksort及partition）的嵌套层次；2给出上述定义对应的嵌套层次的符号表及每个符号表中的符号（假设每个整型数占用4个单元）。