編譯原理練習(xí)題

1、選擇題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) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的a. (1)(2)b. (1)c. (1)(2)(3)d.(2)(3)3、高級(jí)語(yǔ)言的語(yǔ)言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個(gè)階段，而解釋程序通常缺少(1)e 和 (1)b . 其中，(1)e的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高

2、效.與編譯系統(tǒng)相比，解釋系統(tǒng)d .解釋程序處理語(yǔ)言時(shí)，大多數(shù)采用的是b方法.(4)a就是一種典型的解釋型語(yǔ)言.(1)： a.優(yōu)化中間代碼生成b.目標(biāo)代碼生成C.詞法分析 d.語(yǔ)法分析e.代碼(2): a.b.比較簡(jiǎn)單，可移植性好，執(zhí)行速度快比較復(fù)雜，可移植性好，執(zhí)行速度快c.d.比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢 比較簡(jiǎn)單，可移植性好，執(zhí)行速度慢(3)： a.源程序命令被逐個(gè)直接解釋執(zhí)行b.先將源程序轉(zhuǎn)化為之間代碼，再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行 d.以上方法都可以：a. BASIC b. C c. FORTRAN d. PASCAL4、用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序

3、叫b .用不同語(yǔ)言編寫(xiě)的程序產(chǎn)生_b 后，可用連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是a.源程序b.目標(biāo)程序c.函數(shù)d.過(guò)程e.機(jī)器指令代碼f.模塊h.程序庫(kù)5、要在某一臺(tái)機(jī)器上為某種語(yǔ)言構(gòu)造一個(gè)編譯程序g.連接程序，必須掌握下述三方面的內(nèi)容 ：_cd_ C_a.匯編語(yǔ)言b.高級(jí)語(yǔ)言c.源語(yǔ)言d. 目標(biāo)語(yǔ)言e.程序設(shè)計(jì)方法f.編譯方法測(cè)試方法h.機(jī)器語(yǔ)言g.6、由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成(1)d，諸階段的工作往往是(2)d 進(jìn)行的.(1) a. 過(guò)程b.程序 c.批量d.遍a. 順序7、編譯過(guò)程中b.并行 c.成批d.穿插,語(yǔ)法分析器的任

4、務(wù)就是和說(shuō)明的(3)分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的8、編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后編譯 (3)連接(1)編輯9、編譯程序必須完成的工作有a(4)分析程序的結(jié)構(gòu),到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)_b_這幾步.運(yùn)行(1)詞法分析(4)代碼生成語(yǔ)法分析之間代碼生成(3)語(yǔ)義分析代碼優(yōu)化a.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、編譯程序是一種A.匯編程序B.翻譯程序C.解釋程序D.目標(biāo)程序11、按邏輯上劃分,A.語(yǔ)義分析編譯程序第二步工作是詞法分析B.C.語(yǔ)法分析D.代碼優(yōu)化12、通

5、常一個(gè)編譯程序中，不僅包含詞法分析, 代碼生成等五個(gè)部分，還應(yīng)包括 A.模擬執(zhí)行器B.解釋器語(yǔ)法分析，中間代碼生成,代碼優(yōu)化，目標(biāo)13、文法G所描述的語(yǔ)言是CC.表格處理和出錯(cuò)處理D.符號(hào)執(zhí)行器的集合。A. 文法G的字母表V中所有符號(hào)組成的符號(hào)串B. 文法G的字母表V的閉包V*中的所有符號(hào)串C.由文法的開(kāi)始符號(hào)推出的所有終極符串D.由文法的開(kāi)始符號(hào)推出的所有符號(hào)串14、喬姆斯基(Chomsky)把文法分為四種類(lèi)型，即0型、1型、是 BA.短語(yǔ)文法B. 正則文法 C.上下文有關(guān)文法D.15、文法 GN= (b , N, B, N, N b| bB,A. L(GN)=b IB. L(GN)=b2i

6、+1C. L(GN)=b16、一個(gè)句型中的最左可選項(xiàng)有:A.短語(yǔ) B.2型、3型。其中3型文法上下文無(wú)關(guān)文法Bt bN)，該文法所描述的語(yǔ)言是D. L(GN)=b稱(chēng)為該句型的句柄。2i+1簡(jiǎn)單短語(yǔ)C. 素短語(yǔ)D.17、設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào), 的一個(gè)B_ O如果終結(jié)符號(hào)Qx(其中x V),則稱(chēng)x是文法GA.候選式 B. 句型 C.單詞D.產(chǎn)生式18、一個(gè)上下文無(wú)關(guān)文法 G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào), 一個(gè)開(kāi)始符號(hào)，以及一組D OA.句子 B. 句型 C.單詞D.產(chǎn)生式19、文法GE:該文法句型 ( E+ T)可選項(xiàng)有：a 1( E)E+ F * (

7、E + T)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的E+ TF F *(E + T)20、A)和若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的B) 和 C) 和D)D.個(gè)數(shù)是常量21、詞法分析器用于識(shí)別C 。A.句子 B.句型 C.單詞D.產(chǎn)生式22、在語(yǔ)法分析處理中,A.非終極符集first集合、B.終極符集FOLLOW!合、select集 合均是字母表C.D.狀態(tài)集23、編譯程序中語(yǔ)法分析器接收以A為單位的輸入。24、25、26、27、29、30、A.單詞B.表達(dá)式C.產(chǎn)生式 D.句子在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是A.尋找句柄B.尋找句型C.B.消除遞歸D

8、.選擇候選式在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型A.句柄B.前綴C.活前綴DFA狀態(tài)。D. LR(0)項(xiàng)目詞法分析的任務(wù)是(A識(shí)別單詞代碼優(yōu)分的目的是(A.節(jié)省時(shí)間A)B.分析句子的含義C.識(shí)別句子D.生成目代碼C)B.節(jié)省空間C.節(jié)省時(shí)間和空間D.把編譯程序進(jìn)行等價(jià)交換代碼生成階段的主要任務(wù)是(C)A.把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B.把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C.把中間代碼變換成依賴(lài)具體機(jī)器的目標(biāo)代碼D.把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型A.句柄B.前綴C.活前綴的DFA狀態(tài)。D. LR(0)項(xiàng)目一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分,它們是：一組非

9、終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組A.句子B.句型C.單詞D.產(chǎn)生式是非判斷題1、正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。(V)2、如果一個(gè)文法是遞歸的，則其產(chǎn)生的語(yǔ)言的句子是無(wú)窮個(gè)。(V)3、文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。4、一個(gè)LL( I)文法一定是無(wú)二乂的。(V)5、在規(guī)范規(guī)約中用最左素短語(yǔ)來(lái)刻劃可歸約串。6、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。(V)7、編譯程序是對(duì)匯編程序的翻譯。(X)8、計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。9、在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。10、甲機(jī)上的某編譯程序在乙機(jī)上能直接使用

10、的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完(X)11、正則文法其產(chǎn)生式為 A a, A Bb, A,B S, a、b V12、 每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。13、遞歸下降法允許任一非終極符是直接左遞歸的。全相同。(V)(X)14、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(X)(V)15、自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。16、LR法是自頂向下語(yǔ)法分析方法。(X)(V)18、若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。19、一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。20、在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。21、在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。名詞解釋題1、掃描遍:

11、指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2、短語(yǔ)：設(shè)GZ是給定文法，w=xuy V+為該文法的句型，如果滿(mǎn)足下面兩個(gè)條件 Z馬xUy ; U左U ;則稱(chēng)句型xuy中的子串U是句型xuy的短語(yǔ)。3、簡(jiǎn)單短語(yǔ)：設(shè)GZ是給定文法，w=xuy V+為該文法的句型，如果滿(mǎn)足下面兩個(gè)條件 Z芻xUy ; U = u ;則稱(chēng)句型xuy中的子串U是句型xuy的簡(jiǎn)單短語(yǔ)(或直接短語(yǔ))。4、句柄：一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。5、語(yǔ)法分析:按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。6、活前綴：若SaA誦 3是文法G中的一個(gè)規(guī)范推導(dǎo)，G是 G的拓廣文法，符號(hào)串丫是a B的前綴，則

12、稱(chēng)丫是G的，也是G的一個(gè)活前綴。其中S為文法開(kāi) 始符號(hào)?；颍嚎蓺w前綴的任意首部。7、可歸前綴:是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。LR(0)項(xiàng)目：把產(chǎn)生式右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱(chēng)為相應(yīng)文法的一個(gè)LR(O)項(xiàng)目。9、語(yǔ)義規(guī)則:對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為語(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í)刻，稱(chēng)之為翻譯方案。11、后綴式：一種把運(yùn)算量(操作數(shù))寫(xiě)在前面把算符寫(xiě)在后面(后綴)的

13、表示法。即一個(gè)表達(dá)式E的后綴形式可以如下定義:(1)(3)12、過(guò)程活動(dòng):如果E是一個(gè)變量或常量，則 E的后綴式是E自身。如果E是 E1 opE2形式的表達(dá)式，這里op是任何二元操作符，則 巳op,這里B和E2分別為E和E2的后綴式。如果E( E1)形式的表達(dá)式，貝y E1的后綴式就是E的后綴式。E的后綴式為Ei產(chǎn)生該過(guò)程這樣一個(gè)連續(xù)的存一個(gè)過(guò)程的活動(dòng)指的是該過(guò)程的一次執(zhí)行。就是說(shuō)，每次執(zhí)行一個(gè)過(guò)程體, 體的一個(gè)活動(dòng)。13、活動(dòng)記錄:為了管理過(guò)程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊,儲(chǔ)塊稱(chēng)為活動(dòng)記錄。14、活動(dòng)的生存期:指的是從執(zhí)行某過(guò)程體第一步操作到最后一步操作之間的操作序，包括執(zhí)

14、行過(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)代表某變量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-

15、屬性文法？它們之間有什么關(guān)系？S-屬性文法是只含有綜合屬性的屬性文法。17、L- 屬性文法：L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式A X1X2 Xn,其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是 Xj 的一個(gè)繼承屬性，且該屬性?xún)H依賴(lài)于：（1）產(chǎn)生式Xj的左邊符號(hào)X1,X2, Xj-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ǔ)義分析和翻

16、譯工作。19、詞法分析按照記法規(guī)則從構(gòu)成源程序的詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào), 字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位, 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示, 送給語(yǔ)法 分析程序。四、 簡(jiǎn)答計(jì)算題1、已知文法 GE 為：EtT|E+T|E-TTtF|T*F|T/FFt（ E）|i 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合Vt和非終結(jié)符號(hào)集合Vn。 找出句型 T+T*F+i 的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。E。答：該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是 I 該文法的終結(jié)符號(hào)集合VT=+、-、*、/ 、（、）、 i 。非終結(jié)符號(hào)集合 VN=E、T、F 。 句型 T+T*F

17、+I的短語(yǔ)為i、T*F、第一個(gè) T、T+T*F+i; 簡(jiǎn)單短語(yǔ)為i、T*F、第一個(gè)T;句柄為第一個(gè)To2、已知文法 GS 為：StdABaA|aBt Bb| GS 產(chǎn)生的語(yǔ)言是什么？GS能否改寫(xiě)為等價(jià)的正規(guī)文法？答： GS產(chǎn)生的語(yǔ)言是 L(GS)=da nbm | n 1,m 0。GS能改寫(xiě)為等價(jià)的正規(guī)文法，其改寫(xiě)后的等價(jià)的正規(guī)文法GS / 為:S J dAA 7 aA|aB|aB 7 bB|b3、簡(jiǎn)述DFA與 NFA有何區(qū)別答：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面：一是NFA可以若干個(gè)開(kāi)始狀態(tài)，而 DFA僅只一個(gè)開(kāi) 始狀態(tài)。另一方面， DFA的映象M是從KX刀到K,而NFA的映象M是從KX刀到

18、K的子集, 即映象M將產(chǎn)生一個(gè)狀態(tài)集合(可能為空集)，而不是單個(gè)狀態(tài)。4、試給出非確定自動(dòng)機(jī)的定義。2, S, P ）。答：一個(gè)非確定的有窮自動(dòng)機(jī)(NFA) M是一個(gè)五元組：M=( K,其中：1. K是一個(gè)有窮集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；所以也稱(chēng)2為輸入符號(hào)表;2. 2是一個(gè)有窮字母表， 它的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)，3. S ( K是一個(gè)非空初態(tài)集；P: K X 2 *72K ;表明在4. P是狀態(tài)轉(zhuǎn)換函數(shù)，是在KX 2 *7 K的子集的映射，即，某狀態(tài)下對(duì)于某輸入符號(hào)可能有多個(gè)后繼狀態(tài)。5、為正規(guī)式(a|b ) *a(a|b)構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。答：a,b將其轉(zhuǎn)換為確定的自動(dòng)

19、機(jī)。d6、給定下列自動(dòng)機(jī),答：消除邊,得到NFAd十注：帶+號(hào)的結(jié)點(diǎn)為初始狀態(tài);十帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)+ CGHdddAd確定化，得到DFABCEBCE+一d+SAAABCEGABCEGBCEBCEDGGHDGDHHHDHDH注：帶+號(hào)的結(jié)點(diǎn)為初始狀態(tài);d(2)此DFA的正則表達(dá)式為：4-13.消除下列文法 GE的左遞歸。帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)(aab|b)(b或 a b (blab)。Tt T/F IFt ( E )答：消除文法GE的左遞歸后得到:Et teEt -T EI Tt ftTt /ft I ft (E) I i8、在LL(1)分析法中丄L分別代表什么含義？答：第一個(gè)L代表從左到

20、右的掃描，第二個(gè)L代表每次進(jìn)行最左推導(dǎo)。9、自頂向下分析思想是什么？如果全部匹配答：從開(kāi)始符出發(fā)導(dǎo)出句型并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符串進(jìn)行匹配。因此判定給定終結(jié)符號(hào)串是正確句子。成功，則表示開(kāi)始符號(hào)可推導(dǎo)出給定的終結(jié)符串。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)生式，At a ,At 3 ；滿(mǎn)足 SELECT(A t a ) A

21、 SELECT(A t 3 )=。其中，a、3 不能同時(shí)馬 。12、什么是文法的左遞歸？ 答：一個(gè)文法含有下列形式的產(chǎn)生式之一時(shí):1)AtA3 , A VN B V*2)AtB3 , BtAa , A、B VN, a、3 V* 則稱(chēng)該文法是左遞歸的。13、遞歸下降法的主要思想是什么?因?yàn)槲姆ㄟf歸相應(yīng)子程序也答：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫(xiě)出相應(yīng)語(yǔ)法分析子程序。遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱(chēng)此種方法稱(chēng)為遞歸子程序法或遞歸 下降法。14、自底向上分析法的原理是什么?答：在采用自左向右掃描，自底向上分析的前提下，該類(lèi)分析方法是從輸入符號(hào)串入手，通過(guò)反復(fù)查找當(dāng)前句型的句柄(最左簡(jiǎn)單短

22、語(yǔ))，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來(lái)一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開(kāi)始符號(hào)，表明分析成功。15、給定文法 GZ:1.Z t C S2.C t if Ethen3.St a =E4.E t e VA5.E t a6.A t i其中：Z、C、S A、E Vn ；if、then、=、V、 i Vta)構(gòu)造此文法的LR(0)項(xiàng)目集規(guī)范族，并給出識(shí)別活前綴的DFAACTIONGOTO0ifthe n=Vi#ZCSEA0S3121OK2S6453S784r 15S966r 6r 6r 67S10S118r 5r 5r 59S12810211S1312S11r 3134r4r

23、4Follow(A)則可構(gòu)造= = ,# , V ,then SLR (1)分析表為：b)構(gòu)造其SLR( 1 )分析表。答：1首先拓廣文法：在 G中加入產(chǎn)生式0. Z 7Z,識(shí)別全部活前綴的 DFA然后得到新的文法G,再求G的l0： Z 7 . ZZ 7. C SC 7 if E . thenC7. if E then li： Z 7 乙 12: Z 7 c . sS7.A= El9：E7 e . V AS7 A = . EE7 . E V AE7 . AA 7. i13： C7if . E thenE 7. E V A110：111：A7 . iC7 if E then .E 7. AA 7

24、. i|4： Z7c s.|5： S7A. = EI 12：I 13：2. Follow(Z)= #Follow(C)= iFollow(S)=#Follow(E)=#, V ,thenA7 . i S7 A = E.E7 e . V AE7 e V A.ACA112VAthenifAliol816、設(shè)有文法GS:St a aA t AbA t b求識(shí)別該文法所有活前綴的DFA答:(1).首先拓廣文法：在G中加入產(chǎn)生式0.S t S,然后得到新的文法0.S t S1.S t aA2.A t Ab(2).再求G的識(shí)別全部活前綴的 DFA17、語(yǔ)法制導(dǎo)翻譯方法的基本思想是什么G :答：在語(yǔ)法分析過(guò)

25、程中，每當(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)生式 At a都有一套與之相關(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)的繼承屬性變量。19、對(duì)于文法G(E):PT|E+TJ F|T*FJ(E)|i1) 寫(xiě)出句型(T*F+i)的最右推導(dǎo)并畫(huà)出語(yǔ)法樹(shù)。2) 寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。答：1.)匕 BF=(E) =(E+T

26、) =(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 T a B S | b A S | 名A T b A A | aB T a B B | b答：FirstFollowSa, b, z$Aa, ba, b, $Ba, ba, b, $開(kāi)始符號(hào)集合和后繼符號(hào)集合ab$SS T a B SS T b A SS T ZAA T aA T b A ABB T a B BB T bLL(1)分析表五、綜合題1、通過(guò)構(gòu)造識(shí)別活前綴的 DFA和構(gòu)造分析表，來(lái)證明文法 答：先給出接受該文法活前綴的 DFA如下：E T E + id | id 是 SLR(1)文法。再構(gòu)造SLR分析表如下:狀態(tài)動(dòng)作轉(zhuǎn)移id+$E0s211s3acc2r2r23s44r1r1表中沒(méi)有多重定義的條目，因此該文法是SLR(1)的。2、為下面文法構(gòu)造規(guī)范LR(1)分析表，畫(huà)出像教材上圖3.20這樣的狀態(tài)轉(zhuǎn)換圖就可以了。S T V = E | EV T * E | idE T V合并同心項(xiàng)目集后是否會(huì)出現(xiàn)動(dòng)作沖突?(2)上述狀態(tài)轉(zhuǎn)換圖有同心項(xiàng)目集嗎? 答：(1) 狀態(tài)轉(zhuǎn)換圖如下：SJ S T S