编译原理作业题整理

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 的分解树如下：r17r5r6r4r13r12r3)0 1(2)由分解树及基本的Thompson构造算法逐步构造等价的NFA过程如下:r1:r2:r3、r5:r6:r7:r8:r9:r10 :0230801671450237016145Start023019016871450198StartStartStartStartStart9023001109168714501311514012131611114150121317101116114150231010art9101101687145r11

3、:Start .0r12：Startr13:StartStartr14、 r15 :r16 :Startr17:(3)由子集法构造等价的 DFA过程如下:01ABCBBDCBCDECEFGFFGGHIHFGIFIE_closure(0) =01,2,4,7 = AAo =w_closure(3,8) =1,2,3,4,6,7,8 =BA =g_closure(5) =1,2,4,5,6,7 =CB。=g_closure(3,8) =123,4,6,7,8 =BB =g_closure(5,S) =124,5,6,7,9 = DCo =旨 _closure(3,8) = BG =E_closur

4、e(5) =CDo =g_closure(3,8,10) = g_closure(3,8) +g_closure(10) = B+10,11,12,14,17 =1,2,3,4,6,7,8,10U =g_closure(5) =CE。=_closure(3,8,13) =E_closure(3,$) +u_closure(13) =B+11,12,13,14,16,17 =1,2,3,4,6,7,8巳=g_closure( 5,9,15)=w_closure(5,9) + w_closure(15)二 D 11,12,14,15,16,17 =1,2,4,5,6,7,9F0 = g_closu

5、re( 3,8,13) = FR =u_closure(5,9,15) =1,2,4,5,6,7,9,11,12,14,15,16,17 =GG0 =E_closure(3,8,10,13) = E_closure(3,8,1C) + E_closure(13) =E + E_closure(13)=E 11,12,13,14,16,17二1,2,3,4,6,7,8,10,11,12,13,14,16,17 = HG =E_closure( 5,15) =C+E_closure(15) =C+11,12,14,15,16,17 =1,2,4,5,6,7,11,12,14,15,16,17 =

6、IH° 二；_ closure( 3,8,13) =FH1 =；_closure( 5,9,15) =GI 0 二_closure( 3,8,1$) =FI1 二；-_closure(5,15) =1其中含有r.初态的是A作为新的DFA的初态，含有原r17终态的是DFA的终态。做出对应 DFA的状态转换图如下：E、F、和H作为新的DFA，如得到的DFAmin与原DFA 一致说明原DFA本身就是(4 )直接由分割算法处理该 最简的：IT 厂 A,B,C,D,E,F,G,H,I由于 f(A,O) = B, f (B,0) = B, f (C,0) = B, f (D,0) = E 导致

7、A, B, C 和 D 落入的状态集是不等价的，说明 A , B , C和D是不等价的，故 A , B, C, D 应该分裂为 A ,B, 6和 D, 故:IT 广 A,B,C,D,E,F,G,H,I由于f (A,1)二C,f(B,1) =D, f(C,1) =C落入不同的状态集(相对I 1来说是两个不等价的状态集)，说明 A , C和B是不等价的，故 A , B , C, D应该分裂为 A, C和 B,故：IT 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(l,0) = F 落入同一个状态

8、集，故 E, F, G, H , I暂不分裂。由于 f(E,1) =G,f (F,1) =G, f(G,1)=G, f(H ,1) = G, f (1,1) = I 落入同一个状态集，故E, F, G , H , I 暂不分裂。故最终划分为：IT 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如下：0101010101022303331.0100112324031243413100 13.1考虑文法S > ( L ) | aL > L , S

9、| S 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b) 为(a)的两个句子构造最左推导。(c) 为(a)的两个句子构造最右推导。(d) 这个文法产生的语言是什么。(a,(a,a)的分析树a(a,(a,a),(a,a)的分析树a ( L )LS)Sa(a,(a,a)的最左推导S=> Im (L)=> Im (L,S)=> Im (S,S)=> Im (a,S)=> Im 佝(S,S)= > Im=> Im (a,(L)= > Im (a,(L,S)(a,(a,S)=> Im (a,(a,a)(a,(a,a),(a,a)的

10、最左推导=> ImS=> Im (L)=> Im (L,S)=> Im (S,S)=> Im (a,S)(a,(L)=> Im (a,(L,S)=> Im (a,(S,S)=> Im (a,(L),S)=> Im(a,(L,S),S)=> Im 佝(S,S),S)=> Im (a,(a,S),S)=>Im (a,(a,a),S)= > Im 佝(a,a),(L)= > Im(a,(a,a),(L)=> Im (a,(a,a),(L,S)= > Im (a,(a,a),(S,S)= > Im(a

11、,(a,a),(a,S)=> Im (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,a) 的最右推导S = > rm (L)= > rm (L,S)= > rm (L,(L)= > rm(L,(L,S)=> rm(L,(L,(L)=> rm (L,(L,(L,S)=&

12、gt;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)(d)该文法产生的语言是括号匹配的串，串中的各项用“，”隔开，项可以是括号匹配的子串或 a3.2考虑文法4 aSbS|bSaS| &（a）为句子abab

13、构造两个不同的最左推导，以此说明文法是二义的。（b）为abab构造对应的最右推导。（c）为abab构造对应的分析树（a） 1.S=> Im aSbS => Im abSaSbS => Im abaSbS=> Im ababS=> Im abab2.S => Im aSbS => Im abS = > Im abaSbS=> Im ababS = >Im abab(b)S => rm aSbS => rm aSb = > rm abSaSb=> rm abSab => rm abab（C）分析树（1）分析树

14、（2）a S b Se(d) 该文法产生的语言是a、b个数相等的ab串含空串习题33.3下面的二义文法描述命题演算公式，为它写一个等价的非二义性文法。St 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->i nt | realL->id RR->,id R| & 答：Follow(D)=# Follow(T)=id Follow(L)=# Foll

15、ow(R)=#First(TL)=int,real First(T)=int,real First(D)=int,real First(int)=int First(real)=real First(id R)=id First(L)=id First(,id R)=, First( e )= e First( R)= , , e IntRealId,#DD->TLD->TLTT->intT->realLL->id RRR->,id RR-> e该文法有分析表有多个入口，不是LL ( 1)文法。3.11下面的文法是否为LL (1)文法？说明理由。(两种

16、方法)S->A B | P Q xA->x yB->b cP->d P |&Q->a Q | s答：方法一：First(AB)=xFirst(PQx)=d,a,x 因为：First(AB) n First(PQx)=x 所以此文法不是LL(1)文法。Follow(S)=# Follow(A)=b Follow(B)=# Follow(P)=a,x Follow(Q)=x方法二：First(AB)=x First(PQx)=d,a,x First(x y)=x First(b c)=b First(d P)=d First( s )= s First(a Q

17、)=aFirst(S)=d,a,xFirst( A)= xFirst( B)= b First( P)= d, s First( Q)= a, s xdab#SS->AB S->PQxS->PQxS->PQxAA->x yBB->b cPP-> sP->d PP-> sQQ-> sQ->a Q3.19 证明下面的文法不是 LL （1）文法St S A | AA->a答： 该文法存在左递归所以不是LL（ 1）文法。3.20 证明下面的文法是 LL （1）文法S->AaAb| BbBaA-> £B->

18、; £答：Follow(S)=#Follow(A)=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)£ First(B)但是：First(A ) n Follow(A)= First(B ) n Follow(B)= 所以是一个 LL ( 1)文法。习题 33.18 考虑下面的文

19、法E E+T | TT T F | FFF* | a | b(a) 为此文法构造SLR分析表。(b) 构造LALR分析表。 答： (a)EE + TETTTFTFF*FFaFbIlE'-EE-E+TE-TT-TFT-FF*-FF-aF-bIoI3I4Follow(E) = #,+Follow(T) = #,+,a,bFollow(F) = #,+,a,b,*习题3E' E-E E +TET-TT-FF*FFaFbI2TaTF -F*F -F I5EE+ TI9EE+T-T TFTTT F*T FF-FF* FF-aF aF-bF bI6FFTTF -F*F -I745F a -F*F -F b -3.18考虑下面的文法E E+T | TT T F | FF F* | a | b(c)构造LR分析表。 答：(b)74bI3I4bI5EE + TETTTFTFF*F*FaFbIlE E ,$E E+T,$/+E T ,$/+T TF,$/+ /a/bT F ,$/+ /a/bF F ,$/+/a/b/*F a ,$/+ /a/b/*F b ,$/+ /a/b/*IoEE E，$E E +$/+I2aEE+ T,$/+T TF,$/+ /a/bT F,$/+ /a/bF