编译原理阶段测试题

1第一阶段测试卷考试科目:《编译原理》第1章至第4章（总分100分）时间：90分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择与填充（30）1.一个正则语言只能对应()？A.一个正则文法B.一个最小有限状态自动机C.一个自然语言D.一个上下文有关文法2.对于编译程序而言，输入数据是源程序，输出数据是___________________。3.给出在字母表{0,1}上的“所有以00结尾的符号串的集合”的语言的正则表达式：_____________________。4.一个句型中最左的（）称为该句型的句柄。A.简单短语B.短语C.非终结符号D.终结符号5.Micro语言只有三种语句：（）、输入语句和输出语句。A.GOTO语句B.赋值语句C.条件语句D.循环语句6.描述高级语言语法的常用方法有________________和BNF范式。二、给出与正规式R＝（ab）*（a|b*）ab等价的NFA。（16）三、简述DFA与NFA有何区别。（14）四、判断下列文法是否具有二义性：G[P]:P→PaP|PbP|cP|Pe|f(18)五、对于下面的文法G[Z]，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。（22）(1)Z::=E(2)E::=T+E(3)E::=T(4)T::=F*T(5)T::=F(6)F::=(E)(7)F::=i附：参考答案：一、选择与填充（30）1.一个正则语言只能对应(B)？2A.一个正则文法B.一个最小有限状态自动机C.一个自然语言D.一个上下文有关文法2.对于编译程序而言，输入数据是源程序，输出数据是____目标程序_________。3.给出在字母表{0,1}上的“所有以00结尾的符号串的集合”的语言的正则表达式：________(0|1)*00__________。4.一个句型中最左的（A）称为该句型的句柄。A.简单短语B.短语C.非终结符号D.终结符号5.Micro语言只有三种语句：（B）、输入语句和输出语句。A.GOTO语句B.赋值语句C.条件语句D.循环语句6.描述高级语言语法的常用方法有___语法图_____和BNF范式。二、给出与正规式R＝（ab）*（a|b*）ab等价的NFA。（16）三、简述DFA与NFA有何区别。（14）解：DFA与NFA的区别主要有两点：1是NFA可以若干个开始状态，而DFA仅只一个开始状态。2是DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。四、判断下列文法是否具有二义性：G[P]:P→PaP|PbP|cP|Pe|f(18)3解：因为文法存在句型fbfbf，此句型有两棵不同的语法树，所以文法具有二义性。五、对于下面的文法G[Z]，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。（22）(1)Z::=E(2)E::=T+E(3)E::=T(4)T::=F*T(5)T::=F(6)F::=(E)(7)F::=i解：最左：Z=E=T=F*T=(E)*T=(T+E)*T=(F*T+E)*T=(i*T+E)*T=(i*F+E)*T=(i*i+E)*T=(i*i+T)*T=(i*i+F)*T=(i*i+i)*T=(i*i+i)*F=(i*i+i)*i最右：Z=E=T=F*T=F*F=F*i=(E)*i=(T+E)*i=(T+T)*i=(T+F)*i=(T*i)*i=(F*T+i)*i=(F*F+i)*i=(F*i+i)*i=(i*i+i)*i4第二阶段测试卷考试科目:《编译原理》第4章至第7章（总分100分）时间：90分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择与填充（30）1.有限状态自动机能识别()。A.上下文无关文法B.上下文有关文法C.正则文法D.短语文法2．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合都是()。A.非终极符集B．终极符集C．字母表D.状态集3．在自底向上的语法分析方法中，分析的关键是()。A.寻找句柄B.寻找句型C.消除递归D.消除公共前缀4．______________________是这样一种动作文法，即动作符只出现于产生式的末尾。5．文法要满足两个条件：_____________________和_________________________才可以使用自顶向下的语法分析方法。6.文法G[E]:E→E+T|T,T→T*P|P,P→(E)|I,则句型P+T+i的短语有（）。A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P,P+T,i二、若有文法G[S]为：S-Ac|aBA-dfB-be，请写出语言L(G[S])的全部元素。（12）三、文法G[S]为：（18）S→VV→T|ViTT→F|T+FF→)V*|(试给出句型ViFi(的短语，简单(直接)短语,句柄。四、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。（15）五、下面的文法是不是LL(1)文法？若是，请构造相应的LL(1)分析表。（25）S→aDD→STe|εT→bH|HH→d|ε5附：参考答案：一、选择与填充（30）1.有限状态自动机能识别（C）A.上下文无关文法B.上下文有关文法C.正则文法D.短语文法2．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合都是(B)。A.非终极符集B．终极符集C．字母表D.状态集3．在自底向上的语法分析方法中，分析的关键是(A)。A.寻找句柄B.寻找句型C.消除递归D.消除公共前缀4．_______尾动作文法________是这样一种动作文法，即动作符只出现于产生式的末尾。5．文法要满足两个条件：________没有左递归_____和______没有公共前缀_____才可以使用自顶向下的语法分析方法。6.文法G[E]:E→E+T|T,T→T*P|P,P→(E)|I,则句型P+T+i的短语有（B）。A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P,P+T,i二、若有文法G[S]为：S-Ac|aBA-dfB-be，请写出语言L(G[S])的全部元素。（12）解：因为S=Ac=dfcS=aB=abe所以L(G[S])={abcdef}三、文法G[S]为：（18）S→VV→T|ViTT→F|T+FF→)V*|(试给出句型ViFi(的短语，简单(直接)短语,句柄。解:句型ViFi(的语法树如下:6F是句型ViFi(相对于T的短语、简单短语、句柄（是句型ViFi(相对于F的短语、简单短语（是句型ViFi(相对于T的短语ViF是句型ViFi(相对于V的短语ViFi(是句型ViFi(相对于V的短语ViFi(是句型ViFi(相对于S的短语四、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。（15）解：逆波兰表示：abc*＋ab＋/d－三元式序列：(1)(*，b，c)(2)(＋，a，(1))(3)(＋，a，b)(4)(/，(2)，(3))(5)(－，(4)，d)五、下面的文法是不是LL(1)文法？若是，请构造相应的LL(1)分析表。（25）S→aDD→STe|εT→bH|HH→d|ε解:Predict(S→aD)=first(aD)={a}Predict(D→STe)=first(STe)={a}Predict(D→ε)=follow(D)={#,b,d,e}Predict(T→bH)=first(bH)={b}Predict(T→H)=first(H)∪follow(T)={d,e}Predict(H→d)=first(d)={d}Pridict(H→ε)=follow(H)={e}所以该文法是LL(1)文法，LL(1)分析表如下表:aebd#S1D23333T545H76第三阶段测试卷考试科目:《编译原理》第8章至第10章（总分100分）时间：90分钟学习中心（教学点）批次：层次：7专业：学号：身份证号：姓名：得分：一、选择与填充（30）1.四元式之间的联系是通过()来实现的。A．指示器B．临时变量C．符号表D．程序变量2.优化可生成()的目标代码。A.运行时间较短B.运行时间短但占用内存空间大C.占用存储空间较小D.运行时间短且占用存储空间小3.下列()优化方法不是针对循环优化进行的。A.强度削弱B．删除归纳变量C．删除多余运算D．代码外提4.在目标代码生成阶段，符号表用于()。A．目标代码生成B．语义检查C．语法检查D．地址分配5．语法分析是依据语言的__________规则进行的，中间代码产生是依据语言的_________规进行的。6．优化可分为局部优化、_____________和全局优化三种。二、写出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)三、什么是活动记录？它主要由哪些内容构成？(15)四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15)五、文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。(30)G[M]:1)S→VdB2)V→e3)V→ε4)B→a5)B→Bda6)B→ε状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r187S88r5r5附：参考答案：一、选择与填充（30）1.四元式之间的联系是通过(B)来实现的。A．指示器B．临时变量C．符号表D．程序变量2.优化可生成(D)的目标代码。A.运行时间较短B.运行时间短但占用内存空间大C.占用存储空间较小D.运行时间短且占用存储空间小3.下列(C)优化方法不是针对循环优化进行的。A.强度削弱B．删除归纳变量C．删除多余运算D．代码外提4.在目标代码生成阶段，符号表用于(D)。A．目标代码生成B．语义检查C．语法检查D．地址分配5．语法分析是依据语言的___语法__规则进行的，中间代码产生是依据语言的__语义___规进行的。6．优化可分为局部优化、____循环优化____和全局优化三种。二、写出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)解：ABC/D-*EF/+三、什么是活动记录？它主要由哪些内容构成？(15)解：一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：(1)临时变量域存放目标程序临时变量的值；(2)局部数据域存放过程本次执行时的局部数据、简单变量及数组内情向量等；(3)机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；(4)存取链为访问其它活动记录中所存放的非局部数据所提供的链地址；(5)控制链指向主调过程的活动记录；(6)实参存放主调过程为被调用过程所提供的实参信息；(7)返回值为主调过程存放被调过程的返回值四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15)解：该表达式的四元式序列为：9(1)(*,b,c,T1）(2)(+,a,T1,T2)(3)(*,c,b,T3)(4)(+,T3,a,T4)(5)(-,T4,e,T5)(6)(*,b,c,T6)(7)(+,T6,d,T7)(8)(/,T5,T7,T8)(9)(-,T2,T8,T9)可以对该表达式进行删除公共子表达式的优化。优化后的四元式序列为：(1)(*,b,c,T1）(2)(+,a,T1,T2)(3)(-,T2,e,T5)(4)(+,T1,d,T7)(5)(/,T5,T7,T8)(6)(-,T2,T8,T9)五、文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。(30)G[M]:1)S→VdB2)V→e3)V→ε4)B→a5)B→Bda6)B→ε状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5解：状态栈符号栈输入流动作S0#dada#r