(完整版)编译原理及实现课后习题答案

第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。

a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。

a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d图2-1 习题的DFA M2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

第7 题证明下述文法G[〈表达式〉]是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a 构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉a=>〈表达式〉* a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a最右推导2 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a第8 题文法G[S]为：S→Ac|aB A→ab B→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。

所以，该文法是二义的。

或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。

第9 题考虑下面上下文无关文法：S→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

第10 题文法S→S(S)S|ε(1) 生成的语言是什么？(2) 该文法是二义的吗？说明理由。

答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11 题令文法G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→(E)|i证明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 有两种最左推导，所以此文法是二义的。

5.1 考虑以下的文法：S→S;T|TT→a（1）为这个文法构造LR(0)的项目集规范族。

（2）这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。

（3）对输入串“a;a”进行分析。

解：（1）拓广文法G[S’]：0：S’→S1：S→S;T2：S→T3：T→a构造LR(0)项目集规范族（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。

LR(0)分析表如下：（3）对输入串“a;a”进行分析如下：5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。

S→AA→Ab|bBaB→aAc|a|aAb解：文法G[S]：0：S→A1：A→Ab2：A→bBa3：B→aAc4：B→a5：B→aAb状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。

状态5：FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ状态9：FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。

5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。

S→AaAb|BbBaA→εB→ε解：拓广文法G[S’]：0：S’→S1：S→AaAb2：S→BbBa3：A→ε4：B→ε＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。

构造LR(1)项目集规范族：分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。

5.4 考虑以下的文法：E→EE＋E→EE*E→a（1）为这个文法构造LR(1)项目集规范族。

（2）构造LR(1)分析表。

（3）为这个文法构造LALR(1)项目集规范族。

（4）构造LALR(1)分析表。

（5）对输入符号串“aa*a+”进行LR(1)和LALR(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、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。

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

附录部分习题参考答案第1章习题1. 解释下列术语。

翻译程序，编译程序，解释程序，源程序，目标程序，遍，前端，后端解答：略！2. 高级语言程序有哪两种执行方式?阐述其主要异同点。

描述编译方式执行程序的过程。

解答：略！3. 在你所使用的C语言编译器中，观察程序1.1经过预处理、编译、汇编、链接四个过程生成的中间结果。

解答：略！4. 编译程序有哪些主要构成成分？各自的主要功能是什么？解答：略！5. 编译程序的构造需要掌握哪些原理和技术？编译程序构造工具的作用是什么？解答：略！6. 复习C语言，其字母表中有哪些符号？有哪些关键字、运算符和界符？标识符、整数和实数的构成规则是怎样的？各种语句和表达式的结构是什么样的？解答：略！7.编译技术可应用在哪些领域？解答：略！8. 你能解释在Java编译器中，输入某个符号后会提示一些单词、某些单词会变为不同的颜色是如何实现的吗？你能解释在Code Blocks中在输入{后，会自动添加}，输入do 会自动添加while()是为什么吗？解答：略！第2章习题1. 判断题，对下面的陈述，正确的在陈述后的括号内画√，否则画×。

(1) 有穷自动机识别的语言是正规语言。

（）(2) 若r1和r2是Σ上的正则表达式，则r1|r2也是。

（）(3) 设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。

（）(4) 令Σ＝{a,b}，则所有以b开头的字构成的正规集的正则表达式为b*(a|b)*。

（）(5) 对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。

（）1解答：略！2.从供选择的答案中，选出应填入下面叙述中？内的最确切的解答。

有穷自动机可用五元组（Q，V T，δ，q0，Q f）来描述，设有一有穷自动机M定义如下：V T={0,1}，Q={q0,q1,q2}，Q f={q2}，δ的定义为：δ (q0，0)=q1δ (q1，0)=q2δ (q2，1)=q2δ (q2，0)=q2M是一个 A 有穷状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。

第2章参考答案：1，2，3：解答：略！4. 解答：A：① B：③ C：① D：②5. 解答：用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：E → T | E+TT → F | T*FF → (E) | i最左推导：E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T=>i+i+F=>i+i+iE=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i 最右推导：E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i=>F+i+i=>i+i+iE=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i =>i+i*ii+i+i和i+i*i的语法树如下图所示。

i+i+i、i+i*i的语法树6. 解答：(1) 终结符号为：{or,and,not,(,),true,false}非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(2) 句子not(true or false)的语法树为：7. 解答：(1) 把a n b n c i分成a n b n和c i两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S → ABA → aAb|abB → cB|ε(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S → aE|Ea|bSS|SbS|SSbE → aEbE|bEaE|ε(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。

编译原理教程课后习题答案【篇一：编译原理教程课后习题答案——第一章】完成下列选择题：(1) 构造编译程序应掌握a. 源程序b. 目标语言c. 编译方法d. 以上三项都是(2) 编译程序绝大多数时间花在上。

a. 出错处理b. 词法分析c. 目标代码生成d. 表格管理(3) 编译程序是对。

a. 汇编程序的翻译b. 高级语言程序的解释执行c. 机器语言的执行d. 高级语言的翻译【解答】(1) d (2) d(3) d1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

编译原理及实现课后习题解答2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*.x0=(aaa)0=ε| x0|=0xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}A* = A0 ∪A1 ∪ A2∪ …. ∪ A n∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。

S => SS* => Sa* => SS+a* => Sa+a* => aa+a*2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5 已知文法G[S]：S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {a n|n>=0}B∷=bBc︱bc描述的语言：{b n c n|n>=1}L(G[S])={a n b m c m|n>=0,m>=1}2.6 已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。

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

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

编译原理教程课后习题答案【篇一：编译原理教程课后习题答案——第一章】完成下列选择题：(1) 构造编译程序应掌握a. 源程序b. 目标语言c. 编译方法d. 以上三项都是(2) 编译程序绝大多数时间花在上。

a. 出错处理b. 词法分析c. 目标代码生成d. 表格管理(3) 编译程序是对。

a. 汇编程序的翻译b. 高级语言程序的解释执行c. 机器语言的执行d. 高级语言的翻译【解答】(1) d (2) d(3) d1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

（完整版）编译原理课后习题答案第一章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所以该文法是二义性文法。

编译原理习题及答案(整理后)第一章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→某S某|y所识别的语言是a.某y某b.(某y某)某c.某ny某n(n≥0)d.某某y某某2、文法G描述的语言L(G)是指α,α∈VT某}a.L(G)={α|S+某α,α∈V某}b.L(G)={α|ST某α,α∈(V∪V某)}d.L(G)={α|S+α,α∈(V∪V某)}c.L(G)={α|STNTN3、有限状态自动机能识别a.上下文无关文法c.正规文法b.上下文有关文法d.短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立a.若f(a)>g(b)，则a>bc.a~b都不一定成立b.若f(a)5、如果文法G是无二义的，则它的任何句子αa.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是a.短语b.句柄c.句型d.句子7、文法G：E→E+T|TT→T某P|PP→(E)|I则句型P+T+i的句柄和最左素短语为a.P+T和ib.P和P+Tc.i和P+T+id.P和T8、设文法为：S→SA|AA→a|b则对句子aba，下面是规范推导。