【正文】 L1204。L1204。L1204。（5分）句子aadbd有兩棵語法樹（5分，劃一棵樹給3分）。E’→ εE’→ εTT → FT’T → FT’ q 4 q 4 q 3 DFA 的狀態(tài)轉(zhuǎn)換圖（１分） 第三步（２分）：將DFA 最小化 ：（１分） 將狀態(tài)劃分終態(tài)與非終態(tài)兩個集合：Ａ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝，Ｅ＝｛ｑ４｝根據(jù)Ａ、Ｅ集合的情況，對Ａ集合進行劃分狀態(tài) 輸入 I 0 I 1 ｑ０ — Ａ ｑ１ ＡＡ ｑ２Ｅ Ａ ｑ３ Ａ Ａ 將狀態(tài)集Ａ劃分為兩個集合：Ａ＝｛ｑ０，ｑ１，ｑ３｝，Ｂ＝｛２｝根據(jù)Ａ、Ｂ集合的情況，對Ａ集合進行劃分狀態(tài) 輸入 I 0 I 1 ｑ０ — Ａ ｑ１ ＢＡ ｑ３ Ｂ Ａ 將狀態(tài)集Ａ劃分為兩個集合：Ａ＝｛ｑ０｝，Ｃ＝｛ｑ１，ｑ３｝根據(jù)Ａ、Ｃ集合的情況，對Ｃ集合進行劃分狀態(tài) 輸入 I 0 I 1 ｑ１ ＢＡ ｑ３ Ｂ Ａ 最小DFA 的狀態(tài)轉(zhuǎn)換圖（１分） ３．（20分）給定文法 G[E] ： 　　E → E+T | T 　　T → T*F | F　　F → (E) | i 該文法是 LL(1) 文法嗎？（要求給出詳細過程，如果是LL（1），給出分析表）答：（1）該文法不是LL（1）文法，因為有左遞歸，消除左遞歸可獲得一個LL（1）文法 （2分）（2） 消除左遞歸，得新文法 (3分)E → TE’E’→ +TE’| εT → FT’　　T’ → *FT’ |ε　　F → (E) | i (3)求產(chǎn)生式右部的First集 ()First(TE’) = First(T)= First(F)={(,i} First(+TE’) = {+} First(FT’) = First(F)={(,i} First(*FT’) = {*} First((E)) = {(} First(i) = {i} （4） 求所有非終結(jié)符的Follow集()Follow(E) = {$,)} Follow(E’) = Follow(E) = {$,)} Follow(T) = First(E’)∪Follow(E)={+} ∪{$,)}={$,+,)} Follow(T’) = Follow(T) ={$,*,)} Follow(F) = First(T’)∪Follow(T) ∪Follow(T’)= {$,*,)} （5） 求所有產(chǎn)生式的Select集 ()Select（E → TE’）=First(TE’)= {(,i} Select（E’→ +TE’）=First(+TE’)= {+} Select（E’→ ε）= Follow(E’) = {$,)} Select（T → FT’）=First(FT’)= {(,i} Select（T’ → *FT’）=First(*FT’)= {*}Select（T’→ ε）= Follow(T’) ={$,+,)} Select（F → (E)）=First((E))= {(} Select（F → i）=First(i)= {i} （6）對相同左部的所有Select即求交集() Select（E’→ +TE’）∩Select（E’→ ε）= Φ Select（T’ → *FT’）∩Select（T’→ ε）=Φ Select（F → (E)）∩Select（F → i）=Φ 所以，改造后的文法是LL（1）文法，其分析表如下（7） LL(1) 分析表（ 5 分） V N V T + * i ( )$E E → TE’ E → TE’ 答：（ 1 ）（３分）正規(guī)表達式： 1(0|1) * 00 （ 2 ）（７分）第一步（３分）：將正規(guī)表達式轉(zhuǎn)換為 NFA 第二步（２分）：將 NFA 確定化為 DFA ：（１分） 狀態(tài) 輸入 I 0 I 1 ⑶ (3 分 ) 試畫出 001B 關(guān)于 G [S] 的語法樹。X1X2…Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號X1,X2…Xj1的屬性；（2） A的繼承屬性。X9．兩個正規(guī)集相等的必要條件是他們產(chǎn)生的符號串是相同的。 R5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 X1．編譯程序是對高級語言程序的編譯執(zhí)行。x3．一個算符優(yōu)先文法的每個非終結(jié)符號間都也可能存在優(yōu)先關(guān)系。 　C．刪除多余運算　 D． x*yx* 4．如果文法G是無二義的，則它的任何句子α_A____。　A． xyx 　A． M1和M2的狀態(tài)數(shù)相等 5．后綴式abc/所代表的表達式是a/(bc)。1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。3．通常把編譯過程分為分析前端與綜合后端兩大階段?！窘獯稹?1) 6→6，因為D(6)={1,2,4,6}， 所以6 DOM 6，故6→6是回邊； (2) 7→4，因為D(7)={1,2,4,7}， 所以4 DOM 7，故7→4是回邊； (3) 4→2，因為D(4)={1,2,4}， 所以2 DOM 4，故4→2是回邊?；剡叄杭僭O(shè)a→ b是流圖中一條有向邊，如果b DOM a，則稱a→b是流圖中的一條回邊。 (2)轉(zhuǎn)移語句的目標(biāo)語句。 合算原則：以盡可能低的代價取得較好的優(yōu)化效果。活動記錄（AR） 一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū) (塊)叫做一個活動記錄。兩種動態(tài)存儲分配方式：棧式，堆式棧式動態(tài)存儲分配分配策略：將整個程序的數(shù)據(jù)空間設(shè)計為一個棧。 靜態(tài)存儲分配基本策略在編譯時就安排好目標(biāo)程序運行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的單元地址。運行時的存儲區(qū)劃分目標(biāo)區(qū)：存放目標(biāo)代碼。為何要轉(zhuǎn)換成中間代碼邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機上實現(xiàn)同一種語言。：是復(fù)雜性介于源程序語言和機器語言的一種表示形式。(2) 終結(jié)符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián)，只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。V：屬性的有窮集。：一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則,這些語義規(guī)則附在每個產(chǎn)生式上。 1)SaAS 2)Sb 3) AbAS 4)A εFOLLOW（A）={a,b}（3）由于文法含有左遞歸而引起回溯：遞歸子程序法、預(yù)測分析法。T39。 | e E　→ T E39。 A162。 | e 形如： A→Aa1 | Aa2 | . . . | Aan | b1 | b2 | . . . | bm 其中，每個a都不等于e ，b1 , . . . , bm 均不以A開頭。Sa S174。VN , a，b206。VN , b206。,其中：a、β不同時推