编译原理56章作业答案

第二章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）*还可以：然后再确定化，最小化，结果应该一样。

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

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

编译原理第三版课后答案王生原编译原理第三版课后答案王生原【篇一：编译原理课后答案(第三版蒋立源康慕宁编)】class=txt>第一章习题解答1解：源程序是指以某种程序设计语言所编写的程序。

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

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

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

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

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

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

即先翻译、后执行。

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

3解：c语言的关键字有：auto break case char constcontinue default do double else enum extern float for goto if int long register return shortsigned sizeof static struct switch typedef union unsigned void volatile while。

上述关键字在c语言中均为保留字。

4解：c语言中括号有三种：{}，[]，（）。

其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

c语言中无end关键字。

逗号在c语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。

编译原理课后习题答案编译原理习题答案习题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)*00 3.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)⽂法。

编译原理_国防科技大学中国大学mooc课后章节答案期末考试题库2023年1.对于文法G(S')，该文法识别活前缀的DFA如下图，状态I5包含的项目有G(S')：(0) S' → S(1) S → iSeS(2) S → iS(3) S → a【图片】答案:S → iSeŸS_S → ŸiSeS_S → ŸiS_S → Ÿa2.(a+b)/(c-d)对应的逆波兰式(后缀式)是答案:ab+cd-/3.表达式(a+b)/c-(a+b)*d对应的间接三元式表示如下，其中三元式表中第(3)号三元式应为间接码表三元式表(1) OP ARG1 ARG2 (2) (1) + a b (1) (2) / (1)c (3) (3) (4) (4) - (2) (3)答案:( *, (1), d)4.设AS 为文法的综合属性集, AI 为继承属性集, 则对于下面的属性文法G(P)定义中，AS和AI正确描述是产生式语义规则P → xQR Q.b:=R.d R.c:=1R.e:=Q.a Q → u Q.a:=3 R → v R.d:=R.c R.f:=R.e答案:AS={ Q.a, R.d, R.f } AI={ Q.b, R.c, R.e }5.考虑下面的属性文法G（S）【图片】过程enter(name, type)用来把名字name填入到符号表中，并给出此名字的类型type。

按照该属性文法，关于语句【图片】 , 【图片】 , 【图片】:integr的语义描述准确的是答案:说明 , , 是integer变量，把 , , 三个名字填入符号表中，并在类型栏中填上integer6.考虑下面的属性文法G(S)【图片】对于输入字符串abc进行自下而上的语法分析和属性计算，设S.u的初始值为5，属性计算完成后，S.v的值为答案:187.关于属性文法，下列说法中正确的是答案:属性文法是对上下文无关文法的扩展。

第一章1．解答：程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。

一般可以划分为低级语言和高级语言两大类。

低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。

高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如FORTRAN、Pascal、C等等我们熟悉的语言是高级语言。

语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。

它一般可分为解释程序和翻译程序两大类。

翻译程序：翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另一种语言书写的程序（称为目标程序）。

若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。

若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。

解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。

2．解答：编译程序的总框图见图1.2。

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

语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。

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

一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。

编译原理习题参考答案第⼆章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 所组成的任意串结尾。

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

《编译原理》习题答案一.单项选择题(本大题共164小题，每小题2分)1>如果一个编译程序能产生不同于其宿主机的机器代码，则称它为(2、( C )不是编译程序的组成部分。

3、现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个(C )把各个目标模块，包括系统提供的库模块连接在一起，确定程序变暈或常数在主存屮的位置，装入内存屮制定 的起始地址，使之成为一个可运行的绝对指令代码的程序。

A 、重定位程序B 、解释程序C 、连接装配程序D 、诊断程序; 6、 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A 、编译器B 、汇编器C 、解释器D 、预处理器7、 用高级语言编写的程序经编译后产生的程序叫(B)A 、源程序B 、目标程序C 、连接程序D 、解释程序8、 文法 G ： S->b| A(T)T-T,S|S 则 FTRSTVT(T) (C)。

A 、{b, A, (}B 、{b, A,)}C 、{b, A, (, , }D 、{b, A,),, }9、 通常一个编译程序屮，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 等六个部分，还应包括(0。

B 、解释器C 、表格处理和出错处理D 、符号执行器C )oA 、诊断编译程序 B.优化编译程序C 、交叉编译程序 ［人 可变目标编译程序A 、词法分析程序B 、代码生成程序C 、设备管理程序D 、 语法分析程序4、 产生正则语言的文法为(D)。

A 、0型B 、1型 5、 (A)是一种典型的解释型语言。

卜、BASIC B 、 CC 、2型 C 、 FORTRAND 、3型[)、PASCALA.模拟执行器10、编译程序绝大多数时间花在(D)上。

A、出错处理B、词法分析C、日标代码生成D、表格管理11、设文法为：S-SAlAA-^a b则对句子aba,下面（D）是规范推导。

A、S=>SA=>SAA=>AAA=>aAA=>abA=>abaB、S^>SA=>SAA^>AAA=>AAa=>Aba=>abaC、S=>SA=>SAA=>SAa=>Sba=>Abaz=>abaD、S=>SA=>Sa=>SAa=>Sba=>Aba=>aba12、Chomsky把文法分成四种类型，其中，（D ）也称正规文法A、0型B、1型C、2型D、3型13、源程序是句子的集合，（B）可以较好地反映句子的结构。

（完整版）编译原理课后习题答案第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。

2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。

3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。

4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。

2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。

答：Z→SME | BS→1|2|3|4|5|6|7|8|9M→ε | D | MDD→0|SB→2|4|6|8E→0|B3. 设文法G为：N→ D|NDD→ 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。

答：N?ND?N3?ND3?N23?D23?123N?ND?NDD?DDD?1DD?12D?123N?ND?N1?ND1?N01?D01?301N?ND?NDD?DDD?3DD?30D?301N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?7 5431N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754 DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S?iSeS?iiSesS?iS?iiSeS所以该文法是二义性文法。

编译原理_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年1.左线性文法画状态转换图时，文法的开始符号对应的终止状态答案:正确2.e1= (a|b)*，e2=(a*b*)* e1和e2等价答案:正确3.一张状态转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态。

答案:错误4.简单优先分析法是一种规范归约分析法答案:正确5.S∷＝aAa | aBb| bAb| bBa A∷＝x B∷＝x 该文法不是LALR(1)文法答案:正确6.LL(1)文法无左递归、无二义性。

答案:正确7.文法：E∷＝EE+ | EE* | aFOLLOW(E)={+,*,#}答案:错误8.LR分析栈中存放的状态是识别文法规范句型（）的DFA的状态。

答案:活前缀9.已知文法A∷＝BCc | gDBB∷＝ε| bCDEC∷＝DaB | caD∷＝ε| dD E∷＝gAf |cFOLLOW(B)={}答案:{ a，c，d，g，f，#}10.表达式(a+b)/(a-b)-(b*c)的四元式序列为：⑴.(+,a,b,T1)⑵.(-,a,b,T2)⑶.(/,T1,T2,T3)⑷.(*,b,c,T4)⑸.(-,T3,T4,T5)答案:正确11.编译程序与具体的机器有关。

答案:正确12.由文法的开始符经0步或多步推导产生文法符号序列是句子。

答案:错误13.如果在进行归约时，文法的某些规范句型的句柄不唯一，则称该文法是二义性文法。

答案:正确14.规范归约又称为最右归约。

答案:错误15.假设有一文法，如果文法G中没有形如A::=....BC....这样的规则，其中A、B和C都为非终结符号，则称该文法为（）答案:算符文法16.递归下降分析法属于（）分析方法答案:自顶向下17.由正规文法构造状态转换图，其右线性文法识别符号对应是状态转换图的初始状态。

答案:正确18.算符优先分析法是一种一种规范归约分析法答案:错误19.确定的有穷自动机只有唯一的终止状态答案:错误20.正规表达式(a|b)*和(a*b*)*不等价答案:错误21.含有优化部分的编译程序的执行效率高答案:错误22.FORTRAN语言是一种系统程序设计语言，可用来编写编译程序。

第一章1、将编译程序分成若干个“遍”是为了。

a．提高程序的执行效率b．使程序的结构更加清晰c．利用有限的机器内存并提高机器的执行效率d．利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握。

a．源程序b．目标语言c．编译方法d．以上三项都是3、变量应当。

a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在上。

a．出错处理b．词法分析c．目标代码生成d．管理表格5、不可能是目标代码。

a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用可以定义一个程序的意义。

a．语义规则b．语法规则c．产生规则d．词法规则7、词法分析器的输入是。

a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循的是-。

a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对。

a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译10、语法分析应遵循。

a．语义规则b．语法规则c．构词规则d．等价变换规则二、多项选择题1、编译程序各阶段的工作都涉及到。

a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序工作时，通常有阶段。

a．词法分析b．语法分析c．中间代码生成d．语义检查e．目标代码生成三、填空题1、解释程序和编译程序的区别在于。

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

3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。

4、编译程序是指将程序翻译成程序的程序。

单选解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。

2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。

3、对编译而言，变量既持有左值又持有右值，故选c。

4、编译程序打交道最多的就是各种表格，因此选d。

5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。