东师《编译原理》15春在线作业2一、单选题（共20 道试题，共60 分。
）V 1. 在语法分析处理中，FIRST集合、FOLLOW集合均是什么样的集合()。
A. 非终极符集B. 终极符集C. 字母表D. 状态集满分：3 分2. 在BNF表示方法中，“|”表示什么()。
A. 与B. 或C. 非D. 引导开关参数满分：3 分3. 如果一个DFA的两个不同的状态s和t具有什么关系，则称s和t等价()。
A. 已区分B. 待区分C. 可区分D. 不可区分满分：3 分4. 假设某程序语言的文法如下：S→SaT∣T，T→TbR∣R，R→PdR ∣P，P→fSg∣e,那么，此文法是哪一类文法()。
A. 正规文法B. 算符文法C. 二义性文法D. LL(1)文法满分：3 分5. 基本块的性质中包含哪一条()。
A. 只有一个入口语句和一个出口语句B. 有一个入口语句和多个出口语句C. 有多个入口语句和一个出口语句D. 有多个入口语句和多个出口语句满分：3 分6. 表示流程图中各结点间控制关系的一种直观而有效的数据结构，称之为什么()。
A. 控制结点树B. 语法树C. 树形表示D. 二叉树满分：3 分7. 正则式的“*”读作什么()。
A. 并且B. 或者C. 连接D. 闭包满分：3 分8. 两个有穷自动机等价是指它们的什么相等()。
A. 状态数相等B. 有向弧数相等C. 所识别的语言相等D. 状态数和有向弧数相等满分：3 分9. 与正规式(a|b)* 等价的正规式是哪个()。
A. a*|b*B. a*b*C. (a*b*)*D. (ab)*满分：3 分10. 语法制导翻译的模式，就是对文法中的什么都附加一个语义动作或语义子程序()。
A. 非终结符号B. 产生式C. 终结符号D. 开始符号满分：3 分11. 项目A→α•Bβ称为什么项目，其中B∈VN()。
A. 移进B. 归约C. 待约D. 接受满分：3 分12. 代码优化的主要目标是什么()。
《编译原理》作业参考答案一、填空1．图二图一。
2．文法是无ε产生式，且任意两个终结符之间至多有一种优先关系的算符文法。
3．最右推导最右推导。
4．对于循环中的有些代码，如果它产生的结果在循环中是不变的，就把它提到循环外来。
把程序中执行时间较长的运算替换为执行时间较短的运算。
5．对于文法中的每个非终结符A的各个产生式的候选首符集两两不相交；对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）= ø6．控制。
7．语义分析和中间代码产生8．自上而下自下而上自上而下9．自下而上表达式10．自下而上11．源程序单词符号12． DFA初态唯一，NFA初态不唯一；DFA弧标记为Σ上的元素，NFA弧标记为Σ*上的元素；DFA的函数为单射，NFA函数不是单射13．词法，词法分析器，子程序，语法14．ε，a，ab，ab15．终结符号，非终结符号，产生式16．L(G)={a n | n≥1}17．1型，2型，3型18．二义的19．快20．终态，输入字21．单词符号，终结符22．归约23．必须24．直接25．终结符，更快26．E→E+∙T， E→E∙+T， E→∙E+T， E→E+T∙27．归约—归约28．类型检查，一致性检查29．词法分析、词法30．语法分析程序、语法31。
终结符号、产生式、开始符号、非终结符32．2、2、333．不需要避开34．符合、不符合35．推导36．包括37．Ass38．一定没有、一定没有、至多只有一个39．SLR（1）40．移进——归约41．a.控制流检查、b.一致性检查、c.相关名字检查二、判断下面语法是否正确1 ×2 ×3 √4 ×5 √6 ×三、简答题1．词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一，手工编写词法分析程序。
二，由词法分析器自动生成程序生成。
第一章测试题一.解答题1:试述标识符与名字的区别。
答案标识符是由字母和数字(有些语言中还允许含一些其他符号)组成的以字母(及其他符号)打头的字符串。
若给某个标识符赋予确切的含义，这个标识符就称为名字。
标识符只是抽象的字符序列，无确切的意义，而名字则是由标识符表示，且具有语义属性(如类型、种属等)的实体。
2:将高级语言程序翻译为计算机可执行的目标程序有哪些途径？答案主要途径有两种:解释与编译。
解释程序的特点是不先将高级语言程序全部翻译成机器代码，而是每读人一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复，即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的存储空间中，在用户箱要时再执行之,即先翻译后执行。
3:何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？答案源程序是指以某种程序设计语言编写并供加工处理的程序。
目标程序是指编译程序(或解释程序)将源程序处理加工而得的另一种语言(目标语言)的程序。
翻译程序是将用某种语言编写的程序翻译成另一种语言形式的程序的系统软件。
编译程序与解释程序均为翻译程序，但二者工作方法不同。
解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。
即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的存储空间中，在用户需要时再执行之。
即先翻译后执行。
第二章测试题一.解答题1:已给文法G[<表达式>]:试给出句子的规范推导，指出每步推导所得句型的句柄，并画出相应的语法树，指出树中的所有短语。
答案规范推导(有下划线的子串为该句型的句柄)：相应的语法树如图解2.1所示。
