编译原理题库E.doc

西北民族大学计算机科学与信息工程学院期末考试 编译原理试卷（E卷）专业:计算机科学技术 课程代码: 15002171总 分题号一二三四五六核分人题分102010102030复查人得分学号: 姓 名: 得 分评卷人一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入题干后的括号内。每小题2分，共10分）1、编译过程中，语法分析器的任务是 。(1)分析单词是如何构成的(2)分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的（4）分析程序的结构可选项有：A. （2）和（3） B. （4）C. （2）（3）（4） D. （1）（2）（3）（4） 能力层次：理解 难易度：B2、高级语言编译程序常用的语法分析方法中，优先分析法属于 分析方法。A. 自左至右 B. 自顶向下C. 自底向上 D. 自右向左能力层次：理解 难易度：A3、在下述的编译方法中，自顶向下的分析方法有 。 简单优先分析 算符优先分析 递归下降分析 预测分析技术 LR（K）分析 SLR（k）分析 LL（k）分析 LALR（K）分析 A. B. C. D. E. F. 能力层次：理解 难易度：C、下列属于三型性文法的是： AG1：SAbB SAASABabBb BG2:SA ASAabbSa bSAABB ASaabbb Aba CG3: SaB SaA AbA Bb DG4: SAab SB ACc ABb BBb Ba CD CBab Dd 能力层次：简单运用 难易度：B、任何一个上下文无关文法都有 对应的语法树 A1个B2个C没有D以上都不完全正确能力层次：理解 难易度：D得 分评卷人二、判断题（认为对的，在题后的括号内打“”，认为错的打“”。每小题1分，共20分） 1. 上下文无关文法可用来描述程序设计语言中的单词。（ ）能力层次：记忆 难易度：B2. 正规式是语法描述的工具。 （ ）能力层次：记忆 难易度：C3. 所有文法都不是二义的。（ ）能力层次：理解 难易度：C4. 确定的有穷自动机的每个状态转换函数只有一个值。（ ）能力层次：理解 难易度：B5. 不确定的有穷自动机不可转换为确定的有穷自动机。（ ）能力层次：记忆 难易度：A6. 有穷自动机是一种识别活前缀的装置。（ ）能力层次：综合运用和创见 难易度：D7. 词法分析程序不需要源程序。（ ）能力层次：理解 难易度：C8. 语法分析程序和源程序无关。（ ）能力层次：理解 难易度：C9. 中间代码和具体计算机硬件无关。（ ）能力层次：理解 难易度：B10. 文法是用有穷集合描述无穷集合的工具。（ ）能力层次：记忆 难易度：B11. 所有文法都可使用LL（1）预测分析法。（ ）能力层次：综合运用和创见 难易度：D12. 用最右推导导出的句型叫规范句型。（ ）能力层次：简单运用 难易度：C13. 递归子程序的实现方法是对文法中的每一个非终极符编写一个子程序，子程序的结构和该非终极符的产生式结构相同，遇非终极符即匹配，遇终极符则调用该终极符的子程序。 （ ）能力层次：理解 难易度：D14. 自底向上分析法中优先分析法需要相应的优先关系表。（ ）能力层次：理解 难易度：C15. 如果一个文法的LR（0）项目族中包含移入-归约冲突，则能使用LR（）分析表来解决所有移入-归约冲突。 （ ）能力层次：综合运用和创见 难易度：D16. LR（1）分析法需要一个语法分析栈、一个GOTO表及ACTION表、一个驱动程序。 （ ）能力层次：综合运用和创见 难易度：D17. 语义分析阶段产生目标代码。 （ ）能力层次：理解 难易度：C18. 语言由构成语言的基本符号、以及构成单词的规则、单词的结构规则及语义组成。 （ ）能力层次：理解 难易度：B19. 优化的目标是提高目标代码的运行速度。 （ ）能力层次： 难易度：B20. 优化主要有：常量表达式优化（合并常数）、公共表达式优化（消除重复操作）、不便表达式的循环外体、削减运算强度。此外还有消除无用代码、复写传播、数学变换、窥孔优化。 （ ）能力层次：综合运用和创见 难易度：E得 分评卷人三、填空题（每空1分，共10分） 1.语义分析程序的主要工作分两部分，对说明部分的处理是（ ），对语句部分的处理是（ ）。能力层次：理解 难易度：B2.有穷自动机分为（ ）和（ ）两种。能力层次：记忆 难易度：C3.对文法GS如果有S=*并且是由终结符组成，则称是文法GS的（ ）。能力层次：综合运用和创见 难易度：C4.符号表是由编译程序的（ ）阶段构造的。能力层次：理解 难易度：B5.从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。能力层次：理解 难易度：A6.语法规则是（ ）形成规则，词法规则是（）形成规则。能力层次：理解 难易度：C得 分评卷人四、解释概念题（每小题2分，共10分） 1、自顶向下分析能力层次：理解 难易度：C2、目标语言能力层次：理解 难易度：C3、句型能力层次：记忆 难易度：D4、非终极符能力层次：理解 难易度：B5、LL（1）预测分析表能力层次：简单运用 难易度：D得 分评卷人五、简答题（每小题4分，共20分）1. 为什么要使用中间代码形式？能力层次：理解 难易度：C2. 何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 能力层次：理解 难易度：B3. 自顶向下语法分析方法有哪两种？各有什么特点？能力层次：记忆 难易度：A4. 什么叫上下文无关文法？能力层次：记忆 难易度：C5. 自底向上分析方法的动作有哪几步？ 能力层次：理解 难易度：B得 分评卷人六、综合应用题（每小题5分，共30分）1、对于下列的文法和相应的句子，试指出这些句子的全部短语；分别给出句子的最右推导，并指出各步直接推导所得句型的句柄。 MMT+ MT TTN* TN NNP NP PM Pi 句子：iii*i+ 能力层次：综合运用和创见 难易度：D、给出与正规式R（01）*（0|1*）10等价的NFA。 能力层次：综合运用和创见 难易度：D、设已给文法GE： E E+T | -T | T T T*F | F F P F | P P (E) | i 试设计一个递归下降分析器。 能力层次：简单运用 难易度：D4、判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。SxT TxMd | dMAb | AxM | e 能力层次：综合运用和创见 难易度：E、文法GM及其LR分析表如下，请给出对串dtta#的分析过程。 GM: 1) M VtA 2) V d3) V 4) A a5) A Ata 6) A nameACTIONGOTOtda#MAV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5 能力层次：综合运用和创见 难易度：D、一个上下文无