編譯原理復(fù)習(xí)題

1、編譯原理復(fù)習(xí)題一、填空題1.編譯程序的工作過程一般可以劃分為 詞法分析， 語法分析， 語義分析， 中間代碼優(yōu)化 ， 代碼優(yōu)化 等幾個基本階段。2.若源程序是用高級語言編寫的，目標(biāo)程序是 匯編程序或機器語言程序 ，則其翻譯程序稱為編譯程序.3.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 .5.對編譯程序而言，輸入數(shù)據(jù)是 源程序 ，輸出結(jié)果是 目標(biāo)程序 .7.若源程序是用高級語言編寫的，目標(biāo)程序是機器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序 。8.一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括 表格管理 和 出錯處理 。其

2、中，詞法分析器用于識別 單詞 。10.一個上下文無關(guān)文法所含四個組成部分是 一組終結(jié)符號、 一組非終結(jié)符號 、 一個開始符號 、 一組產(chǎn)生式 。12.產(chǎn)生式是用于定義 語法成分 的一種書寫規(guī)則。13.設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)=x|Sx，xVT* 。14.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx（其中xV*），則稱x是文法的一個 句型 。15.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中xVT*)，則稱x是文法的一個 句子 。16.掃描器的任務(wù)是從源程序中識別出一個個 單詞符號 。17.語法分析最常用的兩類方法是 自頂向下 和 自

3、底向上 分析法。18.語法分析的任務(wù)是識別給定的終結(jié)符串是否為給定文法的 句子 。19.遞歸下降法不允許任一非終結(jié)符是直接 左 遞歸的。20.自頂向下的語法分析方法的關(guān)鍵是 如何選擇候選式 的問題。21.遞歸下降分析法是自 頂向下 分析方法。22.自頂向下的語法分析方法的基本思想是：從文法的 開始符號 開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的 句子 ，使之與給定的輸入串匹配。23.自底向上的語法分析方法的基本思想是：從給定的終結(jié)符串開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行 直接歸約 ，試圖 歸約 到文法的 開始符號 。24.自底向上的語法分析方法的基本

4、思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行 直接歸約 ，力求 歸約 到文法的 開始符號 。26.在LR（0）分析法的名稱中，L的含義是 自左向右的掃描輸入串 ，R的含義是 最左歸約，0 的含義是 向右查看輸入串符號的個數(shù)為0 。 31.終結(jié)符只有 ，它們由詞法分析器提供。32.在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 語法 錯誤和 語義 部分錯誤.34一個句型中的最左簡單短語稱為該句型的句柄。36從功能上說，程序語言的語句大體可分為執(zhí)行性語句和說明性語句兩大類。37語法分析是依據(jù)語言的語法規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的語義規(guī)進(jìn)行的。38語法分析器的輸入是單詞

5、符號串，其輸出是語法單位。40逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為（a+b+c）*d-e 。41計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。42自上而下分析法采用移進(jìn)、歸約、錯誤處理、接收等四種操作。43一個LR分析器包括兩部分：一個總控程序和一張分析表。44后綴式abc-/所代表的表達(dá)式是a/(b-c)。 46語法分析基于上下文無關(guān)文法進(jìn)行，即識別的是該類文法的句子。語法分析的有效工具是語法樹。48語義分析階段所生成的與源程序等價的中間表示形式可以有逆波蘭、四元式與三元式等。51.自頂向下語法分析會遇到的主要問題有回溯和左遞歸。52.已知文法GE：ET|E+T; T

6、F|T*F; F(E)|i該文法的開始符號是E，終結(jié)符號集合VT是+,*,(,),，非終結(jié)符號結(jié)合VN是E,T,F。二、單選題1一個編譯程序中，不僅包含詞法分析，( A)，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分。A語法分析 B文法分析C語言分析D解釋分析2語法分析器則可以發(fā)現(xiàn)源程序中的(D )。A語義錯誤   B語法和語義錯誤C錯誤并校正    D語法錯誤3解釋程序處理語言時 , 大多數(shù)采用的是(B)方法。A源程序命令被逐個直接解釋執(zhí)行B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行D以上方法都可以4編譯程序是一種(B)

7、。A匯編程序 B翻譯程序C解釋程序         D目標(biāo)程序5通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括(C)。A模擬執(zhí)行器             B解釋器      C表格處理和出錯處理     D符號執(zhí)行器6一個句型中的最左(B)稱為該句型的句柄。A短語 &#

8、160;       B簡單短語       C素短語          D終結(jié)符號 7文法 GE ：      ETET      TFTF      Fa(E)該文法句型 EF(ET)的簡單短語是下列符號串中的(B)。 （ET）   E

9、T      F    F(ET) A 和 B 和 C 和 D 8詞法分析器用于識別(C)。A句子      B句型         C單詞         D產(chǎn)生式 9在自底向上的語法分析方法中，分析的關(guān)鍵是(A)。A尋找句柄         B尋找句型 &

10、#160;     C消除遞歸       D選擇候選式 10文法 G 產(chǎn)生的(D)的全體是該文法描述的語言。A句型 B終結(jié)符集 C非終結(jié)符集 D句子11若文法 G 定義的語言是無限集，則文法必然是(A)。  A遞歸的   B前后文無關(guān)的C二義性的 D無二義性的12四種形式語言文法中，1型文法又稱為(C)文法。A短語結(jié)構(gòu)文法       B前后文無關(guān)文法 C前后文有關(guān)文法     D正規(guī)文法 13一個文法所

11、描述的語言是(A)。A唯一的   B不唯一的C可能唯一，好可能不唯一   D都不對14(B)和代碼優(yōu)化部分不是每個編譯程序都必需的。A語法分析   B中間代碼生成C詞法分析       D目標(biāo)代碼生成 15(B)是兩類程序語言處理程序。 A高級語言程序和低級語言程序B解釋程序和編譯程序 C編譯程序和操作系統(tǒng)D系統(tǒng)程序和應(yīng)用程序 16. 一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組(D)。 A句子 B句型C單詞 D產(chǎn)生式17 文法分為四種類型，

12、即0型、1型、2型、3型。其中2型文法是(D)。A短語文法    B正則文法     C上下文有關(guān)文法 D上下文無關(guān)文法18文法 G 所描述的語言是(C)的集合。 A文法G的字母表V中所有符號組成的符號串B文法 G 的字母表 V 的閉包 V* 中的所有符號串C由文法的開始符號推出的所有終結(jié)符串D由文法的開始符號推出的所有符號串19文法分為四種類型，即0型、1型、2型、3型。其中0型文法是(A)。A短語文法    B正則文法     C上下文有關(guān)文法 D上下文無關(guān)文法20(A)

13、是一種典型的解釋型語言。  ABASIC BC CFORTRAN  DPASCAL21與編譯系統(tǒng)相比，解釋系統(tǒng)(D)。A比較簡單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快C比較簡單 , 可移植性差 , 執(zhí)行速度慢 D比較簡單 , 可移植性好 , 執(zhí)行速度慢 22用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。 A源程序       B目標(biāo)程序      C連接程序 D解釋程序23編寫一個計算機高級語言的源程序后，

14、到正式上機運行之前，一般要經(jīng)過(B)這幾步: (1) 編輯   (2) 編譯   (3) 連接   (4) 運行 A(1)(2)(3)(4)     B(1)(2)(3)    C(1)(3)     D(1)(4)24把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A編譯器            B匯編器   

15、        C解釋器            D預(yù)處理器25詞法分析器的輸出結(jié)果是(C)。A單詞的種別編碼 B單詞在符號表中的位置C單詞的種別編碼和自身值 D單詞自身值26 正規(guī)式M 1和M 2 等價是指(C)。  AM1和M2的狀態(tài)數(shù)相等BM1和M2的有向邊條數(shù)相等CM1和M2所識別的語言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 27 文法G：SxSx|y所識別的語言是(C)。Axyx  B(

16、xyx)* C     Dx*yx* 28如果文法G是無二義的，則它的任何句子 (A)。A最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同   D可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同 29構(gòu)造編譯程序應(yīng)掌握(D)。A源程序   B目標(biāo)語言C編譯方法      D以上三項都是30四元式之間的聯(lián)系是通過(B)實現(xiàn)的。 A指示器         B臨

17、時變量C符號表             D程序變量 31表達(dá)式(AB)(CD)的逆波蘭表示為(B)。AABCD BABCD      CABCD      DABCD 33 編譯程序是對(D)。  A匯編程序的翻譯   B高級語言程序的解釋執(zhí)行C機器語言的執(zhí)行 D高級語言的翻譯 34 采用自上而下分析，必須(C)。A消除左遞歸  B消除右遞歸C消除回溯 &#

18、160;D提取公共左因子 35在規(guī)范歸約中，用(B)來刻畫可歸約串。A直接短語 B句柄C最左素短語   D素短語 36間接三元式表示法的優(yōu)點為(A)。 A采用間接碼表，便于優(yōu)化處理B節(jié)省存儲空間，不便于表的修改C便于優(yōu)化處理，節(jié)省存儲空間 D節(jié)省存儲空間，不便于優(yōu)化處理 37在目標(biāo)代碼生成階段，符號表用(D)。A目標(biāo)代碼生成 B語義檢查C語法檢查 D地址分配38下面關(guān)于解釋程序的描述正確的是 B .(1) 解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼(2) 解釋程序適用于COBOL 和 FORTRAN 語言(3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的   A.

19、(1)(2)       B. (1)      C. (1)(2)(3)      D.(2)(3)40.用不同語言編寫的程序產(chǎn)生 后，可用 連接在一起生成機器可執(zhí)行的程序.在機器中真正執(zhí)行的是 . 上面三空格對應(yīng)的選項是： A a. 源程序          b. 目標(biāo)程序   c. 函數(shù)   

20、     d. 過程  e. 機器指令代碼    f. 模塊       g. 連接程序    h.程序庫A. b、g、e B. b、c、e C. e、g、f D. e、c、f41.由于受到具體機器主存容量的限制，編譯程序幾個不同階段的工作往往被組合成 ，諸階段的工作往往是 進(jìn)行的. 上面兩空格對應(yīng)的選項是： A a. 過程  b. 程序  c. 批量  d.遍 e. 順序  f. 并行

21、  g. 成批  h.穿插A. d和h B. d和e C. a和h D. a和e42.編譯過程中，語法分析器的任務(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) &

22、#160;  D.(1)(2)(3)(4)43.編譯程序必須完成的工作有 A . (1) 詞法分析  (2) 語法分析        (3) 語義分析 (4) 代碼生成  (5) 中間代碼生成    (6) 代碼優(yōu)化 A. (1)(2)(3)(4)      B. (1)(2)(3)(4)(5)     C. (1)(2)(3)(4)(5)(6)  D. (1)(2)

23、(3)(4)(6)   44按邏輯上劃分，編譯程序第二步工作是 C 。A. 語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化45已知語言L= xnyyn | n>=1，則下述文法中， D 可以產(chǎn)生語言L。A 1.ZxZy|xAy|y B 1.AxAy 2. AxAy|x 2.AxC 1.ZAyB D 1.ZxAy 2.AxA|x 2.AxAy|y 3.ByB|y 46喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B 。A.短語文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無關(guān)文法48設(shè)G是一個給定的文法，S是文法的

24、開始符號，如果Sx(其中xV*)，則稱x是文法G的一個 B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式49若一個文法是遞歸的，則它所產(chǎn)生的語言的句子 A 。A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量50文法的二義性和語言的二義性是兩個 A 的概念。A 不同 B 相同 C 無法判斷 D 不存在51.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非終結(jié)符集 B.終結(jié)符集 C. 字母表 D. 狀態(tài)集52.編譯程序中語法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子53. 在LR分析法中，分析棧中

25、存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項目三、判斷題1計算機高級語言翻譯成低級語言只有解釋一種方式。 （×）2在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。 （×）3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相 同。 （×）4“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行”說法。（×）5正則文法其產(chǎn)生式為Aàa，AàBb， A，BVN，a、bVT。 （）6產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。 (×)7解釋

26、程序適用于 COBOL 和 FORTRAN 語言。 (×)8正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ()9如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 ()10編譯程序是對高級語言程序的解釋執(zhí)行。 (×)11一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 (×)12語法分析時必須先消除文法中的左遞歸 。 (×)13兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 ( )14設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。 (×)15確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。 ()16詞法分析

27、作為單獨的一遍來處理較好。 (×)17構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 ()18編譯程序與具體的機器有關(guān)，與具體的語言無關(guān)。 (×)19每個文法都能改寫為LL(1)文法。 （×）20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （×）21遞歸下降分析法是自頂向下分析方法。 ()22一個 LL(l)文法一定是無二義的。 ()23算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 （）24自底而上語法分析方法的主要問題是候選式的選擇。 （×）25LR分析方法是自頂向下語法分析方法。 （×）26簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 （&

28、#215;）27若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（×）28一個句型的句柄一定是文法某產(chǎn)生式的右部。 （）29在 SLR(1)分析法的名稱中，S的含義是簡單的。 ()30綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (×)31一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 ()32LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 ()33規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。 ()34LR分析技術(shù)無法適用二義文法。 (×)35逆波蘭表示法表示表達(dá)式時無須使用括號。 ()36逆波蘭法表示的表達(dá)式亦稱后綴式 。 ()

29、38在程序中標(biāo)識符的出現(xiàn)僅為使用性的。 （×）39. 設(shè)為a，b，則a，ba，都是上的正規(guī)式。（×）40. 對于上下文無關(guān)文法GS，若 SAB 則A 一定是一條產(chǎn)生式規(guī)則，其中,（VTVN）*。 （×）41. 對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（）42. LR（0）分析法是一種規(guī)范歸約法。（）43. 算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。 （）44. 解釋程序和編譯程序一樣，生成目標(biāo)代碼。 （×）45. 編譯程序生成的目標(biāo)代碼只能是機器語言。 （×）46. 等價文法是指兩個文法完全相同。 （×）47. 對于

30、字母表上的任一NFA M'，必存在上與NFA M' 等價的DFA M。（）48. 不存在正規(guī)文法能產(chǎn)生語言：L=anbn|n>=1（×）四、簡答題1、什么是句子？ 什么是語言?句子：設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx（其中xVT*），則稱x是文法的一個句子。語言：句子的集合。設(shè)GS是給定文法，則由文法G所定義的語言L（G）可描述為：2、已知文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開始符號（識別符號）是什么？E請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。答：VN=E,T,FVT=i,+,-,*,(,), 找

31、出句型T+T*F+i的所有短語、簡單短語和句柄。答：短語T，T*F，i，T+T*F+i簡單短語：T，T*F句柄：T3、已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語言是什么？答：L(GS)=danbn|n1,m0 GS能否改寫為等價的正規(guī)文法？答：能， GS，S，dABAaA|aB|aBbB|b5、證明下面文法GN是二義性文法。 GN： N SEE S SDD E 0210D 012證明：左推導(dǎo)1：N=>SE=>DE=>D0=>10 左推導(dǎo)2：N=>E=>107、 簡述DFA與NFA有何區(qū)別 ? 答：DFA與NFA的區(qū)別：NFA可以有若干個開始狀態(tài)

32、，而DFA僅只有一個開始狀態(tài)；DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。8、 試給出非確定自動機的定義。答：一個NFA（M）是一個五元組：M=(K，f，S，Z)。(K是一個有窮集，它的每個元素稱為一個狀態(tài)；(是一個有窮字母表，它的每個元素成為一個輸入符號，所以也稱為輸入符號表；(f是狀態(tài)轉(zhuǎn)換函數(shù)，是在K×*K的子集的映射，即f：K×*ZK；表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；SCK是一個非空初態(tài)集；ZCK是一個終態(tài)集（可空）。9、為正規(guī)式（a|b）*a(a|b)

33、構(gòu)造一個等價的確定的有限自動機。10、構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101 13、 編譯過程一般分為幾個階段？各階段的輸入輸出分別為什么？15、 在LL(1)分析法中，LL分別代表什么含義?答：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導(dǎo)。16、文法G為： SaAB Aa B |則判斷G為LL（1）文法的條件是：答：Sclect(SaAB)=aSclect(Aa)=aSclect(B|/y)=，y=17、文法G=(A, B, S, a, b, c, P, S) 其中P為： SAc|aB Aab Bbc 該文法是二義的嗎？說明理由。答：是有二義性

34、的，因為句子abc 有兩棵語法樹(或稱有兩個最左推導(dǎo)或有兩個最右推導(dǎo))最左推導(dǎo)1：S Ac abc最左推導(dǎo)2：S aB abc18、文法G=(E, +, *, i, (, ), P, E)其中P為： Ei EE+E EE*E E(E)該文法是二義的嗎？說明理由。答： 是有二義性的，因為句子i*i+i 有兩個最左推導(dǎo)最左推導(dǎo)1：EE+E E*E+E i*E+E i*i+E i*i+i最左推導(dǎo)2：EE*E i*E i*E+E i*i+E i*i+i19、 自頂向下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個符號一個符號地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符

35、串。因此判定給定終結(jié)符號串是正確句子。25、 簡單優(yōu)先方法基本思想是什么？答：簡單優(yōu)先方法基本思想是首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后再利用這種關(guān)系，通過比較兩個相鄰的符號之間的優(yōu)先順序來確定句型的“句柄”并進(jìn)行歸約。28、 語法制導(dǎo)翻譯方法的基本思想是什么?答：在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時，就執(zhí)行該產(chǎn)生式所對應(yīng)的語義動作進(jìn)行屬性計算，完成對輸入符號串的翻譯。33、給定下列中綴式，分別寫出等價的后綴式和四元式(運算符優(yōu)先級按常規(guī)理解)。(1)(ab*c)/(ab)d答：后綴式：abc*+ab+/d-四元式：（*，b，c，t1） （+，a，t1，t2） （+，

36、a，b，t3） （/，t2,t3,t4） (-,t4,d,t5)一、最左、最右推導(dǎo)及語法樹1、令文法為 E®T|E+T|E-T T®F|T*F|T/F F®（E）|i1） 給出i+i*i的最左推導(dǎo)和最右推導(dǎo)；2） 給出i+i*i的最左推導(dǎo)語法樹。3、下面的文法生成的是以x和y為操作數(shù)、二元運算符+、*和-為運算符的前綴表達(dá)式： E®+EE|*EE|-EE|x|y1）給出串+*-xyxy的最左推導(dǎo)和最右推導(dǎo)；2）給出+*-xyxy的語法樹。4、一個上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下：1） 給出該句子相應(yīng)的最左推導(dǎo)，最右推導(dǎo)。2） 該文法的產(chǎn)生式集

37、合P可能有哪些元素？二、自動機的確定化和最小化1、將下圖中的自動機確定化并最小化。3、試構(gòu)造正規(guī)式(0|1)*1(0|1)相應(yīng)的自動機，并將其確定化4、試構(gòu)造正規(guī)式(a|b)*ab(a|b)*相應(yīng)的自動機，并將其確定化和最小化。 三、FIRST和FOLLOW集合1、考慮下面文法G1： Sa|(T)TT，S|S1） 消去G1的左遞歸；2） 經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測分析表(要求寫出詳細(xì)過程，應(yīng)先求出每個非終結(jié)符的FIRST和FOLLOW集合)。2、判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的預(yù)測分析表。SaD DSTe|TbH|HHd|3、對文法G(S)：S 

38、4; S Ú a T | a T | Ú a TT ® Ù a T | Ù a1）消除該文法的左遞歸和提取左公因子；2）構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；3）構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。四、短語、直接短語、句柄和素短語1、對于文法G（S）：S(L)|aS|aLL,S|S1）畫出句型(S,(a)的語法樹。2）寫出上述句型的所有短語、直接短語、句柄和素短語。2、文法GS為：SV VT | ViTTF| T+FF)V* |(1）畫出句型ViFi(的語法樹。2）寫出上述句型的所有短語、直接短語、句柄和素短語。3、對于文法G(E):E®T|E+TT®F|T*FF®(E)|i1） 畫出句型T*F+i1*i2的語法樹。2）寫出上述句型的短語，直接短語、句柄、素短語和最左素短語。答：短語：T*F +i1*i2, T*F, i1*i2 , i1, i2直接短語：T*F, i1, i2句柄：T*F素短語：T*F, i1, i2 最左素短語：T*F五、FIRSTVT集合和LASTVT集合，構(gòu)造優(yōu)先關(guān)系表1、設(shè)