川大《编译原理2243》15春在线作业一100分答案

15春《编译原理》作业1
单选题多选题判断题
一、单选题（共6 道试题，共24 分。

）
1. 审查每个算符是否具有语言规范允许的运算对象是（）的工作。

A. 语法分析
B. 语义分析
C. 中间代码生成
D. 代码优化
E. 目标代码生成
-----------------选择：B
2. 编译程序是将高级语言程序翻译成( )。

A. 高级语言程序
B. 机器语言程序
C. 汇编语言程序
D. 汇编语言或机器语言程序
-----------------选择：D
3. 四元式之间的联系是通过_____实现的。

A. 指示器
B. 临时变量
C. 符号表
D. 程序变量
-----------------选择：B
4. 下列______优化方法不是针对循环优化进行的。

A. 强度削弱
B. 删除归纳变量
C. 删除多余运算
D. 代码外提
-----------------选择：C
5. 中间代码生成时所依据的是_____。

A. 语法规则
B. 词法规则
C. 语义规则
D. 等价变换规则
-----------------选择：C
6. 用高级语言编写的程序经编译后产生的程序叫_____。

A. 源程序
B. 目标程序
C. 连接程序
D. 解释程序
-----------------选择：B
15春《编译原理》作业1。

第二章P-36-6（1）L（G）是0~9组成的数字串；（2）最左推导：N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127N⇒ND⇒DD⇒3D⇒34N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568最右推导：N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127N⇒ND⇒N4⇒D4⇒34N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568P-36-7G（S）：（没有考虑正负符号问题）S→P|APP→1|3|5|7|9A→AD|NN→2|4|6|8|PD→0|N或者：（１）S→ＡＢＣ｜CＡ→１｜２｜３｜４｜５｜６｜７｜８｜９Ｂ→ＢＡ｜Ｂ０｜εＣ→1｜3｜5｜7｜9P-36-8G（E）：E→T|E+T|E-TT→F|T*F|T/FF→（E）|i最左推导：E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T*F⇒i+F*F⇒i+i*F⇒i+i*iE⇒T⇒T*F⇒F*F⇒i*F⇒i*（E）⇒i*（E+T）⇒i*（T+T）⇒i*（F+T）⇒i*（i+T）⇒i*（i+F）⇒i*（i+i）最右推导：E⇒E+T⇒E+T*F⇒E+T*i⇒E+F*i⇒E+i*i⇒T+i*i⇒F+i*i⇒i+i*iE⇒T⇒T*F⇒T*（E）⇒T*（E+T）⇒T*（E+F）⇒T*（E+i）⇒T*（T+i）⇒T*（F+i）⇒T*（i+i）⇒F*（i+i）⇒i*（i+i）语法树：SiSeSiSiiSiS i S eS iiP-36-9句子：iiiei 有两个语法树： S ⇒iSeS ⇒iSei ⇒iiSei ⇒iiiei S ⇒iS ⇒iiSeS ⇒iiSei ⇒iiiei因此iiiei 是二义性句子，因此 该文法是二义性的。

P-36-10 S →TS|T T →(S)|()P-36-11L1: G(S): S →AC A →aAb|ab C →cC|ε L2: G(S): S →AB A →aA|ε B →bBc|bc L3: G(S): S →AB A →aAb|ε B →aAb|ε L4: G(S): S →1S0|A A →0A1|ε或者：S →A|B A →0A1|ε B →1B0|A 第三章（1）Ei+i+iE +TE +TT F iF iF iEE +TT F iT *FF iii+i*i Ei-i-iE-TE -TT F iF iF i确定化：最小化：{0，1，2，3，4，5}，{6}{0，1，2，3，4，5}0={1，3，5} {0，1，2，3，4，5}1={1，2，4，6} {0，1，2，3，4}，{5}，{6} {0，1，2，3，4}0={1，3，5} {0，1，2，3}，{4}，{5}，{6}{0，1，2，3}0={1，3} {0，1，2，3}1={1，2，4} {0，1}，{2，3}，{4}，{5}，{6}{0，1}0={1} {0，1}1={1，2} {2，3}0={3} {2，3}1={4} {0}，{1}，{2，3}，{4}，{5}，{6}P64-8(1)（0|1）*01(2)（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*（0|5）|（0|5）(3)0*1（0|10*1）* | 1*0（1|01*0）*P84-12（a）a最小化：{0，1} {2，3}{0，1}a={1}，{0，1}b={2}{2，3}a={0，3}，{2，3}={3}{0，1}，{2}，{3}a（b）已经确定化，只需最小化：{0，1}，{2，3，4，5}{0，1}a = {1} {0，1}b = {2，4}{2，3，4，5}a = {1，3，0，5} {2，3，4，5}b = {2，3，4，5}又：{2，4}a = {1，0} {2，4}b = {3，5} {3，5}a={3，5} {3，5}b = {2，4} 分划为：{0，1}，{2，4}，{3，5}{0，1}a = {1} {0，1}b = {2，4}{2，4}a = {1，0} {2，4}b = {3，5}{3，5}a = {3，5} {3，5}b = {2，4}所以不能再分aP64-14正规式：（0|10）*还可以：然后再确定化，最小化，结果应该一样。

《编译原理2243》15春在线作业2一、单选题（共20 道试题，共60 分。

）1. 合并表达式中常量运算的目的是______。

（）A. 使表达式的常量尽可能少B. 使表达式尽可能简短C. 将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少正确答案：C2. 在重载符号的引用点，若其含义能确定到唯一，就叫做重载的______。

（）A. 定义B. 消除C. 确定正确答案：B3. 选择最优的寄存器指派方案是困难的，这个问题是______完全的。

（）A. QPB. NQC. NPD. PQ正确答案：C4. “用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行。

”这种说法______。

（）A. 不正确B. 正确正确答案：A5. 文法的二义性和语言的二义性是两个______的概念。

（）A. 不同B. 相同C. 无法判断正确答案：A6. 目标机器指令系统的性质决定了指令选择的______程度。

（）A. 快慢B. 难易C. 简繁正确答案：B7. 编写一个计算机高级语言的源程序后，在正式上机运行之前，一般要经过______这几步。

1）编辑2）编译3）连接4）运行（）A. 1）2）3）4）B. 1）2）3）C. 1）3）D. 1）4）正确答案：B8. 如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算______。

( )A. 之前B. 之后C. 都可以正确答案：B9. 使用解释程序时，在程序未执行完的情况下，______重新执行已执行的部分。

()A. 也能B. 不能正确答案：A10. 下列不属于字符串banana的字串是______。

（）A. bB. baaC. babnD. baan正确答案：C11. 三地址代码是语法树或dag的______表示。

（）A. 直线化B. 图形化C. 图表化D. 线性化正确答案：D12. 一般程序设计语言的定义都涉及_________三个方面;1)语法2)语义3)语用4)程序基本符号的确定。

第1章引言1、解释下列各词源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。

源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。

目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。

目标程序（结果程序）一般可由计算机直接执行。

低级语言：机器语言和汇编语言。

高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。

如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。

翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。

其中包括：编译程序，解释程序，汇编程序。

编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。

解释程序: 以该语言写的源程序作为输入，但不产生目标程序。

按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。

2、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。

3、简述编译程序的基本过程的任务。

编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。

词法分析：输入源程序，进行词法分析，输出单词符号。

语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。

中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。

优化：对中间代码进行优化处理。

目标代码生成：把中间代码翻译成目标语言程序。

4、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。

《编译原理》作业参考答案一、填空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．词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一，手工编写词法分析程序。

二，由词法分析器自动生成程序生成。

川大《编译原理2243》15秋在线作业1满分答案四川大学《编译原理2243》15秋在线作业1一、单选题（共 20 道试题，共 60 分。

）1. 程序块的概念起源于______语言。

（）A. CB. C++C. AlgolD. FORTRAN答案：C大众理财作业满分答案2. 编译程序生成的目标程序______是机器语言的程序。

（）A. 一定B. 不一定答案：B3. 三地址代码是语法树或dag的______表示。

（）A. 直线化B. 图形化C. 图表化D. 线性化答案：D4. 一般程序设计语言的定义都涉及_________三个方面;1)语法2)语义3)语用4)程序基本符号的确定。

()A. 1)2)3)B. 1)2)4)C. 1)3)4)D. 2)3)4)答案：A5. 使用解释程序时，在程序未执行完的情况下，______重新执行已执行的部分。

()A. 也能B. 不能答案：A6. 下列关于标识符和名字的叙述中，正确的为______。

（）A. 标识符有一定的含义B. 名字是一个没有意思的字符序列C. 名字有确切的属性D. 都不对答案：C7. 程序的基本块是指______。

（）A. 一个子程序B. 一个仅有一个入口和一个出口的语句C. 一个没有嵌套的程序段D. 一组顺序执行的程序段，仅有一个入口和一个出口答案：C8. 编写一个计算机高级语言的源程序后，在正式上机运行之前，一般要经过______这几步。

1）编辑2）编译3）连接4）运行（）A. 1）2）3）4）B. 1）2）3）C. 1）3）D. 1）4）答案：B9. 在分析树中，一个结点的______是由该结点的父结点和（或）兄弟结点的属性定义的。

（）A. 继承属性B. 综合属性C. 值D. 作用域答案：A10. 如果从一个类型转换到另一类型可以由编译器自动完成，这样的转换为______的转换，也叫做强制。

A. 隐式B. 显式C. 自动答案：A11. 不包含其他循环的循环叫做______循环。

15春《计算机编译原理》在线作业1一、单选题（共15 道试题，共75 分。

）1. 文法G：S→xSx|y所识别的语言是（）。

A. xyxB. (xyx)*C. xnyxn(n≥0)D. x*yx*正确答案：C2. SLR(1)分析法的名字中，“1”的含义是（）。

A. 自左向右进行分析B. 自右向左进行分析C. 向貌似句柄的符号串后查看1个输入符号D. 向貌似句柄的符号串前查看1个输入符号正确答案：C3. LR(1)分析法的名字中，“L”的含义是（）。

A. 自右向左进行分析B. 采用最右推导的逆过程——最左归约C. 向貌似句柄的符号串后查看1个输入符号D. 自左向右进行分析正确答案：D4. Chomsky 定义的四种形式语言文法中，0型文法又称为（）文法。

A. 短语结构文法B. 前后文无关文法C. 前后文有关文法D. 正规文法E. 图灵机F. 有限自动机G. 下推自动机正确答案：A5. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类：自底向上分析试图为输入符号串构造一个（）。

A. 语法树B. 有向无环图C. 最左推导D. 最右推导正确答案：D6. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类：（）和LL(1)分析法属于自顶向下分析。

A. 深度分析法B. 宽度优先分析法C. 算符优先分析法D. 递归子程序分析法正确答案：D7. 对下列错误信息，请指出可能是编译的哪个阶段，else 没有匹配的if 对应（）。

A. 语法分析B. 语义分析C. 词法分析D. 词义分析正确答案：A8. 在规范归约中，用（）来刻画可归约串。

A. 直接短语B. 句柄C. 最左素短语D. 素短语正确答案：B9. 若文法G 定义的语言是无限集，则文法必然是（）：A. 递归的B. 前后文无关的C. 二义性的D. 无二义性的正确答案：A10. 对应于产生式A->XY继承属性Y.y，可能正确的语义规则是（）。

《编译原理》课后习题答案第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。