编译原理05联办试卷1

大庆师范学院2008——2009学年第一学期《编译原理》期末考试试卷第1页（共3页）系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------大庆师范学院2005级计算机科学与技术专业（联办）《编译原理》期末考试试卷题号一二三四总分核分人得分--------------------------------------------------------------------------------------------------------------------------一、单项选择题（每题1分，共15分）1．（）是LL（1）文法。A．S→aS|aB．S→a|bSC．S→aSa|aSbD．S→Sc|cc2．经过编译所得到的目标程序是（）。A．四元式序列B．二元式序列C．间接三元式序列D．机器语言程序或汇编语言程序3．编译程序是对（）。A．汇编程序的翻译B．高级语言程序的解释执行C．机器语言的执行D．高级语言的翻译4．词法分析器的输出结果是（）。A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值5．编译程序各阶段的工作都涉及到（）。A．语法分析B．表格管理和出错处理C．语义分析D．词法分析6．（）不是含有回溯的文法。A．S→Sa|aB．S→aS|aC．S→aSa|aSaSD．S→bSa|ba7．正规式M1和M2等价是指（）。A．M1和M2的状态数相等B．M1和M2的有向弧条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向弧条数相等8．在规范规约中，用（）来刻画可规约串。A．直接短语B．句柄C．最左素短语D．素短语9．如果文法G是无二义的，则它的任何句子α（）。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同10．文法G[S]：S→（L）|aS|aL→L，S|S则句型（S，（a））的句柄和最左素短语分别是（）。A．（a）和SB．S和aC．a和SD．S和（a）11．文法G：S→b|∧|(T)T→T,S|S则FIRSTVT(T)=（）。A．{b,∧,(}B．{b,∧,)}C．{b,∧,(,,}D．{b,∧,),,}12．设a、b、c是文法的终结符，且满足优先关系ab和bc，则（）。A．必有acB．必有caC．必有baD．a~c都不一定成立13．设文法为：S→SA|AA→a|b则对句子aba，下面是规范推导的是（）。A．S=SA=SAA=AAA=aAA=abA=abaB．S=SA=SAA=AAA=AAa=Aba=abaC．S=SA=SAA=SAa=aba=Aba=abaD．S=SA=Sa=SAa=Sba=Aba=aba14．表达式(┐A∨B)∧（C∨D）的逆波兰表示为()。A．┐AB∨∧CD∨B．A┐B∨CD∨∧C．AB∨┐CD∨∧D．A┐B∨∧CD∨15．四元式之间的联系是通过()实现的。A．指示器B．临时变量C．符号表D．程序变量得分阅卷人大庆师范学院2008——2009学年第一学期《编译原理》期末考试试卷第2页（共3页）系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------二、填空题（每空1分，共20分）1．解释程序和编译程序的区别在于______________________。2．词法分析遵循的是语言的_________规则，而中间代码生成遵循的是语言的_________规则。3．存贮分配策略有分配策略、分配策略、分配策略。4．在词法分析中，能识别出____________、标识符、____________、____________、界符。5．语法分析分为分析方法和分析方法两大类分析方法，具体为，；，。6．Chomsky把文法分为四种类型，编译器构造中采用_________和_________文法，它们分别产生______语言和_________语言，并分别用下推自动机和________自动机识别所产生的语言。三、判断题（每题2分，共20分）1．自动机M与M’的状态数不同，则二者必不等价。（）2．一般而言，中间代码是一种独立于具体硬件的记号系统。（）3．一个有限状态自动机中，有且仅有一个唯一的终态。（）4．LL（1）文法一定不含左递归和二义性。（）5．句柄就是最右直接短语。（）6．算符优先分析方法是一种自上而下的语法分析方法。（）7．如果某一产生式形如A→Aa|a，则称该产生式是直接左递归的。（）8．Else没有匹配的if是编译程序在语法分析阶段报告的错误信息。（）9．若文法是二义性的，则在编译时会产生不确定性。（）10．一个文法所有句型的集合形成该文法所能接受的语言。（）四、应用题（1题10分，2题15分，3、4题各10分，共45分）1．假定DFAM=({S0，S1，S2}，{a，b}，f，S0，{S2})且有：f(S0，a)=S1，f(S0，b)=S2，f(S1，a)=S1，f(S1，b)=S2，f(S2，a)=S2，f(S2，b)=S1，试给出DFAM的状态转换图与状态转换矩阵。2．已知文法G[A]：A→aABl|aB→Bb|d(1)试给出与G[A]等价的LL(1)文法G[A′]；(2)构造G[A′]的LL(1)分析表。得分阅卷人得分阅卷人得分阅卷人大庆师范学院2008——2009学年第一学期《编译原理》期末考试试卷第3页（共3页）系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------系（院）：专业：班级：姓名：学号：---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------装-----------------------------订---------------------------线----------------------------------3．已知表达式文法G[E]，相应的LR分析表如下，则给出语句i+i*i的LR分析过程。G[E]:(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r54．将下面的语句翻译成四元式序列：X=0;while(X10)doX=X+1;