编译原理作业答案最终版

第一章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。

第一章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。

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

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

编译原理作业与答案编译原理独⽴作业2010.5⼀、简答题1、构造⼀个⽂法使其⽣成的语⾔是不允许0打头的偶正整数集合。

2、⽂法][E G ：TT E T E E-+→，FF T F T T/*→，i E F )(→，构造句型i T T T*+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

3、某LL(1)⽂法的预测分析表如下，请在下述分析过程表中填⼊输⼊串（ a , a ）$ 的分析过程。

分析过程表：4、⽂法][S G ：RL S=→，R S →，R L *→，i L →，L R →，求增⼴⽂法中LR(1)项⽬集的初态项⽬集I 0。

5、⽂法][S G ：GG S S ;→，()G G t H →，)(S a H →，求出各⾮终结符的FISTVT 和LASTVT集合。

⼆、分析题：1、构造⾃动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的⾃动机确定化，并写出相应的正规⽂法。

2、⽂法][S G ：RT eT S →εDR T →εdR R → bd a D →，写出每个⾮终结符的FIRST 集和FOLLOW 集，并判断该⽂法是否为LL(1)⽂法。

3、若有⽂法][S G ：AB S →εaBa A →εb A b B → (1)试证明该⽂法是SLR(1) ⽂法，并构造SLR(1)分析表。

（2）给出输⼊串aa # 的分析过程。

参考答案⼀、简答题1、构造⼀个⽂法使其⽣成的语⾔是不允许0打头的偶正整数集合。

8|6|4|2|ABC Z → 9|8|7|6|5|4|3|2|1→A ε|0|B AB B →|8|6|4|2|0→C2、⽂法][E G ：TT E T E E-+→，FF T F T T/*→，i E F )(→，构造句型i T T T *+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

短语：T ，T-T ，i ，T*i ，T-T+T*i直接短语：T ， i 句柄： T素短语（P72）：T-T,i 最左素短语：T-T3 某LL(1)⽂法的预测分析表如下，请在下述分析过程表中填⼊输⼊串（ a , a ）$ 的分析过程。

第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 有两种最左推导，所以此文法是二义的。

编译原理(龙书)课后习题解答(详细)编译原理(龙书)课后题解答第一章1.1.1 ：翻译和编译的区别？答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。

1.1.2 ：简述编译器的工作过程？答：编译器的工作过程包括以下三个阶段：(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。

1.2.1 ：解释器和编译器的区别？答：解释器和编译器的主要区别在于执行方式。

编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。

1.2.2 ：Java语言采用的是解释执行还是编译执行？答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。

但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。

第二章2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式答：<加法表达式> ::= <加法表达式> "+" <乘法表达式> | <乘法表达式><乘法表达式> ::= <乘法表达式> "*" <单项式> | <单项式><单项式> ::= <数字> | "(" <加法表达式> ")"2.2.3 ：什么是自下而上分析？答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。

《编译原理》习题解答：第一次作业：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、将编译程序分成若干个“遍”是为了。

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所识别的语言是。

a. xyxb. (xyx)*c.x n yx n(n≥0) d. x*yx*2、文法G描述的语言L(G)是指。

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

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

a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。

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

编译原理作业参考答案作业一一、是非题1.(×)2.(×)3.(×)4.(×)5.(×)6.(√)7. (√)8.(√)9.(√) 10.(×) 11.(√) 12.(√) 13.(√)二、填空题1.（词法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成）2．（单词符号），（语法单位）。

3.（源程序），（单词符号）4.（语法），（语义）5. (词法分析)、(语法分析)、(语义分析)，(中间代码产生)，(代码优化)，(目标代码生成)6.(解释方式)7. (语法规则)8. (上下文无关文法)9. (自上而下分析法)，(自下而上分析法)10. (规范推导)11. (最左归约)三、名词解释题：1．词法分析器-----执行词法分析的程序。

2. 自编译方式------先对语言的核心部分构造一个小小的编译程序，再以它为工具构造一个能够编译更多语言成分的较大编译程序。

如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期待的整个编译程序。

3. 遍-----所谓“遍”就是对源程序或中间结果长头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

4. 编译程序-----一种翻译程序: 能够把某一种语言程序(称为源语言程序)转换成另一种语言(成为目标程序),而后着与前者在逻辑上是等价的。

5. 超前搜索-----所谓超前搜索是在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。

6. 短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。

7. 规范句型------由规范推导所得到的句型。

8. 句柄------一个句型的最左直接短语。

9. -规范推导-----最右推导又称为规范推导。

四、简答题：1. 正规式a ( a | b )*。

2.(a*b|b*a)={a,b,ab,ba,aab,bba……}3.状态转换图是一张有限方向图。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

第二章2.3叙述由下列正规式描述的语言(a) 0(0|1)*0在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串(b) ((ε|0)1*)*在字母表{0, 1}上,所有的01串,包括空串(c) (0|1)*0(0|1)(0|1)在字母表{0, 1}上,倒数第三位是0的01串(d) 0*10*10*10*在字母表{0, 1}上,含有3个1的01串(e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*在字母表{0, 1}上,含有偶数个0和偶数个1的01串2.4为下列语言写正规定义C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。

［解答］ other → a | b | … other指除了*以外C语言中的其它字符other1 → a | b | …other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */(f) 由偶数个0和偶数个1构成的所有0和1的串。

［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以，x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1）x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1）因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：由此可以写出其正规文法为：S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00(1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10(2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得：S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00|11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10)) => S0 = ((00|1 1)|(01|10) (00|11)* (01|10))+因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为： S0 → ((00|11)|(01|10) (00|11)* (01|10))* (g) 由偶数个0和奇数个1构成的所有0和1的串。

《编译原理》习题答案一.单项选择题(本大题共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）可以较好地反映句子的结构。

编译原理答案(总11页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--一、填空题1. 汇编程序将翻译成；编译程序将翻译成。

2. 编译程序工作工程可以划分为、、、和等5个基本阶段，同时还会伴有和。

3. 对编译程序而言，输入数据是，输出数据是。

4. 已知文法G[E]: E—>T|E+T|E-F, T－>F|T*F|T/F,,F—>(E)|I (“,”是间隔符号，不是文法中的符号)。

该文法的开始符号（识别字符）是，终结符号集合V T是，非终结符号结合V N是，句型T+T*F+i的短语有。

该文法消除直接左递归，改写后的文法为E－> ,T －> ,F－> .5. Chomsky定以来寺中形式语言的文法分别为：文法（又称文法）、文法（又称文法）、文法（又称文法）、文法（又称文法）。

6. 编译过程中扫描器所完成的任务是从中识别出一个个具有。

7. 确定的有穷自动机是一个，通常表示为。

8. LL(k)分析中，第一个L的含义是，第二个L的含义是，“k”的含义是。

9. LL(1)分析中，第一个L的含义是，第二个L的含义是，“1”的含义是。

(0)分析中，“L”的含义是，“R”的含义是，“0”的含义是。

(1)分析中，“L”的含义是，“R”的含义是，“1”的含义是。

(1)分析中，“L”的含义是，“R”的含义是，“1”的含义是。

13.算术表达式：a*(-b+c)的逆波兰式表示为：。

14.算术表达式：a＋b*(c+d/e)的逆波兰式表示为：。

15.在编译程序中安排中间代码生成的目的是和。

16.语法制导的翻译程序能同时进行分析和分析。

17.根据所涉及的程序范围，优化可分为、、三种。

二、简单题1. 有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗说明理由。

2. 多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序”，对吗为什么3. LR分析器与优先分析器在识别被归约串时的主要异同时什么三、给出生成下述语言的上下文无关的文法{1n0m1m0n|n,m>=0}{WaW r|W属于{0|1}*,W r表示W的逆}四、给出生成下列语言的三型文法：{a n|n>=0}{a n b m|n,m>0}{a n b m c k|n,m,k>=0}五、构造正规式1(0|1)*101相应的最小DFA。

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

作业参考答案第二章 高级语言及其语法描述6、（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98、（1）最左推导：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) (2)9、证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。