編譯原理答疑題

1、編譯原理答疑題1 .編譯程序的結(jié)構(gòu)是什么 ？答：編譯過程的六個階段的任務(wù)，再加上表格管理和出錯處理的工作可分別由幾個模塊或程序完成，它們分別稱作詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、 代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和出錯處理程序。2 . PL/0編譯程序的結(jié)構(gòu)是什么？答：由PL/0的EBNF可知，PL/0語言可看成是 PASCAL語言的子集，它的編譯程序是 一個編譯解釋執(zhí)行系統(tǒng)。PL/0的目標(biāo)程序為假想棧式計算機的匯編語言，與具體計算機無關(guān)。PL/0的編譯程序和目標(biāo)程序的解釋執(zhí)行程序都是用PASCAL語言書寫的，因此 PL/0語言可在配備PASCAL語言的任

2、何機器上實現(xiàn)。其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析程序和代碼生成程序都作為一個獨立的過程，當(dāng)語法分析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語法分析正確需生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生成程序。此外，用表格管理程序建立變量、常量和過程標(biāo)識符的說明與引用之間的信息聯(lián)系。用出錯處理程序?qū)υ~法和語法分析遇到的錯誤給出在源程序中出錯的位置和錯誤性質(zhì)。當(dāng)源程序編譯正確時，PL/0編譯程序自動調(diào)用解釋執(zhí)行程序，對目標(biāo)代碼進行解釋執(zhí)行，并按用戶程序要求輸入數(shù)據(jù)和輸出運行結(jié)果。3 .關(guān)系有哪些基本性質(zhì)？答：自反的 在集合X上的關(guān)系R,如對任意xCX,均有(x, x) C R,則稱關(guān)系R是自

3、 反的。非自反的在集合X上的關(guān)系R,如對任意xCX,均有(x, x)任IR,則稱關(guān)系R是非自反。對稱的 在集合X上的關(guān)系R,如果合(x, y) C R,便必有(y, x) C R,則稱關(guān)系R 是對 稱的。非對稱的在集合X上的關(guān)系R,如果有(x, y) CR叢xwy,便必有(y, x)任I R,則稱關(guān)系R是非對稱的。傳遞的 在集合X上的關(guān)系R,如果合(x, y) eR且(y, z) CR,必有(x, z) C R,則 稱關(guān)系R是傳遞的。4 .設(shè)有文法GI:I->I1/I0/Ia/Ic/a/b/c判斷下面符號串中哪些是該文法的句子.ab0 (2)a0c01 (3)aaa (4)bc10 (5

4、)aabc (6)bbca 答：錯誤(2)正確(3)正確 (4)正確 錯誤 (6)錯誤錯誤5 .給定文法G = (VN , VT , P, S),對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹)。這棵樹應(yīng)滿足那些條件？答：給定文法 G = (VN, VT, P, S),對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)機)。這棵樹滿足下列 4個條件：1 .樹中每個結(jié)點都有一個標(biāo)記，此標(biāo)記為VNUVT中的一個符號2 .根的標(biāo)記為文法的開始符3 .若一結(jié)點n至少有一個它自己除外的子孫，并且有標(biāo)記為A,則A 一定是非終結(jié)符4 .如果結(jié)點n的直接子孫，從左到右的次序是句a，界上，且分支結(jié)點的標(biāo)記分別為B

5、1、B2,，Bn,則 A-B1B2Bn一定是 P中的一個產(chǎn)生式。6.自下而上分析算法的基本思想是什么？答：從所給符號串x開始，在其中尋找與文法的某條規(guī)則右部相匹配的子串，并用該規(guī)則的左部取代此子串(即歸約)，重復(fù)此過程，步步向上歸約，最后試圖將符號串x歸約到文法的識別符號Z。如歸約成功，則符號串 x是文法的句子。7設(shè)有文法G:s:=Qc|c Q:kRb|b R:=Sa|a 試求 HARD(S),HARD(Q),HARD(R). 答：HARD(S尸S,Q,R,a,b,cHARD(Q尸S,Q,R,a,b,c HARD(R尸S,Q,R,a,b,c 8.用擴充的BNF范式表布下述文法以消去e規(guī)則：S:

6、=aABb|ab A:=Aab| e B:=Aa|a 解：S:=aABb|abA:=ab B:=Aa|a9.將詞法分析做為一個獨立的階段，把編譯過程的分析工作劃分成詞法分析和語法分析兩個階段主要的考慮因素是什么？答：1.使整個編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化。詞法分析比語法分析簡單的多，但 是由于源程序結(jié)構(gòu)上的一些細節(jié)，常使得識別單詞的工作甚為曲折和費時。例如，空白和注釋的處理；再比如對于FORTRAN那種受書寫格式限制的語言，需在識別單詞時進行特殊處理等等。如果統(tǒng)統(tǒng)合在語法分析時一并考慮，顯然會使得分析程序的結(jié)構(gòu)復(fù)雜得多。2 .編譯程序的效率會改進。大部分編譯時間是花費在掃描字符以把單詞符

7、號分離出來。把詞法分析獨立出來， 采用專門的讀字符和分離單詞的技術(shù)可大大加快編譯速度。另外，由于單詞的結(jié)構(gòu)可用有效的方法和工具進行描述和識別，進而可建立詞法分析程序的自動構(gòu)造工具。3 .增強編譯程序的可移植性。在同一個語言的不同實現(xiàn)中，或多或少地會涉及到與設(shè)備有關(guān)的特征，比如采用ASCII還是EBCDIC字符編碼。另外語言的字符集的特殊性的處理，一些專用符號，如PASCAL中的"T”的表示等等，都可置于詞法分析程序中解決而不影響編譯程序其它成分的設(shè)計。10 .轉(zhuǎn)換圖容易用程序?qū)崿F(xiàn)，最簡單的辦法是讓每個狀態(tài)結(jié)點對應(yīng)一小段程序。引進一組全 局變量和過程，將它們作為實現(xiàn)轉(zhuǎn)換圖的基本成分，這

8、些變量和過程是什么？ 答：(1)ch字符變量，存放最新讀進的源程序字符。(2)strToken字符數(shù)組，存放構(gòu)成單詞符號的字符串。(3)GetChar子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。(4)GetBC 子程序過程，檢查 ch中的字符是否為空白。若是，則調(diào)用 GetChar直至ch 中進人一個非空白字符。(5)Concat子程序過程，將ch中的字符連接到 strToken之后。例如，假定strToken原來的值為"AB",而ch中存放著'C',經(jīng)調(diào)用 Concat后，strToken的值就變?yōu)?quot;ABC"。(6)

9、IsLetter和IsDigit布爾函數(shù)過程，它們分別判斷ch中的字符是否為字母和數(shù)字。(7)Reserve整型函數(shù)過程，對strToken中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。(8)Retract子程序過程，將搜索指示器回調(diào)一個字符位置，將 ch置為空白字符。(9)InsertId整型函數(shù)過程，將 strToken中的標(biāo)識符插入符號表，返回符號表指針。(10)InsertConst整型函數(shù)過程，將 strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。這些函數(shù)和子程序過程都不難編制。使用它們能夠方便地構(gòu)造狀態(tài)轉(zhuǎn)換圖的對應(yīng)程序。一般來說，

10、可讓每個狀態(tài)結(jié)點對應(yīng)一程序段。11 .什么是正規(guī)式，正規(guī)式的遞歸定義是什么？答：正規(guī)式也稱正則表達式，也是表示正規(guī)集的工具。也是我們用以描述單詞符號的方便工 具。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。設(shè)字母表為匯，輔助字母表為匯'=，£,|,*,(,)(1) . £和都是匯上的正規(guī)式，它們所表示的正規(guī)集分別為&和中(2) .任意aC!2, a是匯上的一個正規(guī)式，它所表示的正規(guī)集為a(3) .若e1, e2都是匯上的一個正規(guī)式，它們所表示的正規(guī)集分別為 L(e1)和L(e2),那么e1|e2, e1 e2和厘，(e1)也都是正規(guī)式，它們所表示的正規(guī)集分別為

11、L(e1) U L(e2),L(e1) L(e2)和 口),L(e1)(4) .僅由有限次使用上述三步驟而定義的表達式才是匯上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是匯上正規(guī)集。12 .什么是有窮自動機？什么是確定的有窮自動機？答：有窮自動機(也稱有限自動機)作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī) 文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。有窮自動機分為兩類：確定的有窮自動機(Deterministic Finite Automata)和不確定的有窮自動機(Nondeterministic Finite Auto

12、mata),下面我們分別給出確定有窮自動機和不確定的有 窮自動機的定義，有關(guān)概念及不確定的有窮自動機的確定化，確定的有窮自動機的化簡等算法。確定的有窮自動機(DFA)一個確定的有窮自動機(DFA)是一個五元組：M= (K,匯，f, S, Z),其中(1) K是一個有窮集，它的每個元素稱為一個狀態(tài)；(2)匯是一個有窮字母表，它的每個元素稱為一個輸入字符，所以也稱匯為輸入符號字母 表；f是轉(zhuǎn)換函數(shù)，是在 KX匯一 K上映像，即，如f (耳，a)=幻(L CK,0ck), 就意味著，當(dāng)前狀態(tài)為 國，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài) 比，我們把處稱作耳的 一個后繼狀態(tài)；(4) S C K是唯一的一個初

13、態(tài)；(5)2仁玄，是終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。13 .正規(guī)式的構(gòu)造步驟是什么？答：我們把狀態(tài)轉(zhuǎn)換圖的概念拓廣，令每條弧可用一個正規(guī)式作標(biāo)記。 構(gòu)造步驟：第一步 在M的狀態(tài)轉(zhuǎn)換圖上加進兩個狀態(tài)，一個為 x, 一個為y。從x狀態(tài)出發(fā)，用 £弧連接到M的所有初始態(tài)；從 M的所有終止態(tài)出發(fā)，用 £弧連接到y(tǒng)狀態(tài)。形成一個與 M等價的M'。第二步 逐步消去M'中的所有狀態(tài)，直至只剩下 x和y狀態(tài)。在消結(jié)過程中，逐步用正 規(guī)式來標(biāo)記弧。消結(jié)的規(guī)則如下：最后x和y結(jié)點間的弧上的標(biāo)記則為所求的正規(guī)式Ro14 .舉例說明判斷LL(1)文法的步驟。答：S 一 ABS

14、 f bCA- £AfbB 一 £BfaDC f ADC f bD 一 aSD-c判別步驟：1 . 求出能推出£的非終結(jié)符首先建立一個以文法的非終結(jié)符個數(shù)為上界的一維數(shù)組，其數(shù)組元素為非終結(jié)符，對應(yīng)每一個非終結(jié)符有一標(biāo)志位，用來記錄能否推出8 ,其值有三種情況"未定"，"是"，"否"。例1所對應(yīng)數(shù)組X的內(nèi)容如表一所示。表一非終結(jié)符能否推出空的表計算能推出£的非終結(jié)符步驟如下:(1)將數(shù)組X中對應(yīng)每一個非終結(jié)符的標(biāo)記置初值為"未定”(2)掃描文法中的產(chǎn)生式 刪除所有右部含有終結(jié)符的產(chǎn)生式

15、，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)記值改為"否"，說明該非終結(jié)符不能推出£ o若某一非終結(jié)符的某一產(chǎn)生式右部為£ ,則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為”是”,并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。例中對應(yīng)非終結(jié)符A、B的標(biāo)志改為"是"。(3)掃描產(chǎn)生式右部的每一符號 若所掃描到的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志是"是"，則刪去該非終結(jié)符， 若這使產(chǎn)生式右部為空，則對產(chǎn)生式左部的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志改為"是"，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。 若所

16、掃描到的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志是"否"，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)的產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對應(yīng)的標(biāo)志改成"否"。(4)重復(fù)(3),直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對應(yīng)的特征再沒有改變 為止。由2)中得知例中對應(yīng)非終結(jié)符 D的標(biāo)志改為"否"。經(jīng)過上述2)中(a)、(b)兩步后文法中的產(chǎn)生式只剩下：S-AB C-AD也就是只剩下右部全是非終結(jié)符串的產(chǎn)生式。再由3)中的(a)步掃描到產(chǎn)生式 S-AB時，在數(shù)組中A、B對應(yīng)的標(biāo)志都為"是"，刪去后 S的右部變?yōu)榭?，所?S對

17、應(yīng)標(biāo)志置為"是"。最后由3)中的(b)掃描到產(chǎn)生式 C-AD時，其中，A對應(yīng)的標(biāo)志為"是"，D對應(yīng)的標(biāo)志是" 否"，刪去該產(chǎn)生式后，再無左部為C的產(chǎn)生式，所以 C的對應(yīng)標(biāo)志改成"否"。15 .如何計算FIRST集答：根據(jù)定義計算由 FIRST 集定義 FIRST ( a )=a| a => * a 3 , a V? ,”， 3CV*若 a => * s ,則規(guī)定 s FIRST( “)。對每一文法符號 XCV,計算FIRST(X)(a)若 XC Vt ,則 FIRST(X)=X(b)若 X C VN ,

18、且有產(chǎn)生式 X - a,aC VT ,則 aC FIRST(X)(C)若 XC VN ,且有產(chǎn)生式 X- e ,則 e C FIRST(X)(d)若 XC %, yi 丫2,YiC Vn ,而有產(chǎn)生式 X-Y1Y2Yn。當(dāng) Y1Y2 丫/ 者 B=> 'e 時，(其中 IWiWn),則 FIRST(Y1)- £ , FIRST(Y2)- £ ,FIRST 工-1 )- £ , FIRST(Yi)都包含在 FIRST(X)中。(e)當(dāng)(d)中所有 Yi=> * e(i=1, 2, .n),則FIRST(X)= FIRST(Y1) U FIRST(

19、Y2) UU FIRST(Yn) U £反復(fù)使用(a)-(e)步，直到每個符號的 FIRST集合不再增大為止16 . PL/ 0編譯程序?qū)φZ法錯誤的處理采用哪兩種辦法？答：(1)對于一些易于校正的錯誤，如丟了逗號、分號等，則指出出錯位置，并加以校正。校正的方式就是補上逗號或分號。(2)對某些錯誤，編譯程序難于確定校正的措施，為了使當(dāng)前的錯誤不致影響整個程序的 崩潰，把錯誤盡量局限在一個局部的語法單位中。這樣就需跳過一些后面輸入的單詞符號， 直到讀入一個能使編譯程序恢復(fù)正常語法分析工作的單詞為止。17 .解釋說明下列指令 LIT、LOD、STO、CAL、INT、JMP、JPC、OPR?

20、答：1.LIT :將常量值取到運行棧頂。2. LOD :將變量放到棧頂。3. STO:將棧頂?shù)膬?nèi)容送入某變量單元中。4. CAL :調(diào)用過程的指令。5. INT:為被調(diào)用的過程(或主程序)在運行棧中開辟數(shù)據(jù)區(qū)。6. JMP:無條件轉(zhuǎn)移指令。7. JPC：條件轉(zhuǎn)移指令。8. OPR:關(guān)系運算和算術(shù)運算指令。將棧頂和次棧頂?shù)膬?nèi)容進行運算，結(jié)果存放在次棧頂， 此外還可以是讀寫等特殊功能的指令。18 .解釋符號串聯(lián)結(jié)？答：設(shè)有符號串x和y,把y的符號寫在x的符號之后所得的符號串，叫做 x與y的聯(lián)結(jié), 記為xy。19 .什么是最左素短語？答：設(shè)有文法 GS,其句型的素短語是一個短語，它至少包含一個終結(jié)符

21、，并除自身外不 包含其他素短語。最左邊的素短語稱最左素短語。20 .簡述LR(1)項目集族的構(gòu)造？答:(1)構(gòu)造LR(1湮目集的閉包函藪.a)若I的任何項目都屬于CLOSUREDb)有項目AfQ. A 6，a屬于CLOSURED)，BY是文法中的產(chǎn)生式，0三¥*,b三FIRST。a)則Bf ¥.b也屬于CLOSURE(；】)中.c)重復(fù)垃直到CLO£URE( I)不再增大為止.(2)轉(zhuǎn)換函數(shù)的構(gòu)造LR(1)轉(zhuǎn)換函數(shù)的構(gòu)造與 LR(0)的相似，GO(I , X) = CLOSURE( J )其中I是LR(1)的項目集，X是文法符號：J= 任何形如A-aX. 3, a

22、的項目 | A-a.X3,a CI對文法G'的LR(1)項目集族的構(gòu)造仍以S'一. S, #為初態(tài)集的初始項目，然后對其求閉 包和轉(zhuǎn)換函數(shù)，直到項目集不再增大。也就是對狀態(tài)I經(jīng)過符號X后轉(zhuǎn)向狀態(tài)J,求出J的核后，對核求閉包即為 CLOSURE(J)。21 . L-屬性文法的定義是什么？答：一個屬性文法稱為 L-屬性文法，如果對于每個產(chǎn)生式A-X1X2Xn,其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是 Xj(1 wjwn)的一個繼承屬性且這個繼承屬性僅依賴 于：(1)產(chǎn)生式Xj的左邊符號X1, X2,，Xj-1的屬性；(2)A的繼承屬性。22 .要提高訪問符號表的效率和節(jié)省存儲空間，要考慮哪些問題？答：首先，要考慮程序設(shè)計語言的性質(zhì)， 它包含哪些語法成分， 應(yīng)該進行哪些語義真缺性檢 查等等；其次，不能離開支撐環(huán)境，如目標(biāo)機器的性能怎樣， 將借助符號表產(chǎn)生怎樣的目標(biāo) 代碼，編譯程序所依賴的操作，系統(tǒng)能提供哪些存儲、管理方式等等。23 .常見的符號表的結(jié)構(gòu)有哪些？答：常見的符號表結(jié)構(gòu)有：無序符號表：是按標(biāo)識符出現(xiàn)的順序建立符號表有序符號表：建表時，各標(biāo)識符名按字典順序排列于符號表中棧符號表：對于分析程序(或過程)嵌套結(jié)構(gòu)型程序設(shè)計語言，將其符號表設(shè)計為棧式符號表?？偸菑臈ｍ敿尤?；而查找則從棧頂向底檢查)。24 .什么是靜態(tài)存儲分配？答：在