編譯原理課后答案_第三版

1、三12 將圖a確定化 最小化10a,baa圖a解：引入新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y(X,Y不屬于源非確定集)得圖如下：YaX0 a,b a1列出狀態(tài)轉(zhuǎn)換矩陣如下所示：abA X,0,Y0,1,Y1B 0,1,Y0,1,Y1 C 10,Y D 0,Y0,1,Y1CDBADFA如下：aabbbba最少化：終態(tài)A,B,Da=A,BA,B,DA,B,Db=B,A,B,D 最少化為：10aba(b)將圖b最少化b154320babaaabbaab圖b解：終態(tài)0,1 a0,10,1 b=2,42,3,4,50,1不能再分非終態(tài)2,3,4,5 a =0,1,3,5 2,4 a =0,1 2,4 b =3,5

2、3,5 a =3,5 3,5 b =2,40代表0,1,2代表2,4,3代表3,5得最少化為：320ababba14.構(gòu)造一個(gè)DFA，它接收=0,1上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。解：構(gòu)造正規(guī)式為：（0|10）*則可構(gòu)造如下NFA：GBAFEDCqfq0010列出狀態(tài)轉(zhuǎn)換矩陣如下：01A q0,F,A,C, qf B,G,F,A,C, qfDB B,G,F,A,C, qfB,G,F,A,C, qfDC DE,G,F,A,B,C, qf D E,G,F,A,B,C, qf B,G,F,A,C, qfD則得DFA如下：CDBA0001101最少化得 A,B,D0=B A,B,

3、D1=CA0C 1015.給定右線性文法G：S-0S|1S|1A|0BA-1C|1B-0C|0C-0C|1C|0|1求出一個(gè)與G等價(jià)的左線性文法。BSC解：由G得NFA=A1f0,1110,10,1000由NFA得左線性文法：GL=:A-1 B-0 C-A1|B0|C0|C1 f-A1|B0|C0|C1四1.考慮下面文法G：S-a|(T)T-T,S|S(1)消除G的左遞歸(2)改寫后的文法是否是LL(1)的？給出預(yù)分析表。解：(1) S-a|(T) T-ST T-,ST|(2) FIRSTFOLLOWSa,(#, , , ) Ta,()T, , )預(yù)分析表：a ( ) ， #SS-a S- S

4、-(T)TT-ST T-ST T-STTT- T-,ST是LL(1)的。五5文法 S-AS|bA-SA|a(1) 列出所有LR(0)項(xiàng)目(2) 構(gòu)造LR(0)項(xiàng)目集規(guī)范族及識(shí)別活前綴的DFA(3) 該文法是SLR的么？若是構(gòu)造它的SLR分析表。解：擴(kuò)展文法：S-SSI6:A-SA A-SA A-a S-AS S-b S-AS|b A-SA|abI1: S-S A-SA A-a S-AS S-bI0 : S-S S-ASS-b A-SA A-aAaSI5: A-SA S-AS S-AS S-b A-SA A-aAa S bAI2 : S-ASS-AS S-b A-SA A-aI3 : S-bbb

5、SI4 : A-aaa I7 : S-AS A-SA A-SAA-aS-AS S-bSAbAaa SbA(3)Follow FirstS # a,bS#,a,ba,bAa,ba,b沖突項(xiàng)目I中：有接受項(xiàng)目和移進(jìn)沖突，可解決.a,bI5 , I7 存在移進(jìn)，歸約沖突，不可解決Follow(S) a b所以，該文法不是SLR的.證明下面的文法 S-AaAb|BbBa A- B-是LL(1)文法。不含左遞歸；First(1) First(2) =First(A) Follow(A) =該文法是LL(1)文法七1 給出下面表達(dá)式的逆波蘭表示（后綴式）：a*(-b+c)a+b*(c+d/e)not A

6、or not(C or not D)(A and B)or (not C or D) 后綴式分別為：ab-c+*abcde/+*+A not CD not or not orAB and C not D or or3. 請(qǐng)將表達(dá)式-（a+b）*(c+d)-(a+b+c)分別表示成三元式、間接三元式和四元式序列。三元式：(0)（+，a, b）(1) ( -, (0), _)(2) (+, c, d)(3) (*,(1),(2)(4)（+，a, b）(5) (+, (4), c)(6) (-,(3),(5)間接三元式：(1)（+，a, b）(2) ( -, (1), _)(3) (+, c, d)

7、(4) (*,(2),(3)(5) (+, (1), c)(6) (-,(4),(5)間接代碼： （1） （2） （3） （4） （1） （5） （6）四元式：（0）（+，a, b, T1）（1）（-，T1, _, T2）（2）（+， c, d, T3）（3）（*, T2, T3, T4）（4）（+，a, b, T5）（5）（+，T5, c, T6）（6）（-，T4,T6,T7）7.用7.5.1節(jié)的方法，把下面語句翻譯成四元式序列： While AC and BD do If A=1 then C:=C+1 Else while AD do A:=A+2;100 （j, A,C,102）101

8、 （j , _, _, 115）102 （j,B,D,104）103 （j ,_, _, 115）104 （j=,A, 1, 106）105 （j , _, _, 109）106 （+, C, 1, T1）107 （:=, T1,_, C）108 （j , _, _, 114）109 （j,A,D,111）110 （j , _, _, 115）111 （+, A, 2, T2）112 （:=,T2, _, A）113 （j ,_, _, 109）114 （j , _, _,100）115十3.試對(duì)以下基本塊B1和B2：B1：A:=B*CD:=B/CF:=2*EG:=B*CH:=G*GF:=H*

9、GL:=FM:=LB2：B:=3D:=A+CE:=A*CG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L分別應(yīng)用DAG對(duì)它們進(jìn)行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列：（1） 假設(shè)只有G,L,M在基本塊后面還要被引用；（2） 假設(shè)只有L在基本塊后面還要被引用。n91n11n21n51n441n31解：B1：F,L,Mn61*En81H2+*A,GD/*BCB1優(yōu)化后：A:=B*C(1) G:=B*C(2) G:=B*C D:=B/CH:=G*GH:=G*G E:=A+DL:=G*HL:=G*H G:=AM:=L H:=G*G F:=H*G L:=F M

10、:=LB2：n10L,M+n81+E,In4n51D,Hn71G+ *n1n31n91n61n2*K BF315ACB2優(yōu)化后：B:=3 (1) G:=3*F(2) H:=A+CD:=A+C H:=A+CI:=A*CE:=A*C I:=A*C J:=H+IG:=B*F J:=H+I L:=15+JH:=D L:=15+J I:=E M:=LJ:=H+IK:=15L:=K+JM:=L5.以下程序是某程序的最內(nèi)循環(huán)，試對(duì)它進(jìn)行循環(huán)優(yōu)化A:=0I:=1L1：B:=J+1C:=B+IA:=C+AIf I=100 GOTO L2I:=I+1GOTO L1L2：解：代碼外提： B:=J+1刪除歸納變量I：