编译原理作业题整理

资源描述

《编译原理作业题整理》由会员分享，可在线阅读，更多相关《编译原理作业题整理（19页珍藏版）》请在金锄头文库上搜索。

1、第一章习题一1解释名词：源语言、目标语言、翻译器、编译器和解释器。答：源语言：被翻译器翻译的语言，用于书写源程序的语言。目标语言：被翻译器翻译之后得到的语言，用于书写目标程序的语言。翻译器：能够完成从一种语言到另一种语言的变换的软件。编译器：一种特殊的翻译器，要求目标语言比源语言低级。解释器：解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。第二章词法分析作业：假设=0,1，求1. 写出包含 010 的所有串的正规式2. 写出不包含 010 的所有串的正规式答： 1. （0|1） *（ 010）（0|1 ） *2.（10 *

2、1） *|（ 11|00） *|0111*0） * .2.（0|1 ） *010（0|1） *解：（1）RE 的分解树如下：r17r16r11*r15r14( )|r12 r130 1r100r9r81r7r60r5*r4r3( )|r1 r20 1（2）由分解树及基本的 Thompson 构造算法逐步构造等价的 NFA 过程如下：2 30Startr1：4 51Startr2：1243501r3、r4:6Start0 12435016r5: 7Start7 80Startr6：0 124350167 0r7: 8Start8 91Startr8：0 124350167 80 1r9: 9St

3、art9 100Startr10：0 124350167 80 1r11: 9 100Start12 130r12： Start14 151r13： Start1112141315Start0116r14、r15：10Start 1112141315011617r16：0 124350167 80 91 100 1112141315011617r17:（3）由子集法构造等价的 DFA 过程如下：0 1A B CB B DC B CD E CE F GF F GG H IH F GI F IAclosure7,4210)(_ BA8,6380StartCclosureA7,6542,1)(_1

4、BB8380 Dclsre9,)9,(1ouC_0Cclsre)5(1 EBclosureclosureD 17,42,0876,43217,41,0)1(_)8,3(_10,830 closure)5(_1 FclosureclosureE 17,643,218,7643,217,643,21)3(_)8,3(_13,80 GDllclosure ,5,9,5,5,)5()9,5()5,9(_1FlF)13,8(0 Gcosure 17,654,219,7654,295_1 HE closureEclosureclosurelG ,3,0,8,317,643,2 )13(_)3(_)(_)0

5、(0 IClCclosure 7,654,27,6516514255_1FlH),8(0 Gcsre191louI)3,(_0I51其中含有 r.初态的是 A 作为新的 DFA 的初态，含有原 r17 终态的是 E、F、G 和 H 作为新的 DFA 的终态。做出对应 DFA 的状态转换图如下：A0 HBC101D010E1F0G101011I010（4）直接由分割算法处理该 DFA，如得到的 DFAmin 与原 DFA 一致说明原 DFA 本身就是最简的：0 ,IHGFEDCBA由于导致A，B，C和 D 落入的状EDfCfff )0,(),()0,(),(态集是不等价的，说明A， B，C和

6、D 是不等价的，故A，B，C，D应该分裂为A，B，C 和 D ，故：1 ,IHGFE由于落入不同的状态集（相对来说是两个不等fff )1()(),( 1价的状态集），说明A，C和 B 是不等价的，故A，B，C ，D 应该分裂为A，C和B ，故：2 ,IHGFED由于落入同一个状态集，FIffffEf )0,(),()0,(),()0,(故E，F，G， H，I暂不分裂。由于落入同一个状态集，故IfGffFff )1,(),()1,(),()1,(E，F ，G，H，I暂不分裂。故最终划分为：f IGEDBCA,说明 A 和 C 是等价的，E、F、G、H 和 I 是等价的。合并等价状态（

7、A 和 C 中保留A，E、F、G 、H 和 I 中保留 E）并处理对应弧线得最小化 DFA 如下：StartA 0 B01D10E1100 0 10121031100 10 1 01 0 22 3 03 3 31.0 10 0 11 2 32 4 03 1 24 3 40 1 1 0 200 40310 1013.1 考虑文法S ( L ) | aL L , S | S(a)建立句子（a,(a,a)）和(a,(a,a),(a,a)的分析树。(b)为（ a）的两个句子构造最左推导。(c)为（ a）的两个句子构造最右推导。(d)这个文法产生的语言是什么。（a,(a,a)）的分析树S（ L ）L ，

8、 SS （ L ）a L , SS aa(a,(a,a),(a,a)的分析树 S（ L ）L ， Sa ( L )L , Sa ( L )L , Sa ( L )L , SS aa（a,(a,a)）的最左推导Slm (L) lm (L,S) lm (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)的最左推导Slm （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,

9、(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,(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)）的最右推导Srm (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,a)的最右推导Srm (L) rm (L,S) rm (L,

10、(L) rm (L,(L,S)rm (L,(L,(L) rm (L,(L,(L,S) rm (L,(L,(L,a) rm (L,(L,(S,a) rm (L,(L,(a,a) rm (L,(S,(a,a) rm (L,(L),(a,a) rm (L,(L,S),(a,a) rm (L,(L,a),(a,a) rm (L,(S,a),(a,a) rm (L,(a,a),(a,a) rm (S,(a,a),(a,a)rm (a,(a,a),(a,a)（d）该文法产生的语言是括号匹配的串，串中的各项用“， ”隔开，项可以是括号匹配的子串或 a3.2 考虑文法SaSbS|bSaS|（a）为句子 ab

11、ab 构造两个不同的最左推导，以此说明文法是二义的。（b）为 abab 构造对应的最右推导。（c）为 abab 构造对应的分析树（a）1.Slm aSbS lm abSaSbS lm abaSbSlm ababSlm abab2.S lm aSbSlm abSlm abaSbSlm ababSlm abab(b)Srm aSbS rm aSbrm abSaSbrm abSabrm abab(C)分析树（1）Sa S b S a S b S 分析树（2）Sa S b Sa S b S (d)该文法产生的语言是 a、b 个数相等的 ab 串含空串习题 33.3 下面的二义文法描述命题演算公式，

13、(id R)=idFirst(L)=idFirst(,id R)=,First()= First(R)= , , Int Real Id , #D D-TL D-TLT T-int T-realL L-id RR R-,id R R-3.11 下面的文法是否为 LL（1）文法？说明理由。（两种方法）S-A B | P Q x A-x y B-b cP-d P | Q-a Q |答：方法一：First(AB)=x First(PQx)=d,a,x因为：First(AB)First(PQx)=x所以此文法不是 LL(1)文法。方法二：First(AB)=x Follow(S)=#First(PQx)=d,a,x Follow(A)=bFirst(x y)=x Follow(B)=#First(b c)=b Follow(P)=a,xFirst(d P)=d Follow(Q)=xFirst()=First(a Q)=aFirst(S)=d,a,xFirst(A)=xFirst(B)=bFirst(P)= d,First(Q)= a,x d a b #S S-ABS-PQx S-PQx S-PQxA A-x yB B-b cP P- P-d P P-Q Q- Q-a Q该文法有分析表有多个入口，不是 LL（1）文法。3.19 证明下面的文法不是 LL（1）文法SS

展开阅读全文