编译原理第8章作业及习题参考答案

编译原理习题及答案（整理后）第⼀章1、将编译程序分成若⼲个“遍”是为了。

b．使程序的结构更加清晰2、构造编译程序应掌握。

a．源程序b．⽬标语⾔c．编译⽅法3、变量应当。

c．既持有左值⼜持有右值4、编译程序绝⼤多数时间花在上。

d．管理表格5、不可能是⽬标代码。

d．中间代码6、使⽤可以定义⼀个程序的意义。

a．语义规则7、词法分析器的输⼊是。

b．源程序8、中间代码⽣成时所遵循的是- 。

c．语义规则9、编译程序是对。

d．⾼级语⾔的翻译10、语法分析应遵循。

c．构词规则⼆、多项选择题1、编译程序各阶段的⼯作都涉及到。

b．表格管理c．出错处理2、编译程序⼯作时，通常有阶段。

a．词法分析b．语法分析c．中间代码⽣成e．⽬标代码⽣成三、填空题1、解释程序和编译程序的区别在于是否⽣成⽬标程序。

2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码⽣成、代码优化和⽬标代码⽣成。

3、编译程序⼯作过程中，第⼀段输⼊是源程序，最后阶段的输出为标代码⽣成程序。

4、编译程序是指将源程序程序翻译成⽬标语⾔程序的程序。

⼀、单项选择题1、⽂法G：S→xSx|y所识别的语⾔是。

c. x n yx n(n≥0)d. x*yx*2、⽂法G描述的语⾔L(G)是指。

a. L(G)={α|S + ?α , α∈VT*} b. L(G)={α|S*?α, α∈VT*}c. L(G)={α|S *?α,α∈(VT∪V N*)} d. L(G)={α|S+ ?α, α∈(VT∪V N*)}3、有限状态⾃动机能识别。

a. 上下⽂⽆关⽂法b. 上下⽂有关⽂法c.正规⽂法d. 短语⽂法4、设G为算符优先⽂法，G的任意终结符对a、b有以下关系成⽴。

a. 若f(a)>g(b)，则a>bb.若f(a)c. a~b都不⼀定成⽴d. a~b⼀定成⽴5、如果⽂法G是⽆⼆义的，则它的任何句⼦α。

a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由⽂法的开始符经0步或多步推导产⽣的⽂法符号序列是。

第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。

解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。

解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。

如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。

分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。

N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

1、已知文法：A → aAd|aAb|ξ判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串 #ab# 给出分析过程。

解：(0) A’→ A(1)A → aAd(2) A → aAb(3) A →ξ构造该文法的活前缀DFA：由上图可知该文法是SLR（1）文法。

构造SLR（1）的分析表：3、考虑文法：S →AS|b A→SA|aFollow(A) = first(S) = {b}+first(A)= {a,b}(1)列出这个文法的所有LR（0）项目(2)按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。

(3)这个文法是SLR的吗？若是，构造出它的SLR分析表。

(4)这个文法是LALR或LR（1）的吗？解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a(1)列出所有LR（0）项目：S’→·S S→·b A→·a S’→ S· S→b· A→a·S →·AS A→·SAS →A·S A→S·AS →AS· A→SA·(3)构造该文法的活前缀NFA：由上可知：I1 I3 I5 中存在着移进和归约冲突在I1中含项目：S’→ S·归约项 Follow(S’)={#}A →·a 移进项 Follow(S’)∩{a}=∮S →·b 移进项 Follow(S’)∩{b}=∮在I3中含项目：A →SA·归约项 Follow(A)={a,b}S →·b 移进项 Follow(A) ∩ {b}≠∮A →·a 移进项 Follow(A) ∩ {a}≠∮在I5中含项目：S →AS·归约项 Follow(S)={#,a,b}A →·a 移进项 Follow(S) ∩ {a}≠∮S →·b 移进项 Follow(S) ∩ {b }≠∮由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR （1）文法。

第二章高级语言的语法描述6、令文法G 6为：N →D|ND D → 0|1|2|3|4|5|6|7|8|9（1）G 6 的语言L （G 6）是什么？（2）给出句子01270127、、34和568的最左推导和最右推导。

解答：思路：由N N →→ D|ND 可得出如下推导N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞…＝＞＝＞…＝＞＝＞…＝＞D D n（n ＞=1=1））可以看出，N 最终可以推导出1个或多个（也可以是无穷）D ，而D D →→ 0|1|2|3|4|5|6|7|8|9可知，每个D 为0～9中的任一个数字，所以，中的任一个数字，所以，N N N 最终推导出的就是由最终推导出的就是由0～9这10个数字组成的字符串。

（1）G 6 的语言L （G 6）是由0～9这10个数字组成的字符串个数字组成的字符串,,或{0{0，，1,1,……,9}+。

(2)(2)句子句子01270127、、34和568的最左推导分别为的最左推导分别为: : N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞＝＞＝＞NDDD NDDD NDDD＝＞＝＞＝＞DDDD DDDD DDDD＝＞＝＞＝＞0DDD 0DDD 0DDD＝＞＝＞＝＞01DD 01DD 01DD＝＞＝＞＝＞012D 012D 012D＝＞＝＞＝＞0127 0127 N ＝＞＝＞ND ND ND＝＞＝＞＝＞DD DD DD＝＞＝＞＝＞3D 3D 3D＝＞＝＞＝＞34 34N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞＝＞＝＞DDD DDD DDD＝＞＝＞＝＞5DD 5DD 5DD＝＞＝＞＝＞56D 56D 56D＝＞＝＞＝＞568 568 句子01270127、、34和568的最右推导分别为的最右推导分别为: :N ＝＞＝＞ND ND ND＝＞＝＞＝＞N7N7N7＝＞＝＞＝＞ND7ND7ND7＝＞＝＞＝＞N27N27N27＝＞＝＞＝＞ND27ND27ND27＝＞＝＞＝＞N127N127N127＝＞＝＞＝＞D127D127D127＝＞＝＞＝＞0127 0127 N ＝＞＝＞ND ND ND＝＞＝＞＝＞N4N4N4＝＞＝＞＝＞D4D4D4＝＞＝＞＝＞34 34N ＝＞＝＞ND ND ND＝＞＝＞＝＞N8N8N8＝＞＝＞＝＞ND8ND8ND8＝＞＝＞＝＞N68N68N68＝＞＝＞＝＞D68D68D68＝＞＝＞＝＞568 5687、写一个文法，使其语言是奇数集，且每个基数不以0开头。

第七章
习题7.2.6 ：C语言函数f的定义如下：
Int f(int x, *py, **ppz){
**ppz +=1；*py +=2；x +=3; return x+*py+**ppz;
}
变量a是一个指向b的指针；变量b是一个指向c的指针，而c是一个当前值为4的整数变量。

如果我们调用f(c,b,a),返回值是什么？
答：x是传值,而b和c是传地址方式；由函数定义可以得到：b=&c,a=&b, 而**a=**a+1=c+1=5 => c=5; *b=*b+2=c+2=7 =>c=7,**a=7;c=c+3=4+3=7
所以调用f(c,b,a)返回值是7+7+ 7=21
练习7.3.2：假设我们使用显示表来实现下图中的函数。

请给出对fib0（1）的第一次调用即将返回时的显示表。

同时指明那时在栈中的各种活动记录中保存的显示表条目
答：结果如下
第八章
练习8.2.1：假设所有的变量都存放在内存中，为下面的三地址语句生成代码：
5）下面的两个语句序列
X=b*c
Y=a+X
答：生成的代码如下
练习8.5.1：为下面的基本块构造构造DAG
d=b*c
e=a+b
b=b*c
a=e-d
答：DAG如下
练习8.6.1：为下面的每个C语言赋值语句生成三地址代码1)x=a+b*c
答：生成的三地址代码如下。

1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系?1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么?1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。

1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。

1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。

第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3.解：C语言的关键字有：auto break case char const continue default do double else enum externfloat for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。

编译原理8参考答案编译原理8参考答案编译原理是计算机科学中的一门重要课程，它研究的是将高级语言转化为机器语言的过程。

在编译原理的学习过程中，学生们经常会遇到各种难题，而参考答案则是帮助他们解决这些问题的有力工具。

下面是一些编译原理8的参考答案，希望能对学习者有所帮助。

1. 什么是编译器？编译器是一种将高级语言转化为机器语言的程序。

它负责将源代码进行词法分析、语法分析、语义分析等一系列处理，最终生成可执行的目标代码。

2. 请简述编译器的工作原理。

编译器的工作原理主要包括以下几个步骤：- 词法分析：将源代码分解为一个个的词法单元。

- 语法分析：根据语法规则将词法单元组织成语法树。

- 语义分析：对语法树进行类型检查、语义检查等操作。

- 中间代码生成：将语法树转化为中间代码，比如三地址码、四元式等。

- 代码优化：对中间代码进行优化，提高程序的执行效率。

- 目标代码生成：将优化后的中间代码转化为目标机器代码。

- 目标代码优化：对目标机器代码进行优化，进一步提高执行效率。

3. 什么是词法分析？词法分析是编译器的第一步，它将源代码分解为一个个的词法单元。

词法单元包括关键字、标识符、运算符、常量等。

词法分析器通常使用正则表达式、有限自动机等方法进行实现。

4. 什么是语法分析？语法分析是编译器的第二步，它根据语法规则将词法单元组织成语法树。

语法分析器通常使用上下文无关文法和语法分析算法（如LL(1)、LR(1)等）进行实现。

5. 什么是语义分析？语义分析是编译器的第三步，它对语法树进行类型检查、语义检查等操作。

语义分析器通常使用符号表、类型检查规则等进行实现。

6. 什么是中间代码生成？中间代码生成是编译器的第四步，它将语法树转化为中间代码。

中间代码是一种介于源代码和目标代码之间的抽象表示形式，可以是三地址码、四元式、虚拟机指令等。

7. 什么是代码优化？代码优化是编译器的第五步，它对中间代码进行优化，提高程序的执行效率。

第八章习题答案2、请将算术表达式翻-（a+b）*(c+d)+(a+b+c)翻译为：（1）四元式（2）三元式（3）间接三元式答：（2）三元式（3）间接三元式间接码表：三元式：4、修改图8.5中计算声明语句中的名字的类型及相对对峙的翻译方案，以允许在一个声明中可以同时声明多个变量名。

答：翻译方案如下：P->{ offset:= 0 } DD-> D;DD->LL->id,L1 {L.type = L1.type;L.width = L1.width;enter(id,name,L.type,offset;Offset:= offset +L.width}L->:T{ L.type = T.type;L.width = T.width;}T->integer { T.type = integer; T.width:= 4 }T->real { T.type= real; T.width:= 8 }T-> array[num] of T1 { T.type:= array(num.val, T1.type);T.width:= num.val X T1.width }T->^T1 {T.type:=pointer(T1.type); T.width : = 4 }7、利用8.11的翻译方案，将下面的赋值语句翻译成三地址代码：A[i，j] = B[i,j] + C[A[k,l]]+D[i+j]答：令:域宽为wA的维数为：da1,da2, 不变部分为na, B的维数为db1,db2, 不变部分nbC的维数为dc,不变部分ncD的维数为dd,不变部分nd,t1 := i*db1t1:= t1+jt2:= B-nbt3:=w*t1t4:=t2[t3]xb = t4;t1 := k*da1t1:= t1+lt2:= A-nat3:=w*t1t4:=t2[t3]xa = t4;t1:=xa;t2:=C-nc;t3:=w*t1t4:=t2[t3]xca:=t4t1:=i+j;t2:=D-nd;t3:=w*t1;t4:=t2[t3];xd=t4;t5:=xb+xca;t6:=t5+xd;t1 := i*da1t1:= t1+jt2:= A-nat3:=w*t1t2[t3]:=t6。

在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对各位有些帮助。

一1、画出编译程序的总体结构图，简述其部分的主要功能。

[答案]编译程序的总框图见下图。

图编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。

语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间优化器对中间代码进行优化处理。

一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码目标代码生成器把中间代码翻译成目标程序。

中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。

编译程序各个阶段所产生的中间结果都记录在表格出错处理程序对出现在源程序中的错误进行处理。

如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。

编译程2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?[答案]计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。

像Basic之类的语言，属于解释型的高级语言。

它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读总而言之，是边翻译边执行。

像C，Pascal之类的语言，属于编译型的高级语言。

它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素。

[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V+。

《编译原理》习题解答：第一次作业：P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。

P14 3、编译程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。

具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。

语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

P15 5、编译程序分遍由哪些因素决定？答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。

补充：1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。

对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。