《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。
( X )2.一个句型的直接短语是唯一的。
( X )3.已经证明文法的二义性是可判定的。
（ X ）4.每个基本块可用一个DAG表示。
（√）5.每个过程的活动记录的体积在编译时可静态确定。
（√）6.2型文法一定是3型文法。
（ x ）7.一个句型一定句子。
( X )8.算符优先分析法每次都是对句柄进行归约。
(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。
（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。
( x )11.一个优先表一定存在相应的优先函数。
( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
( )13.递归下降分析法是一种自下而上分析法。
( )14.并不是每个文法都能改写成LL(1)文法。
( )15.每个基本块只有一个入口和一个出口。
( )16.一个LL(1)文法一定是无二义的。
( )17.逆波兰法表示的表达试亦称前缀式。
( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
( )19.正规文法产生的语言都可以用上下文无关文法来描述。
( )20.一个优先表一定存在相应的优先函数。
( )21.3型文法一定是2型文法。
( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。
( )二、填空题：1.( 最右推导 )称为规范推导。
2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。
4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。
5.语法分析器的输入是（），其输出是（）。
6.扫描器的任务是从（）中识别出一个个（）。
编译原理试题及答案
编译原理是计算机科学中的一门重要课程，它涉及到程序设计语言的语法、语义分析以及编译器的设计与实现等内容。
下面我们将为大家提供一些编译原理的试题及答案，希望能够帮助大家更好地理解和掌握这门课程的知识。
1. 什么是编译原理？
编译原理是研究编译器的设计与实现的一门学科，它主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等内容。
2. 什么是词法分析？
词法分析是编译原理中的一个重要内容，它主要负责将源程序转换成一个个的单词符号，也就是词法单元。
3. 什么是语法分析？
语法分析是编译原理中的另一个重要内容，它主要负责将词法单元序列转换成抽象语法树，以便进行后续的语义分析和中间代码生成。
4. 什么是语义分析？
语义分析是编译原理中的一个关键环节，它主要负责对源程序进行语义检查，以确保程序的正确性和合法性。
5. 什么是中间代码生成？
中间代码生成是编译原理中的一个重要环节，它主要负责将源程序转换成一种中间形式的代码，以便进行后续的代码优化和代码生成。
6. 什么是代码优化？
代码优化是编译原理中的一个关键环节，它主要负责对中间代码进行优化，以提高程序的执行效率和减少资源消耗。
7. 什么是代码生成？
代码生成是编译原理中的最后一个环节，它主要负责将优化后的中间代码转换成目标机器代码，以便计算机能够执行。
以上就是关于编译原理的一些试题及答案，希望能够帮助大家更好地理解和掌握这门课程的知识。
如果大家对编译原理还有其他疑问，可以随时向我们提问，我们将竭诚为大家解答。
2013– 2014学年第二学期 计算机科学与技术专接本专业编译原理试卷（A ）卷一、填空题（每空2分，10个空，共20分，请将正确的答案填写在答题纸上）1.若将X 语言的源程序翻译成Y 语言的程序，翻译的实现语言为Z 语言，则称Z 语言是翻译的 宿主 语言2.设有字母表Σ={a,bb,c},字母表Σ上的符号串ω=abbc、，则|ω3|=93.设有有限自动机如下图所示，设I={x}，则Ib={ 1,2,3 }4.语言中具有独立意义的最小语法单位是 单词5.设有文法S→ABc A→a|ε B→b|ε，则First(S)={ a,b,c }6.规范归约中的可归约串是指（句柄）。
7.中间代码产生是依据语言的 语义 规则进行的8.存储分配的基本单元是过程的 活动记录9.在基本块范围内的优化称为 局部优化10.在目标代码生成阶段，符号表是 地址分配___的依据。
二、选择题（每题2分，10题，共20分）（在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填在答题纸上。
错选、多选或未选均无分。
）题 号一二三四五合计得 分阅卷人河北科技师范学院装订线系（部）班 级学 号姓 名1.目前最常用的文法表示方法为………………………………（ A ）A. BNF 表示法B.YACCC. LexD. DAG2. 下图所示自动机所描述的语言是…………………………………………（ B）A. aa(ε(a|b)*(a|b))B. aa((a|b)*|ab)C. aa((a|b)|ab)D. aa((a|b|ab)*3. 词法分析器的输出结果是…………………………………………………（ C ）A ．单词的种别编码B ．单词在符号表中的位置C ．单词的种别编码和属性值D ．单词属性值4. 在自顶向下的语法分析方法中，分析的关键是…………………………（ D ）A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式5.设有文法G[S]为：S →AB A →Aa|bB B →a|Sb ，下面哪个不是句型 baSb 的短语…………………………………………………………………………………（ C）A. baSbB. SbC.aSbD. ba6. 在编译过程中，引起源程序发生质的变化的阶段是………………………（ B ）A. 语法分析B. 语义分析C. 词法分析D. 中间代码生成7. 常用的两种动态存贮分配办法是 动态分配和 动态分配………（ A）A. 栈式、堆式B. 栈式、队列式C. 堆式、队列式D. 记录式、队列式8. 有代码为 x=a+b+c; y=a+b+d;可以采用的优化方法是 ……………………………………………………（B5b a）A. 常量的合并与传播B. 公共子表达式删除C. 无用赋值的删除D. 死代码删除9. 设有如下代码段，则其可以被划分的基本块的个数为……………………（ C ）Read NI=NJ=2L1：if I≤J goto L3I∶=I-JJ∶=J+1goto L1L3：Print ′YES′haltA. 2B. 3C. 4D. 510.经过编译所得到的目标程序是……………………………（ D ）A．四元式序列 B．间接三元式序列C．二元式序列 D．机器语言程序或汇编语言程序三、判断题（每题1分，10题，共10分）（对的打“√”号错误的打“×”，写在答题纸上）1.解释程序和编译程序的区别在于是否生成目标代码…………（√）2.若一个文法是递归的，则它所产生语言的句子个数必定是无穷的……………………………………………………………………（√）3.词法分析应遵循的是语义规则…………………………………(×）4.语法分析方法中的递归下降分析法属于自底向上分析方法…（ × ）5.算符优先分析法的实质就是借助优先关系来寻找可规约串…（√）6.编译中进行语法检查的目的是为了发现程序中所有错误……（ × ）7.中间代码产生是依据语言的语义规进行的…………………（√）8.环境把名字映射到左值，而状态把左值映射到右值…………（√）9.含有优化功能的编译程序执行效率高 …………………………(×）10.目标代码指令越丰富，代码生成的工作越复杂………………(×）四、简答题（共四小题，每题5分，共20分）1. 设有确定的有限自动机M:（{1,2,3,4,5},{a,b},f，1，{4,5}）f（1，a）=2 f（1，b）=3f（2，a）=2 f（2，b）=3f（3，a）=4 f（4，a）=5f（4，b）=3 f（5，a）=2画出其状态转换图和状态转换矩阵状态转换图2. 设文法G(S)： S→(L)|Sa|a L→L，S|La|ab消除其左递归，写出写出左递归后的文法S→(L)S’|aS’S’ →aS’|εL→abL’L’ →,SL’|aL’|ε3. 有文法G(S):S→a|∧|(T)T→T,S|S求非终结符S和T的FIRSTVT和LASTVT答案：FIRSTVT(S)={a，∧，（}FIRSTVT(T)={，，a，∧，（ }LASTVT（S）={ a，∧，)}LASTVT（T）={，，a，∧，)}4. 写出赋值语句 a=w+(a+b)*(c+d/(e-10)+8)的逆波兰式和四元式表示逆波兰式：wab+cde10-/+8+*=四元式：+ a b t1- e 10 t2/ d t2 t3+ c t3 t4+ t4 8 t5* t1 t5 t6+ w t6 t7= t7 a五、分析题（3小题，每题10分，共30分）1. 给定非确定的有限自动机M如下图所示将M确定化，并画出确定化后的状态转换图（要求：写出步骤）2.设有文法G[S]:S→bBS′S′→aBS′|εA→S|aB→Ac其LL(1)分析表如下a b c#S S→bBS′S′S′→aBS′S′→εS′→εA A→a A→SB B→Ac B→Ac利用此分析表判断输入串bacaac（改）是否为文法G[S]的句子，给出bacaac的分析过程3. 应用DAG对下面的基本块进行优化，写出优化后的基本块（要求写出过程）1. T0:=3.14 6. T3:=2*T02. T1:=2*T0 7. T4:=R+r3. T2:=R+r 8. T5:=T3*T44. A:=T1*T2 9. T6:=R-r5. B:=A 10. B:=T5*T。
参考答案一、单项选择题(共10小题，每小题2分，共20分)1．语言是A ．句子的集合B ．产生式的集合C ．符号串的集合D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析C ．词法分析、语法分析、语义分析和中间代码生成D ．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左A ．非终结符号B ．短语C ．句子D ．直接短语 4．下推自动机识别的语言是A ．0型语言B ．1型语言C ．2型语言D ．3型语言5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A ． 字符B ．单词C ．句子D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0⊂L 1⊂L 2⊂L 3 B ．L 3⊂L 2⊂L 1⊂L 0C ．L 3=L 2⊂L 1⊂L 0D ．L 0⊂L 1⊂L 2=L 3 7．词法分析的任务是A ．识别单词B ．分析句子的含义C ．识别句子D ．生成目标代码 8．常用的中间代码形式不含A ．三元式B ．四元式C ．逆波兰式D ．语法树 9． 代码优化的目的是A ．节省时间B ．节省空间C ．节省时间和空间D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言C ．把中间代码变换成依赖具体机器的目标代码装 订 线D．把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分）1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。
2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。
3．通常把编译过程分为分析前端与综合后端两大阶段。
词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。
