编译原理第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步或多步推导产⽣的⽂法符号序列是。

第八章 语法制导翻译和中间代码生成1．给出下面表达式的逆波兰表示(后缀式)： (1) a*(-b+c)(4) (A ∧B) ∨(⌝C ∨ D)(7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c解(1) ab-c+*(4) AB ∧C ⌝D ∨∨(7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算）2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

答案：三元式(1) (+ a, b) (2) (+ c, d)(3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b)(6) (+,(5),c) (7) (- (4), (6)) 间接三元式间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4)￥= :=*:=+ xyzs +cxa bs* c*a b(5) (- (4), (1)) (1)(6) (- (4), (5)) (5)(6)四元式(1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4)(5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7)3. 采用语法制导翻译思想，表达式E 的"值"的描述如下： 产生式 语义动作(0) S ′→E {print E.VAL}(1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL}如果采用LR 分析法，给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。

第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）文法。

《编译原理》习题解答：第一次作业：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、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。

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

第二章高级语言的语法描述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开头。