资源描述：
《编译原理作业题整理.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章习题一1．解释名词：源语言、目标语言、翻译器、编译器和解释器。答：源语言：被翻译器翻译的语言，用于书写源程序的语言。目标语言：被翻译器翻译之后得到的语言，用于书写目标程序的语言。翻译器：能够完成从一种语言到另一种语言的变换的软件。编译器：一种特殊的翻译器，要求目标语言比源语言低级。解释器：解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。第二章词法分析作业：假设∑={0,1}，求1.写出包含010的所有串的正规式2.写出不包含010的所有串的正规式答：1.（0
2、1）*（010）（0
3、1）*2.（10*1）*
4、（（11
5、00
6、）*
7、0111*0）*.2.（0
8、1）*010（0
9、1）*解：（1）RE的分解树如下：r17r16r11*r15r14()
10、r12r1301r100r9r81r7r60r5*r4r3()
11、r1r201（2）由分解树及基本的Thompson构造算法逐步构造等价的NFA过程如下：230Startr1：451Startr2：1243501r3、r4:6Start012435016r5:7Start7’80Startr6：01243501670r7:8Start8’91Startr8：0124350167801r9:9Start9’100Startr10：0124350167801r11:9100St
12、art12130r12：Start14151r13：Start1112141315Start0116r14、r15：10’Start1112141315011617r16：Start012435016780911001112141315011617r17:（3）由子集法构造等价的DFA过程如下：01ABCBBDCBCDECEFGFFGGHIHFGIFI其中含有r.初态的是A作为新的DFA的初态，含有原r17终态的是E、F、G和H作为新的DFA的终态。做出对应DFA的状态转换图如下：StartA0HBC101D010E1F0G101011I010（4）直接由分割算法处理该DFA，如得到的DFAm
13、in与原DFA一致说明原DFA本身就是最简的：由于导致｛A，B，C｝和D落入的状态集是不等价的，说明｛A，B，C｝和D是不等价的，故｛A，B，C，D｝应该分裂为｛A，B，C｝和｛D｝，故：由于落入不同的状态集（相对来说是两个不等价的状态集），说明｛A，C｝和B是不等价的，故｛A，B，C，D｝应该分裂为｛A，C｝和｛B｝，故：由于落入同一个状态集，故｛E，F，G，H，I｝暂不分裂。由于落入同一个状态集｝，故｛E，F，G，H，I｝暂不分裂。故最终划分为：说明A和C是等价的，E、F、G、H和I是等价的。合并等价状态（A和C中保留A，E、F、G、H和I中保留E）并处理对应弧线得最小化DFA如下：A0B
14、01D10E110001012103110010101022303331.010011232403124340110200403101013.1考虑文法S®(L)
15、aL®L,S
16、S(a)建立句子（a,(a,a)）和(a,((a,a),(a,a)))的分析树。(b)为（a）的两个句子构造最左推导。(c)为（a）的两个句子构造最右推导。(d)这个文法产生的语言是什么。（a,(a,a)）的分析树S（L）L，SS（L）aL,SSaa(a,((a,a),(a,a)))的分析树S（L）L，Sa(L)L,Sa(L)L,Sa(L)L,SSaa（a,(a,a)）的最左推导S＝＞lm(L)＝＞lm(L,S)＝＞l
17、m(S,S)＝＞lm（a,S）＝＞lm(a,(L))＝＞lm(a,(L,S))＝＞lm(a,(S,S))＝＞lm(a,(a,S))＝＞lm(a,(a,a))(a,((a,a),(a,a)))的最左推导S＝＞lm（L）＝＞lm(L,S)＝＞lm(S,S)＝＞lm(a,S)＝＞lm(a,(L))＝＞lm(a,(L,S))＝＞lm(a,(S,S))＝＞lm(a,((L),S))＝＞lm(a,((L,S),S))＝＞lm(a,((S,S),S))＝＞lm(a,((a,S),S))＝＞lm(a,((a,a),S))＝＞lm(a,((a,a),(L)))＝＞lm(a,((a,a),(L)))＝＞lm(a,
18、((a,a),(L,S)))＝＞lm(a,((a,a),(S,S)))＝＞lm(a,((a,a),(a,S)))＝＞lm(a,((a,a),(a,a)))（a,(a,a)）的最右推导S＝＞rm(L)＝＞rm(L,(L))＝＞rm(L,(L,S))＝＞rm(L,(L,a))＝＞rm(L,(S,a))＝＞rm(L,(a,a))＝＞rm(S,(a,a))＝＞rm(a,(a,a))(a,((a,a),(a
