【正文】 。因此，這個文法是LL(1)的。, a/b/]} I5 = {[B→a→S → S 1．S → A2．A → BA 3．A → e4．B → aB 5．B → b構造其LR(0)項目集規(guī)范族和goto函數(識別活前綴的DFA)如下:I0 = { [S39。)={ }}I7 = {S→SabS, R→→ 求各個非終結符的Follow集，以便構造分析表： Follow(S39。aA, A→b}I5 = {S→aS}I3 = {S→a → S 1．S → aSAB2．S → BA 3．A → aA4．A → B 5．B → b其LR(0)項目集規(guī)范族和識別活前綴的DFA如下:I0 = {S39。12. 解答：① 最右推導：E=T=F=(E)=(E＋T)=(E＋F)=(E＋i)= (T＋i)=(T*F＋i)語法樹： 句型(T*F＋i)的語法樹② 短語：(T*F＋i)，T*F＋i，T*F，i　　　　　 　素短語：T*F，i最左素短語：T*F③ 由于E =E+T =E+T*F，故E+T*F為該文法的句型 短語：T*F、E+T*F 直接短語： T*F 句柄： T*F13. 解答：最左推導：S= (T) = (T,S) = (S,S) = (a,S) = (a,(T)) = (a,(T,S)) = (a,(S,S)) = (a,(a,S)) = (a,(a,a))最右推導：S= (T) = (T,S) = (T,(T)) = (T,(T,S)) = (T,(T,a)) = (T,(T,a)) = (T,(a,a)) = (S,(a,a)) = (a,(a,a))文法中S和T的FirstVT和LastVT集為：FirstVT(S)={a,(} FirstVT(T)={,a, (} lastVT(S)={a, ）} lastVT(T)={,a,)}→*F39。→eFF→PF39。T→FT39。E→TE39。)={+, e}∩{,),}=FFirst(T39。)= Follow(E)={，)} (1)（使用的產生式）Follow(T) = First(E39。)20))L39。)L39。)L39?！?,SL39。) = { ) }按以上結果，構造預測分析表M如下：文法G39。else error。false39。match(39。{and39。例如Ada語言的注釋始于雙連字符（），隨行的結束而終止。： 對應的NFA為： 增加狀態(tài)X、Y，再確定化：IIaIb{x,5}{A,T,Y}{ }{A,T,Y}{A,T,Y}{B}{B}{ }{B,T,Y}{B,T,Y}{ }{T,Y}{T,Y} { }{ }得到的DFA為： 最小化：該自動機已經是最小化的DFA了。d (q2，1)=q1狀態(tài)轉換圖為：(2) DFA d (q0，1)=q2d (q1，0)=q1由0和1組成的符號串，且從右邊開始數第3位為0。則 S→S10|S21，|S1|=2k (k0），|S2|=2k (k≥0）。確定有限自動機的確定性表現在映射d：QVT q是單值函數，也就是說，對任何狀態(tài) q∈Q和輸入字符串a∈VT，d (q,a)唯一確定下一個狀態(tài)。 (2) 〈奇數頭〉→ 2|4|6|8|〈奇數尾〉 C：① D：②|〈奇數頭〉〈奇數尾〉 〈整數〉→ 〈整數〉〈數字〉|〈數字〉 S = aSbS = aSbaSbS = aSbaSb = aSbab = abab√ (5)顯然，本題給出的是一個確定的有限自動機，它的狀態(tài)轉換圖是C中的②。 B:③且S1是{0,1}上的串，含有奇數個0和奇數個1。(4) d (q0，1)=q0d (q1，0)=q2 d (q2，1)=q0狀態(tài)轉換圖為：(2) 正規(guī)式: 1*01*01*01* DFAM=({0，1}，{q0}，q0，{q0}，d)，其中d定義如下:d (q0，0)=q013．解答：其中a代表1元硬幣，b代表5角硬幣14．解答：正規(guī)式為：(0|1)*(00|01) 化簡：(0|1)*0(0|1)不確定的有窮自動機為：確定化，并最小化得到：正規(guī)文法為：S→1S | 0AA→0B | 0 | 1C | 1B→0B | 0 | 1C | 1C→1S | 0A：① 正規(guī)式：(dd*:| e)dd*(.dd*| e)，d代表a~z的字母 ② NFA為：③ DFA為：：詞法分析器對源程序采取非常局部的觀點，因此象C語言的語句 fi (a == f (x) ) …中，詞法分析器把fi當作一個普通的標識符交給編譯的后續(xù)階段，而不會把它看成是關鍵字if的拼寫錯。如果用Ada語言的注釋格式，那么上面函數應寫成long gcd(p,q)long p,q。bterm()。}}void bterm()。){match (39。bfactor()。)39。})}8. 解答：消除所給文法的左遞歸，得G39。是LL(1)的，因為它的LL(1)分析表不含多重定義入口。8)L39。aa,a))S →a13)L39。Sa))16)L39。→e21)＼{e}∪Follow(T39。)∩Follow(T39。E39。T39。F→PF39。F39?！鶶AB, S→AB, A→B, B→)={} Follow(A)={a,b,}S, S→a, S→}顯然，I1和I5存在移進歸約沖突?！? ]}I2 = {[S→AB, a/b/], [B→(2) 下面構造這個文法的識別活前綴的DFA?！鶶b}I7 = {S→BbB為 0．S39。SR, S→}I7 = {R→,因此，此文法是LR(0)文法。而display表內容的項數與過程的嵌套層次有關，一般比過程的嵌套層數大1。 D(n5) = {n0, n1, n2, n5} (4) 代碼外提：由于刪除歸納變量后有R :=K * 100，是循環(huán)不變運算，可以提到前置結點B239。 /* 第一個for語句 */ /* 數組A的基地址 */ B6: T4 := i j := j + i 根據這條回邊找到循環(huán) L3 = { B11, B9, B10, B8, B7, B6, B5 }(3) 進行代碼外提把在循環(huán)中不隨循環(huán)變化的操作提到循環(huán)外的前置結點中，且在基本塊中作復寫傳播和刪除無用賦值。R1，R2MOVR1，CADD R1，DMOV S，x，R14. 解答：MOV (4) 進行強度削弱和刪除歸納變量后，其程序流圖如圖2。 D(B10) = { B1, B2, B4, B5, B6, B9, B10 }，又有 B10 → B9，所以 B10 → B9 是一條回邊。 B11: i := i + 1 T6 := 2 * T6 /* [T3]是對T3的值取整 */ T2 := addr(A) i := 27. 解答：8. 解答：(1) DAG如下： (2) 優(yōu)化后的三地址代碼為：T3:＝S－RT4:＝S＋RA:＝5*T4B:＝T3＋T4 9. 解答：(本題中假設采用字節(jié)地址，兩個字節(jié)作為一個機