編譯原理期末考試

一、填空（每題2分，共20分）

1.從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性）語句兩大類。

2.掃描器的任務(wù)是從（源程序）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。

3.所謂最左派生是指（任何一步a都是對(duì)a中最左非終結(jié)符進(jìn)行替換的）。

4.語法分析最常用的兩類方法是（自頂向下）和（自底向上）分析法。

5.■?個(gè)上下文無關(guān)文法所含的四個(gè)組成部分是（一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)、一個(gè)開始符

號(hào)、一組產(chǎn)生式）?

6.所謂語法制導(dǎo)翻譯方法是（為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序，并在語法分析的同時(shí)執(zhí)行這

些子程序）。

7.LR分析法中的兩種沖突是（移入一歸約）和（歸約一歸約）。

8.產(chǎn)生式是用于定義（語法范疇）的一種書寫規(guī)則。

9.屬性定義中有兩種性質(zhì)的屬性，分別是（繼承屬性）和（綜合屬性）。

10.常用的兩種動(dòng)態(tài)存儲(chǔ)分配方法是（棧式動(dòng)態(tài)分配）和（堆式動(dòng)態(tài)分配）。

11.所謂最仃推導(dǎo)是指：任何一步呻都是對(duì)a中最右非終結(jié)符進(jìn)行替換的。

12.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地

址。）

13.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（類型、種屬、所占單元大小、地址）

等等。

短語：一棵子樹的所有葉I咱左至右排列起來形成一個(gè)相對(duì)于上樹根的短而

直接短酒：僅有父子兩代的一梃網(wǎng)，它的所仙I舊M起來所形成的符利

句柄：一個(gè)句型的分析樹巾用左地F那棵只有父f兩代的子樹的所有葉子的自左至右排列.

14.運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？

答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立

一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i,則它的diaplay表含有i+1個(gè)單元，

自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層....直至最外層（主程序，0層）等每層過程的

最新活動(dòng)記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。

二、名詞解釋（每題3分，共15分）

1.編譯器預(yù)處理：對(duì)于一個(gè)編譯器，如果要處理的輸入是對(duì)原編譯器的輸入的擴(kuò)充，就把輸入

中的擴(kuò)充部分轉(zhuǎn)換成原輸入的形式，然后把其結(jié)果交給原編譯器處理，也就是把擴(kuò)展的部分

轉(zhuǎn)換成標(biāo)準(zhǔn)形式，這就是編譯器預(yù)處理

2.LL（K）文法——（P89）

3.歧義文法一一（p71）

二義性（或歧義性，ambiquity）的定義：

如果一個(gè)文法的句子存在兩棵分析樹，那么，該句f是二義性的.如果一個(gè)文法包含二義性的句

￡則稱這個(gè)文法是二義性的.否她該文法是無二義性的.

正則表達(dá)式一一(P47)：每個(gè)正則表達(dá)式定義一個(gè)正則集。若用RE表示E上的正則表達(dá)式，并

用L(RE)所表示的正則集，則RE的語法定義和相應(yīng)正則集如下面所述，其中A和B表示正則表

達(dá)式，并且a表示字母表￡中的任一符號(hào)。

WeRSiLC0)-Q⑵短陽L何■(祖

向■(a)

⑷⑶1RE,L(W)■W圜A|B《R&L蜃聞?L⑴

時(shí)&BeRE.L(A■B)-L用L?[7]A'3RB,

4.屬性文法一一(P260)

三、簡(jiǎn)答題(每題5分，共15分)

1.設(shè)有L(G)—{a2n+1b2m+lc2p|n>=l,m>=l,p>=l}

1)給出它的正則表達(dá)式。

2)構(gòu)造識(shí)別該語言的DFA。

2.生成語言L(G)fa-mcPa%"|p>=0,m>=l,n>=2}的文法G是什么？它是chomsky的哪型

文法。

解:G(3)文法為

S->AC

A->aAc|B

B->bB|b

C->aCb|ab

它是喬姆斯基2型文法

3.已知文法G(S)：S-a|b|(T)T-T,SS寫出句子((a,b),b)的規(guī)范規(guī)約過程及每一步

的句柄。

解：句型規(guī)約句柄

((a,b),b)

((S,b),b)S->aa

((T,b),b)T->SS

((T,S),b)S->bb

((T),b)T->T,ST,S

(S,b)S->(T)(T)

(T,b)T->SS

(T,S)S->bb

(T)T->T,ST,S

SS->(T)(T)

四、計(jì)算題(每題10分，共20分)

1.已知文法G(E)

E-T|E+T

T-F|T*F

F-(E)|i

給出句型&=(T*F+i)的最右派生及畫出語法樹。

解：1.(4分)

EnT=F=(E)n(E+T)=(E+F)

=(E+i)=(T+i)=(T*F+i)

Zl\

Zl\

E+T

Zl\

T*F

2.(4分)

短語：(T*F+i),T*F+i,T*F,i

直接短語：T*F,i

句柄：T*F

素短語：T*F,i

2.說明下面的文法不是SLR(l)文法，并重寫一個(gè)等價(jià)的SLR(l)文法。

SfMa|bMc|dc|bda

Mfd

解：SSfMa|bMc|dc|bdaMfd

S'f.S

S—.Ma

Sfb.Mc

Sf.bMc

S—>b.daS-bd.a

S—.dc

M-?.dMfd.

S.bda

M->.d

因?yàn)閍是M的后繼符號(hào)之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn)-歸約沖突。

等價(jià)的SLR(l)文法是

Sfda|bdc|dc|bda

五、設(shè)計(jì)題(每題15分，共30分)

1.下面的文法定義詳"；L={a'ncm|m,nWl}。3個(gè)講法制導(dǎo)定義，其語義規(guī)則的作用是：對(duì)

不屬于語言L的子集L尸(anbncn|n>1}的句子，打印出錯(cuò)信息°

SfDCDfaDb|abC-?Cc|c

解：語法制導(dǎo)的定義如下：

S->DCifD.lengthwC.lengththenprint("error”)

D->abD.length:=1

D—>aD)bD.length:=D|.length+1

C->cC.length:=1

C—>CicC.length:=Cj.length+1

2.給;II文法G(L)的翻譯模式，它分別計(jì)灣，彳川；中0l-j1的個(gè)數(shù)，(要求ANTLR代碼)

S^L.LlL

L—BL

L-e

B-0|1

GrammerLOI

@membcrs{intnO;intnl;}

Start:{n0=0;nl=0;}j{system.out.println(nO);system.out.println(nl);}

j：<O>j{nO+=l;}

ri，j{nl+=l；}

I'a，

ws：C丁\門'\n'r\r')+{skip。;};

名詞解釋

1.遍一一指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。

2.無環(huán)路有向圖(DAG)一一如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為無環(huán)路有向圖，

簡(jiǎn)稱DAGo

3.語法分析一一按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。

4.短語一一令G是一個(gè)文法。S劃文法的開始符號(hào)，假定a66是文法G的一個(gè)句型，如果有$

aA6且AB,則稱B是句型a0相對(duì)非終結(jié)符A的短語。

5.后綴式一一??種把運(yùn)算量寫在前面，把算符寫在后面的表示表達(dá)式的方法。

筒述題

1、寫出表達(dá)式(a+b*c)/(a+b)-d的逆波蘭表示及三元式序列。

2、已知文法G(S)

S-a|A|(T)

T-T,S|S

寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄。

3、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？

4、目標(biāo)代碼有哪兒種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？

答

翦

1>逆波二表示：abc*+ab+/d—

三

■送r

L'?

①/*O

I

X，

②Z①

(

③Y+,

za,3

(

+,人

④xa.

z

(

⑤v-?④,@d)

z

(

\

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ī)器語言，匯編語言，待裝配機(jī)器語言模塊。

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

內(nèi)存次數(shù)；

(3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。

計(jì)算題：1、寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。(5分)

解：文法G(N)：

N—AB|B

ATAQD

BT1|3|5|7|9

D->B|2|4|6|8

C—O|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'TS|￡

L—SL'

L'TSL'W

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

(2)FIRST)S)={(,a}FOLLOW(S)={#,,,)}

FIRST(S,)={,a,8}FOLLOW⑻)={#,,,)}

F1RST(L)={(,a)FOLLOW(L)={)}

FIRST(L,)={,,￡}FOLLOW(L')={)}

3、Whilea>0Vb<0do

Begin

X：=X+1；

ifa>0thena：=a_1

elseb：=b+l

End；

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

解：

a,0,5)

3)

(3)(jV,b,0,5)

(4)0,一，一，15)

(5)(+,x,1,Tl)

(6)(：=,Tl,x)

(7)(jN，a,0,9)

(8)(j,一，—12)

(9)(-,a,1,T2)

(10)(：=,T2,a)

(11)0,一，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)及畫出語法樹；

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

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

ETF(E)(E+T)(E+F)(E+i)

(T+i)(T*F+i)

(2)短語：(T*F+i),T*F+i,T*F,i(2分)

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

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

E->E(1)VE(2)

E->E(1)AE(2)

E—i

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

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

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

解：⑴EO—E(l)

E-E0E(2)

EA-E⑴

E—EAE(2)

E—i(3分)

⑵E-E⑴

{BACKPATCH(E(1)FC,NXQ)；

EOTC：=E(1)TC}

ETE0E(2)

{EFC：=E(2)FC；

ETC：=MERG(E0TC,E(2)TC)}

EA-E⑴

{BACKPATCH(E(1)TC,NXQ)；

EOFC：=E(1)FC)

E—EAEQ)

{ETC：=E(2)TC；

EFC：=MERG(EAFC,E(2)FC)

E—i

{ETC：=NXQ；EFC：=NXQ+1；

GEN(jn2,entry(i),一0)；

GEN(j,0)(3分)

6、設(shè)有基本塊

Tl：=2

T2：=10/T

T3：=S-R

T4：=S+R

A：=T2*T4

B：A

T5：=S+R

T6：=T3*T5

B：=T6

(1)畫出DAG圖；

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

解：(l)DAG：

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

T3：=S-R

T4：=S+R

A：=5*T4

B：=T3+T4(3分)

例題3

若正規(guī)表達(dá)式r=(a|b|c)(011)*,則L(r)中有_D_個(gè)元素。

(12)A.12B.18C.6D.無窮

解析：本題考察的是程序的語言的組成句子與文法之間的關(guān)系；正規(guī)表達(dá)式r=(a13|0(0|1)*表

示的是a,b,c中的任意一個(gè)與0、1串的連接，由于0、1串的長度和組成是不固定的，所以整個(gè)

句子的數(shù)據(jù)就是不固定的，也就是說語言L(r)的組成元素是無窮的。

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

程序的處理過程可以劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代

碼生成等幾個(gè)階段：其中，代碼優(yōu)化和_仁并不是每種編譯器都必需的。詞法分析的作用是識(shí)別

源程序中的B；語法分析中的預(yù)測(cè)分析法是的一種語法分析方法；編譯器在C階段進(jìn)行

表達(dá)式的類型檢查及類型轉(zhuǎn)換。

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

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

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

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

(14)A、詞法分析B、語法分析C、中間代碼生成D、語義分析

(15)A、字符串B、單詞C、標(biāo)識(shí)符D、語句

(16)A、自左至右B、自頂向下C、自底向上D、自右至左

(17)A、詞法分析B、語法分析C、語義分析D、目標(biāo)代碼生成

例題5：假設(shè)某程序語言的文法如下：

S-a|b⑴

T-TdS|S

其中，V產(chǎn){a,b,d,(,)},V產(chǎn){S,T},S是開始符號(hào)。

考查該文法，稱句型(Sd(T)db)是S的一個(gè)A。其中B是句柄；C是素短語；D是該句型的直接短

語；E是短語。

A：①最左推導(dǎo)②最右推導(dǎo)③規(guī)范推導(dǎo)④推導(dǎo)

B：①S②b③⑴@Sd(T)

C：①S②b③⑴@Sd(T)

D：①S②S,⑴，b③S,(T),TdS,b④(SdCT)db)

E：①(Sd(T)db)②d(T)③Td④Sd(T)d

此句型的語法樹如下所示：

S

(T)

(TdS)

(TdSb)

(S(T))

從語法樹我們可以看出，短語就是位于同一個(gè)非終端結(jié)點(diǎn)的所有葉子結(jié)點(diǎn)，比如S、Sd(T)、

Sd(T)db就是是相對(duì)于T的短語，b、(T)、(Sd(T)db)是相對(duì)于S的短語。而直接短語則進(jìn)一步要

求這些葉子結(jié)點(diǎn)的非終端結(jié)點(diǎn)是它們的直接父結(jié)點(diǎn)。因此可以S、(T)、b都是該句型的直接短語。

語法樹上最左的直接短語就是句柄，本題中是S。

所謂素短語是指這樣一個(gè)短語，它至少含有一個(gè)終結(jié)符，并且除它自身之外不再含任何更小

的素短語。最左素短語則指處于句型最左邊的那個(gè)素短語。

最左推導(dǎo)是指任何一步推導(dǎo)過程。一B,都是對(duì)。中的最左非終結(jié)符進(jìn)行替換。因此，在語

法樹中也很容易看出，如果語法樹中的只有最左的非終結(jié)符結(jié)點(diǎn)(包括各級(jí)結(jié)點(diǎn))具有其子樹，

則它就是最左推導(dǎo)。最右推導(dǎo)與之類似，最右推導(dǎo)也稱規(guī)范推導(dǎo)。本題從語法推導(dǎo)樹可以看出，

既不是最左推導(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è)賦值是否真是無用的。正確

4、每個(gè)文法都能改寫為LL(1)文法。不正確

5、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。不正確

一、回答下列問題：(30分)

1.什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？

解答：S-屬性文法是只含有綜合屬性的屬性文法。(2分)

L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式A9X1X2…Xn,其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性,

或者是Xj的一個(gè)繼承屬性，且該屬性僅依賴于：

(1)產(chǎn)生式Xj的左邊符號(hào)X1,X2…Xj-1的屬性；

(2)A的繼承屬性。(2分)

S-屬性文法是L-屬性文法的特例。(2分)

2.什么是句柄？什么是素短語？

一個(gè)句型的最左直接短語稱為該句型的句柄。(3分)素短語是這樣的一個(gè)短語，它至少包含一個(gè)

終結(jié)符并且不包含更小的素短語。(3分)

3.劃分程序的基本塊時(shí)，確定基本塊的入口語句的條件是什么？

解答：(1)程序第一個(gè)語句，或

(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或

(3)緊跟在條件轉(zhuǎn)移語句后面的語句。

4.(6分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？

答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立

一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i,則它的diaplay表含有i+1個(gè)

單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、…、直至最外層(主程序，0層)等每層

過程的最新活動(dòng)記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。

5.(6分)對(duì)下列四元式序列生成目標(biāo)代碼：

A:=B*C

D:=E+F

G:=A+D

H:=G*2

其中，H是基本塊出口的活躍變量，R0和R1是可用寄存器

答：

LDRO,B

MULRO,C

LDRI,E

ADDRI,F

ADDRO,RI

MULRO,2

STRO,H

二、設(shè)￡={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分）

三、（6分）寫一個(gè)文法使其語言為L（G）={anbn,ambn|

答：文法G（S）:

S->aSb|B

BfbBa|ba

四、對(duì)于文法G（E）:（8分）

E->T|E+T

T->F|T*F

Ff（E）|i

1.寫出句型（T*F+i）的最右推導(dǎo)并畫出語法樹。E

2.寫出上述句型的短語，直接短語、句柄和素短語。

答:1.（4分）

E=>T=>F=>(E)n(E+T)=(E+F)T

F

/1\

n(E+i)=>(T+i)n(T*F+i)

2.(4分)短語：CT*F+i),T*F+i,T*F,i直接短語：T*F,i

句柄：T*F素短語：T*F,i

五、設(shè)文法G(S)：(12分)

SfSiA|A

ATA+B|B

Bf)A*|(

1.構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；

2.構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。(12分)

答：(6分)

FIRSTVT(S)={i,+,),(}

FIRSTVT(A)={+,),(}

F1RSTVT(B)={),(}

LASTVT(S)={i,+,*,(}

LASTVT(A)={+,*,(}

LASTVT(B)={*,(}

優(yōu)先關(guān)系表:(3分)

*

ii()

i><<<

+>><<>

(>>>

)<<<

*>>>

優(yōu)先函數(shù):（3分）

i+()*

f26616

g14661

六、設(shè)某語言的do-while語句的語法形式為（9分）

S->doS⑴WhileE

其語義解釋為:

針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式:

（1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；

（2）寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。

答：（1）.適合語法制導(dǎo)翻譯的文法（3分）

G(S):

Rfdo

UfRS⑴While

SfUE

(2).(6分)

R—>do

{R,QUAD:=NXQ}

UfRS⑴While

{U?QUAD:=R.QUAD;

BACKPATCH(S.CHAINzNXQ)}

SfUE

{BACKPATCH(E.TC,U.QUAD);

S.CHAIN:=E.FC}

答案二：(1)SfdoMiS⑴WhileM2E

MfE(3分)

(2)Mfg{M.QUAD:=NXQ}(6分)

(1)

SfdoMiSWhileM2E

(

(1)

BACKPATCH(S.CHAIN,M2.QUAD);

BACKPATCH(E.TC,M^.QUAD);

S.CHAIN:=E.FC

)

七、(8分)將語句if(A〈X)八(B>0)thenwhileC>0doC:=C+D翻譯成四元式。

答：100(jv,A,X,102)

101(j,-，，109)

1020>,B,0,104)

103(j,?，，109)

104(j>,C,0,106)

105(j,-，-，109)

106(+,c,D,Tl)

107(:=,Tl,?，C)

1080，-，-,104)

109

八、（10分）設(shè)有基本塊如下:

T1:=S+R

T2:=3

T3:=12/T2

T4:=S/R

A:=T1-T4

T5:=S+R

B:=T5

T6:=T5*T3

B:=T6

(1)畫出DAG圖；

⑵設(shè)A,B是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。

(2)BfaB

(3)Bfb

00#abab#

103#abab#

2034#abab#

3038#aBab#

402#Bab#

5026#Bab#

60267#Bab#

70269#BaB#

8025#BB#

901#S#acc

二、(10分)設(shè)有文法G[A]:A->iB*e

BfSB|s

S->[eC]|.i

C—>eC|￡

判定該文法是否為LL(1)文法？若是則給出它的LL(1)分析表，否則說明理由。

解：先計(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->￡)={]}

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

LL(1)分析表如下:

i*e[

->iB*e->￡

A

->sB->SB

B

->[eC]->.i

S

->eC->8

C

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

S—LaR|R

LfbR|c

R->L

判斷該文法是否為LR(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)的短語、簡(jiǎn)單短語和句柄。

解：短語共有7個(gè)：a(T+S);H;(S)

a(T+S);H

a(T+S)

T+S

(S)

H

a

簡(jiǎn)單短語4個(gè)：a,T+S,H,(S)

句柄：a。

6.已知文法G⑶為：

STABIbCA->b|九

B—aD|XC—AD|b

D-aS|c

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

解：First(S)={b,a,X)

First(A)={b,X}

First(B)={a,X}

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

First(D)={a,c}

Follow(S)={#}

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

Follow(B)={#}

Follow(C)={#}

Follow(D)={#}

1.編譯程序在邏輯上由哪幾部分組成？

答：六個(gè)階段：詞法分析，語法分析，語義分析,中間代碼生成，中間代碼優(yōu)化和目標(biāo)代碼生成。

2.文法的產(chǎn)生式為：

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

<T>-*<S>c<T>|<S>

<R>-*<T>

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

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)單短語，所以文法的開始符號(hào)不是句柄。

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

解答：1)句型(bc<S>c<T?的推導(dǎo)樹如圖2.1所示:

圖2.1句型（bc〈S>c<T〉）的推導(dǎo)樹

短語：b;bc<S>c<T>;<S>c<T>;（bc<S>c<T?

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

句柄：b

2）a）句型（（。>￡；（13）））的推導(dǎo)樹如圖2.2所示：

（中）

中

圖2.2句型（?S>c（b）））的推導(dǎo)樹

句柄為bo

b）句型（〈S>）的推導(dǎo)樹如圖2.3所示:

圖2.3句型(<S>)的推導(dǎo)樹

句柄為<S>.

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

半

T

T

T

.

圖2.4句子(a)的推導(dǎo)樹

句柄為a。

d)〈S>c〈T>不是文法G［〈S>］的句型，.?.句柄不存在。

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

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

T

b

圖2.5句子b的推導(dǎo)樹

句柄為b。

3.試證具有直接左遞歸產(chǎn)生式的文法不是LL(k)文法。

證明：考察文法G［<S>］：

<S>f<S>a

<S>—>b

BP<A>=<S>a=<S>ap=b,

考慮最左推導(dǎo)vS>='<S>a'n<S>aa'與最左推導(dǎo)<S>n'〈S>a'nba’,

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

iik-1

當(dāng)i>k時(shí)FIRSTk(<S>aa)AFIRSTk(ba)=baH0,

刁不是LL(k)文法。

由于文法G［<S>］是有直接左遞歸產(chǎn)生式的文法，所以命題得證。

4.考察如下文法G［<S>］：

<S>-<A>a<B>

<S>一<B>b

<A>fa<D>

<A>一〈D>

<B>—d

<B>-e

〈BAe

<D>-f〈D>

<D>-g

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

解答：

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

Select(<S>—><A>a<B>)=FIRST(<A>a<B>)={aXg}

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>)=muedzns

Select(<B>—?e)=FIRST(<e>)={e}

Select(<B>->8)=FOLLOW(<B>)={b,l}

Select(<D>->f<D>)=FIRST(長D>)={f}

Select(<D>-^g)=FlRST(g)={g}

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

.,.GL<s>］是LL(1)文法。

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

<S>-<AXA>

<A>f<A>a

<A>fa

解答：a)???對(duì)文法G［<S>］存在的句子aaa,有二棵不同的推導(dǎo)樹(圖5.1)：

中I

<A>aa

?<A>■

...該文法是二義性文法,G[<S>]不是LR(1)文法。

(c)DS,A,B可導(dǎo)出空

2)first(S)={a,b},first(A)={a,X},first(B)={b,X}

follow(S)={#},follow(A)={a,b,#},follow(B)={a,b,#!

predict(S->ABBA)={a,b,#}

predict(A->a)={a},predict(A->入)={a,b,#}(*)

predict(B->b)=,predict(B->入)={a,b,#}(**)

由(*)和(**)兩行知，不是LL(D文法.

(d)1)沒有非終極符可導(dǎo)出空

2)first(C)={c,d},first(B)={b,c,c},first(S)={a,b,c,d}

follow(S)={e,#},follow(B)={e,#},follow(C)={c,e,#}

predict(S->aSe)={a},predict(S->B)={b,c,d}

predict(B->bBe)=,predict(B->C)={c,d}

predict(C->cCc)={c},predict(C->d)=fyyscyx

因?yàn)闈M足LL(1)文法的條件，所以是LL(1)文法.

4.13

First(E)=[-,(,id}Follow(E)={#J}

First(Etail)={-%)Follow(Etail)={4$,)}

First(Var)={id}Follow(Var)={-，#,)}

First(Vtail)={(,%}Follow(Vtail){-,#,)}

[1]predict(E-E)={-}

⑵predict(E-(E))={(}

⑶predict(E-VarEtail)={id)

predict(Etail--E)={-}

⑸predict(Etail-A)={#.)}

[6]predict(Vai-idVtail)={id}

[7]predict(Vtail-(E?={()

[8]predict(VtaiLA)={-,))

分析表:

-()id#

E123

Etail455

Var6

Vtail8788

2001年編譯原理試題

1.（10分）處于/*和*/之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)

轉(zhuǎn)換圖。

2.（10分）為語言

L={a'V|0<m<2n）（即a的個(gè)數(shù)不超過b的個(gè)數(shù)的兩倍）

寫一個(gè)LR（1）文法，不準(zhǔn)超過6個(gè)產(chǎn)生式。（若超過6個(gè)產(chǎn)生式，不給分。若所寫文法不是LR

（1）文法，最多給5分。）

3.（10分）構(gòu)造下面文法的LL（1）分析表。

D->TL

Tfint|real

LridR

R.,idR|￡

4.(15分)就下面文法

S.(L)|aLfL,S|S

?給出一個(gè)語法制導(dǎo)定義，它輸出配對(duì)括號(hào)的個(gè)數(shù)。

?給出一個(gè)翻譯方案，它輸出每個(gè)a的嵌套深度。

如句子(a,(a,a)),第一小題的輸出是2,第二小題的輸出是122。

9.(10分)如果在A機(jī)器上我們有C語言編譯器C。，也有它的源碼&(用C語言寫成)。如

何利用它通過盡量少的工作來得到B機(jī)器的C語言編譯器CCBo

10.(5分)表達(dá)式(標(biāo).(九yz.(x+y)+z)3)45和(Xx.(九yz.(x+y)+z)35)4有同樣的結(jié)果。在抽象機(jī)

FAM上，哪一個(gè)表達(dá)式對(duì)應(yīng)的目標(biāo)代碼的執(zhí)行效率高？為什么？

2001年編譯原理試題參考答案

1.

2.LR(1)文法LR(1)文法二義文法

S->AB|aABbSfABSfAASb|￡

A->aaAb|8AfaaAb|ab|8A->a|8

B->Bb|8B—>Bb|￡

3.intrealid,$

DD-?TLDfTL

TTfintT—>real

LLfidR

RR.—idRR—>￡

4.SJSprint(S.num)

Sf(L)S.num:=L.num+1

SfaS.num:=0

LfLhSL.num:=L^num+S.num

LfSL.num:=S.num

S，->{S.depth:=0}S

S.{L.depth:=S.depth+1}(L)

Sfa{print(S.depth)}

Lt{Li.depth:=L.depth}L,,{S.depth:=L.depth}S

L->{S.depth:=L.depth}S

9.?修改源碼5八的代碼生成部分，讓它產(chǎn)生B機(jī)器的代碼，稱結(jié)果程序?yàn)橥狻?/p>

?將品提交給C。進(jìn)行編譯，得到一個(gè)可執(zhí)行程序。

?將區(qū)提交給上述可執(zhí)行程序進(jìn)行編譯，得到所需的編譯器Cg。

10.第一個(gè)表達(dá)式在執(zhí)行大yz.(x+>')+z)3時(shí)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況，因此有FUNVAL的值進(jìn)

入棧頂，然后發(fā)現(xiàn)參數(shù)個(gè)數(shù)不足，又把它做成FANVAL的情況。而第二個(gè)表達(dá)式執(zhí)行的是(心心。

+y)+z)35,不會(huì)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況。因此第二個(gè)表達(dá)式的執(zhí)行效率比第一個(gè)表達(dá)式的高。

2003年編譯原理試題

1.（20分）寫出字母表￡={a,b}上語言L={卬|卬中a的個(gè)數(shù)是偶數(shù)}的正規(guī)式，并畫出接受該

語言的最簡(jiǎn)DFAo

2.（15分）考慮下面的表達(dá)式文法，它包括數(shù)組訪問、加和賦值：

EfE[E]|E+E|E=E|（E）|id

該文法是二義的。請(qǐng)寫一個(gè)接受同樣語言的LR（1）文法，其優(yōu)先級(jí)從高到低依次是數(shù)組訪問、加

和賦值，并且加運(yùn)算是左結(jié)合，賦值是右結(jié)合。

3.（10分）下面是產(chǎn)生字母表￡={0,1,2}上數(shù)字串的-—個(gè)文法：

SfDSD|2

D-0|1

寫一個(gè)語法制導(dǎo)定義，它打印一個(gè)句子是否為回文數(shù)（一個(gè)數(shù)字串，從左向右讀和從右向左讀都

一樣時(shí)，稱它為回文數(shù)）。

4.（10分）教材上721節(jié)的翻譯方案

PT{offset:=0)

D

DTD;D

。fid:7{,T.type,offset);offset:=offset+T.width}

Ttinteger{T.type:=integer;T.width:=4}

TTreal{T.type:=real;T.width:=8}

使用了變量offset,請(qǐng)重寫該翻譯方案，它完成同樣的事情，但只使用文法符號(hào)的屬性，而不使

用變量。

2003年編譯原理試題參考答案

1.語言L的出規(guī)弓是：，

（4b*a|b）或b9（ab*a/?*）*

接受該語言的最簡(jiǎn)DFA是：

2.EfT=E|T

TfT+F|F

FtF[E]|(E)|id

3.S-Sprint(S.val)

S—>D]S]D2S.val=(Di.val=D2.val)andSi.val

Sf2S.val=true

Df0D.val=0

D-?1D.val=1

4.文法符號(hào)。的屬性協(xié)亮八是繼承屬性，代表在分析。前原來使用的變量奶外的大??；屬性

叨是綜合屬性，代表在分析。后原來使用的變量加々的大小。P的屬性奶e/是綜合屬性，

記錄該過程所分配的空間。

P—>{D.offset\:=0}D{P,offset:=D.offset!}

D—>{D\.ojfset\:=D.offsetl\D\;

{D2.offset\:=D\.offset2}Di{D.ojfsetl:=D2.offset2}

￡)-?id:T{enter(,T.type,D.offsetI);

D.offsetl:=D.offset\+T.width)

Ttinteger{T.type:=integer;T.width:=4}

TTreal{T.type:=real;T.width:=8}

1.(15分)

(a)字母表X={(,)}上的語言{(),(()()),((())),()()()()()}是不是正規(guī)語言？為什么？

(b)正規(guī)式(0|1)*和((￡|0)「)*是否等價(jià)，說明理由。

2.(15分)接受文法

S^Aa|bAc|dc|bda

Afd

活前綴的DFA見下圖。請(qǐng)根據(jù)這個(gè)DFA來構(gòu)造該文法的SLR(l)分析表，并說明該文法為什么不

是SLR(l)文法。

3.(10分)現(xiàn)有字母表￡=｛a｝,寫一個(gè)和正規(guī)式a*等價(jià)的上下文無關(guān)文法，要求所寫的文法既不

是LR文法，也不是二義文法。

4.(20分)

(a)下面的文法定義語言L=｛a'11/|m,n21｝。寫一個(gè)語法制導(dǎo)定義，其語義規(guī)則的作用是：

對(duì)不屬于語言L的子集L尸｛anbncn|n>1｝的句子，打印出錯(cuò)信息。

S—>DCD—>aDb|abCfCc|c

(b)語句的文法如下：

S—>id:=E|ifEthenS|whileEdoS|beginS;Send|break

寫一個(gè)翻譯方案，其語義動(dòng)作的作用是：若發(fā)現(xiàn)break不是出現(xiàn)在循環(huán)語句中，及時(shí)報(bào)告錯(cuò)誤。

2005年編譯原理和技術(shù)試題參考答案

1.(a)語言｛(),(()()),((())),()()()()()｝是正規(guī)語言,因?yàn)樵撜Z言只包括有限個(gè)句子，它可

以用正規(guī)式定義如下：

()1(()())1((()))1()()()()()

(b)我們分析正規(guī)式(伯|0)1*)*表示的語言?？梢钥闯稣?guī)式(￡[0)1*描述的語言是集合｛￡,1,

11,111,...,0,01,011,0111,它含長度