編譯原理期末復(fù)習(xí)資料

1、一、選擇題1詞法分析器的輸出結(jié)果是_C_。A單詞的種別編碼 B單詞在符號(hào)表中的位置 C單詞的種別編碼和自身值 D單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_C_。  AM1和M2的狀態(tài)數(shù)相等          BM1和M2的有向邊條數(shù)相等CM1和M2所識(shí)別的語言集相等 D M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語言是_C_。A xyx  B (xyx)* C xnyxn(n0)     Dx*yx* 4如果文法G是無二義的，則它的任何句子_

2、A_。A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C最左推導(dǎo)和最右推導(dǎo)必定相同   D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_D_。A源程序   B目標(biāo)語言        C編譯方法      D以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過_B_實(shí)現(xiàn)的。 A指示器         B臨時(shí)變量 C符號(hào)表   &#

3、160;         D程序變量 7表達(dá)式(AB)(CD)的逆波蘭表示為_B_。A. ABCD BABCD         CABCD         DABCD 8. 優(yōu)化可生成_D_的目標(biāo)代碼。A運(yùn)行時(shí)間較短               &#

4、160;B占用存儲(chǔ)空間較小C運(yùn)行時(shí)間短但占用內(nèi)存空間大 D運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_C_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. 強(qiáng)度削弱     B 刪除歸納變量     C刪除多余運(yùn)算  D代碼外提10編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。 A.說明標(biāo)識(shí)符的過程或函數(shù)名B說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D. 標(biāo)識(shí)符的行號(hào)1語言是AA句子的集合 B產(chǎn)生式的集合 C符號(hào)串的集合 D句型的集合2編譯程序前三個(gè)階段完成的工作是CA詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化

5、和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成 D詞法分析、語法分析和代碼優(yōu)化3一個(gè)句型中稱為句柄的是該句型的最左D A非終結(jié)符號(hào) B短語 C句子 D直接短語4下推自動(dòng)機(jī)識(shí)別的語言是CA0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即B A 字符 B單詞 C句子 D句型6對(duì)應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是B AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37詞法分析的任務(wù)是A A識(shí)別單詞 B分析句子的含義 C識(shí)別句子 D生成目標(biāo)代碼8常用的中間代碼形式不含D

6、A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是C A節(jié)省時(shí)間 B節(jié)省空間 C節(jié)省時(shí)間和空間 D把編譯程序進(jìn)行等價(jià)交換10代碼生成階段的主要任務(wù)是C A把高級(jí)語言翻譯成匯編語言 B把高級(jí)語言翻譯成機(jī)器語言C把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼 D把匯編語言翻譯成機(jī)器語言【 D 】1_型文法也稱為正規(guī)文法。A 0 B 1 C 2 D 3【 D 】2_文法不是LL(1)的。 A 遞歸 B 右遞歸 C 2型 D 含有公共左因子的【 B 】3 文法EE+E|E*E|i的句子i*i+i*i的不同語法分析樹的總數(shù)為_。A1 B3 C5 D7【 A 】4四元式之間的聯(lián)系是通過 實(shí)現(xiàn)。 A臨時(shí)變

7、量 B指示器 C符號(hào)表 D程序變量【 C 】5同心集合并可能會(huì)產(chǎn)生的新沖突為 。 A二義 B移進(jìn)/移進(jìn) C移進(jìn)/歸約 D歸約/歸約【 C 】6代碼優(yōu)化時(shí)所依據(jù)的是 。 A語法規(guī)則 B詞法規(guī)則 C等價(jià)變換規(guī)則 D語義規(guī)則【 B 】7表達(dá)式a-(-b)*c的逆波蘭表示為 。 Aa-bc* Babc*- Cab- Dabc-* （注：為單目減運(yùn)算符）【 B 】8過程的DISPLAY表記錄了 。 A過程的連接數(shù)據(jù) B過程的嵌套層次 C過程的返回地址 D過程的入口地址1. 一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符，一組非終結(jié)符，一個(gè)（C ），以及一組（B ）。A 字符串 B 產(chǎn)生式 C 開始符號(hào)

8、 D 文法2.程序的基本塊是指（D ）。A 一個(gè)子程序 B 一個(gè)僅有一個(gè)入口和一個(gè)出口的語句C 一個(gè)沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（B ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4在通常的語法分析方法中，（ A）特別適用于表達(dá)式的分析。A 算符優(yōu)先分析法 B LR分析法C 遞歸下降分析法 D LL（1）分析法5經(jīng)過編譯所得到的目標(biāo)程序是（ D）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機(jī)器語言程序或匯編語言程序6 一個(gè)文法所描述的語言是（A ）；描述一個(gè)語言的

9、文法是（ C）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一個(gè)句子，當(dāng)其滿足下列條件（BCD ）之一時(shí)，則稱該文法是二義文法。A 其最左推導(dǎo)和最右推導(dǎo)相同 B 該句子有兩個(gè)不同的最左推導(dǎo)C 該句子有兩個(gè)不同的最右推導(dǎo) D 該句子有兩棵不同的語法樹E 該句子對(duì)應(yīng)的語法樹唯一8 下面（ BCD）語法制導(dǎo)翻譯中，采用拉鏈回填技術(shù)。A. 賦值語句 B. 布爾表達(dá)式的計(jì)算 C. 條件語句 D. 循環(huán)語句1. 設(shè)有文法GI： II1|I0|Ia|Ic|a|b|c下列符號(hào)串中是該文法句子的有（ B ）。 ab0 a0c01 aaa bc10可選項(xiàng)有：A B C D5 運(yùn)行階段

10、的存儲(chǔ)組織與管理的目的是（ C ）。 提高編譯程序的運(yùn)行速度 節(jié)省編譯程序的存儲(chǔ)空間 提高目標(biāo)程序的運(yùn)行速度 為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備可選項(xiàng)有：A. B. C. D. 1將編譯程序分成若干個(gè)“遍”是為了_b_。 a.提高程序的執(zhí)行效率 b.使程序的結(jié)構(gòu)更加清晰 c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率 2.構(gòu)造編譯程序應(yīng)掌握_d_。 a.源程序 b.目標(biāo)語言 c.編譯方法 d.以上三項(xiàng)都是 3變量應(yīng)當(dāng)c。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 4.編譯程序絕大多數(shù)時(shí)間花在_d_上。 a.出錯(cuò)處理 b

11、.詞法分析 c.目標(biāo)代碼生成 d.管理表格 5.詞法分析器的輸出結(jié)果是_c_。 a.單詞的種別編碼 b.單詞在符號(hào)表中的位置 c.單詞的種別編碼和自身值 d.單詞自身值 6.中間代碼生成時(shí)所依據(jù)的是c。 a.語法規(guī)則 b詞法規(guī)則 c語義規(guī)則 d等價(jià)變換規(guī)則 7.,后綴式ab+cd+/可用表達(dá)式_b_來表示。 a.a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d 8.程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為_c_管理技術(shù)。 a.動(dòng)態(tài)存儲(chǔ) b.棧式存儲(chǔ) c.靜態(tài)存儲(chǔ) d.堆式存儲(chǔ) 9.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_d_原則。 a.先請(qǐng)先放 b.先請(qǐng)后

12、放 c.后請(qǐng)先放 d.任意 1 一個(gè)編譯程序中，不僅包含詞法分析，_A_，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。 A語法分析 B文法分析 C語言分析 D解釋分析 2 詞法分析器用于識(shí)別_C_。 A字符串B語句C單詞 D標(biāo)識(shí)符 3 語法分析器則可以發(fā)現(xiàn)源程序中的_D_。 A語義錯(cuò)誤 B語法和語義錯(cuò)誤 C錯(cuò)誤并校正 D語法錯(cuò)誤 4 下面關(guān)于解釋程序的描述正確的是_B_。 (1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼 (2) 解釋程序適用于 COBOL 和 FORTRAN 語言 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的 A(1)(2) B(1) C(1)(2)(3) D(2)

13、(3) 5 解釋程序處理語言時(shí) , 大多數(shù)采用的是_B_方法。 A源程序命令被逐個(gè)直接解釋執(zhí)行 B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行 C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行 D 以上方法都可以 6 編譯過程中 , 語法分析器的任務(wù)就是_B_。 (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu) A(2)(3) B (2)(3)(4)C (1)(2)(3) D(1)(2)(3)(4) 7 編譯程序是一種_C_。 A. 匯編程序 B翻譯程序C解釋程序 D目標(biāo)程序 8 文法 G 所描述的語言是_C_的集合。

14、 A. 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串 B文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串 C由文法的開始符號(hào)推出的所有終極符串 D. 由文法的開始符號(hào)推出的所有符號(hào)串 9 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_B_。 A. 短語文法 B 正則文法C 上下文有關(guān)文法 D 上下文無關(guān)文法 1 文法 G 產(chǎn)生的_D_的全體是該文法描述的語言。 A句型 B 終結(jié)符集 C非終結(jié)符集 D句子 2 若文法 G 定義的語言是無限集，則文法必然是 _A_。 A遞歸的 B前后文無關(guān)的 C二義性的 D無二義性的 3 四種形式語言文法中，1型文法又稱為 _C_文法。 A短語

15、結(jié)構(gòu)文法 B前后文無關(guān)文法 C前后文有關(guān)文法 D正規(guī)文法 5 _B_和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。 A語法分析 B中間代碼生成 C詞法分析 D目標(biāo)代碼生成 6_B_是兩類程序語言處理程序。 A高級(jí)語言程序和低級(jí)語言程序 B解釋程序和編譯程序 C編譯程序和操作系統(tǒng) D系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_A_的信息。 A. 維數(shù) B類型 C維上下界 D各維的界差 9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_D_。 A. 短語文法 B正則文法 C上下文有關(guān)文法 D上下文無關(guān)文法 4_A_是一種典型的解釋型語言。 ABASIC BC CFORTRAN

16、 D PASCAL 5與編譯系統(tǒng)相比，解釋系統(tǒng)_D_。 A比較簡單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 C比較簡單 , 可移植性差 , 執(zhí)行速度慢 D比較簡單 , 可移植性好 , 執(zhí)行速度慢 6用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_B_。 A源程序 B目標(biāo)程序 C連接程序 D解釋程序 8編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后 , 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過_B_這幾步: (1) 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行 A. (1)(2)(3)(4) B(1)(2)(3) C (1)(3) D (1)(4) 9把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)

17、程序的工作是由_B_完成的。 A編譯器 B匯編器 C 解釋器 D預(yù)處理器 2 編譯程序是對(duì)_D_。 A匯編程序的翻譯 B高級(jí)語言程序的解釋執(zhí)行C機(jī)器語言的執(zhí)行 D高級(jí)語言的翻譯 3 采用自上而下分析，必須_C_。 A 消除左遞歸 B消除右遞歸 C消除回溯 D提取公共左因子 4在規(guī)范歸約中，用_B_來刻畫可歸約串。 A直接短語 B句柄 C最左素短語 D素短語 5 若a為終結(jié)符，則A-> · a為_B_項(xiàng)目。 A歸約 B移進(jìn) C接受 D待約 6間接三元式表示法的優(yōu)點(diǎn)為_A_。 A采用間接碼表，便于優(yōu)化處理 B節(jié)省存儲(chǔ)空間，不便于表的修改C便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D節(jié)省存儲(chǔ)空間，

18、不便于優(yōu)化處理 7基本塊內(nèi)的優(yōu)化為_B_。 A. 代碼外提，刪除歸納變量 B刪除多余運(yùn)算，刪除無用賦值C強(qiáng)度削弱，代碼外提 D循環(huán)展開，循環(huán)合并 8. 在目標(biāo)代碼生成階段，符號(hào)表用_D_。 A目標(biāo)代碼生成 B語義檢查 C語法檢查 D地址分配 9若項(xiàng)目集Ik含有A-> · ，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aFOLLOW(A)時(shí)，才采取“A-> · ”動(dòng)作的一定是_D_。 A. LALR文法 BLR(0)文法 CLR(1)文法 DSLR(1)文法 10堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_D_原則。 A. 先請(qǐng)先放 B先請(qǐng)后放 C后請(qǐng)先放 D.任意 二、簡答題1、正

19、規(guī)表達(dá)式定義P182、上下文無關(guān)文法定義P39VT 是一個(gè)非空有限集合，其元素稱為終結(jié)符。VN是一個(gè)非空有限集合，其元素稱為非終結(jié)符，并有VTVN=非空S是一個(gè)非終結(jié)符，稱為開始符號(hào)。P是產(chǎn)生式的有限集合。3、分離詞法分析器的理由P44語言的詞法規(guī)則簡單，不必用功能更強(qiáng)的上下文無關(guān)文法描述它；對(duì)于詞法記號(hào)，正規(guī)式給出的描述比上下文無關(guān)文法給出的更簡潔且易于理解；從正規(guī)式自動(dòng)構(gòu)造出的詞法分析器比從上下文無關(guān)文法構(gòu)造出的更有效；編譯器的效率會(huì)改進(jìn)；編譯器的可移植性加強(qiáng)；把語言的語法結(jié)構(gòu)分成詞法和非詞法兩部分，為編譯器前端的模塊劃分提供了方便的 途徑。4、LR分析器富有吸引力的原因P71LR分析器能

20、夠被構(gòu)造來識(shí)別所有能用上下文無關(guān)文法寫出的編程語言構(gòu)造。LR分析方法是已知的最一般的無回溯的移進(jìn)歸約方法，它能和其他移進(jìn)歸約方 法一樣有效地實(shí)現(xiàn)。LR方法能分析的文法類是預(yù)測分析法或者說LL方法能分析的文法類的直超集。在自左向右掃描輸入的前提下，LR分析器盡可能快地發(fā)現(xiàn)語法錯(cuò)誤。5、語法制導(dǎo)定義的形式P107綜合屬性：如果b是A的屬性，c1，c2，····，ck是產(chǎn)生式右部文法符號(hào)的屬性或A的其他屬性，那么b稱為A的綜合屬性。繼承屬性：如果b是產(chǎn)生式右部某個(gè)文法符號(hào)X的屬性，c1，c2，···，ck是A的屬性或右部文法符號(hào)的

21、屬性，那么b稱為X的繼承屬性。S屬性定義：僅僅使用綜合屬性的語法制導(dǎo)定義稱為S屬性定義。注釋分析樹：每個(gè)結(jié)點(diǎn)的屬性值都標(biāo)注出來的分析樹。依賴圖：分析樹結(jié)點(diǎn)的屬性之間的互相依賴可以用依賴圖的有向圖來描繪。6、翻譯方案設(shè)計(jì)原則P117產(chǎn)生式右部符號(hào)的繼承屬性必須在先于這個(gè)符號(hào)的動(dòng)作中計(jì)算。一個(gè)動(dòng)作不能引用該動(dòng)作右邊符號(hào)的綜合屬性。左部非終結(jié)符的綜合屬性只能在它所引用的所有屬性都計(jì)算完后才能計(jì)算。只有綜合屬性的情況最簡單。7、活動(dòng)記錄結(jié)構(gòu)P166臨時(shí)數(shù)據(jù)；保存臨時(shí)值。局部數(shù)據(jù)；保存過程的局部數(shù)據(jù)。保存的機(jī)器狀態(tài)；保存剛好在過程調(diào)用前的機(jī)器狀態(tài)信息，包括返回地址及調(diào)用過 程使用并且在返回時(shí)必須恢復(fù)的寄

22、存器的內(nèi)容。訪問鏈；有些語言需要通過訪問鏈來訪問非局部數(shù)據(jù)?？刂奇?；用來指向調(diào)用者的活動(dòng)記錄。參數(shù)；調(diào)用過程提供的實(shí)在參數(shù)，由被調(diào)用過程使用。返回值。用于存放被調(diào)用過程返回給調(diào)用過程的值。8、活動(dòng)記錄設(shè)計(jì)布局原則P171調(diào)用者和被調(diào)用者之間交流的數(shù)據(jù)一般放在被調(diào)用者活動(dòng)紀(jì)錄的開始處，并盡可能 靠近調(diào)用者的活動(dòng)紀(jì)錄。固定長度的項(xiàng)通常放在活動(dòng)紀(jì)錄的中間，一般包括控制鏈、訪問鏈和機(jī)器狀態(tài)鏈。在編譯時(shí)不能及時(shí)知道大小的一些項(xiàng)放在活動(dòng)紀(jì)錄的末端。 9、參數(shù)傳遞的方法和特點(diǎn)P180值調(diào)用。值調(diào)用是最簡單的傳遞參數(shù)的方法。調(diào)用者計(jì)算實(shí)參，并把它的值（右值） 傳給被調(diào)用過程。引用調(diào)用。調(diào)用者把實(shí)參存儲(chǔ)單元的地

23、址（即實(shí)參的左值）傳給被調(diào)用者，被調(diào)用 者對(duì)形參的任何訪問就是對(duì)對(duì)應(yīng)實(shí)參的訪問。換名調(diào)用。P18110、使用獨(dú)立于機(jī)器的中間形式的好處P199再目標(biāo)比較容易。把針對(duì)新機(jī)器的后端加到現(xiàn)成的前端上，可以得到另一種機(jī)器的 編譯器。獨(dú)立于機(jī)器的代碼優(yōu)化器可用于這種中間表示。三、應(yīng)用題狀態(tài)轉(zhuǎn)換圖（有窮狀態(tài)自動(dòng)機(jī)）： ： ： ： ： ： ： ： ： ： ： 1、（a|b）*（aa|bb）（a|b）*畫出狀態(tài)轉(zhuǎn)換圖。IaIb 1,2,32,3,42,3,5 2,3,42,3,4,6,7,82,3,5 2,3,52,3,42,3,5,6,7,8 2,3,4,6,7,82,3,4,6,7,82,3,5,7,8

24、2,3,5,6,7,82,3,4,7,82,3,5,6,7,8 2,3,5,7,82,3,4,7,82,3,5,6,7,8 2,3,4,7,82,3,4,6,7,82,3,5,7,8IaIb123243325446575675746 新的狀態(tài)轉(zhuǎn)換圖如下： （1）A=1,2,3，B=4,5,6,7 Aa=2,4 ×（2）A=1,3，B=2，C=4,5,6,7 Aa=2B，Ab=3,5 ×（3）A=1，B=2，C=3,D=4,5,6,7（單元素可以不用看，必有，古先看D） Da=4,7D，Db=5,6D，Aa=2B，Ab=3C，Ba=4D，Bb=3C，Ca=2B，Cb=5C，則

25、有ab ABC BDCCBDDDD2、（a*|b*）b（ba）*的狀態(tài)轉(zhuǎn)換圖。IaIb 1,2,3,42,43,4,5,6,8 2,42,45,6,8 3,4,5,6,8-3,4,5,6,7,8 5,6,8-7 3,4,5,6,7,86,83,4,5,6,7,8 76,8- 6,8-7IaIb1232243-54-657567-7-6新的狀態(tài)轉(zhuǎn)換圖如下：化簡：（用終結(jié)狀態(tài)與非終結(jié)狀態(tài)，然后輸出狀態(tài)一致分一類）。（1）A=1,2,6，B=3,4,5,7 Aa=2 ×（2）A=1,2，B=6，C=3,4,7，D=5 Cb=5,6 ×（只要有一個(gè)不屬于任何一個(gè)集合，就不行）（3）

26、A=1,2，B=6，C=3，D=4,7，E=5 Ab=3,4 ×（4） A=1，B=2，C=6，D=3，E=4,7，F(xiàn)=5 Aa=2B，Ab=3D，Ba=2B，Bb=4E，Ca=7E，Db=5F，Eb=6C，F(xiàn)a=7E，F(xiàn)b=5Fab ABD BBECE-D-FE-CFEF知識(shí)點(diǎn)First集合的求法： First集合最終是對(duì)產(chǎn)生式右部的字符串而言的，但其關(guān)鍵是求出非終結(jié)符的First集合，由于終結(jié)符的First集合就是它自己，所以求出非終結(jié)符的First集合后，就可很直觀地得到每個(gè)字符串的First集合1. 直接收取：對(duì)形如U->a的產(chǎn)生式（其中a是終結(jié)符），把a(bǔ)收入到Firs

27、t(U)中2. 反復(fù)傳送：對(duì)形入U(xiǎn)->P1P2P3Pn的產(chǎn)生式（其中P是非終結(jié)符），應(yīng)先把First(P1)中的全部內(nèi)容傳送到First(U)中,如果P1中有，把First(P2)中的內(nèi)容傳送到First(U)中,類推直到Pi中無。Follow集合的求法： Follow集合是針對(duì)非終結(jié)符而言的，F(xiàn)ollow(U)所表達(dá)的是句型中非終結(jié)符U所有可能的后隨終結(jié)符號(hào)的集合，特別地，“$”是識(shí)別符號(hào)的后隨符,先直接加入到S中。1. 直接收取：注意產(chǎn)生式右部的每一個(gè)形如“Ua”的組合，把a(bǔ)直接收入到Follow(U)中。2. 直接收?。簩?duì)形如“UP”(P是非終結(jié)符)的組合，把First(P)中非收

28、入到Follow(U)中。3. 反復(fù)傳送：對(duì)形如U>aP的產(chǎn)生式（其中P是非終結(jié)符）或U->aPQ(P,Q為非終結(jié)符且Q中含)，應(yīng)把Follow(U)中的全部內(nèi)容傳送到Follow(P)中。例 文法：SABc Aa| Bb|First集合求法:能由非終結(jié)符號(hào)推出的所有的開頭符號(hào)或可能的，但要求這個(gè)開頭符號(hào)是終結(jié)符號(hào)。如此題A可以推導(dǎo)出a和，所以FIRST（A）=a，；同理 FIRST（B）=b,;S可以推導(dǎo)出aBc，還可以推導(dǎo)出bc，還可以推導(dǎo)出c，所以FIRST(S）=a，b，cFollow集合的求法:緊跟隨其后面的終結(jié)符號(hào)或。但文法的識(shí)別符號(hào)包含，在求的時(shí)候還要考慮到。 具體做

29、法是把所有包含你要求的符號(hào)的產(chǎn)生式都找出來，再看哪個(gè)有用。 Follow（S）=如求A的，產(chǎn)生式：SABc Aa| ，但只有SABc 有用。跟隨在A后面的終結(jié)符號(hào)是FIRST（B）=b，當(dāng)FIRST（B）的元素為時(shí)，跟隨在A后的符號(hào)就是c，所以 Follow（A）=b，c同理Follow（B）=c對(duì)下面的文法 G ： (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。(2) 證明這個(gè)方法是 LL(1) 的。(3) 構(gòu)造它的預(yù)測分析表。解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(