編譯練習(xí)題答案

一、填空題:1-01.編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析，之間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有表格處理和出錯處理.1-02.若源程序是用高級語言編寫的,目標(biāo)程序是機器語言程序或匯編程序,則其翻譯程序稱為編譯程序.1-03.編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼.1-04.翻譯程序是這樣一種程序,它能夠?qū)⒂眉渍Z言書寫的程序轉(zhuǎn)換成與其等價的用乙語言書寫的程序.1-05.對編譯程序而言,輸入數(shù)據(jù)是源程序,輸出結(jié)果是目標(biāo)程序.1-06.如果編譯程序生成的目標(biāo)程序是機器代碼程序,則源程序的執(zhí)行分為兩大階段:編譯階段和運行階段.如果編譯程序生成的目標(biāo)程序是匯編語言程序,則源程序的執(zhí)行分為三個階段:編譯階段,匯編階段和運行階段.1-07.若源程序是用高級語言編寫的，目標(biāo)程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序。1-08.一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。其中，詞法分析器用于識別單詞。1-09.編譯方式與解釋方式的根本區(qū)別為是否生成目標(biāo)代碼。2-01.所謂最右推導(dǎo)是指：任何一步αβ都是對α中最右非終結(jié)符進行替換的。2-02.一個上下文無關(guān)文法所含四個組成部分是一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式。2-03.產(chǎn)生式是用于定義語法成分的一種書寫規(guī)則。2-04.設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)＝{x│Sx,x∈VT*}。2-05.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx（其中x∈V*），則稱x是文法的一個句型。2-06.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈VT*),則稱x是文法的一個句子。3-01.掃描器的任務(wù)是從源程序中識別出一個個單詞符號。4-01.語法分析最常用的兩類方法是自上而下和自下而上分析法。4-02.語法分析的任務(wù)是識別給定的終極符串是否為給定文法的句子。4-03.遞歸下降法不允許任一非終極符是直接左遞歸的。4-04.自頂向下的語法分析方法的關(guān)鍵是如何選擇候選式的問題。4-05.遞歸下降分析法是自頂向上分析方法。4-06.自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。5-01.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的開始符號。5-02.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行直接歸約，力求歸約到文法的開始符號。5-03.簡單優(yōu)先方法每次歸約當(dāng)前句型的句柄，算符優(yōu)先方法每次歸約當(dāng)前句型的最左素短語，二者都是不斷移進輸入符號，直到符號棧頂出現(xiàn)可歸約串的尾，再向前找到可歸約串的頭，然后歸約。5-04.在LR（0）分析法的名稱中，L的含義是自左向右的掃描輸入串，R的含義是最左歸約，0的含義是向貌似句柄的符號串后查看0個輸入符號。5-05.在SLR（1）分析法的名稱中，S的含義是簡單的。6-01.所謂屬性文法是一個屬性文法是一個三元組：A＝（G，V，F(xiàn)），一個上下文無關(guān)文法G；一個屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個斷言與文法的某產(chǎn)生式相聯(lián)。6-02.綜合屬性是用于“自下而上”傳遞信息。6-03.繼承屬性是用于“自上而下”傳遞信息。6-04.終結(jié)符只有綜合屬性，它們由詞法分析器提供。7-01.在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部A錯誤和B部分錯誤.a.語法

b.語義

c.語用

d.運行8-01.符號表中的信息欄中登記了每個名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。8-02.一個過程相應(yīng)的DISPLAY表的內(nèi)容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址。9-01.一個過程相應(yīng)的DISPLAY表的內(nèi)容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址。9-02.常用的兩種動態(tài)存貯分配辦法是棧式動態(tài)分配和堆式動態(tài)分配。9-03.常用的參數(shù)傳遞方式有傳地址，傳值和傳名。10-01.局部優(yōu)化是局限于一個基本塊范圍內(nèi)的一種優(yōu)化。10-02.代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運行速度和如何減少目標(biāo)程序運行時所需的空間。二、單選題:1-10.一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括(1)c.其中,(2)b和代碼優(yōu)化部分不是每個編譯程序都必需的.詞法分析器用于識別(3)c,語法分析器則可以發(fā)現(xiàn)源程序中的(4)d.(1)

a.模擬執(zhí)行器

b.解釋器

c.表格處理和出錯處理

d.符號執(zhí)行器(2)

a.語法分析

b.中間代碼生成

c.詞法分析

d.目標(biāo)代碼生成(3)

a.字符串

b.語句

c.單詞

d.標(biāo)識符(4)

a.語義錯誤

b.語法和語義錯誤

c.錯誤并校正

d.語法錯誤1-11.程序語言的語言處理程序是一種(1)a.(2)b是兩類程序語言處理程序,他們的主要區(qū)別在于(3)d.(1)

a.系統(tǒng)軟件

b.應(yīng)用軟件

c.實時系統(tǒng)

d.分布式系統(tǒng)(2)

a.高級語言程序和低級語言程序

b.解釋程序和編譯程序c.編譯程序和操作系統(tǒng)

d.系統(tǒng)程序和應(yīng)用程序(3)

a.單用戶與多用戶的差別

b.對用戶程序的查錯能力c.機器執(zhí)行效率

d.是否生成目標(biāo)代碼1-12.匯編程序是將a翻譯成b,編譯程序是將c翻譯成d.a.匯編語言程序b.機器語言程序c.高級語言程序d.a或者be.a或者cf.b或者c1-13.下面關(guān)于解釋程序的描述正確的是b.(1)解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼(2)解釋程序適用于COBOL和FORTRAN語言(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的

a.(1)(2)

b.(1)

c.(1)(2)(3)

d.(2)(3)1-14.高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個階段，而解釋程序通常缺少(1)e和(1)b.其中，(1)e的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效.與編譯系統(tǒng)相比，解釋系統(tǒng)(2)d.解釋程序處理語言時,大多數(shù)采用的是(3)b方法.(1):a.中間代碼生成

b.目標(biāo)代碼生成

c.詞法分析

d.語法分析

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

b.目標(biāo)程序

c.函數(shù)

d.過程

e.機器指令代碼

f.模塊

g.連接程序

h.程序庫1-16.要在某一臺機器上為某種語言構(gòu)造一個編譯程序,必須掌握下述三方面的內(nèi)容:c,d,f.a.匯編語言

b.高級語言

c.源語言

d.目標(biāo)語言e.程序設(shè)計方法

f.編譯方法

g.測試方法

h.機器語言1-17.由于受到具體機器主存容量的限制,編譯程序幾個不同階段的工作往往被組合成(1)d,諸階段的工作往往是(2)d進行的.(1)a.過程

b.程序

c.批量

d.遍(2)a.順序

b.并行

c.成批

d.穿插1-18.編譯程序與具體的機器a,與具體的語言a.a.

有關(guān)

b.無關(guān)1-19.使用解釋程序時,在程序未執(zhí)行完的情況下，a重新執(zhí)行已執(zhí)行過的部分.a.也能

b.不可能1-20.編譯過程中,語法分析器的任務(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)1-21.編譯程序是一種常用的b軟件.a.

應(yīng)用

b.系統(tǒng)1-22.編寫一個計算機高級語言的源程序后,到正式上機運行之前，一般要經(jīng)過b這幾步.(1)編輯

(2)編譯

(3)連接

(4)運行a.(1)(2)(3)(4)

b.(1)(2)(3)

c.(1)(3)

d.(1)(4)1-23.編譯程序必須完成的工作有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)(3)(4)(6)

e.(1)(2)(3)(5)(6)1-24.“用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運行”這種說法a.a.不正確

b.正確1-25.把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由b完成的.a.編譯器

b.匯編器

c.解釋器

d.預(yù)處理器1-26.編譯程序生成的目標(biāo)程序b是機器語言的程序.a.

一定

b.不一定1-27.編譯程序生成的目標(biāo)程序b是可執(zhí)行的程序.a.

一定

b.不一定1-28．編譯程序是一種B。A.匯編程序B.翻譯程序C.解釋程序D.目標(biāo)程序1-29．按邏輯上劃分，編譯程序第二步工作是C。A.語義分析B.詞法分析C.語法分析D.代碼優(yōu)化1-30．通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括C。A.模擬執(zhí)行器

B.解釋器

C.表格處理和出錯處理

D.符號執(zhí)行器2-06．已知語言L={xnyyn|n>=1}，則下述文法中，D可以產(chǎn)生語言L。A1.Z→xZy|xAy|yB1.A→xAy2.A→xAy|x2.A→xC1.Z→AyBD1.Z→xAy2.A→xA|x2.A→xAy|y3.B→yB|y2-07．文法G所描述的語言是C的集合。A.文法G的字母表V中所有符號組成的符號串B.文法G的字母表V的閉包V*中的所有符號串C.由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串2-08．喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是B。A.短語文法B.正則文法C.上下文有關(guān)文法D.上下文無關(guān)文法2-09.文法G[N]=（，{N，B}，N，{N→b│bB，B→bN}），該文法所描述的語言是C。A.L(G[N])={bi│i≥0}B.L(G[N])={b2i│i≥0}C.L(G[N])={b2i+1│i≥0}D.L(G[N])={b2i+1│i≥1}2-10．一個句型中的最左B稱為該句型的句柄?？蛇x項有：A.短語B.簡單短語C.素短語D.終結(jié)符號2-11．設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈V*),則稱x是文法G的一個B。A.候選式B.句型C.單詞D.產(chǎn)生式2-12．一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組D。A.句子B.句型C.單詞D.產(chǎn)生式2-13.文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）該文法句型E＋F﹡(E＋T)的簡單短語是下列符號串中的B。①（E＋T）②E＋T③F④F﹡(E＋T)可選項有：A)①和③B)②和③C)③和④D)③2-14．若一個文法是遞歸的，則它所產(chǎn)生的語言的句子A。A.是無窮多個B.是有窮多個C.是可枚舉的D.個數(shù)是常量2-15．文法的二義性和語言的二義性是兩個A的概念。A不同B相同C無法判斷D不存在3-02．詞法分析器用于識別C。A.句子B.句型C.單詞D.產(chǎn)生式4-07.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是B。A.非終極符集B.終極符集C.字母表D.狀態(tài)集4-08.編譯程序中語法分析器接收以A為單位的輸入。A.單詞B.表達式C.產(chǎn)生式D.句子5-06．在自底向上的語法分析方法中，分析的關(guān)鍵是D。A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式5-07.在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型C的DFA狀態(tài)。A.句柄B.前綴C.活前綴D.LR(0)項目6.DFA和NFA的區(qū)別在于C。A．初始狀態(tài)個數(shù)要求不同B．轉(zhuǎn)換函數(shù)要求不同C．A和B兩個的合并10.對于允許過程遞歸調(diào)用的語言，在它的目標(biāo)程序的運行環(huán)境中至少應(yīng)該使用B。A.靜態(tài)分配B.動態(tài)分配C.存儲分配D內(nèi)存分配11.文法G[Z]：ZBb,AAe,Ae,BAf,其中e和f為終極符，#是輸入串的結(jié)束符，F(xiàn)OLLOW（A）為A。A．{e,f}B．{e}C．{f}D．{#}12.在編譯中，中間代碼生成的常用方法有D。A．LR法B．遞歸法C．最優(yōu)匹配法D．語法制導(dǎo)翻譯方法13.下列關(guān)于標(biāo)識符和名字的敘述中，正確的為C。A.標(biāo)識符有一定的含義B.名字是一個沒有意義的字符序列C.名字有確切的屬性D.都不對14.已知語言L={anbbn|n>=1}，則下述文法中，B可以產(chǎn)生語言L。A．1.Z→aZb|aAb|bB．1.A→aAb2.A→aAb|b2.A→bC．1.Z→AbBD．1.Z→aAb2.A→aA|a2.A→aAb|b3.B→bB|b15文法的二義性和語言的二義性是兩個C的概念。A．不存在B．相同C．不同D．無法判斷三、是非題(下列各題，你認(rèn)為正確的，請在題干的括號內(nèi)打“√”，錯的打“×”。)1-31.計算機高級語言翻譯成低級語言只有解釋一種方式。（×）1-32.在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。（×）1-34.甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。（×）2-15.正則文法其產(chǎn)生式為Aa，ABb,A,B∈VN，a、b∈VT。（√）4-09.每個文法都能改寫為LL(1)文法。（×）4-10.遞歸下降法允許任一非終極符是直接左遞歸的。（√）5-08.算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。（√）5-09.自底而上語法分析方法的主要問題是候選式的選擇。（×）5-10.LR法是自頂向下語法分析方法。（×）5-11.簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。（×）5-12.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（×）5-13.一個句型的句柄一定是文法某產(chǎn)生式的右部。（√）7-02.數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。（√）8-03.在程序中標(biāo)識符的出現(xiàn)僅為使用性的。（×）9-04.對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。（×）9-05.在程序中標(biāo)識符的出現(xiàn)僅為使用性的。（×）10-03.僅考慮一個基本塊，不能確定一個賦值是否真是無用的。（√）10-04.削減運算強度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。（×）10-05.在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提和削減運算強度。（√）(×)6.活前綴不包含句柄中的任何符號。(√)9.對任一編譯程序來說，產(chǎn)生中間代碼不一定是必要的。(×)13.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(×)16.活前綴就是任何句型的有用前綴。(×)17.編譯程序在優(yōu)化時可能要用到源程序中的注釋。(×)18.目標(biāo)代碼就只有可立即執(zhí)行的機器語言代碼一種。(×)19.任何句型都存在一個規(guī)范推導(dǎo)，任何句子也都存在一個規(guī)范推導(dǎo)。(×)22.中間代碼優(yōu)化的目的是檢查源語言的各種錯誤。(√)23.解釋與編譯方式的區(qū)別是解釋沒有生成目標(biāo)代碼。(×)24.目標(biāo)代碼的生成與目標(biāo)機無關(guān)，與宿主機有關(guān)。四、名詞解釋1-35.掃描遍____指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語——設(shè)G[Z]是給定文法,w=xuy∈V+，為該文法的句型,如果滿足下面兩個條件:①ZxUy；②Uu；則稱句型xuy中的子串u是句型xuy的短語。2-17.簡單短語——設(shè)G[Z]是給定文法,w=xuy∈V+，為該文法的句型,如果滿足下面兩個條件:①ZxUy；②Uu；則稱句型xuy中的子串u是句型xuy的簡單短語（或直接短語）。2-18.句柄——一個句型中的最左簡單短語稱為該句型的句柄。2-19.答：規(guī)范推導(dǎo)——如果在任一步推導(dǎo)vTw中，都是對符號串v的最右非終結(jié)符進行替換，則稱其為規(guī)范推導(dǎo)。*2-21.答：語言——L（G[Z]）={x|ZTx，x∈VT*}。*4-11.語法分析－－按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。4-12.選擇符集合SELECT－－給定上下文無關(guān)文法的產(chǎn)生式A→α,A∈VN,α∈V*,若αε,則SELECT(A→α)=FIRST(α),其中如果αε，則SELECT(A→α)=FIRST(α\ε)∪FOLLOW(A),FIRST(α\ε)表示FIRST(α)的非{ε}元素。RR5-14.活前綴——若S′αAωαβω是文法G′中的一個規(guī)范推導(dǎo)，G′是G的拓廣文法，符號串γ是αβ的前綴，則稱γ是G的，也是G′的一個活前綴。其中S'為文法開始符號?；颍嚎蓺w前綴的任意首部。RR5-15.可歸前綴——是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。5-16.LR(0)項目——把產(chǎn)生式右部某位置上標(biāo)有圓點的產(chǎn)生式稱為相應(yīng)文法的一個LR(0)項目。5-17.算符優(yōu)先文法——設(shè)有一不含ε產(chǎn)生式的算符文法G，如果對任意兩個終結(jié)符對a，b之間至多只有、和三種關(guān)系中的一種成立，則稱G是一個算符優(yōu)先文法。5-18.最左素短語——設(shè)有文法G[S],其句型的素短語是一個短語,它至少包含一個終結(jié)符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。6-05.語義規(guī)則——對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。6-06.翻譯方案——將屬性文法中的語義規(guī)則用花括號{}括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計算次序，陳述一些細(xì)節(jié)，得到一種語義動作與語法分析交錯的表示方法，以表述語義動作在語法分析過程中的執(zhí)行時刻，稱之為翻譯方案。6-07.語法制導(dǎo)翻譯——為文法中每個產(chǎn)生式配備一組語義規(guī)則，并且在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動作）進行翻譯的辦法稱作語法制導(dǎo)翻譯。7-03.后綴式——一種把運算量（操作數(shù)）寫在前面把算符寫在后面（后綴）的表示法。即一個表達式E的后綴形式可以如下定義：如果E是一個變量或常量，則E的后綴式是E自身。如果E是E1opE2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1’E2’op，這里E1’和E2’分別為E1和E2的后綴式。如果E是（E1）形式的表達式，則E1的后綴式就是E的后綴式。7-04.四元式——一個四元式是一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為op、arg1、arg2及result。域op包含一個代表運算符的內(nèi)部碼。9-06.活動答：一個過程的活動指的是該過程的一次執(zhí)行。就是說，每次執(zhí)行一個過程體，產(chǎn)生該過程體的一個活動。9-07.活動記錄答：為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，這樣一個連續(xù)的存儲塊稱為活動記錄。9-08.活動的生存期答：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時調(diào)用其它過程花費的時間。10-02.答：基本塊——源程序中只有一個入口和一個出口的順序執(zhí)行的代碼段。10-07.基本塊的DAG。答：一個基本塊的DAG是一種其結(jié)點帶有下述標(biāo)記或附加信息的DAG。

(1)圖的葉結(jié)點（沒有后繼的結(jié)點）以一標(biāo)識符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量A的地址，則用addr（A）作為該結(jié)點的標(biāo)記。通常把葉結(jié)點上作為標(biāo)記的標(biāo)識符加上下標(biāo)0，以表示它是該變量的初值。

(2)圖的內(nèi)部結(jié)點（有后繼的結(jié)點）以一運算符作為標(biāo)記，表示該結(jié)點代表應(yīng)用該運算符對其后繼結(jié)點所代表的值進行運算的結(jié)果。

(3)圖中各個結(jié)點上可能附加一個或多個標(biāo)識符，表示這些變量具有該結(jié)點所代表的值。五、簡答題：2-19什么是句子？什么是語言?答：設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈VT*),則稱x是文法的一個句子。設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)＝{x│Sx,x∈VT*}。2-20.已知文法G[E]為：E→T|E+T|E-TT→F|T*F|T/FF→（E）|i①該文法的開始符號（識別符號）是什么？②請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。③找出句型T+T*F+i的所有短語、簡單短語和句柄。解：①該文法的開始符號（識別符號）是E。②該文法的終結(jié)符號集合VT={+、-、*、/、（、）、i}。非終結(jié)符號集合VN={E、T、F}。③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個T。2-21.已知文法G[S]為：S→dABA→aA|aB→Bb|ε①G[S]產(chǎn)生的語言是什么？②G[S]能否改寫為等價的正規(guī)文法？解：①G[S]產(chǎn)生的語言是L(G[S])={danbm│n≥1,m≥0}。②G[S]能改寫為等價的正規(guī)文法,其改寫后的等價的正規(guī)文法G[Sˊ]為：Sˊ→dAA→aA|aB|aB→bB|b2-22.設(shè)有語言L(G)={adaR|a∈(a,b)*,aR為a之逆}，試構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法G。解：根據(jù)題義，可知aR為a之逆的含義就是句子中的符號a、b以d為中心呈左右對稱出現(xiàn)；由于a∈(a,b)*，所以a、b的個數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法G[S]為：S→aSa|bSb|d2-23.證明下面文法G[N]是二義性文法。G[N]：N→SE∣ES→SD∣DE→0∣2∣10D→0∣1∣2答：10是文法G[N]的一個句子，并且有兩個不同的最右推導(dǎo)。（1）1S=>E=>10（2）S=>SE=>S0=>D0=>10因此說明此文法有二義性。3-03．簡述DFA與NFA有何區(qū)別?答：DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以若干個開始狀態(tài)，而DFA僅只一個開始狀態(tài)。另一方面，DFA的映象M是從K×∑到K，而NFA的映象M是從K×∑到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。3-04.試給出非確定自動機的定義。答：一個非確定的有窮自動機（NFA）M是一個五元組：M=（K，Σ，f，S，Z）。其中:1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號表；3.f是狀態(tài)轉(zhuǎn)換函數(shù)，是在K×Σ*→K的子集的映射，即，f:K×Σ*→2K；表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；4.S﹙K是一個非空初態(tài)集；5.Z﹙K是一個終態(tài)集（可空）。3-05.為正規(guī)式（a|b）*a(a|b)構(gòu)造一個等價的確定的有限自動機。解答：a,ba,baab0123-06.給定下列自動機，將其轉(zhuǎn)換為確定的自動機。dddεd··dddd＋startd―εSADBCEGH注：帶＋號的結(jié)點為初始狀態(tài)；帶―號的結(jié)點為終止?fàn)顟B(tài)―――＋解答：(1)消除ε邊，得到NFA：――＋――ddddd··dddd＋―ddd·＋SADBCEGH注：帶＋號的結(jié)點為初始狀態(tài)；帶―號的結(jié)點為終止?fàn)顟B(tài)(2)確定化，得到DFA：＋―d·＋―d·SABCDEGHAABCEBCEBCDEHHGDG+[SA][A][BCE][G][DG][H][DH][A][A][BCE][BCE][BCE][H][DH][H][DH][G][G][DG]――――ddd·ddd＋―d··＋SAAAHBCEADGADHA注：帶＋號的結(jié)點為初始狀態(tài)；帶―號的結(jié)點為終止?fàn)顟B(tài)G3-07.給定下列自動機：其中：開始狀態(tài)：0其中：開始狀態(tài)：0終止?fàn)顟B(tài)：2aaa0bbb12(1)把此自動機轉(zhuǎn)換為確定自動機DFA。(2)給出此DFA的正則表達式。解答：（1）：有狀態(tài)矩陣如圖：abab001201012－21212ab00,1212－212從而可得DFA如圖：--02aaba101bbb極小化后：02babb1a（2）此DFA的正則表達式為：(aa*bb)(bab)*或a*b（bab）*。4-13.消除下列文法G[E]的左遞歸。E→E-T∣TT→T/F∣FF→(E)∣i解答：消除文法G[E]的左遞歸后得到：E→TE’E’→-TE’∣εT→FT’T’→/FT’∣εF→(E)∣i4-14.在LL(1)分析法中,LL分別代表什么含義?答:第一個L代表從左到右的掃描，第二個L代表每次進行最左推導(dǎo)。4-15.自頂向下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個符號一個符號地與給定終結(jié)符串進行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。4-16.自頂向下的缺點是什么？答：在推導(dǎo)過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點是不斷地回溯，大大影響速度。4-17.LL（1）文法的定義是什么？答：一個上下文無關(guān)文法是LL(1)文法的充分必要條件是每個非終結(jié)符A的兩個不同產(chǎn)生式，A→α,A→β；滿足SELECT(A→α)∩SELECT(A→β)=Ф。其中，α、β不能同時ε。4-18.什么是文法的左遞歸？答：一個文法含有下列形式的產(chǎn)生式之一時：1)A→Aβ，A∈VN，β∈V*2)A→Bβ，B→Aα，A、B∈VN，α、β∈V*則稱該文法是左遞歸的。4-19.遞歸下降法的主要思想是什么？答：對每個非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因為文法遞歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。5-19.自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復(fù)查找當(dāng)前句型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來一步步地進行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。5-20.簡單優(yōu)先方法基本思想是什么？答：簡單優(yōu)先方法基本思想是首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后在利用這種關(guān)系，通過比較兩個相鄰的符號之間的優(yōu)先順序來確定句型的“句柄”并進行歸約。5-21.三種優(yōu)先關(guān)系的定義是什么？答：三種優(yōu)先關(guān)系的定義是：1.sisj當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U→…SiSj…2.sisj當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U→…SiW…的生產(chǎn)式，且有WSj3.sisj當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U→…VW…的生產(chǎn)式,且有VSi和WSj5-22.如何確定簡單優(yōu)先文法的句柄？答：設(shè)S1S2…Sn是簡單優(yōu)先文法的規(guī)范句型，其子串SiSi+1…Sj是滿足下列條件的最左子串：Si-1Si

SiSi+1……Sj-1Sj

SjSj+1則SiSi+1…Sj定是S1S2…Sn的句柄。Z→CZ→CSC→ifEthenS→A＝EE→E∨AE→AA→i其中：Z、C、S、A、E∈VN；if、then、＝、∨、i∈VT構(gòu)造此文法的LR(0)項目集規(guī)范族，并給出識別活前綴的DFA。構(gòu)造其SLR（1）分析表。解答：1.首先拓廣文法：在G中加入產(chǎn)生式0．Z′→Z，然后得到新的文法G′，再求G′的識別全部活前綴的DFA：II0：Z′→.ZZ→.CSC→.ifEthenI1：Z′→Z.I2：Z→C.SS→.A＝EA→.iI3：C→if.EthenE→.E∨AE→.AA→.iI4：Z→CS.I5：S→A.＝EI6：A→i.I7：C→ifE.thenE→E.∨AI9：S→A＝.EE→.E∨AE→.AA→.iI10：C→ifEthen.I11：E→E∨.AA→.iI12：S→A＝E.E→E.∨AI13：E→E∨A.CCSiAi＝iEAZI0I1I6I5I2I3I7I9I12I13I11I10I8I4A∨then∨iifEA2．Follow(Z)＝{#}Follow(C)＝{i}Follow(S)＝{#}Follow(E)＝{#,∨,then}Follow(A)＝{＝,#,∨,then}則可構(gòu)造SLR（1）分析表為：ACTIONGOTO0ifthen＝∨i#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r45-24.設(shè)有文法G[S]：SS→aAA→AbA→bI1:I1:S′→S.I0:S′→.SS→.aAI2:S→a.AA→.AbA→.baI3:S→aA.A→A.bAI4:A→Ab.A→b.bbS解答：(1).首先拓廣文法：在G中加入產(chǎn)生式0.S′→S，然后得到新的文法G′:0.S0.S′→S1.S→aA2.A→Ab3.A→b(2).再求G′的識別全部活前綴的DFA：6-07.語法制導(dǎo)翻譯方法的基本思想是什么?答：在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進行推導(dǎo)或歸約時，就執(zhí)行該產(chǎn)生式所對應(yīng)的語義動作進行屬性計算，完成對輸入符號串的翻譯。6-08.何謂“語法制導(dǎo)翻譯”?答：在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動作）進行翻譯的辦法稱作語法制導(dǎo)翻譯。6-09.在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A→a都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b：＝f（c1,c2…，ck），其中對于b的要求是什么？答：語義規(guī)則中的左部屬性變量b被規(guī)定為只能是下述兩種變量：對應(yīng)產(chǎn)生式左部符號的綜合屬性變量；對應(yīng)產(chǎn)生式右部符號的繼承屬性變量。6-10.給定文法及相應(yīng)的翻譯方案：SS→bTc{print(“0”)}S→a{print(“1”)}T→R{print(“2”)}R→R/S{print(“3”)}R→S{print(“4”)}為該文法設(shè)計翻譯方案，使句型bR/bTc/bSc/ac經(jīng)該翻譯方案翻譯后,輸出串：SbSbcRRS/SaRSRSRbcT//TbcT解：給出句型bR/bTc/bSc/ac的語法樹如右圖：則對于句型bR/bTc/bSc/ac,處理完該句型后輸出是：4245130341246-10.給定文法及相應(yīng)的翻譯方案：)EE→E+T{print(“5”)}E→T{print(“4”)}T→T*F{print(“3”)}T→F{print(“2”)}F→(E){print(“1”)}F→i{print(“0”)}EETFEETF()ETiTTFFTFT()+**EET+解：給出句型T+(T*(F+T)*i)的語法樹如右圖：則對于句型T+(T*(F+T)*i),處理完該句型后輸出是：4245130341247-05.常用的中間語言種類有哪幾種？答：有逆波蘭式、三地址代碼、抽象語法樹和DAG。7-06.給定下列中綴式，分別寫出等價的逆波蘭表示(運算符優(yōu)先級按常規(guī)理解)。(1)―a≤b∧a＞0∨b＜0解答：逆波蘭表示為：a―b≤a0＞∧b0＜∨。(2)a―(a*b―d)*(a―b*d)/d解答：逆波蘭表示為：aab*d―abd*―*d/―。(3)―a＋b≤0∨a＜0∧(a―b)>2解答：逆波蘭表示為：a―b＋0≤a0＜ab―2＞∧∨。(4)a*(b*c―a)≤b＋c∧d解答：逆波蘭表示為：abc*a―*bc＋≤d∧。7-07給定下列中綴式，分別寫出等價的后綴式和四元式(運算符優(yōu)先級按常規(guī)理解)。(1)(a＋b*c)/(a＋b)－d解：后綴式：abc*+ab+/d-四元式：①（*，b,c,t1）②(+,a,t1,t2)③(+,a,b,t3④(/,t2,t3,t4)⑤(-,t4,d,t5)(2)x+y≤z∨a>0解：后綴式：xy+z≤a0>∨四元式：①（+，x,y,t1）②(≤,t1,z,t2)③(>,a,0,t3④(∨,t2,t3,t4)(3)x＋y≤0∨(x―y)>2解：后綴式：xy+0≤xy-2>∨四元式：①（+，x,y,t1）②(≤,t1,0,t2)③(-,x,y,t3④(>,t3,2,t4)⑤(∨,t2,t4,t5)(4)a:=(b*c―a)*a解：后綴式：abc*a-a*:=四元式：①（*，b,c,t1）②(-,t1,a,t2)③(*,t2,a,t3④(:=,t3,,a)8-04.符號表的組織方式有哪幾種？答：一個編譯程序?qū)Ψ柋淼目傮w組織可有三種選擇：第一種：把屬性種類完全相同的那些符號組織在一起，構(gòu)造出表項是分別為等長的多個符號表。這樣組織的最大優(yōu)點是每個符號表的屬性個數(shù)和結(jié)構(gòu)完全相同。則表項是等長的，并且表項中的每個屬性欄都是有效的，對于單個符號表示來說，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點是一個編譯程序?qū)⑼瑫r管理若干個符號表，增加了總體管理的工作量和復(fù)雜度。而且對各類符號共同屬性的管理必須設(shè)置重復(fù)的運行機制。使得符號表的管理顯得臃腫。

第二種：把所有語言中的符號都組織在一張符號表中。組成一張包括了所有屬性的龐大的符號表。這樣組織方式的最大優(yōu)點是總體管理非常集中單一，且不同種類符號的共同屬性可一致地管理和處理。這樣組織所帶來的缺點是，由于屬性的不同，為完整表達各類符號的全部屬性必將出現(xiàn)不等長的表項，以及表項中屬性位置的交錯重疊的復(fù)雜情況，這就極大地增加了符號表管理的復(fù)雜度。為使表項等長且實現(xiàn)屬性位置的唯一性，可以把所有符號的可能屬性作為符號表項屬性。這種組織方法可能有助于降低符號表管理復(fù)雜性，但對某個具體符號，可能增加了無用的屬性空間，從而增加了空間開銷。第三種：折衷方式是根據(jù)符號屬性相似程度分類組織成若干張表，每張表中記錄的符號都有比較多的相同屬性。這種折衷的組織方式在管理復(fù)雜性及時空效率方面都取得折衷的效果，并且對復(fù)雜性和效率的取舍可由設(shè)計者根據(jù)自己的經(jīng)驗和要求及目標(biāo)系統(tǒng)的客觀環(huán)境和需求進行選擇和調(diào)整。8-05.在整個編譯期間，對于符號表的操作有哪些？答：在整個編譯期間，對于符號表的操作大致可歸納為五類：·對給定名字，查詢此名是否已在表中；·往表中填入一個新的名字；·對給定名字，訪問它的某些信息；·對給定名字，往表中填寫或更新它的某些信息；·刪除一個或一組無用的項。8-06.符號表的作用有哪些？答：在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識符的屬性信息，這些信息集中反映了標(biāo)識符的語義特征屬性。起主要作用是：①收集符號屬性；②上下文語義的合法性檢查的依據(jù)；③作為目標(biāo)代碼生成階段地址分配的依據(jù)。9-09．運行時存儲器的劃分是怎樣的？答：運行時存儲器的劃分如下圖所示。目標(biāo)代碼目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆10-07.簡述優(yōu)化的原則是什么？答：編譯程序提供的對代碼優(yōu)化必須遵循的原則是：等價原則。經(jīng)過優(yōu)化后不應(yīng)改變程序運行的結(jié)果。有效原則。使優(yōu)化后所產(chǎn)生的目標(biāo)