15春地大《编译原理(新)》在线作业二答案

东师《编译原理》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. 代码优化的主要目标是什么()。

E=>E+T=>E+T*F，所以E+T*F是句型。
从子树和短语之间的关系可知：
E+T*F是句型E+T*F相对于E的短语；
T*F是句型E+T*F相对于T的短语，也是简单短语和句柄。
13、(1)最左推导：S => ABS =>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
B—>AB | 0B |ε
C—>0 | 2 | ห้องสมุดไป่ตู้ | 6 | 8
考虑包括“0”的情况：
G[S]：S—>AB | C
B—>AB | C
A—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
C—>0 | 2 | 4 | 6 | 8
Π0：{A,B}，{C}
对终态组进行审查，判断A和B是等价的，故这是最后的划分
重新命名，以A、C代替{A,B}、{C}得DFA
a
b
–+A
A
C
C
A
(2)这是DFA，直接最小化
初始分划得：终态组{0}，非终态组{1,2,3,4,5}
Π0：{0}，{1,2,3,4,5}
对{1,2,3,4,5}进行审查：
∵{4}输入a后 到达{0}，{1,2,3,5}输入a后 到达{1,3,5}，故得到新分划{0,1,3,5}，{4}
C—>2 | 4 | 6 | 8
6、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导

《编译原理》作业参考答案一、填空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 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。