編譯原理期末考試

PAGEPAGE一、填空（每題2分，共20分）1．從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（執(zhí)行性）語(yǔ)句和（說(shuō)明性）語(yǔ)句兩大類(lèi)。2．掃描器的任務(wù)是從（源程序）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。3．所謂最左派生是指（任何一歩α→β都是對(duì)α中最左非終結(jié)符進(jìn)行替換的）。4．語(yǔ)法分析最常用的兩類(lèi)方法是（自頂向下）和（自底向上）分析法。5．一個(gè)上下文無(wú)關(guān)文法所含的四個(gè)組成部分是（一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)、一個(gè)開(kāi)始符號(hào)、一組產(chǎn)生式）。6．所謂語(yǔ)法制導(dǎo)翻譯方法是（為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序）。7．LR分析法中的兩種沖突是（移入—?dú)w約）和（歸約—?dú)w約）。8．產(chǎn)生式是用于定義（語(yǔ)法范疇）的一種書(shū)寫(xiě)規(guī)則。9．屬性定義中有兩種性質(zhì)的屬性，分別是（繼承屬性）和（綜合屬性）。10．常用的兩種動(dòng)態(tài)存儲(chǔ)分配方法是（棧式動(dòng)態(tài)分配）和（堆式動(dòng)態(tài)分配）。11.所謂最右推導(dǎo)是指：任何一步αβ都是對(duì)α中最右非終結(jié)符進(jìn)行替換的。12.一個(gè)過(guò)程相應(yīng)的DISPLAY表的內(nèi)容為（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址。）13.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（類(lèi)型、種屬、所占單元大小、地址）等等。14．運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過(guò)程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、…、直至最外層(主程序，0層)等每層過(guò)程的最新活動(dòng)記錄的起始地址。通過(guò)DISPLAY表可以訪問(wèn)其外層過(guò)程的變量。二、名詞解釋?zhuān)款}3分，共15分）編譯器預(yù)處理：對(duì)于一個(gè)編譯器，如果要處理的輸入是對(duì)原編譯器的輸入的擴(kuò)充，就把輸入中的擴(kuò)充部分轉(zhuǎn)換成原輸入的形式，然后把其結(jié)果交給原編譯器處理，也就是把擴(kuò)展的部分轉(zhuǎn)換成標(biāo)準(zhǔn)形式，這就是編譯器預(yù)處理LL（K）文法――（P89）歧義文法――(p71)正則表達(dá)式――(P47)：每個(gè)正則表達(dá)式定義一個(gè)正則集。若用RE表示∑上的正則表達(dá)式，并用L(RE)所表示的正則集，則RE的語(yǔ)法定義和相應(yīng)正則集如下面所述，其中A和B表示正則表達(dá)式，并且а表示字母表∑中的任一符號(hào)。1?∈RE,L?={34A∈RE,L6A?B∈RE,LＡ屬性文法――(P260)三、簡(jiǎn)答題（每題5分，共15分）設(shè)有L（G）＝{a給出它的正則表達(dá)式。構(gòu)造識(shí)別該語(yǔ)言的DFA。生成語(yǔ)言L（G）＝{ap解：G(3)文法為S->ACA->aAc|BB->bB|bC->aCb|ab它是喬姆斯基2型文法已知文法G（S）：S→a|b|(T)T→T,S|S寫(xiě)出句子（（a,b）,b）的規(guī)范規(guī)約過(guò)程及每一步的句柄。解：句型規(guī)約句柄（（a,b）,b）（（S,b）,b）S->a a((T,b),b) T->S S((T,S),b) S->b b((T),b) T->T,S T,S(S,b) S->(T) (T)(T,b) T->S S(T,S) S->b b(T) T->T,S T,SS S->(T) (T)四、計(jì)算題（每題10分，共20分）已知文法G（E）E→T|E+TT→F|T*FF→(E)|i給出句型α＝（T*F+i）的最右派生及畫(huà)出語(yǔ)法樹(shù)。解：1.(4分)ETTTFT(E)T(E+T)T(E+F)T(E+i)T(T+i)T(T*F+i)2.(4分)短語(yǔ)：(T*F+i),T*F+i,T*F,i直接短語(yǔ)：T*F,i句柄：T*F素短語(yǔ)：T*F,i2．說(shuō)明下面的文法不是SLR(1)文法，并重寫(xiě)一個(gè)等價(jià)的SLR(1)文法。 SMa|bMc|dc|bda Md解：S’S SMa|bMc|dc|bda MdS’S’.SS.MaS.bMcS.dcS.bdaM.dSb.McSb.daM.dSbd.aMd.bd 因?yàn)閍是M的后繼符號(hào)之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn)歸約沖突。 等價(jià)的SLR(1)文法是 Sda|bdc|dc|bda五、設(shè)計(jì)題（每題15分，共30分）1．下面的文法定義語(yǔ)言L={anbncm|m,n1} SDC DaDb|ab CCc|c解：語(yǔ)法制導(dǎo)的定義如下： SDC ifD.lengthC.lengththenprint(“error”) Dab D.length:=1 DaD1b D.length:=D1.length+1 Cc C.length:=1 CC1c C.length:=C1給出文法G（L）的翻譯模式，它分別計(jì)算字符串中0與1的個(gè)數(shù)。（要求ANTLR代碼）S→L.L|LL→BLL→εB→0|1GrammerL01@members{intn0;intn1;}Start:{n0=0;n1=0;}j{system.out.println(n0);system.out.println(n1);};j:‘0’|‘1’|‘a(chǎn)’;ws:(‘’|‘\t’|‘\n’|‘\r’)+{skip();};名詞解釋

1．遍－－指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2．無(wú)環(huán)路有向圖(DAG)－－如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。3．語(yǔ)法分析－－按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。4．短語(yǔ)－－令G是一個(gè)文法。S劃文法的開(kāi)始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有SαAδ且AB，則稱β是句型αβ相對(duì)非終結(jié)符A的短語(yǔ)。5．后綴式－－一種把運(yùn)算量寫(xiě)在前面，把算符寫(xiě)在后面的表示表達(dá)式的方法。簡(jiǎn)述題1、寫(xiě)出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示及三元式序列。2、已知文法G(S)

S→a|∧|(T)

T→T，S|S

寫(xiě)出句子((a，a)，a)的規(guī)范歸約過(guò)程及每一步的句柄。3、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？4、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？答案：1、逆波蘭表示：abc*＋ab＋/d－

三元式序列：

①(*，b，c)

②(＋，a，①)

③(＋，a，b)

④(/，②，③)

⑤(－，④，d)3、優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。

三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。4、目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。

應(yīng)著重考慮的問(wèn)題：(1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；

(3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。計(jì)算題：1、寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。(5分)

解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D(5分)

2、設(shè)文法G(S)：

S→(L)|aS|a

L→L，S|S

(1)消除左遞歸和回溯；

(2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；

(3)構(gòu)造預(yù)測(cè)分析表。

解：(1)

S→(L)|aS’

S’→S|ε

L→SL’

L’→SL’|ε

評(píng)分細(xì)則：消除左遞歸2分，提公共因子2分。

(2)FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{)}

FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}

3、Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa＞0thena：＝a－1

elseb：＝b＋1

End；

翻譯成四元式序列。(7分)

解：

(1)(j＞，a，0，5)

(2)(j，－，－，3)

(3)(j＜，b，0，5)

(4)(j，－，－，15)

(5)(＋，×，1，T1)

(6)(：＝，T1，－，×)

(7)(j≥，a，0，9)

(8)(j，－，－，12)

(9)(－，a，1，T2)

(10)(：＝，T2，－，a)

(11)(j，－，－，1)

(12)(＋，b，1，T3)

(13)(：＝，T3，－，b)

(14)(j，－，－，1)

(15)

評(píng)分細(xì)則：控制結(jié)構(gòu)4分，其它3分。

4、已知文法G(E)

E→T|E＋T

T→F|T*F

F→(E)|i

(1)給出句型(T*F＋i)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；

(2)給出句型(T*F＋i)的短語(yǔ)、素短語(yǔ)。(7分)

解：(1)最右推導(dǎo)：

ETF(E)(E＋T)(E＋F)(E＋i)

(T＋i)(T*F＋i)

(2)短語(yǔ)：(T*F＋i)，T*F＋i，T*F，i(2分)

素短語(yǔ)：T*F,i(1分)

5、設(shè)布爾表達(dá)式的文法為

E→E(1)∨E(2)

E→E(1)∧E(2)

E→i

假定它們將用于條件控制語(yǔ)句中，請(qǐng)

(1)改寫(xiě)文法，使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯和實(shí)現(xiàn)回填；

(2)寫(xiě)出改寫(xiě)后的短個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作。(6分)

解：(1)E0→E(1)

E→E0E(2)

EA→E(1)

E→EAE(2)

E→i(3分)

(2)E→E(1)

{BACKPATCH(E(1)·FC，NXQ)；

E0·TC：＝E(1)·TC}

E→E0E(2)

{E·FC：＝E(2)·FC；

E·TC：＝MERG(E0·TC，E(2)·TC)}

EA→E(1)

{BACKPATCH(E(1)·TC，NXQ)；

E0·FC：＝E(1)·FC}

E→EAE(2)

{E·TC：＝E(2)·TC；

E·FC：＝MERG(EA·FC，E(2)·FC}

E→i

{E·TC：＝NXQ；E·FC：＝NXQ＋1；

GEN(jn2，entry(i)，－0)；

GEN(j，－，－，0)(3分)

6、設(shè)有基本塊

T1：＝2

T2：＝10/T

T3：＝S－R

T4：＝S＋R

A：＝T2*T4

B：A

T5：＝S＋R

T6：＝T3*T5

B：＝T6

(1)畫(huà)出DAG圖；

(2)假設(shè)基本塊出口時(shí)只有A，B還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。(6分)

解：(1)DAG：

(2)優(yōu)化后的四元式

T3：＝S－R

T4：＝S＋R

A：＝5*T4

B：＝T3＋T4(3分)

例題3若正規(guī)表達(dá)式r=(a|b|c)(0|1)*，則L(r)中有__D__個(gè)元素。（12）A．12

B．18

C．6

D．無(wú)窮解析：本題考察的是程序的語(yǔ)言的組成句子與文法之間的關(guān)系；正規(guī)表達(dá)式r=(a|b|c)(0|1)*表示的是a,b,c中的任意一個(gè)與0、1串的連接，由于0、1串的長(zhǎng)度和組成是不固定的，所以整個(gè)句子的數(shù)據(jù)就是不固定的，也就是說(shuō)語(yǔ)言L(r)的組成元素是無(wú)窮的。

試題4：編譯器和解釋器是兩種高級(jí)語(yǔ)言處理程序，與編譯器相比，

B。編譯器對(duì)高級(jí)語(yǔ)言源程序的處理過(guò)程可以劃分為詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等幾個(gè)階段：其中，代碼優(yōu)化和C并不是每種編譯器都必需的。詞法分析的作用是識(shí)別源程序中的

B；語(yǔ)法分析中的預(yù)測(cè)分析法是

B的一種語(yǔ)法分析方法；編譯器在

C階段進(jìn)行表達(dá)式的類(lèi)型檢查及類(lèi)型轉(zhuǎn)換。（13）A、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度慢

B、解釋器參與運(yùn)行控制，程序執(zhí)行的速度慢

C、解釋器參與運(yùn)行控制，程序執(zhí)行的速度快

D、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度快（14）

A、詞法分析

B、語(yǔ)法分析

C、中間代碼生成

D、語(yǔ)義分析(15)

A、字符串

B、單詞

C、標(biāo)識(shí)符

D、語(yǔ)句(16)

A、自左至右

B、自頂向下

C、自底向上

D、自右至左(17)

A、詞法分析

B、語(yǔ)法分析

C、語(yǔ)義分析

D、目標(biāo)代碼生成例題5：假設(shè)某程序語(yǔ)言的文法如下：S→a|b|(T)T→TdS|S其中，VT={a,b,d,(,)}，VN={S,T}，S是開(kāi)始符號(hào)。考查該文法，稱句型(Sd(T)db)是S的一個(gè)A。其中B是句柄；C是素短語(yǔ)；D是該句型的直接短語(yǔ)；E是短語(yǔ)。A：①最左推導(dǎo)

②最右推導(dǎo)

③規(guī)范推導(dǎo)

④推導(dǎo)B：①S

②b

③(T)

④Sd(T)C：①S

②b

③(T)

④Sd(T)D：①S

②S,(T),b

③S,(T),TdS,b

④(Sd(T)db)E：①(Sd(T)db)

②d(T)

③Td

④Sd(T)d此句型的語(yǔ)法樹(shù)如下所示：

S(T)（T

d

S）（T

d

S

b）（S

（T））

從語(yǔ)法樹(shù)我們可以看出，短語(yǔ)就是位于同一個(gè)非終端結(jié)點(diǎn)的所有葉子結(jié)點(diǎn)，比如S、Sd(T)、Sd(T)db就是是相對(duì)于T的短語(yǔ)，b、(T)、(Sd(T)db)是相對(duì)于S的短語(yǔ)。而直接短語(yǔ)則進(jìn)一步要求這些葉子結(jié)點(diǎn)的非終端結(jié)點(diǎn)是它們的直接父結(jié)點(diǎn)。因此可以S、(T)、b都是該句型的直接短語(yǔ)。語(yǔ)法樹(shù)上最左的直接短語(yǔ)就是句柄，本題中是S。

所謂素短語(yǔ)是指這樣一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且除它自身之外不再含任何更小的素短語(yǔ)。最左素短語(yǔ)則指處于句型最左邊的那個(gè)素短語(yǔ)。

最左推導(dǎo)是指任何一步推導(dǎo)過(guò)程σ→β，都是對(duì)σ中的最左非終結(jié)符進(jìn)行替換。因此，在語(yǔ)法樹(shù)中也很容易看出，如果語(yǔ)法樹(shù)中的只有最左的非終結(jié)符結(jié)點(diǎn)（包括各級(jí)結(jié)點(diǎn)）具有其子樹(shù)，則它就是最左推導(dǎo)。最右推導(dǎo)與之類(lèi)似，最右推導(dǎo)也稱規(guī)范推導(dǎo)。本題從語(yǔ)法推導(dǎo)樹(shù)可以看出，既不是最左推導(dǎo)也不是最右推導(dǎo)，就是一般的推導(dǎo)。A：④

B：①

C：③

D：②

E：①1、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。正確

2、數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。正確

3、僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。正確

4、每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。不正確5、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。不正確一、回答下列問(wèn)題：(30分)1．什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？解答：S-屬性文法是只含有綜合屬性的屬性文法。（2分）L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式AàX1X2…Xn，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj的一個(gè)繼承屬性，且該屬性僅依賴于：產(chǎn)生式Xj的左邊符號(hào)X1,X2…Xj-1的屬性；A的繼承屬性。（2分）S-屬性文法是L-屬性文法的特例。（2分）2．什么是句柄？什么是素短語(yǔ)？一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。（3分）素短語(yǔ)是這樣的一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符并且不包含更小的素短語(yǔ)。（3分）3．劃分程序的基本塊時(shí)，確定基本塊的入口語(yǔ)句的條件是什么？解答：（1）程序第一個(gè)語(yǔ)句，或（2）能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或（3）緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。4．(6分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過(guò)程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、…、直至最外層(主程序，0層)等每層過(guò)程的最新活動(dòng)記錄的起始地址。通過(guò)DISPLAY表可以訪問(wèn)其外層過(guò)程的變量。5．(6分)對(duì)下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本塊出口的活躍變量，R0和R1是可用寄存器答：LDR0，BMULR0，CLDR1，EADDR1，F(xiàn)ADDR0，R1MULR0，2STR0，H二、設(shè)S={0，1}上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。(8分)答：構(gòu)造相應(yīng)的正規(guī)式：(0|1)*1(0|1)(3分)NFA:(2分)1110432eeee11043200確定化：(3分)I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}0143210010043210011三、(6分)寫(xiě)一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)={anbmambn|m,n≥1}。答：文法G(S):S?aSb|BB?bBa|ba四、對(duì)于文法G(E):(8分)E?T|E+TT?F|T*FF?(E)|iETF(EETF(E)E+TFiTT*F2.寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)、句柄和素短語(yǔ)。答：1.(4分)ETTTFT(E)T(E+T)T(E+F)T(E+i)T(T+i)T(T*F+i)2.(4分)短語(yǔ)：(T*F+i),T*F+i,T*F,i直接短語(yǔ)：T*F,i句柄：T*F素短語(yǔ)：T*F,i五、設(shè)文法G(S)：(12分)構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。(12分)答：(6分)FIRSTVT(S)={i，+，)，(}FIRSTVT(A)={+，)，(}FIRSTVT(B)={)，(}LASTVT(S)={i，+，*，(}LASTVT(A)={+，*，(}LASTVT(B)={*，(}優(yōu)先關(guān)系表:(3分)i+()*i><<<+>><<>(>>>)<<<*>>>優(yōu)先函數(shù):(3分)i+()*f26616g14661六、設(shè)某語(yǔ)言的do-while語(yǔ)句的語(yǔ)法形式為(9分)S?doS(1)WhileE其語(yǔ)義解釋為：真真假S(1)的代碼E的代碼針對(duì)自下而上的語(yǔ)法分析器，按如下要求構(gòu)造該語(yǔ)句的翻譯模式：(1)寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；(2)寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。答：(1).適合語(yǔ)法制導(dǎo)翻譯的文法(3分)G(S):R?doU?RS(1)WhileS?UE(2).(6分)R?do{R.QUAD:=NXQ}U?RS(1)While{U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN,NXQ)}S?UE{BACKPATCH(E.TC,U.QUAD);S.CHAIN:=E.FC}答案二：(1)S?doM1S(1)WhileM2EM?ε(3分)(2) M?ε{M.QUAD:=NXQ}(6分) S?doM1S(1)WhileM2E {BACKPATCH(S(1).CHAIN,M2.QUAD);BACKPATCH(E.TC,M1.QUAD);S.CHAIN:=E.FC }七、(8分)將語(yǔ)句if(A<X)ù(B>0)thenwhileC>0doC:=C+D翻譯成四元式。答：100(j<，A，X，102)101(j，-，-，109)102(j>，B，0，104)103(j，-，-，109)104(j>，C，0，106)105(j，-，-，109)106(+，C，D，T1)107(:=，T1，-，C)108(j，-，-，104)109八、(10分)設(shè)有基本塊如下：T1:=S+RT2:=3T3:=12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫(huà)出DAG圖；T1,T5,B3T24ST1,T5,B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7答：(1)DAG如右圖：(6分)(2)四元式序列：(4分) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4九、(9分)設(shè)已構(gòu)造出文法G(S)：S?BBB?aBB?b的LR分析表如下ACTIONGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab，請(qǐng)給出LR分析過(guò)程(即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過(guò)程)。答：步驟 狀態(tài) 符號(hào) 輸入串0 0 # abab#1 03 #a bab#2 034 #ab ab#3 038 #aB ab#4 02 #B ab#5 026 #Ba b#6 0267 #Bab #7 0269 #BaB #8 025 #BB #9 01 #S # acc二、（10分）設(shè)有文法G[A]:A?iB*e

B?SB|e

S?[eC]|.i

C?eC|e

判定該文法是否為L(zhǎng)L(1)文法？若是則給出它的LL(1)分析表，否則說(shuō)明理由。解：先計(jì)算各個(gè)產(chǎn)生式的Predict集：

Predict(A->iB*e)={i};

Predict(B->SB)={[,.}

Predict(B->e)={*}

Predict(S->[eC])={[}

Predict(S->.i)={.}

Predict(C->eC)={e}

Predict(C->e)={]}

因?yàn)镻redict集沒(méi)有沖突，所以是LL(1)文法。

LL(1)分析表如下：

i*e[].A->iB*e->e

B

->SB->SBS

->[eC]

->.iC

->eC

->e

三、（15分）設(shè)有文法G[S]:

S?LaR|R

L?bR|c

R

?

L

判斷該文法是否為L(zhǎng)R(1)文法。若是則給出它的LR(1)狀態(tài)機(jī)以及LR分析表。5． 已知文法G[S]：

S→S；G│G

G→G(T)│H

H→a│(S)

T→T+S│S

找出句型：a(T+S)；H；(S)的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解：短語(yǔ)共有7個(gè)：a(T+S);H;(S)

a(T+S);H

a(T+S)

T+S

(S)

H

a簡(jiǎn)單短語(yǔ)４個(gè)：a,T+S,H,(S)句柄：a。6． 已知文法G[S]為：

S→AB|bC A→b|λ

B→aD|λ C→AD|b

D→aS|c

對(duì)其每一個(gè)非終級(jí)符求First集和Follow集。解：First(S)

={b,a,λ}

First(A)={b,λ}

First(B)={a,λ}

First(C)={b,a,c}

First(D)={a,c}

Follow(S)

={#}

Follow(A)={a,c,#}

Follow(B)={#}

Follow(C)={#}

Follow(D)={#}編譯程序在邏輯上由哪幾部分組成？答：六個(gè)階段:詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,中間代碼優(yōu)化和目標(biāo)代碼生成。2.文法G[<S>]的產(chǎn)生式為：

<S>→a|b|(<R>)

<T>→<S>c<T>|<S>

<R>→<T>

1）構(gòu)造句型（bc<S>c<T>）的推導(dǎo)樹(shù)，并指出該句型的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄。

2）若句柄存在，求下述符號(hào)串的句柄。

a)((<S>c(b)))

b)(<S>)

c)(a)

d)<S>c<T>

e)<S>

f)b分析：符號(hào)串的某一部分符號(hào)要成為句柄，必須滿足：

a）該符號(hào)串必須是該文法的句型（句子）。

b）是最左簡(jiǎn)單短語(yǔ)，所以文法的開(kāi)始符號(hào)不是句柄。

因此只要給出句型(句子)對(duì)應(yīng)的推導(dǎo)樹(shù)就容易求出短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。

解答：1）句型（bc<S>c<T>）的推導(dǎo)樹(shù)如圖2.1所示：圖2.1句型（bc<S>c<T>）的推導(dǎo)樹(shù)短語(yǔ)：b;bc<S>c<T>;<S>c<T>;(bc<S>c<T>)

簡(jiǎn)單短語(yǔ)：b;<S>c<T>

句柄：b

2)a）句型((<S>c(b)))的推導(dǎo)樹(shù)如圖2.2所示：圖2.2句型((<S>c(b)))的推導(dǎo)樹(shù)

∴句柄為b。

b)句型(<S>)的推導(dǎo)樹(shù)如圖2.3所示：圖2.3句型(<S>)的推導(dǎo)樹(shù)

∴句柄為<S>。

c)句子(a)的推導(dǎo)樹(shù)如圖2.4所示：圖2.4句子(a)的推導(dǎo)樹(shù)

∴句柄為a。

d）<S>c<T>不是文法G[<S>]的句型，∴句柄不存在。

e）<S>是開(kāi)始符號(hào)，∴句柄不存在。

f）句子b的推導(dǎo)樹(shù)如圖2.5所示：圖2.5句子b的推導(dǎo)樹(shù)

∴句柄為b。3.試證具有直接左遞歸產(chǎn)生式的文法不是LL(k)文法。證明：考察文法G[<S>]：

<S><S>a

<S>b

即<A>=<S>

=<S>a

=b，

考慮最左推導(dǎo)<S>i<S>ai<S>aai與最左推導(dǎo)<S>i<S>aibai，

i0表示i次直接推導(dǎo)，

當(dāng)ik時(shí)FIRSTk(<S>aai)∩FIRSTk(bai)=bak-1，

∴G[<S>]不是LL(k)文法。

由于文法G[<S>]是有直接左遞歸產(chǎn)生式的文法，所以命題得證。4.考察如下文法G［<S>］：

<S>→<A>a<B>

<S>→<B>b

<A>→a<D>

<A>→<D>

<B>→d

<B>→e

<B>→ε

<D>→f<D>

<D>→g

a)試證文法G是LL(1)文法。解答：

a)G［<S>］各個(gè)產(chǎn)生式的選擇集合為：

Select(<S>→<A>a<B>)=FIRST(<A>a<B>)={a,f,g}

Select(<S>→<B>b)=FIRST(<D>b)={d,e,b}

Select(<A>→a<D>)=FIRST(a<B>)={a}

Select(<A>→<D>)=FIRST(<D>)={f,g}

Select(<B>→d)=FIRST(<d>)=ue6wiaq

Select(<B>→e)=FIRST(<e>)={e}

Select(<B>→ε)=FOLLOW(<B>)={b,}

Select(<D>→f<D>)=FIRST(f<D>)={f}

Select(<D>→g)=FIRST(g)={g}

顯然，具有相同左部的產(chǎn)生式的選擇集合不相交

∴G［<S>］是LL(1)文法。5.試判定下述文法G［<S>］是否是LR（1）文法？為什么？

<S>→<A><A>

<A>→<A>a

<A>→a解答：a）∵對(duì)文法G［<S>］存在的句子aaa，有二棵不同的推導(dǎo)樹(shù)（圖5.1）：∴該文法是二義性文法，G［<S>］不是LR（1）文法。4.132001年編譯原理試題1．（10分）處于/*和*/之間的串構(gòu)成注解，注解中間沒(méi)有*/。畫(huà)出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。2．（10分）為語(yǔ)言 L＝{ambn|0m2n}（即a的個(gè)數(shù)不超過(guò)b寫(xiě)一個(gè)LR（1）文法，不準(zhǔn)超過(guò)6個(gè)產(chǎn)生式。（若超過(guò)6個(gè)產(chǎn)生式，不給分。若所寫(xiě)文法不是LR（1）文法，最多給5分。）3．（10分）構(gòu)造下面文法的LL（1）分析表。 DTL Tint|real LidR R,idR|4．（15分）就下面文法 S(L)|a LLS|S 給出一個(gè)語(yǔ)法制導(dǎo)定義，它輸出配對(duì)括號(hào)的個(gè)數(shù)。 給出一個(gè)翻譯方案，它輸出每個(gè)a的嵌套深度。 如句子(a,(a,a))，第一小題的輸出是2，第二小題的輸出是122。9．（10分）如果在A機(jī)器上我們有C語(yǔ)言編譯器CCA，也有它的源碼SA（用C語(yǔ)言寫(xiě)成）。如何利用它通過(guò)盡量少的工作來(lái)得到B機(jī)器的C語(yǔ)言編譯器CCB。10．（5分）表達(dá)式(x.(yz.(x+y)+z)3)45和(x.(yz.(x+y)+z)35)4有同樣的結(jié)果。在抽象機(jī)FAM上，哪一個(gè)表達(dá)式對(duì)應(yīng)的目標(biāo)代碼的執(zhí)行效率高？為什么？2001年編譯原理試題參考答案1．1124start52othersothers/***/2．LR（1）文法 LR（1）文法 二義文法 SAB|aABb SAB SAASb| AaaAb| AaaAb|ab| Aa|BBb| BBb|3． int real id , $ D DTL DTL T Tint Treal L LidR R R,idR R4． SS print(S.num) S(L) S.num:=L.num+1 Sa S.num:=0 LL1,S L.num:=L1.num+S.num LS L.num:=S.num S{S.depth:=0}S S{L.depth:=S.depth+1}(L) Sa{print(S.depth)} L{L1.depth:=L.depth}L1,{S.depth:=L.depth}S L{S.depth:=L.depth}S9． 修改源碼SA的代碼生成部分，讓它產(chǎn)生B機(jī)器的代碼，稱結(jié)果程序?yàn)镾B。 將SB提交給CCA進(jìn)行編譯，得到一個(gè)可執(zhí)行程序。 將SB提交給上述可執(zhí)行程序進(jìn)行編譯，得到所需的編譯器CCB。10．第一個(gè)表達(dá)式在執(zhí)行yz.(x+y)+z)3時(shí)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況，因此有FUNVAL的值進(jìn)入棧頂，然后發(fā)現(xiàn)參數(shù)個(gè)數(shù)不足，又把它做成FANVAL的情況。而第二個(gè)表達(dá)式執(zhí)行的是(yz.(x+y)+z)35，不會(huì)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況。因此第二個(gè)表達(dá)式的執(zhí)行效率比第一個(gè)表達(dá)式的高。2003年編譯原理試題1．（20分）寫(xiě)出字母表={a,b}上語(yǔ)言L={w|w中a的個(gè)數(shù)是偶數(shù)}的正規(guī)式，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。2．（15分）考慮下面的表達(dá)式文法，它包括數(shù)組訪問(wèn)、加和賦值： EE[E]|E+E|E=E|(E)|id該文法是二義的。請(qǐng)寫(xiě)一個(gè)接受同樣語(yǔ)言的LR(1)文法，其優(yōu)先級(jí)從高到低依次是數(shù)組訪問(wèn)、加和賦值，并且加運(yùn)算是左結(jié)合，賦值是右結(jié)合。3．（10分）下面是產(chǎn)生字母表={0,1,2}上數(shù)字串的一個(gè)文法： SDSD|2 D0|1寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義，它打印一個(gè)句子是否為回文數(shù)（一個(gè)數(shù)字串，從左向右讀和從右向左讀都一樣時(shí)，稱它為回文數(shù)）。4．（10分）教材上7.2.1節(jié)的翻譯方案P {offset:=0} DDD;DDid:T {enter(,T.type,offset);offset:=offset+T.width}Tinteger {T.type:=integer;T.width:=4}Treal {T.type:=real;T.width:=8}使用了變量offset。請(qǐng)重寫(xiě)該翻譯方案，它完成同樣的事情，但只使用文法符號(hào)的屬性，而不使用變量。2003年編譯原理試題參考答案1．語(yǔ)言L的正規(guī)式是： (ab*a|b)*或b*(ab*ab*)*22start1aabb接受該語(yǔ)言的最簡(jiǎn)DFA是：2． ET=E|T TT+F|F FF[E]|(E)|id3． SS print(S.val)SD1S1D2 S.val= (D1.val=D2.val)andS1.valS2 S.val=true D0 D.val=0D1 D.val=14．文法符號(hào)D的屬性offset1是繼承屬性，代表在分析D前原來(lái)使用的變量offset的大小；屬性offset2是綜合屬性，代表在分析D后原來(lái)使用的變量offset的大小。P的屬性offset是綜合屬性，記錄該過(guò)程所分配的空間。 P {D.offset1:=0}D{P.offset:=D.offset2}D {D1.offset1:=D.offset1}D1;{D2.offset1:=D1.offset2}D2{D.offset2:=D2.offset2}Did:T{enter(,T.type,D.offset1);D.offset2:=D.offset1+T.width}Tinteger{T.type:=integer;T.width:=4}Treal {T.type:=real;T.width:=8}1．（15分）(a)字母表={(,)}上的語(yǔ)言{(),(()()),((())),()()()()()}是不是正規(guī)語(yǔ)言？為什么？(b)正規(guī)式(0|1)*和((|0)1*)*是否等價(jià)，說(shuō)明理由。2．（15分）接受文法 SAa|bAc|dc|bda AdS’S’.SS.AaS.bAcS.dcS.bdaA.dI0Sb.AcSb.daA.dI3daSd.cAd.I4AS’S.I1SSA.aI2ASAa.I5bSbA.cI6dSdc.I8Sbd.aAd.I7cSbAc.I9Sbda.I10ca活前綴的DFA見(jiàn)下圖。請(qǐng)根據(jù)這個(gè)DFA來(lái)構(gòu)造該文法的SLR(1)分析表，并說(shuō)明該文法為什么不是SLR(1)文法。3．（10分）現(xiàn)有字母表={a}，寫(xiě)一個(gè)和正規(guī)式a*等價(jià)的上下文無(wú)關(guān)文法，要求所寫(xiě)的文法既不是LR文法，也不是二義文法。4．（20分） (a)下面的文法定義語(yǔ)言L={anbncm|m,n1}。寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義，其語(yǔ)義規(guī)則的作用是：對(duì)不屬于語(yǔ)言L的子集L1={anbncn|n1}的句子，打印出錯(cuò)信息。 SDC DaDb|ab CCc|c (b)語(yǔ)句的文法如下： Sid:=E|ifEthenS|whileEdoS|beginS;Send|break寫(xiě)一個(gè)翻譯方案，其語(yǔ)義動(dòng)作的作用是：若發(fā)現(xiàn)break不是出現(xiàn)在循環(huán)語(yǔ)句中，及時(shí)報(bào)告錯(cuò)誤。2005年編譯原理和技術(shù)試題參考答案1． (a)語(yǔ)言{(),(()()),((())),()()()()()}是正規(guī)語(yǔ)言，因?yàn)樵撜Z(yǔ)言只包括有限個(gè)句子，它可以用正規(guī)式定義如下： ()|(()())|((()))|()()()()()(b)我們分析正規(guī)式((|0)1*)*表示的語(yǔ)言?？梢钥闯稣?guī)式(|0)1*描述的語(yǔ)言是集合{,1,11,111,…,0,01,011,0111,…}，它含長(zhǎng)度為1的兩個(gè)串0和1。那么，(0|1)*所描述的語(yǔ)言是((|0)1*)*所描述的語(yǔ)言的子集，因?yàn)?0|1)*表示字母表{0,1}上所有串的集合，因此((|0)1*)*所描述的語(yǔ)言不可能再有更多的句子，因而也是表示字母表{0,1}上所有串的集合。2．分析表如下。因?yàn)橛袃商幱幸七M(jìn)－歸約沖突，所以該文法不是SLR(1)文法。注：Fallow(A)={a,c}狀態(tài)狀態(tài)動(dòng)作轉(zhuǎn)移abcd$SA0s3s4121acc2s53s764r5s8,r55r16s97s10,r58r39r210r43．滿足條件的一個(gè)文法如下： SaSa|a|4． (a)語(yǔ)法制導(dǎo)的定義如下： SDC ifD.lengthC.lengththenprint(“error”) Dab D.length:=1 DaD1b D.length:=D1.length+1 Cc C.length:=1 CC1c C.length:=C1(b)翻譯方案如下：S{S.loop:=false}SSid:=ESifEthen{S1.loop:=S.loop}S1SwhileEdo{S1.loop:=true}S1Sbegin{S1.loop:=S.loop}S1;{S2.loop:=S.loop}S2endSbreak{ifnotS.loopthenprint(“error”)}1、（15分）(a)用正規(guī)式表示字母表{a,b}上，a不會(huì)相鄰的所有串。b*(abb*)*(a|)(b)畫(huà)出一個(gè)最簡(jiǎn)的確定有限自動(dòng)機(jī)，它接受所有大于101的二進(jìn)制整數(shù)。2、（10分）構(gòu)造下面文法的LL(1)分析表。 SaBS|bAS| AbAA|aBaBB|b3、（10分）下面的文法是二義文法 SE EwhileEdoE|id:=E|E+E|id|(E)請(qǐng)你為該語(yǔ)言重寫(xiě)一個(gè)規(guī)范的LR(1)文法，它為該語(yǔ)言中的各種運(yùn)算體現(xiàn)通常的優(yōu)先級(jí)和結(jié)合規(guī)則。不需要證明你的文法是規(guī)范LR(1)的。4、（10分）為下面文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的定義，它完成一個(gè)句子的while-do最大嵌套層次的計(jì)算并輸出這個(gè)計(jì)算結(jié)果。 SE EwhileEdoE|id:=E|E+E|id|(E)8、（5分）把下面左邊的文件file1.c提交給編譯器，編譯器沒(méi)有報(bào)告任何錯(cuò)誤。而把文件file2.c提交給編譯器，錯(cuò)誤報(bào)告如下： file2.c:2:error:conflictingtypesfor‘func’ file2.c:1:error:previousdeclarationof‘func’試分析原因。（在這兩個(gè)文件中，第1行都是函數(shù)func的原型，第2行都是函數(shù)func的定義，函數(shù)體為空。）file1.c file2.c intfunc(double); intfunc(double); intfunc(f)floatf;{} intfunc(floatf){}9、（5分）教材上第342頁(yè)倒數(shù)第7行說(shuō)“將C++語(yǔ)言中一個(gè)類(lèi)的所有非靜態(tài)屬性構(gòu)成一個(gè)C語(yǔ)言的結(jié)構(gòu)類(lèi)型，取類(lèi)的名字作為結(jié)構(gòu)類(lèi)型的名字”。在這一章都學(xué)過(guò)后，你認(rèn)為這句話需要修改嗎？參考答案1、(a)b*(abb*)*(a|)01start01start>52100,13,4,5100,10,12、 開(kāi)始符號(hào)集合和后繼符號(hào)集合 LL(1)分析表FirstFollowSa,b,$Aa,ba,b,$Ba,ba,b,$ab$SSaBSSbASSAAaAbAABBaBBBb3、 SE EwhileEdoE|A Aid:=A|TTT+F|FFid|(E)4、語(yǔ)法制導(dǎo)的定義如下：SE print(S.loop); EwhileE1doE2 E.loop:=m