下载文档原格式
编译原理第六章到第十一章课后习题答案p116/1.已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算FIRSTVT -- LASTVT表(2) 构造算符优先关系表（OPERATER PRIORITY RELATION TABLE），说明是否为算符优先文法。
=: #=#, (=)<: (< FIRSTVT(T) , ,<firstvt(s)<="" ,="" p="">>:LASTVT(S)># , LASTVT(T)>), LASTVT(T)> ,表中无多重人口所以是算符优先（OPG）文法。
（3）计算G[S]的优先函数。
收敛（4）对输入串（a,a）#的算符优先分析过程为Success!3.有文法G（S）：s->Vv->T/ViTT->F/T+FF->)V*|((1)(+(i(的规范推导S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)F+Fi（的短语、句柄、素短语。
短语S: F+Fi（T1:F+F （素短语）T2:F （句柄）F:( （素短语）(3) G(S)是否为OPG？若是，给出（1）中句子的分析过程！S’->#S# S->V V->T/ViT T->F/T+F F->)V*|(算符优先关系表（OPERATER PRIORITY RELATION TABLE）对输入串(+(I(的算符优先分析过程为:p152/2文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→SI3若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：I5B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。
第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S=> ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T =>E+T*F ，所以E+T*F 是句型。
第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。
（2） 优先顺序为↑，+，*，同级优先采用右结合。
解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。
解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E 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 TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。
程序设计语言编译原理第三版答案【篇一：西北工业大学版(蒋立源第三版)编译原理课后习题答案】解：源程序是指以某种程序设计语言所编写的程序。
目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。
翻译程序是将某种语言翻译成另一种语言的程序的统称。
编译程序与解释程序均为翻译程序，但二者工作方法不同。
解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。
即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。
即先翻译、后执行。
2解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。
3解：c语言的关键字有：auto break case char constcontinue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。
上述关键字在c语言中均为保留字。
4解：c语言中括号有三种：{}，[]，（）。
其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。
c语言中无end关键字。
逗号在c语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。
5略第二章习题解答1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{anbn|n≥0}（2）{anbmcp|n,m,p≥0}（3）{an # bn|n≥0}∪{cn # dn|n≥0}解：对应文法为g(s) = ({s,x,y},{a,b,c,d,#}, {s→x,s→y,x→axb|#,y→cyd|# },s)（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}解：g(s) = ({s,w,r},{0,1,#}, {s→w#, w→0w0|1w1|# },s)（5）任何不是以0打头的所有奇整数所组成的集合（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为s→0a|1b|e，a→0s|1c b→0c|1s c→1a|0b3.描述语言特点（1）s→10s0s→aaa→baa→a解：本文法构成的语言集为：l(g)={(10)nabma0n|n, m≥0}。
第一章编译程序概述1.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。
对有些高级语言甚至配置了几个不同性能的编译程序。
1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。
从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。
一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。
事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。
我们将分别介绍各阶段的任务。
另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。
编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。
图1.1表示了编译的各个阶段。
图1.1 编译的各个阶段1.3 高级语言解释系统为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。
第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。
从功能上说，一个解释程序能让计算机执行高级语言。
它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。
第二章：高级语言及其语法描述问答第1题写一文法，使其语言是偶正整数的集合。
编译原理习题参考答案第⼆章2.构造产⽣下列语⾔的⽂法（2）{a n b m c p|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{a n # b n|n≥0}∪{cn # dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# }（5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应⽂法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B3.描述语⾔特点（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全为零}该语⾔特点是：产⽣的句⼦中，0、1 个数相同，并且若⼲相接的1 后必然紧接数量相同连续的0。
（5）S→aSS S→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5. (1) 解：由于此⽂法包含以下规则：AA→ε，所以此⽂法是0 型⽂法。
7.解：(1)aacb 是⽂法G[S]中的句⼦，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是⽂法G[S]中的句⼦aacbccb 不能从S推导得到时，它仅是⽂法G[S]的⼀个句型的⼀部分，⽽不是⼀个句⼦。
11.解：最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上⾯推导中，下划线部分为当前句型的句柄。
对应的语法树为：3 假设M:⼈ W:载狐狸过河，G:载⼭⽺过河，C:载⽩菜过河6 根据⽂法知其产⽣的语⾔是L={a m b n c i| m,n,i≧1}可以构造如下的⽂法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性⽂法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输⼊串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9．对于矩阵(iii)(1) 状态转换图：(2) 3型⽂法（正规⽂法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)⽤⾃然语⾔描述输⼊串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由⼀个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由⼀个a,b 所组成的任意串结尾。
编译原理习题答案习题11.1翻译程序：把用某种程序设计语言（源语言）编写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。
编译程序：一种翻译程序，将高级语言编写的源程序翻译成等价的机器语言或汇编语言的目标程序。
1.2词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成1.3词法分析：根据语言的词法规则对构成源程序的符号进行扫描和分解，识别出一个个的单词。
语法分析：根据语言的语法规则，把单词符号串分解成各类语法单位。
语义分析及中间代码生成：对语法分析识别出的语法单位分析其含义，并进行初步翻译。
代码优化：对中间代码进行加工变换，以产生更高效的目标代码。
目标代码生成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。
以上5个阶段依次执行。
习题22.1 （1）有穷非空的符号集合（2）利用产生是规则A->v将A替换为v时与A的上下文无关。
（3）略（4）推导是把句型中的非终结符用一个产生是规则的右部开替代的过程；直接推导是将非终结符的替代结果只用了一次产生式规则。
（5）略（6）一个句型的最左直接短语（7）如果一个文法存在某个句子对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个文法是二义的。
2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e}（2）abbcde,abbbcde是，acde不是。
2.3 （1）L[G]={d|n≥1,m≥0}（2）2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae（3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg =>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg（3）中题目有错应为C fCg|e2.5L[G]=｛aⁿbⁿcⁿ|aab,n≥2｝2.6 (1)Z→AB A→Aa|ε B→Bb|ε(2)Z→aZb|ab(3)Z→aAb A→aAb|b(4)Z→AB A→aAb|ab B→cB|ε(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb2.7 一位数：Z→2|4|6|8两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8三位以上：Z→ACB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 C→CDD→0|1|2|3|4|5|6|7|8|92.8证明：E=>E+T=>E+T*F短语：T*F E+T*F 直接短语：T*F 句柄：T*F2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T)E *F 直接短语：E*T , FT ↑ F 句柄：FF ( E )E * T2.10（1）语法树（2）直接短语：a , ZZ 句柄：Z( L )L , ZZ ( L )Za2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB=>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA=>(+)+a(*a(直接短语：（，+句柄：(2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeIS=>iS=>iiSeS=>iiIeS=>iiIeI(2) S=>SaS=>cSaS=>cfaS=>cfafS=>cS=>cSaS=>cfaS=>cfaf(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-iE=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i2.13 Z→aABZ|cCACdA→bAB|aZA|cCCB→bAB|CzbC→cZ|c习题33.1(1)确定的有限自动机(2)不确定的有限自动机(3)正规集是一类特殊的单词集合，正规式是正规集的描述工具 3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*003.3 证明：b *(a|b)+=｛a,b,ab,ba,aa,bb …｝ (a|b)+=｛a,b,ab,ba,aa,bb …｝ 3.4 (1)(2)DDDD3.5(1) (2)(3)3.6(1) (01|10) *(01|10)(2) (0(1|00)*)|003.7(1) Z →1AB (2)Z →ABA →(0|1)A A →0A|εA →0|1B →(0|1)B|ε B →0B B →ε3.8 r=a(a|b )*bb3.9 Z →1BB →0Z|0 Z →0Z|ε3.10 3.11DDD习题44.1 (1)若文法G[Z]满足①文法不含左递归②③(2)4.2(1) First(S)={a,d} First(B)={a,d,c,ε}First(A)={a,d,e,c} First(D)={a,d,ε}Follow(S)={#,a,b,d,e} Follow(B)={a,d}Follow(A)={b} Follow(D)={e,a,d,b}(2) 不是4.3 (1) 证明： First(Z)={a,b,c} Follow(S)={#,a,b,c,d}First(A)={a,b,c,d} Follow(A)={ #,a,b,c,d }First(B)={a,d,c} Follow(B)={ a,b,c,d } 是LL(1)文法。
(2)(3)略4.4 (1) Z→NZ1 Z1→[E]|εE→ZE1 E1 →*E|ε N→i(2) First(Z)={i} Follow(Z)={#,*,]}First(Z1)={[,ε } Follow(Z1)={ #,*,]}First(E)={i} Follow(E)={ ] }First(E1 )={*,ε} Follow(E1 )={ ] }First(N)={i} Follow(N)={#,[,* ] }(3)4.5 (1) First(A)={a,ε} Follow(A)={ #,a }不是LL(1)文法(2) void A(){If(sym==’a’){ getsymbol();A();If(sym==’a’) getsymbol();Else error();}}4.6 A→[BB→X]B’B’→AB’|εX→aX’|bX’X’→ aX’|bX’|εvoid A() { if(sym==’[’) { getsymbol(); B();}}void B() { X(); if(sym==’]’) { getsymbol(); B’();}} void B’(){ if(sym==’[’) { A(); getsymbol(); B’();}} void X(){if(sym==’a’) { getsymbol(); X’();}else if(sym==’b’) { getsymbol(); X’();}else error();}4.7(1) Z→(L)|aZ|bL→ZL’L’→,ZL’|εB→dB’B’→bB’|ε(2) First(Z)={(,a,b} Follow(Z)={,,),#}First(L)={ (,a,b } Follow(L)={),}First(L’)={,,ε} Follow(L’)={ )}First(B)={d} Follow(B)={# }First(B’)={b,ε} Follow(B’)={# } (3)4.8(1) Z→aPZ’|*aPZ’Z’→*aPZ’|εP→+aP’P’→P|ε(2) First(Z)={a,*} Follow(Z)={ #}First(Z’)={ *,ε } Follow(Z’)={# }First(P)={+} Follow(P)={ #,*}First(P’)={+,ε} Follow(P’)={#,* }(3)习题55.1 分析：先求出FirstVT,LastVT集S TFirstVT a b ( , a b (LastVT a b ) , a b )(1)算符优先关系表如下：a b ( ) ,ab(),(2)因为关系表中无多重定义项，顾是算符优先文法(3)一种优先函数如下a b ( ) ,f 2 2 0 2 2g 4 4 4 0 05.2(1)FirstVT,LastVT集如下S TFirstVT a c d a c d ,LastVT b c d b c d ,(2)算符优先关系表a b c D ,ab c d,(3)是算符优先文法 (4)优先函数a b c d , f 0 3 3 3 2 g4331(5)题目有误 5.3(1)文法要拓广① S ’→S ② S →A S ③ S →b ④ A →SA ⑤ A →aa A S bb AabAI6:A →SA. ④S →A.S S →.AS S →.b A →. SAA →.aSI6:S →A S. ② A →S.A A →.SA A →.a S →.A S S →.bA SbbI3: S →b. ③aI0: S ’→.S S →.A S S →.b A →.SA A →.aI1: S ’→S. accA →S.A A →. SA A →.a S →.AS S →.bSS I5: A →S.AA →. SA A →.a S →.AS S →.bI2:A →a. ⑤I4:S →A.SS →.A S S →.b A →.SA A →.aASaAb(3)不是LR(0)文法。
5.4(1)文法要拓广① S ’→S ② S →A S ③ S →b ④ A →AA ⑤ A →a ⑥ A →ε先求Follow(S)={#} Follow(A)={a,b}(3)不是SLR(1)文法。
(4)LR(1)项目集族(5) LR(1)分析表(6)不是LR(1)文法。
5.5(1)拓广文法① S→A② A→aAd③ A→aAb④ A→ε是SLR(1)文法，其SLR(1)表如下：#ab#分析过程： ═5.6LR(0)项目集族：从上述项目集族中，状态集I9是归约-归约冲突。
