编译原理题库A.doc

西北民族大学计算机科学与信息工程学院期末考试 编译原理试卷（A卷）专业:计算机科学技术 课程代码: 15002171 总 分题号一二三四五六核分人题分102010102030复查人得分学号: 姓 名: 得 分评卷人一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入题干后的括号内。每小题2分，共10分）1、一般程序设计语言的定义都涉及 三个方面。(1)语法 (2)语义 (3)语用 (4)程序基本符号的确定供选答案：. (1)(2)(3) . (1)(2)(4) . (1)(3)(4) . (2)(3)(4)能力层次：记忆 难易度：B2、编译过程中，语法分析器的任务是 。 (1)分析单词是如何构成的(2)分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的（4）分析程序的结构可选项有：A. （2）和（3） B. （4）C. （2）（3）（4） D. （1）（2）（3）（4） 能力层次：理解 难易度：A3、在下述的编译方法中，自顶向下的分析方法有 。 简单优先分析 算符优先分析 递归下降分析 预测分析技术 LR（K）分析 SLR（k）分析 LL（k）分析 LALR（K）分析 A. B. C. D. E. F. 能力层次：理解 难易度：A4、高级语言编译程序常用的语法分析方法中，优先分析法属于 分析方法。A. 自左至右 B. 自顶向下C. 自底向上 D. 自右向左能力层次：记忆 难易度：A5、赋值语句X:=-(a+b)/(c-d)-(a+b*c)逆波兰表示是 。A. Xab+cd-/-bc*a+-:=B. Xab+/cd-bc*a+-:=C. Xab+-cd-/abc*+-:=D. Xab+cd-/abc*+-:= 能力层次：简单运用 难易度：C得 分评卷人二、判断题（认为对的，在题后的括号内打“”，认为错的打“”。每小题1分，共20分） 1、扫描器扫描源程序中的符号，产生具有最小语义信息的单词（ ）能力层次：理解 难易度：C2、所有编译程序直接将源程序翻译成机器语言（ ）能力层次：理解 难易度：B3、上下文无关文法可用来描述程序设计语言中的单词。（ ）能力层次：理解 难易度：B4、正规式、正规文法、有穷自动机都是单词描述的工具。（ ）能力层次：记忆 难易度：C5、任何一个上下文无关文法都只有一个对应的语法树。（ ）能力层次：理解 难易度：D6、有穷自动机从起点到终点的任一条路径上的符号序列就是该有穷自动机识别的一种单词。 （ ）能力层次： 简单运用 难易度：B 7、确定的有穷自动机有多个终态。 （ ）能力层次：理解 难易度：C 8、不确定的有穷自动机可转换为确定的有穷自动机。 （ ）能力层次：简单运用 难易度：C9、有穷自动机是一种识别装置。 （ ）能力层次：理解 难易度：B10、语义分析程序需要源程序。 （ ）能力层次：理解 难易度：B11、正规文法也叫三型文法。 （ ）能力层次：记忆 难易度：A12、2型文法叫上下文无关文法，是语法分析的工具。 （ ）能力层次：理解 难易度：B 13、文法是用有穷集合描述无穷集合的工具。 （ ）能力层次：理解 难易度：B14、所有文法都可使用LL（1）预测分析法。 （ ）能力层次：简单运用 难易度：B15、推导就是不断用某一产生式的右部去替换句型中的某个非终极符。 （ ）能力层次：简单运用 难易度：C16、将某一语法分析树的叶结点从左到右排列，得到的节点序列就是该文法的一个句型。若所有叶结点都是终极符，则该序列就是该文法的一个句子。 （ ） 能力层次： 综合运用和创见 难易度：D17、如果某语法树的一个节点没有子节点，则该节点代表的是文法中的一个终极符。 （ ）能力层次：综合运用和创见 难易度：D18、自底向上分析法中包含LL（1）预测分析法和LR分析法。 （ ）能力层次：理解 难易度：C19、自底向上分析法中LR分析法需要相应的优先关系表。 （ ）能力层次：简单运用 难易度：D20、自底向上分析法主要有移入、归约、出错、接受四个动作。 （ ）能力层次： 简单运用 难易度：B得 分评卷人三、填空题（每空1分，共10分） 1计算机可以直接执行的语言称为（ ）。能力层次：理解 难易度：A2.词法分析的工具有（ ）、（ ）、（ ）。能力层次：记忆 难易度：B3.语义分析程序的主要工作分两部分，对说明部分的处理是 （ ），对语句部分的处理是（ ）。能力层次：理解 难易度：B4 有穷自动机分为（ ）和（ ）两种。能力层次：记忆 难易度：A符号表是由编译程序的（ ）阶段构造的。能力层次：理解 难易度：B表达式a-b/(c+d)的逆波兰表示为（ ）。能力层次：简单运用 难易度：D得 分评卷人 四、 解释概念题（每小题2分，共10分） 1.语法分析。能力层次：简单运用 难易度：C2.文法能力层次：理解 难易度：D3.非终极符能力层次：记忆 难易度：B4.终极符能力层次：理解 难易度：B5.文法的语言能力层次：记忆 难易度：B得 分评卷人五、简答题（每小题4分，共20分）1、在编译过程中为什么要建立符号表？符号表应包括哪些内容？能力层次：理解 难易度：C2、何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 能力层次：记忆 难易度：C3、 编译程序的结构分为哪几步？各部分的主要作用是什么？能力层次：简单运用 难易度：B4、 自顶向下语法分析方法有哪两种？各有什么特点？能力层次：简单运用 难易度：C5、 自底向上分析方法的动作有哪几步？能力层次：简单运用 难易度：B得 分评卷人六、综合应用题（每小题5分，共30分）1、设已给文法G程序： 程序分程序|复合语句 分程序无标号分程序|标号：分程序 复合语句无标号复合语句|标号：复合语句 无标号分程序分程序首部；复合尾部 无标号复合语句begin复合尾部 分程序首部begin说明|分程序首部；说明 复合尾部语句end|语句；复合尾部 说明d 语句s 标号L (1) 给出句子 L: L: begin d; d; s; s end 的最左推导和最右推导。 能力层次：综合运用和创见 难易度：D(2) 画出上述句子的语法树。 能力层次：简单运用 难易度：D2、对于如下的文法，用某种高级语言写出递归下降分析程序。 Pbegin d; X end Xd;X XsY Y;sY Y 能力层次：综合运用和创见 难易度：D3、对于下列的文法和相应的句子，试指出这些句子的全部短语；分别给出句子的最右推导，并指出各步直接推导所得句型的句柄。 S(AS) S(b) A(SaA) A(a) 句子：(b) a (a) (b) 能力层次：简单运用 难易度：D4、给出与正规式R（ab）*（a|b）*ba等价的NFA能力层次：简单运用 难易度：D5、 证明下列文法为LL（1）文法并构造文法的LL（1）预测分析表。并根据LL（1）表给出对句子abcdcee#的分析过程。SaSeSBBbBeBCCcCcCd能力层次：综合运用和创见 难易度：E6、文法GM及其LR分析表如下，请给出对串dbba#的