編譯原理練習(xí)題

1、“編譯原理”練習(xí)題一、 選擇題1、匯編程序是將 a 翻譯成 b ,編譯程序是將 c 翻譯成 d .a.匯編語(yǔ)言程序 b.機(jī)器語(yǔ)言程序 c.高級(jí)語(yǔ)言程序d. a 或者 b e. a 或者 c f. b 或者 c2、下面關(guān)于解釋程序的描述正確的是 b . (1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼 (2) 解釋程序適用于COBOL 和 FORTRAN 語(yǔ)言 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的   a. (1)(2)       b. (1)     

2、; c. (1)(2)(3)      d.(2)(3)3、高級(jí)語(yǔ)言的語(yǔ)言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個(gè)階段，而解釋程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效. 與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d .解釋程序處理語(yǔ)言時(shí),大多數(shù)采用的是 (3)b 方法. (4)a 就是一種典型的解釋型語(yǔ)言. (1): a. 中間代碼生成   b.目標(biāo)代碼生成   c.詞法分析  d.語(yǔ)法分析   e.代碼優(yōu)化 (2):

3、 a.比較簡(jiǎn)單,可移植性好,執(zhí)行速度快 b.比較復(fù)雜,可移植性好,執(zhí)行速度快 c.比較簡(jiǎn)單,可移植性差,執(zhí)行速度慢 d.比較簡(jiǎn)單,可移植性好,執(zhí)行速度慢 (3): a.源程序命令被逐個(gè)直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為之間代碼,再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,在執(zhí)行 d.以上方法都可以 (4) : a. BASIC b. C c. FORTRAN d. PASCAL4、用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b .用不同語(yǔ)言編寫的程序產(chǎn)生 b 后,可用 g 連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是 e .a. 源程序    &#

4、160;     b. 目標(biāo)程序   c. 函數(shù)        d. 過(guò)程  e. 機(jī)器指令代碼    f. 模塊       g. 連接程序    h.程序庫(kù)5、要在某一臺(tái)機(jī)器上為某種語(yǔ)言構(gòu)造一個(gè)編譯程序,必須掌握下述三方面的內(nèi)容: c , d , f .a. 匯編語(yǔ)言     

5、0;  b. 高級(jí)語(yǔ)言   c. 源語(yǔ)言      d. 目標(biāo)語(yǔ)言e. 程序設(shè)計(jì)方法    f. 編譯方法   g. 測(cè)試方法    h. 機(jī)器語(yǔ)言6、由于受到具體機(jī)器主存容量的限制,編譯程序幾個(gè)不同階段的工作往往被組合成 (1)d ,諸階段的工作往往是 (2)d 進(jìn)行的. (1) a. 過(guò)程  b. 程序  c. 批量  d.遍 (2) a. 順序  b. 并行  c. 成批 

6、; d.穿插7、編譯過(guò)程中,語(yǔ)法分析器的任務(wù)就是 b . (1) 分析單詞是怎樣構(gòu)成的            (2)  分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的 (3) 分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的  (4) 分析程序的結(jié)構(gòu)8、編寫一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后,到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò) b 這幾步. (1) 編輯  (2) 編譯  (3) 連接  (4) 運(yùn)行9、編譯程序必須完成的工作有 a . (1) 詞法分析  (2) 語(yǔ)

7、法分析        (3) 語(yǔ)義分析 (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)(3)(4)(6)   e. (1)(2)(3)(5)(6)10、編譯程序是一種 B 。A. 匯編程序 B. 翻譯

8、程序 C. 解釋程序 D. 目標(biāo)程序11、按邏輯上劃分，編譯程序第二步工作是 C 。A. 語(yǔ)義分析 B. 詞法分析 C. 語(yǔ)法分析 D. 代碼優(yōu)化12、通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 C 。A.模擬執(zhí)行器  B.解釋器   C.表格處理和出錯(cuò)處理    D.符號(hào)執(zhí)行器13、文法G所描述的語(yǔ)言是 C 的集合。A.文法G的字母表V中所有符號(hào)組成的符號(hào)串B.文法G的字母表V的閉包V*中的所有符號(hào)串C.由文法的開始符號(hào)推出的所有終極符串D.由文法的開始符號(hào)推出的所有符號(hào)

9、串14、喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B 。A.短語(yǔ)文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無(wú)關(guān)文法15、文法GN=（b，N，B，N，NbbB，BbN），該文法所描述的語(yǔ)言是 C 。A. L(GN)=bii0 B. L(GN)=b2ii0C. L(GN)=b2i+1i0 D. L(GN)=b2i+1i116、一個(gè)句型中的最左 B 稱為該句型的句柄?？蛇x項(xiàng)有：A. 短語(yǔ) B. 簡(jiǎn)單短語(yǔ) C. 素短語(yǔ) D. 終結(jié)符號(hào)17、設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Sx(其中xV*),則稱x是文法G的一個(gè) B 。A. 候選式 B

10、. 句型 C. 單詞 D. 產(chǎn)生式18、一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式19、文法GE：ETETTFTF Fa（E）該文法句型EF(ET)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的 B 。（ET） ET F F(ET)可選項(xiàng)有：A) 和 B) 和 C) 和 D) 20、若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子 A 。A.是無(wú)窮多個(gè) B.是有窮多個(gè) C.是可枚舉的 D.個(gè)數(shù)是常量21、詞法分析器用于識(shí)別 C 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式22、在語(yǔ)法分析處理中，F(xiàn)IRS

11、T集合、FOLLOW集合、SELECT集合均是 B 。A. 非終極符集 B.終極符集 C. 字母表 D. 狀態(tài)集23、編譯程序中語(yǔ)法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子24、在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是 A 。A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式25、在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目26、詞法分析的任務(wù)是（A）A識(shí)別單詞B.分析句子的含義C.識(shí)別句子D.生成目代碼27、代碼優(yōu)分的目的是（C）A.節(jié)省時(shí)間B.節(jié)省空間C.

12、節(jié)省時(shí)間和空間D.把編譯程序進(jìn)行等價(jià)交換28、代碼生成階段的主要任務(wù)是（C）A.把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B.把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C.把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D.把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言29、在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目30、一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式二、 是非判斷題1、正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。    （

13、×）2、如果一個(gè)文法是遞歸的，則其產(chǎn)生的語(yǔ)言的句子是無(wú)窮個(gè)。  （）3、文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。   （）4、一個(gè)LL( l)文法一定是無(wú)二義的。   （）5、在規(guī)范規(guī)約中用最左素短語(yǔ)來(lái)刻劃可歸約串。   （×）6、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。  （）7、編譯程序是對(duì)匯編程序的翻譯。            （×）8、計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)

14、語(yǔ)言只有解釋一種方式。 （×）9、在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。 （×）10、甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 （×）11、正則文法其產(chǎn)生式為Aàa，AàBb, A,BVN，a、bVT。 （）12、每個(gè)文法都能改寫為L(zhǎng)L(1)文法。 （×）13、遞歸下降法允許任一非終極符是直接左遞歸的。 （×）14、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 （）15、自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。 （×）16、LR法是自頂向下語(yǔ)法分析方法。 （

15、×）18、若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 （×）19、一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （）20、在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 （×）21、在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 （×）三、 名詞解釋題1、掃描遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2、短語(yǔ)：設(shè)GZ是給定文法, w=xuyV+，為該文法的句型,如果滿足下面兩個(gè)條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的短語(yǔ)。3、簡(jiǎn)單短語(yǔ)：設(shè)GZ是給定文法, w=xuyV+，為該文法的句型,如果滿足下面兩個(gè)條件: Z xU

16、y； U Þ u； 則稱句型xuy 中的子串u是句型xuy的簡(jiǎn)單短語(yǔ)（或直接短語(yǔ)）。4、句柄：一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄。5、語(yǔ)法分析：按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。RR6、活前綴：若S A 是文法G中的一個(gè)規(guī)范推導(dǎo)，G是G的拓廣文法，符號(hào)串是的前綴，則稱是G的，也是G的一個(gè)活前綴。其中 S'為文法開始符號(hào)?；颍嚎蓺w前綴的任意首部。7、可歸前綴：是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。8、LR(0)項(xiàng)目：把產(chǎn)生式右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱為相應(yīng)文法的一個(gè)LR(0)項(xiàng)目。9、語(yǔ)義規(guī)則：對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬

17、性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。10、翻譯方案：將屬性文法中的語(yǔ)義規(guī)則用花括號(hào) 括起來(lái)，插在產(chǎn)生式右部的合適地方，指明語(yǔ)義規(guī)則的計(jì)算次序，陳述一些細(xì)節(jié)，得到一種語(yǔ)義動(dòng)作與語(yǔ)法分析交錯(cuò)的表示方法，以表述語(yǔ)義動(dòng)作在語(yǔ)法分析過(guò)程中的執(zhí)行時(shí)刻，稱之為翻譯方案。11、后綴式： 一種把運(yùn)算量（操作數(shù)）寫在前面把算符寫在后面（后綴）的表示法。即 一個(gè)表達(dá)式E的后綴形式可以如下定義：(1) 如果E是一個(gè)變量或常量，則E的后綴式是E自身。(2) 如果E是E1 op E2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1 E2op，這里E1和E2分別為E1和E2的后綴式。(3) 如果E是（E1）形式的表達(dá)式，

18、則E1的后綴式就是E的后綴式。12、過(guò)程活動(dòng)：一個(gè)過(guò)程的活動(dòng)指的是該過(guò)程的一次執(zhí)行。就是說(shuō)，每次執(zhí)行一個(gè)過(guò)程體，產(chǎn)生該過(guò)程體的一個(gè)活動(dòng)。13、活動(dòng)記錄：為了管理過(guò)程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這樣一個(gè)連續(xù)的存儲(chǔ)塊稱為活動(dòng)記錄。14、活動(dòng)的生存期：指的是從執(zhí)行某過(guò)程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過(guò)程時(shí)調(diào)用其它過(guò)程花費(fèi)的時(shí)間。15、 基本塊的DAG：一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG。   (1)圖的葉結(jié)點(diǎn)（沒(méi)有后繼的結(jié)點(diǎn)）以一標(biāo)識(shí)符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)代表某變量

19、A的地址，則用addr（A）作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。   (2)圖的內(nèi)部結(jié)點(diǎn)（有后繼的結(jié)點(diǎn)）以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。   (3)圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。16、S-屬性文法：？什么是L-屬性文法？它們之間有什么關(guān)系？S-屬性文法是只含有綜合屬性的屬性文法。 17、L-屬性文法：L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式AàX1X2Xn，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj的一

20、個(gè)繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號(hào)X1,X2Xj-1的屬性；（2） A的繼承屬性。 18、語(yǔ)法制導(dǎo)翻譯：語(yǔ)法制導(dǎo)翻譯是對(duì)前后文無(wú)關(guān)文法的擴(kuò)充，即對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序，且在語(yǔ)法分析過(guò)程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作或調(diào)用相應(yīng)的語(yǔ)義子程序，完成相應(yīng)的語(yǔ)義分析和翻譯工作。19、詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照記法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示，送給語(yǔ)法分析程序。四、 簡(jiǎn)答計(jì)算題1、已知

21、文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開始符號(hào)（識(shí)別符號(hào)）是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VN。 找出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。答： 該文法的開始符號(hào)（識(shí)別符號(hào)）是E。該文法的終結(jié)符號(hào)集合VT=+、-、*、/、（、）、i。非終結(jié)符號(hào)集合VN=E、T、F。句型T+T*F+I的短語(yǔ)為i、T*F、第一個(gè)T、T+T*F+i;簡(jiǎn)單短語(yǔ)為i、T*F、第一個(gè)T;句柄為第一個(gè)T。2、已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語(yǔ)言是什么？ GS能否改寫為等價(jià)的正規(guī)文法？答： GS產(chǎn)生的語(yǔ)言是L(GS)=danbmn1,m0

22、。 GS能改寫為等價(jià)的正規(guī)文法,其改寫后的等價(jià)的正規(guī)文法GS為： SdA A aA|aB|a B bB|b3、簡(jiǎn)述DFA與NFA有何區(qū)別 答：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以若干個(gè)開始狀態(tài)，而DFA僅只一個(gè)開始狀態(tài)。另一方面，DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。4、試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)非確定的有窮自動(dòng)機(jī)（NFA）M是一個(gè)五元組：M=（K，S，P ）。其中:1. K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所

23、以也稱為輸入符號(hào)表；3. SK是一個(gè)非空初態(tài)集； 4. P是狀態(tài)轉(zhuǎn)換函數(shù)，是在K×*K的子集的映射，即，P: K×*2K ；表明在某狀態(tài)下對(duì)于某輸入符號(hào)可能有多個(gè)后繼狀態(tài)。5、為正規(guī)式（a|b）*a(a|b) 構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。答：a,baabÞ0126、給定下列自動(dòng)機(jī)，將其轉(zhuǎn)換為確定的自動(dòng)機(jī)。ddd··ddddstartdSADBCEGH注：帶號(hào)的結(jié)點(diǎn)為初始狀態(tài)； 帶號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)答：(1)消除邊，得到NFA：ddddd··ddddddd·SADBCEGH注：帶號(hào)的結(jié)點(diǎn)為初始狀態(tài)； 帶號(hào)的結(jié)點(diǎn)為

24、終止?fàn)顟B(tài)(2)確定化，得到DFA：d·d·SABCDEGHAABCEBCEBCDEHHGDG+SAABCEGDGHDHAABCEBCEBCEHDHHDHGGDGddd·dddd··SAAAHBCEADGADHA注：帶號(hào)的結(jié)點(diǎn)為初始狀態(tài)； 帶號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)G7、 給定下列自動(dòng)機(jī)：其中：開始狀態(tài)：0 終止?fàn)顟B(tài)：2aaÞa0bbb12(1)把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)DFA。 (2)給出此DFA的正則表達(dá)式。答：（1）： 有狀態(tài)矩陣如圖： a bÞ0 01 201 01 22 1 2 1 2a b Þ0 0,1 2 1

25、 2 2 1 2Þ-Þ02aaba101bbb極小化后：Þ02babb1a從而可得DFA如圖：（2）此DFA的正則表達(dá)式為： (aa*b½b)(b½ab)* 或 a*b（b½ab）*。4-13.消除下列文法GE的左遞歸。EE-TTTT/FFF( E )i答：消除文法GE的左遞歸后得到：ETEE -TETFTT/FTF( E )i8、在LL(1)分析法中,LL分別代表什么含義?答:第一個(gè)L代表從左到右的掃描，第二個(gè)L代表每次進(jìn)行最左推導(dǎo)。9、自頂向下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符串進(jìn)行匹配。如果

26、全部匹配成功，則表示開始符號(hào)可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號(hào)串是正確句子。10、自頂向下的缺點(diǎn)是什么？答：在推導(dǎo)過(guò)程中，如果對(duì)文法不做限制。那么產(chǎn)生式的選擇成為無(wú)根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點(diǎn)是不斷地回溯，大大影響速度。11、LL（1）文法的定義是什么？答：一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A,A；滿足SELECT(A )SELECT(A )=。其中，、不能同時(shí)。12、什么是文法的左遞歸？答：一個(gè)文法含有下列形式的產(chǎn)生式之一時(shí)：1)AA，AVN，V*2)AB，BA，A、BVN，、V* 則稱該文法

27、是左遞歸的。13、遞歸下降法的主要思想是什么？答：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語(yǔ)法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。14、自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號(hào)串入手，通過(guò)反復(fù)查找當(dāng)前句型的句柄（最左簡(jiǎn)單短語(yǔ)），并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來(lái)一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開始符號(hào)，表明分析成功。1 ZC S2 Cif E then3 SAE4 EEA5 EA6 Ai其中：Z、C、S、A、EVN ； if、then

28、、iVT15、給定文法GZ：a) 構(gòu)造此文法的LR(0)項(xiàng)目集規(guī)范族，并給出識(shí)別活前綴的DFA。b) 構(gòu)造其SLR（1）分析表。答：1.首先拓廣文法：在G中加入產(chǎn)生式0ZZ，然后得到新的文法G，再求G的識(shí)別全部活前綴的DFA：I0：Z.ZZ.C SC.if E thenI1：ZZ.I2：ZC .SS.AEA.iI3：Cif .E thenE.EAE.AA.iI4：ZC S.I5：SA.EI6：Ai.I7：Cif E .thenEE.AI9：SA.EE.EAE.AA.iI10：Cif E then.I11：EE.AA.iI12：SAE.EE.AI13：EEA.CSiAiiEAZI0I1I6I5I

29、2I3I7I9I12I13I11I10I8I4AtheniifEA2 Follow(Z)#Follow(C)iFollow(S)#Follow(E)#,thenFollow(A),# ,then 則可構(gòu)造SLR（1）分析表為：ACTIONGOTO0iftheni#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r416、 設(shè)有文法GS：SaAAAbAbI1:SS.I0:S.S S.aAI2:Sa.AA.AbA.baI3:SaA.AA.bAI4:AAb.Ab.bbS 求識(shí)別該文法所有

30、活前綴的DFA。答：(1).首先拓廣文法： 在G中加入產(chǎn)生式0.SS，然后得到新的文法G: 0.SS 1.SaA2.AAb3.Ab(2).再求G的識(shí)別全部活前綴的DFA：17、語(yǔ)法制導(dǎo)翻譯方法的基本思想是什么?答：在語(yǔ)法分析過(guò)程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義動(dòng)作進(jìn)行屬性計(jì)算，完成對(duì)輸入符號(hào)串的翻譯。18、在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b：f（c1,c2，ck），其中對(duì)于b的要求是什么？答：語(yǔ)義規(guī)則中的左部屬性變量b被規(guī)定為只能是下述兩種變量： 對(duì)應(yīng)產(chǎn)生式左部符號(hào)的綜合屬性變量； 對(duì)應(yīng)產(chǎn)生式右部符號(hào)的繼承屬

31、性變量。19、對(duì)于文法G(E):E®T|E+TT®F|T*FF®(E)|i1） 寫出句型(T*F+i)的最右推導(dǎo)并畫出語(yǔ)法樹。ETF(E)E+TFiTT*F2） 寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。答：1.）EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i) 2） 短語(yǔ)：(T*F+i), T*F+i, T*F, i直接短語(yǔ)：T*F, i句柄：T*F20、構(gòu)造下面文法的LL(1)分析表。S ® a B S | b A S | eA &#

32、174; b A A | aB ® a B B | b 答： 開始符號(hào)集合和后繼符號(hào)集合LL(1)分析表FirstFollowSa, b, e$Aa, ba, b, $Ba, ba, b, $ab$SS ® a B SS ® b A SS ® eAA ® aA ® b A ABB ® a B BB ® b五、 綜合題1、通過(guò)構(gòu)造識(shí)別活前綴的DFA和構(gòu)造分析表，來(lái)證明文法E ® E + id | id是SLR(1)文法。答：先給出接受該文法活前綴的DFA如下：E¢ ®·EE &

33、#174;·E + idE ®·idI0E¢ ® E·E ® E·+ idI1E ® id·I2Eid+E ® E +·idI3E ® E + id·I4id再構(gòu)造SLR分析表如下：狀態(tài) 動(dòng)作轉(zhuǎn)移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中沒(méi)有多重定義的條目，因此該文法是SLR(1)的。2、為下面文法構(gòu)造規(guī)范LR(1)分析表，畫出像教材上圖3.20這樣的狀態(tài)轉(zhuǎn)換圖就可以了。S ® V = E

34、| EV ® * E | idE ® V（2）上述狀態(tài)轉(zhuǎn)換圖有同心項(xiàng)目集嗎？若有，合并同心項(xiàng)目集后是否會(huì)出現(xiàn)動(dòng)作沖突？答：（1） 狀態(tài)轉(zhuǎn)換圖如下：S¢ ® · S, $ S ® · V = E, $S ® · E, $V ® · * E, =/$V ® · id, =/$E ® · V, $I0SEidV*S¢ ® S ·, $I1=S ® V · = E, $E ® V ·,

35、 $I2S ® E ·, $I3S ® V = E ·, $I9S ® V = · E, $E ® · V, $V ® · * E, $V ® · id, $I6EV ® id ·, =/$I5E ® V ·, =/$I8idV ® * · E, =/$E ® · V, =/$V ® · * E, =/$V ® · id, =/$I4*VEV ®

36、* E ·, =/$I7E ® V ·, $I10idV ® * · E, $E ® · V, $V ® · * E, $V ® · id, $I11*EV ® * E ·, $I13V ® id ·, $I12idVVS¢ ® · S, $ S ® · V = E, $S ® · E, $V ® · * E, =/$V ® · id, =/$E ® · V, $I0SEid