《最新编译原理作业题整理.docx》由会员分享，可在线阅读，更多相关《最新编译原理作业题整理.docx（21页珍藏版）》请在三一文库上搜索。
1、精品文档第一章习题一1解释名词：源语言、目标语言、翻译器、编译器和解释器。答： 源语言 ：被翻译器翻译的语言，用于书写源程序的语言。目标语言 ：被翻译器翻译之后得到的语言，用于书写目标程序的语言。翻译器：能够完成从一种语言到另一种语言的变换的软件。编译器：一种特殊的翻译器，要求目标语言比源语言低级。解释器：解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。第二章词法分析 作业：假设!>0,1,求1. 写出包含010 的所有串的正规式2. 写出不包含010 的所有串的正规式答： 1. （ 0|1） *（ 010） （ 0|1
2、）2.（ 10*1） *|（ （ 11|00） *|0111*0）2.（ 0|1） *010（ 0|1） *解： （ 1 ） RE 的分解树如下：精品文档精品文档精品文档r17NFA过程如下:(2)由分解树及基本的 Thompson构造算法逐步构造等价的r3、ri:r2:r4:r5:r6:r7:r8:r9:0r10:1r11:r12：r13:r14、r16 :(3)由子集法构造等价的 DFA过程如下:01ABCBBDCBCDECEFGFFGGHIHFGIFI_closure(0) 01,2,4,7 AA_closure(3,8)1,2,3,4,6,7,8BA_closure(5)1,2,4,5
3、,6,7CB0_closure( 3,8)1,2,3,4,6,7,8BBi_closure(5,9)1,2,4,5,6,7,9DC0_closure(3,8) BC1_closure(5) CD0 _closure( 3,8,10)_closure(3,8)_ closure (10)B 10,11,12,14,17 1,2,3,4,6,7,8,10D1_closure( 5) CE0 _closure( 3,8,13)_closure(3,8)_ closure (13)B 11,12,13,14,16,17 1,2,3,4,6,7,8E1 _closure( 5,9,15)_ closur
4、e (5,9)_closure(15)D 11,12,14,15,16,171,2,4,5,6,7,<F0_closure(3,8,13)FFi_closure(5,9,15)1,2,4,5,6,7,9,11,12,14,15,16,17GG0_closure(3,8,10,13)_closure(3,8,10)_closure(13) E _closure(13)E 11,12,13,14,16,17 1,2,3,4,6,7,8,10,11,12,13,14,16,17HG1_closure( 5,15) C _ closure(15) C 11,12,14,15,16,17 1,2,
5、4,5,6,7,11,12,14,15,16,17 IH0_closure(3,8,13)FH1_closure( 5,9,15)GI0_closure(3,8,13) FI1_closure(5,15)I其中含有r.初态的是A作为新的DFA的初态，含有原r17终态的是DFA的终态。做出对应 DFA的状态转换图如下：E、F、和H作为新的DFA ,如得至ij的 DFAmin(4)直接由分割算法处理该 最简的：与原DFA 一致说明原DFA本身就是0 A,B,C,D,E,F,G,H,I由于 f (A,0) B, f(B,0) B, f(C,0)B, f(D,0)E导致 A, B, C和D落入的状态集
6、是不等价的，说明 A, B, C和DB, C和 D,故：是不等价的，故 A, B, C, D应该分裂为 A,1 A,B,C,D,E,F,G,H,I由于 f(A,1) C,f(B,1) D, f(C,1)C落入不同的状态集(相对来说是两个不等价的状态集)，说明 A, C和B是不等价白1故 A, B, C, D应该分裂为 A, C和 B,故：2 A,C,B,D,E,F,G,H,I由于 f(E,0) F,f(F,0) F,f(G,0) H,f(H,0) F,f(I,0) F 落入同一个状态集，故 E, F, G, H, I暂不分裂。由于 f(E,1) G,f(F,1) G,f(G,1) G,f(H,
7、1) G,f(I,1) I 落入同一个状态集，故E, F, G, H, I暂不分裂。故最终划分为：f A,C,B,D,E,F,G,H,I说明A和C是等价的，E、F、G、H和I是等价的。合并等价状态( A和C中保留A, E、F、G、H和I中保留E)并处理对应弧线得最小化DFA如下：10101010102230333精品文档1.010011232403124343.1考虑文法S(L )| aLL , S | S建立句子(a,(a,a)和(a,(a,a),(a,a) 的分析树(b)为(a)的两个句子构造最左推导。为(a)的两个句子构造最右推导。(d)这个文法产生的语言是什么。(a,(a,a)的分析树
8、精品文档精品文档S(a,(a,a),(a,a)的分析树(a,(a,a)的最左推导S= > Im (L)= >lm (L,S)= >lm (S,S) =>lm (a,S)=> Im (a,(L)= > Im (a,(L,S)= > Im (a,(S,S)= > Im(a,(a,S) =>lm (a,(a,a) (a ,(a ,a),(a,a)的最左推导S= > Im (L) = > Im (L,S)= > Im (S,S) = > Im (a,S)= > Im(a,(L)= >lm (a,(L,S) =&g
9、t;lm (a,(S,S) =>lm (a,(L),S) =>lm (a,(L,S),S) =>lm (a,(S,S),S) =>lm (a,(a,S),S)= >Im (a,(a,a),S)= > Im (a,(a,a),(L)= > Im(a,(a,a),(L)=>lm (a,(a,a),(L,S)= > Im (a,(a,a),(S,S)= > Im(a,(a,a),(a,S) =>lm (a,(a,a),(a,a)(a,(a,a)的最右推导S= > rm (L) = > rm(L,(L)= > rm (
10、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)的最右推导S = > rm (L) = > rm (L,S)= > rm (L,(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)= &
11、gt; 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考虑文法A aSbS|bSaS| £(a)为句子abab构造两个不同的最左推导，以此说明文法是二义的。(b)为abab构造对应的最右推导。(c)为abab构造对应的分析树(
12、a) 1.S= > lm aSbS = > Im abSaSbS = > Im abaSbS= > Im ababS => Im abab2.S = > lm aSbS = > lm abS = > lm abaSbS= > lm ababS = > lm abab(b)S = > rm aSbS = > rm aSb = > rm abSaSb= > rm abSab= > rm abab(C)分析树(1)分析树(2)£ £(d)该文法产生的语言是a、b个数相等的ab串含空串习题33
13、.3下面的二义文法描述命题演算公式，为它写一个等价的非二义性 文法。S-S and S| S or S| not S| true| false|(S)E->E or T | TT->T and F | FF->not F | (E) | true | false3.10 构造下面文法的LL(1)分析表D->TLT->int | real L->id RR->,id R| £答：Follow(D)=# Follow(T尸id Follow(L)=# Follow(R)=#First(TL)=int,real First(T)=int,real
14、First(D)=int,real First(int)=intFirst(real)=real First(id R尸id First(L)=id First(,id R)=, First( £ )= £ First( R)= , ,£ IntRealIdDD->TLD->TLTT->intT->realLL->id RRR->,id RR-> £3.11 下面的文法是否为LL (1)文法？说明理由。(两种方法)S->A B | P Q xA->x yB->b cP->d P |
15、63;Q->a Q | £答：方法一：First(AB尸xFirst(PQx尸d,a,x 因为：First(AB) n First(PQx尸x 所以此文法不是LL(1)文法。方法二：Follow(S尸的Follow(A尸bFollow(B尸讲Follow(P尸a,xFollow(Q尸xFirst(AB尸xFirst(PQx尸d,a,xFirst(x y)=xFirst(b c)=bFirst(d P)=d First( £ )= £ First(a Q)=aFirst(S尸d,a,xFirst( A尸xFirst( B)=bFirst( P)= d,
16、63; First( Q= a, £ xdab#SS->ABS->PQxS->PQxS->PQxAA->x yBB->b cPP-> sP->d PP-> sQQ-> sQ->a Q该文法有分析表有多个入口，不是LL (1)文法。3.19 证明下面的文法不是LL (1)文法Sf S A | A A->a 答：该文法存在左递归所以不是LL (1)文法。3.20 证明下面的文法是LL (1)文法S->AaAb| BbBaA-> £B-> £答：Follow(S尸的Follow(A
17、尸a,bFollow(B尸a,bFirst(AaAb尸a First(BbBa尸b First(A)= £ First(B)= £ First( £ )= £ First(S尸a,b1,该文法无二义性，无左递归2, First(AaAb) n First(BbBa尸中 3, £ First(A)£ 6 First(B)但是：First(A ) n Follow(A尸 First(B ) n Follow(B尸 所以是一个LL (1)文法。习题33.18考虑下面的文法E E+T | TT T F | FF F* | a | b(a)为此
18、文法构造SLR分析表。(b)构造LALR分析表。答：(a) E' E EE + TETTTFTF*FFFaFbI0E'- E+T- TFE'I6I9E- TFE+T-I7ET -TTF -TT - F*FF -*F- FF aF- bI3TF ,FF -I4aFF ,a ,FI3aI4I5FabFollow(E) = #,+精品文档Follow(T) = #,+,a,bFollow(F) = #,+,a,b,*习题 33.18 考虑下面的文法E E+T | TT T F | FFF* | a | b(c)构造LR分析表。答： (b) E' E EE + T ET
19、 TTF TF* FF Fa Fb状态ActionMove+*ab#ETF0S4S51231S6acc2R2S4S5R273R4S8R4R4R44R6R6R6R6R65R7R7R7R7R76S4S5397R3S8R3R3R38R5R5R5R5R59R1S4S5R174.7用S的综合属性val给出下面文法中产生的二进制数的值，例如， 输入 101.101 时,s.val=5.625。S L.L|LL LB|BB 0|1(a)仅用综合属性决定s.val。(b)用L属性定义决定s.vab在该定义中，B的唯一综合属性是c(还 需要继承属性)，它给出由B产生的位对最终值的贡献。例如， 101.101的最前一位和最后一位对值5.625的贡献分别是4和0.125。解：给文法符号B、L和S以综合属性vaL另外再给L 一个表示长 度的综合属性length,所求的语法制导定义如下：S L1.L2 S.val=L1.val+L2.val/2ength精品文档精品文档S L S.val=L.valL L1B L.val=L1.val*2+B.val;L.length=L1.length+1B 0 B.val=0B 1 B.val=1精品文档