1、1.判斷下面文法是否為LL(1)文法，若是,請構(gòu)造相應(yīng)的LL(1)分析表。S aH H aMd | d M Ab | A aM | e解：首先計(jì)算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非終結(jié)符FIRST集FOLLOW集Sa.# .Ha ，d.# .Ma ，e ，d ，bAa ，e.b.由于first（HaMd）first（Hd）=ad = first（MAb）first（M）=a ，ed ，b = first（AaM）first（Ae）= a e = 所以該文法是LL(1)文法，LL(1)分析表如下表。 LL(1)分析表adbe#SaH.HaMdd.

2、MAb.AbAaM.e.2.給出與正規(guī)式R（ab）*（a|b*）ba等價(jià)的NFA。解：與正規(guī)式R（ab）*（a|b*）ba 等價(jià)的NFA如下圖3進(jìn)行確定的自上而下語法分析要求語言的文法是無左遞歸和公共左因子的。4常用的優(yōu)化技術(shù)包括：刪除公共子表達(dá)式 、 代碼外提、強(qiáng)度削弱、復(fù)寫傳播、歸納變量刪除 等。5局部優(yōu)化是在_ 基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。6.源程序中使用的標(biāo)識符及其屬性放在 符號表 中。7.一個(gè)上下文無關(guān)文法所含四個(gè)組成是 開始符號 、 產(chǎn)生式集合 、 終結(jié)符號集合 、 非終結(jié)符號集合 。8對于文法G，僅含終結(jié)符號的句型稱為 句子 。9、后綴式abc-/所代表的表達(dá)式是_a/(b-c

3、)_ _。10.編譯程序是指將 源語言 程序翻譯成 目標(biāo)語言 程序的程序。11詞法分析器的輸出結(jié)果是_C_。A 單詞的種別編碼 B 單詞在符號表中的位置C單詞的種別編碼和自身值 D單詞自身值12正規(guī)式 M 1 和 M 2 等價(jià)是指_C_。A M1和M2的狀態(tài)數(shù)相等 B M1和M2的有向邊條數(shù)相等C M1和M2所識別的語言集相等 D M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等13文法G：SxSx|y所識別的語言是_C_。A xyx B (xyx)* C xnyxn(n0) D x*yx*14如果文法G是無二義的，則它的任何句子_A_。A最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語

4、法樹可能不同 C最左推導(dǎo)和最右推導(dǎo)必定相同 D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同15表達(dá)式(AB)(CD)的逆波蘭表示為_B_。A. ABCD B ABCDC ABCD D ABCD16、“運(yùn)算符與運(yùn)算對象類型不符”屬于_B_。A.語法錯(cuò)誤 B. 語義錯(cuò)誤 C. 語用錯(cuò)誤 D.規(guī)則錯(cuò)誤17、一個(gè)語言的文法是_B_A惟一的 B不惟一的 C.個(gè)數(shù)有限的 D.以上都不對18、一個(gè)句型的最左直接短語稱為該句型的_D_。 A.句型 B.短語 C.簡單短語 D.句柄 19. 在LR(0)分析法中，若a,V*且a則稱“A a.”為 B 項(xiàng)目，稱“S a.a”為 項(xiàng)目。A歸約 待歸 B歸約 移

5、進(jìn)C接收 移進(jìn) D歸約 接收20. 基本塊 A 。A只有一個(gè)入口語句和一個(gè)出口語句 B有一個(gè)入口語句和多個(gè)出口語句C有多個(gè)入口語句和一個(gè)出口語句 D有多個(gè)入口語句和多個(gè)出口語句21編譯程序是對高級語言程序的解釋執(zhí)行。( ) 22一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。( ) 23語法分析時(shí)必須先消除文法中的左遞歸 。 ( ) 24逆波蘭表示法表示表達(dá)式時(shí)無須使用括號。 ( ) 25靜態(tài)數(shù)組的存儲空間可以在編譯時(shí)確定。 ( ) 26進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 ( ) 27.歸約是從文法開始符號出發(fā)，推出最后的輸入串。（ ）28.A*=AA+

6、。（ ）29如果一個(gè)文法是遞歸的，則其產(chǎn)生的語言的句子是無窮個(gè)。（ ）30僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。（ ）31.請寫出由下列文法所確定的語言。S10S01SaAAbAAa解：.(10)nabma(01)n32.設(shè)有文法GS：SaBc|bABAaAb|bBb|（1）、計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合。（2）、構(gòu)造文法的LL(1)分析表。解：(1) FIRST(S)=a,b FOLLOW(S)=# FIRST(A)=a,b FOLLOW(A)=b,#FIRST(B)=,b FOLLOW(B)=c(2)abc#SSaBcSbABAAaAbAbBBbB33.給

7、定下面的文法SAaAb|BbBa A B（1） 、求出每個(gè)非終結(jié)符的FIRST和FOLLOW集合。（2） 、判斷該文法是否為LL（1）文法。（3） 、構(gòu)造該文法的項(xiàng)目集規(guī)范族。（4） 、判斷該文法是否為SLR(1)的。解：（1）FIRST(S)=a,b FOLLOW(S)=#FIRST(A)= FOLLOW(A)= a,b FIRST(B)= FOLLOW(B)= a,b (2).該文法不含左遞歸；.對于S的兩個(gè)候選其中FIRST(AaAb)=a, FIRST(BbBa)= b,首符集無交集。所以該文法是LL(1)文法。（3）I0:SAaAbABI1: SAaAbI2: SAaAbABI3: SAaAbI4: SAaAb(4).在項(xiàng)目集規(guī)范族中I0中存在歸約-歸約沖突，又因?yàn)镕OLLOW(A)=FOLLOWW(B)=a,b，當(dāng)面臨輸入符號a或b時(shí)，不能選擇用哪個(gè)產(chǎn)生式進(jìn)行歸約，即沖突不能解決，所以該文法不是SLR(1)的。34. 請對下面的流圖進(jìn)行