編譯原理題庫-簡(jiǎn)答題

編譯原理A

1.簡(jiǎn)要說明語義分析的基本功能。

2.考慮文法G[S]:

Sf(T)|a+S|a

T-T,S|S

消除文法的左遞歸及提取公共左因子。

3試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。

4.按照三種基本控制結(jié)構(gòu)文法將下面的語句潮譯成四元式序列：

while(A<CAB<D)

(

if(A21)C=C+1;

elsewhile(AWD)

A=A+2;

)?

5.已知文法G[S]為S-aSb|Sb|b,試證明文法G[S]為二義文法。

A答案

1答：語義分析的基本功能包括：確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查.

2解：消除文法G[S]的左遞歸：

S-(T)|a+S|a

T-ST'

T'-,ST,|e

提取公共左因子：

Sf(T)|aS;

S'-+S|e

T-ST，

T'-,ST,|￡

3答：wab+cdel0-/+8+*+

4答：該語句的四元式序列如下(其中El、E2和E3分另ij對(duì)應(yīng)A<CAB<D、A21和AWD,并

且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：

100(j<,A,C,102)

101(j____113)

102(j<,B,D,104)

103113)

104(j=A,1,106)

105(j,108)

106(+,C,1,C)

107U2)

108(j近,A,D,AO)

109112)

110(+,A,2,A)

111(J,108)

112(j____100)

113

5答：證明：

由文法G[S]：S-aSbSbb,對(duì)句子aabbbb對(duì)應(yīng)的兩棵語法樹為:

因此，文法G[S]為二義文法。

編譯原理B

1.什么是句子？什么是語言？

2.寫文法，使其語言是偶正整數(shù)的集合,要求:

(1)允許0打頭；

(2)不允許0打頭。

3.已知文法G[E]為：

E-T|E+T|E-T

T-F|T*F|T/F

F-(E)|i

①該文法的開始符號(hào)(識(shí)別符號(hào))是什么？

②請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VNo

③找出句型T+T*F+i的所有短語、簡(jiǎn)單短語和句柄。

4.構(gòu)造正規(guī)式相應(yīng)的NFA:1(0

5.寫出表達(dá)式(a+b*c)/(a+b)—d的逆波蘭表示和三元式序列。

B卷答案

1答：⑴設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Sx(其中xCVT*),則稱x是

文法的一個(gè)句子。

(2)設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為:L(G)={x|Sx,xWVT*}。

2解：⑴G[S]=({S,P,D,N},{0,1,2,…,9},P,S)

P:

S->PD11)

P->NP|N

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

N->0|l|2|3|4|5|6|7|8|9

(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)

P:

S->PDP0|D

P->NR|N

R->QRQ

D->2|4|6|8

N->12|3|4|5|6|7|8|9

Q->01|2|3|4|5|6|7|8|9

3解：①該文法的開始符號(hào)（識(shí)別符號(hào)）是E。

②該文法的終結(jié)符號(hào)集合VT={+、-、*、/、（、）、i）。非終結(jié)符號(hào)集合VN={E、T、F}o

③句型T+T*F+I的短語為i、T*F、第一個(gè)T、T+T*F+i;簡(jiǎn)單短語為i、T*F、第一個(gè)T;句柄

為第一個(gè)T。

4解:1（0對(duì)應(yīng)的NFA為

0

5解：逆波蘭表示：abc*+ab+/d—

三元式序列：①（*,b,c）②（+,a,①）③（+,

a,b）④（/,②，③）⑤（一，④，d）

編譯原理C

1.（10分）對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段（詞法分析、語法分析、語義

分析、代碼生成）報(bào)告的。

（1）else沒有匹配的if

（2）數(shù)組下標(biāo)越界

（3）使用的函數(shù)沒有定義

（4）在數(shù)中出現(xiàn)非數(shù)字字符

（5）函數(shù)調(diào)用時(shí)實(shí)參與形參類型不一致。

2.（15分）構(gòu)造一個(gè)DFA,它接收工={0,1}上所有滿足如下條件的字符串：每個(gè)1都有。直

接跟在右邊。并給出該語言的正規(guī)式

3.（10分）為下面的語言設(shè)計(jì)文法：

（1）其中m>n]

（2）{獷?E[a,6}*,曠的長(zhǎng)度為奇數(shù)}

證明￡、+律（id）是文法的一個(gè)句型，指出該句型的所有短語、直接短語和句柄。

5.（15分）給定文法：

EE+TIE-TIT

T-T*F/T/FIF

Ff（￡）/id

C卷答案

1答案：(每小題2分)

(1)語法分析

(2)語法分析

(3)語義分析

(4)詞法分析

(5)語義分析

2答案：

按題意相應(yīng)的正規(guī)表達(dá)式是(0*10)*。*,或0*(0|10)*0*,構(gòu)造相應(yīng)的DFA。

3答案：(每小題10分)

(1)考慮在先產(chǎn)生同樣數(shù)目的a,b,然后再生成多余的a。以下是一種解法：

S—■aSb|aS\e

(2)AaB\bB

Z?-aJ|bA\e

5證明E+T*(id)是文法的一個(gè)句型，指出該句型的所有短語、直接短語和句柄。

答：E=E+TnE+7*F=E+T*(E)=E+T*(T)=E+T*(F)=E+T*(id),

rmrmrmrmrmnn

短語：id,(id),性(id),E+7*(id)?

直接短語：id。

句柄是id。

編譯原理D卷

3、何謂“標(biāo)識(shí)符”，何謂“名字”，兩者的區(qū)別是什么？

4、令+、*和t代表加、乘和乘幕，按如下的非標(biāo)準(zhǔn)優(yōu)先級(jí)和結(jié)合性質(zhì)的約定，計(jì)算1+

1*2t*1t2的值:

(1)、優(yōu)先順序(從高至低)為+、*和f,同級(jí)優(yōu)先采用左結(jié)合。

(2)、優(yōu)先順序?yàn)閠、+、*,同級(jí)優(yōu)先采用右結(jié)合。

6、令文法金為N-D|ND,D-0|1|2|3|4|5|6|7|8|9

⑴、Ge的語言L(Ge)是什么?

(2)、給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。

7、寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。

8、令文法為E-T|E+T|E-T

T-F|T*F|T/F

F-(E)|i

(1)給出i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)；

給出i+i+i、i+i*i和i-i-i的語法樹。

9、證明下面的文法是二義的：S-iSeS|iS|i

11、給出下面語言的相應(yīng)文法：

Li={a"b"c’|n》l,i>0})

L={a'bnc"In>l,i20}

L=|n,mNO}

L^frOTO"In,m20}

3解：標(biāo)識(shí)符是高級(jí)語言中定義的字符串，一般是以英文字母(包括大小寫字母)或下劃線

開頭的，由數(shù)字、字母和下劃線組成的一定長(zhǎng)度的字符串，它只是一個(gè)標(biāo)志，沒有其他含義。

名字是用標(biāo)識(shí)符表示的，但名字不僅僅是一個(gè)字符串，它還具有屬性和值。

4解：

⑴、1+1*2t*1t2=2*2t*1t2=4t*1t2=4tt2=

⑵、1+1*2t*1t2=

6解：

(1)、L(Ge)是由。到9這10個(gè)數(shù)字組成的字符串。

(2)、句子0127、34和568的最左推導(dǎo)：

N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127

N=>ND=>DD=>3D=>34

N=>ND=>NDD=>DDD=>5DD=>56D=>568

句子0127、34和568的最右推導(dǎo)：

N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127

N=>ND=>N4=>D4=>34

N=>ND=>N8=>ND8=>N68=>D68=>568

7解:

G(S)：A-2|4|6|8ID

BfA|0

C-CB|A

D-l|3|5|7|9

S-CDID

8解：

(1)最左推導(dǎo)為：

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

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

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

最右推導(dǎo)為：

E=>E+T=>E+T*F=〉E+T*i=〉E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i

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

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

(2)語法樹：

9解：考慮句子iiiei,存在如下兩個(gè)最右推導(dǎo):

S=>iSeS=>iSei=>iiSei=>iiiei

S=>iS=>iiSeS=>iiSei=>iiiei

由此該文法是二義的。

11解：

Li的文法:S-AC：A-aAbIab：C-*cCIe

L的文法：SfAB；AfaA|e；B-bBc|be

L；的文法：S-AB；A-aAb|e；B-aBb|e

L，的文法：S-*ISO|A；A-OA1|e；

編譯原理E卷

1、令A(yù)、B和C是任意正規(guī)式，證明以下關(guān)系成立：

A|A=A

(A*)*=A*

A*=t|AA*

(AB)*A=A(BA)*

(A|B)*=(A*B*)*=(A*|B*)*

A=b|aA當(dāng)且僅當(dāng)A=a*b

2、構(gòu)造下列正規(guī)式相應(yīng)的DFA

1(0|1)*101

1(1010*|1(010)*1)*0

0*10*10*10*

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

3、給出下面正規(guī)表達(dá)式：

(1)以01結(jié)尾的二進(jìn)制數(shù)串；

(2)能被5整除的十進(jìn)制整數(shù)；

包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串；

4、對(duì)下面情況給HlDFA及正規(guī)表達(dá)式：

(1){0,1}上不含子串010的所有串。

5、將圖3.18的(a)和(b)分別確定化和最小化。

a

6、構(gòu)造一個(gè)DFA,它接受￡={0,1}上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在

右邊八

7、給定右線性文法G：

S-OS|IS|1A|0B

A-1C|1

B-*OC|0

C-OC|1C|0|1

求出一個(gè)與G等價(jià)的左線性文法。

文法G對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：

0,10,1

E卷答案

1證明：

⑴、A|A=A

L(A|A)=L(A)UL(A)=L(A),所以有A|A=A。

(2)、(A*)*=A*

⑶、A*=e|AA*

通過證明兩個(gè)正規(guī)式所表示的語言相同來證明兩個(gè)正規(guī)式相等。

L(￡|AA*)=L(￡)UL(A)L(A*)=L(￡)UL(A)(L(A))*

23

=L(E)UL(A)((L(A))°U(L(A))'U(L(A))U(L(A))U-)

=L(e)U(L(A))'U(L(A))2U(L(A))3U(L(A))"U-

=(L(A))*=L(A*)

即:L(eIAA*)=L(A*),所以有：A*=e]AA*

(4)、(AB)*A=A(BA)*

利用正規(guī)式的分配率和結(jié)合律直接推導(dǎo)。

(AB)*A=((AB)°|(AB)1I(AB)2I(AB)3|-)A

=￡A|(AB)'A|(AB)2AI(AB)%|…

=Ae|A(BA)1|A(BA)2|A(BA)3|…

=A(ej(BA)1|(BA)2I(BA)3|???)

=A(BA)*

l|J：(AB)*A=A(BA)*

⑸、(A|B)*=(A*B*)*=(A*|B*)*

證明:先證(A|B)*=(A*B*)*

因?yàn)長(zhǎng)(A)UL(A)*L(B)*,L(B)uL(A)*L(B)*

故:L(A)UL(B)cL(A)*L(B)*

于是由本題第二小題結(jié)論可知(L(A)UL(B))*G(L(A)*L(B)*)*①

又L(A)QL(A)UL(B),L(B)CL(A)UL(B)

故：L(A)*=(L(A)UL(B))*

L(B)*c(L(A)UL(B))*

因此有:L(A)*L(B)*G(L(A)UL(B))*(L(A)UL(B))*=((L(A)UL(B))*)2

故(L(A)*L(B)*)*Q((L(A)UL(B))*)*

由本題第二小題得：((L(A)UL(B))*)*=(L(A)UL(B))*

故得：(L(A)*L(B)*)*c(L(A)UL(B))*②

則由??得：(L(A)UL(B))*=(L(A)*L(B)*)*

由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*

即有(L(A)UL(B))*=L((A*B*))*③

而(A|B)*對(duì)應(yīng)的語言為(L(A)UL(B))*,且(A*B*)*對(duì)應(yīng)的語言為L(zhǎng)((A*B*))*

則根據(jù)③得(AIB)*=(A*B*)*

再證:(A*|B*)*=(A*B*)*

因?yàn)?A,B是任意正規(guī)式，由以上結(jié)論得：(A*.B*)*=((A*)*(B*)*)*

又由本題第二小題目的結(jié)論可得：(A*)*=A*,(B*)*=B*

因此,(A*|B*)*=(A*B*)*

綜合上述兩種結(jié)論，最后得：(A|B)*=(A*B*)*=(A*IB*)*

2解：

⑴、1(0|1)*101

第一步：根據(jù)正規(guī)式構(gòu)造NFA,先引入初始狀態(tài)X和終止?fàn)顟B(tài)Y：

再對(duì)該轉(zhuǎn)換圖進(jìn)行分解，得到分解后的NFA如下圖:

0

1

第二步：對(duì)?NFA進(jìn)行確定化，獲得狀態(tài)轉(zhuǎn)換矩陣:

狀態(tài)01

{X}0(1,2,3}

{1,2,3){213}{2,3,4}

(2,3)⑵3)(2,3,4}

{2,3,4}{2,3,5}(2,3,4}

⑵3.5}{2,3}{2,3,4,Y)

{2,3,4,Y}{2,3,5}(2,3,4}

根據(jù)轉(zhuǎn)換矩陣獲得相應(yīng)的DFA：

第三步：化簡(jiǎn)該DFA,獲得最簡(jiǎn)的DFA即為所求。

首先根據(jù)是否終止?fàn)顟B(tài)將所有狀態(tài)分為兩個(gè)集合{0,1,2,3,4}和{5},這里集合{5}

已經(jīng)不可劃分，只需考慮集合{0,1,2,3,4}。

(0,1,2,3,4}。={2,4,{0,1,2,3,4}1={1,3,5}

因?yàn)閧1,3,5}和{2,4,-}不在一個(gè)集合里面，所以需要對(duì)集合{0,1,2,3,4}進(jìn)行

進(jìn)一步的劃分，檢查其中的所有狀態(tài)。狀態(tài)0不能接受字符0,需要把狀態(tài)0劃分出來；另

外，只有狀態(tài)4讀入字符1后進(jìn)入狀態(tài)5,因此將狀態(tài)4劃分出來，劃分的結(jié)果為4個(gè)集合:

{0},{1,2,3},⑷，⑸。

檢查集合{1,2,3},{1,2,3}o={2,4},不屬于同一個(gè)集合，因此要對(duì)集合{1,2,

3}進(jìn)行進(jìn)一步劃分，劃分結(jié)果為5個(gè)集合：{0},{1,2},{3},{4},{5}。

檢查集合{1,2},{1,2}。=⑵，{1,2}尸3,不需要進(jìn)行進(jìn)?步劃分。所以最終劃分結(jié)

果為5個(gè)集合：{0},{1,2},⑶，⑷，{5},

所以，最終所求DFA如下圖示：

0

(1)以01結(jié)尾的二進(jìn)制數(shù)串;

(1|0)*01。

(2)能被5整除的十進(jìn)制整數(shù);

(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)(0|5)o

(3)包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串;

1*0(1|01*0)*|0*1(0|10*1)*。

4解:

（1）、直接寫出滿足條件的正規(guī)表達(dá)式?？紤]滿足條件的字符串中的1：在串的開始部

分可以有0個(gè)或多個(gè)1,串的尾部也可以有。個(gè)或多個(gè)1,但串的中間只要出現(xiàn)1則至少在

兩個(gè)以上，所以滿足條件的正規(guī)表達(dá)式為1*（0門11*）*1*。

所求的DFA如下圖所示:

10

5解：

(1)、圖(a)中為一個(gè)NFA,所以需要先對(duì)它進(jìn)行確定化，得到DFA,然后再對(duì)DFA

進(jìn)行最小化。

首先進(jìn)行確定化，如下兩個(gè)表所示：

狀態(tài)ab

{0}{0,1}{1}

{0,1}{011}{1}

{1}{0}0

狀態(tài)ab

012

112

20

根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到如下圖所示的DFA：

化簡(jiǎn)后的DFA為:

(2)、題中所給即為一個(gè)DFA,不需要確定化，只對(duì)它進(jìn)行最小化即可。

首先將狀態(tài)劃分為兩個(gè)集合{{0,1}，{2,3,4,5}}.有{0,1}產(chǎn){1},{0,1'={2,4}

和{2,3,4,5}?={1,3,0,5},{2,3,4,5}b={2,3,4,5),所以可以進(jìn)一步劃分為{{0,

1},{2,4},{3,5}},然后有{0,1}產(chǎn){1},{0,1}產(chǎn){2,4},{2,4}產(chǎn){1,0},{2,4}?={3,

5},{3,5}產(chǎn){3,5},{3,5}產(chǎn){2,4}。因此，最后劃分結(jié)果是{{0,1},{2,4},{3,5}}。

最小化后的DFA如下圖所示:

6解：第一步：寫出正規(guī)表達(dá)式。根據(jù)題意，該DFA接受的字符串由0和1組成，并且

每個(gè)1的后面都有0直接跟在右邊，因此，可以將該字符串理解為由0和10構(gòu)成的串，則

相應(yīng)的正規(guī)表達(dá)式就是(0門0)*。

第二步：構(gòu)造NFA。首先得出下圖：

然后對(duì)上圖進(jìn)行分解后得到如下圖所示的NFA。

0

第三步：確定化，得到DFA。確定化結(jié)果如表14.1所列；給狀態(tài)編號(hào)，得到表14.2所

示的狀態(tài)轉(zhuǎn)換矩陣:

狀態(tài)01

{X,1,Y){1.Y)⑵

{1,Y}{1,Y}{2}

{2}{1,Y}0

表14.1狀態(tài)轉(zhuǎn)換矩陣

狀態(tài)01

012

112

21

表14.2新的狀態(tài)轉(zhuǎn)換矩陣

根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到DFA如下圖所示:

第四步：對(duì)該DFA進(jìn)行最小化。其分析過程如下:

{0,1},{2}

{0,{0,l}i={2}

{0,1},{2}

最小化后的DFA如圖所示，該DFA即為所求。

對(duì)狀態(tài)轉(zhuǎn)換圖進(jìn)行確定化，得到狀態(tài)轉(zhuǎn)換矩陣:

狀態(tài)01

{S}{S,B}{S,A}

{s,B}{S,B,C,Z){S,A}

{S,A}{S,B}{S,A,C,Z)

{S,B,C,Z){S,B,C,Z){S,A,C,Z)

{S,A,C,Z){S,B,C,Z){S,A,C,Z)

給狀態(tài)編號(hào)，得到新的狀態(tài)轉(zhuǎn)換矩陣:

狀態(tài)01

012

132

214

334

434

根據(jù)狀態(tài)轉(zhuǎn)換矩陣獲得DFA如下:

0

還可以對(duì)上圖的DFA進(jìn)行化簡(jiǎn)，狀態(tài)3和4可以合并，化簡(jiǎn)后的DFA如下圖所示:

不難看出，該DFA接受的語言是｛0,1｝上包含00或11的字符串。根據(jù)化簡(jiǎn)后的DFA,

我們可以寫出相應(yīng)的左線性文法G'：

T-AO|Bl|TO|T1

A-*BO|0

B-A1|1

編譯原理F卷

1、考慮下面的文法G,：

S-aIAI(T)

TfT,S|S

(1)消去Gi的左遞歸。然后對(duì)每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。

(2)經(jīng)改寫后的文法是否是LL⑴的？給出它的預(yù)測(cè)分析表。

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

FIRST(S)={a,A,(}

FIRST(T)={a,A,()

FIRST(『)={,,e}

FOLLOW(S)={),',',#}

FOLLOW(T)={)}

FOLLOW(T‘)={)}

從而可見改造后的文法符合LL(1)文法的充分必要條件，所以是此(1)的。

該文法的預(yù)測(cè)分析發(fā)

a()

sS->as->"S->(T)

TT->S『T->S『T->SV

v->&T->,ST

2、對(duì)下面的文法G：

ETE，

E'-+E|e

TfFT'

T'-T|e

FTF，

F'-?*F'|e

P-(E)|a|b|A

(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW.,

(2)證明這個(gè)文法是LL⑴的。

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

(4)構(gòu)造它的遞歸下降分析程序。

3、下面文法中，哪些是LL(1)的，說明理由。

⑴、

S-Abe

A-a|e

B-b|￡

(2)、

S-*Ab

A-a|B|￡

B-*b|￡

⑶、

S-ABBA

A-a|e

B-b|e

(4)、

S-aSe|B

B-bBe|C

C-*cCe|d

4、對(duì)下面文法：

Expr-*-Expr

Exprf(Expr)|Var

ExprTail-?-ExprI￡

Var-*idVarTail

VarTail->(Expr)I￡

(1)、構(gòu)造LL(1)分析表。

⑵、給出對(duì)句子id—id((id))的分析過程。

5、把下面文法改寫為L(zhǎng)L(1)的：

Declist-*Declist；DeciIDeci

Decl-*IdList：Type

IdList->IdList,id|id

Type-*ScalarTypeIarray(ScalarTypeList)ofType

ScaiarType-*id|Bound..Bound

BoundfSignIntLiteralIid

Sign-+I-Ie

ScalarTypeListfScalarTypeList,ScalarType|ScalarType

1、令文法G為

E-E+T|T

T-*T*F|F

F-*(E)|i

證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語，直接短語和句柄。

2、考慮下面的表格結(jié)構(gòu)文法我：

S-aIAI(T)

TfT,S|S

(1)給出(a,(a,a))和(((a,a),A,(a)),a)的最左和最右推導(dǎo)。

指出(((a,a),\(a)),a)的規(guī)范歸約及每一步的句柄。根據(jù)這個(gè)規(guī)范歸約，給出“移進(jìn)-

歸約”的過程，并給出它的語法樹自下而上的構(gòu)造過程。

3、⑴計(jì)算練習(xí)2文法Gz的FIRSTVT和LASTVT,

(2)計(jì)算G2的優(yōu)先關(guān)系。。是一個(gè)算符優(yōu)先文法嗎？

(3)給出輸入串(a,(a,a))的算符優(yōu)先分析過程。

4、考慮文法：

S-AS|b

A-SA|a

(1)列出這個(gè)文法的所有LR(0)項(xiàng)目。

(2)構(gòu)造這個(gè)文法的LR(O)項(xiàng)目集規(guī)范族及識(shí)別活前綴的DFA?

(3)這個(gè)文法是SLR的嗎？若是，構(gòu)造出它的SLR分析表。

(4)這個(gè)文法是LALR或LR⑴的嗎？

F卷答案

1答：解：

(1)按照T、S的順序消除左遞歸，得到文法：0

G'(S)

SfaIAI(T)

T-ST'

T'一，SV|￡

對(duì)于非終結(jié)符S",『的遞歸子程序如下:

ProcedureS;

Begin

Ifsym='a'orsym=

Thenadvance

Elseifsym='('

Thenbegin

Advance;

T;

Ifsym=9y

Thenadvance

Elseerror

End

Elseerror

Ends;

ProcedureT;

Begin

S;『;

Ends;

ProcedureT'

Begin

Ifsym='

Thenbegin

Advance;

S;T'

Ends

ends;

2解：

(1)計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下:

FIRST(E)={(,a,b,A}

FIRST(E')={+,e}

FIRST(T)={(,a,b,A}

FIRST(T')={(,a,b,A,e)

FIRST(F)={(,a,b,A}

FIRST(F')={*,e}

FIRST(P)={(,a,b,A}

FOLLOW(E)={#,)}

FOLLOW(E')={#,)}

FOLLOW(T)={+,),#}

FOLLOW(T')={+,),#}

FOLLOW(F)={(,a,b,A,+,),#}

FOLLOW(F')={(,a,b,A,+,),#}

FOLLOW(P)={*,(,a,b,△,+,),#}

(2)本文法是LL(1)文法。

證明：通過觀察可知文法中不含有左遞歸，滿足LL(1)文法定義的第一個(gè)條件。

考慮下列產(chǎn)生式：

E'-+E|e

T'fT|e

F'一*F'|e

P~(E)|a|b|A

因?yàn)椋?/p>

FIRST(+E)nFIRST(e)={+}Cl{e}=0

FIRST(E')CFOLLOW(E')={+}D{#,)}=0

FIRST(T)nFIRST(e)={(,a,b,A}A{e}=0

FIRST(T')nFOLLOW(T')={(,a,b,A)n{+,),#}=0

FIRST(*『)nFIRST(e)={*}A{￡}=0

FIRST(F，)AFOLLOW(")={*}A{(,a,b,A,+,),#}二0

FIRST((E))nFIRST(a)AFIRST(b)AFIRST(A)=0

所以該文法是LL⑴文法。

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

預(yù)測(cè)分析表

a

+*()ab#

EE9TE，E-?TE'ETTE，E-?TE'

E,E'9+EE'斗E，-乂

TT今FT『fFT'T->FT,T今FT'

T'T'"T'9TT'型T'9TT'9TT'

FFTPF'F今PF'P-?PF,F今PF'

F,F'&F，F(xiàn)'今&F'F'*F'"F'*F'型

9*F'

pP今⑻P->aP->bp今*

(4)構(gòu)造其遞歸下降分析程序:

ProcedureE;

Begin

T;E'

End;

ProcedureE’;

Begin

Ifsym='+'

Thenbegin

Acvance;

E

End

End;

ProcedureT;

Begin

F;T'

End;

ProcedureT';

Begin

Ifsym￡first(T)

ThenT

Elseifsym=thenerror

End;

ProcedureF;

Begin

Ifsym《first(P)

P；F';

End;

ProcedureF'

Begin

Ifsym='*'

Thenbegin

Advance;

F，

End

End;

ProcedureP

Begin

Ifsym='a'orsym='b'orsym='"

Thenacvance

Elseifsym='('

Thenbegin

Advance;

E;

Ifsym=')'

Thenadvance

Elseerror

End

Elseerror

End;

3解：

(1)該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下:

FIRST(S)={a,b,c}

FIRST(A)={a,e}

FIRST(B)={b,e}

FOLLOW(S)={#}

FOLLOW(A)={b,c)

FOLLOW(B)={c}

可見該文法滿足LL⑴文法的三個(gè)條件，是LL(1)文法。

(2)該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下:

FIRST(S)={a,b}

FIRST(A)={a,b,e}

FIRST(B)-{b,t}

FOLLOW(S)={#}

FOLLOW(A)=

FOLLOW(B)=

考慮A-a|B|e,因?yàn)镕IRST(B)AFOLLOW(A)=r0,所以該文法不是LL⑴文

法。

(3)該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下:

FIRST(S)={a,b,s}

FIRST(A)={a,e}

FIRST(B)={b,e}

FOLLOW(S)={#}

FOLLOW(A)={a,b,#}

FOLLOW(B)={a,b,#}

考慮A—a|e和B-bIe,因?yàn)?/p>

FIRST(a)nFOLLOW(A)={a}#0

FIRST(b)AFOLLOW(B)=W0

所以該文法不是LL(1)文法。

(4)該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下:

FIRST(S)={a,b,c,d}

FIRST(B)={b,c,d}

FIRST(C)={c,d}

FOLLOW(S)={e,#}

FOLLOW(B)={e,#}

FOLLOW(C)={e,#}

可見該文法滿足LL(1)文法的三個(gè)條件，是LL(1)文法。

4解：

(1)、計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：

FIRST(Expr)={-,(,id)

FIRST(ExprTail)={-,e}

FIRST(Var)={id}

FIRST(VarTail)={(,t)

FOLLOW(Expr)={),#}

FOLLOW(ExprTail)={),#}

FOLLOW(Var)={-,),#}

FOLLOW(VarTai1)={-,I,#}

構(gòu)造其預(yù)測(cè)分析表如下：

-id()#

ExprExpr-*-ExprExprExprExprf

-(Expr)

ExprTailExprTail->-ExprExprTailExprTail-

8e

VarVarfid

VarTail

VarTai1VarTail-*￡VarTailfVarTail-*-eVarTail-*￡

(Expr)

(2)、句子id—id((id))的分析過程如下:

步驟符號(hào)棧輸入申所用產(chǎn)生式

0#Exprid—id((id))

#

1#ExprTailVarid—id((id))Expr-*VarExprTail

#

2#ExprTailVarTailidid—id((id))Var-*idVarTail

#

3#ExprTailVarTail-id((id))#

4#ExprTail-id((id))#VarTail->￡

5#Expr--id((id))#ExprTail-*-Expr

6#Expr-id((id))#

7#Expr--id((id))#Expr-*-Expr

8#Exprid((id))#

9#ExprTailVarid((id))#Expr-*VarExprTail

10#ExprTailVarTailidid((id))#Var-idVarTail

11#ExprTailVarTail((id))#

12#ExprTail)Expr(((id))#VarTail->(Expr)

13#ExprTail)Expr(id))#

14itExprTail))Expr((id))#

15#ExprTail))Exprid))#

16#ExprTail))ExprTalVarid))#Expr-*VarExprTail

17#ExprTail))ExprTailVarTailid))#Var-*idVarTail

id

18#ExprTail))ExprTailVarTail))#

19#ExprTail))ExprTail))#VarTail->￡

20#ExprTail))))#ExprTail->￡

21#ExprTail))#

22#ExprTail#

23##ExprTail￡

sue

5解:

首先消除左遞歸，得到文法G(Declist)：

Declist->DeclDeclistJ

Declist'f；DeciDeclist,I￡

Decl-*IdList：Type

IdList-idIdList,

IdList'f,idList'|￡

Type-*ScalarTypeIarray(ScalarTypeList)ofType

ScalarType->idIBound..Bound

BoundfSignIntLiteral|id

Sign一+|-IE

ScalarTypeList->ScalarTypeScalarTypeListJ

ScalarTypeList)—,ScalarTypeScalarTypeListJI￡

顯然，改造后的文法沒有左公共因子，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合

如下：

FIRST(Declist)={id}

FIRST(Declist,)={；,e}

FIRST(Deci)={id}

FIRST(IdList)={id}

FIRST(IdList,)={；,e}

FIRST(Type)={id,+,IntLiteraLarray}

FIRST(ScalarType)={id,+,IntLiteral}

FIRST(Bound)={id,+,InLiteral}

FIRST(Sign)={+,e}

FIRST(ScalarTypeList)={id,+,IntLiteral)

FIRST(ScalarTypeList,)={,,e}

FOLLOW(Deciist)={#}

FOLLOW(Declistr)={#}

FOLLOW(Decl)={id,；}

FOLLOW(IdList)={：}

FOLLOWddList')={:}

FOLLOW(Type)={id,；}

FOLLOW(ScalarType)={id,；,,}

FOLLOW(Bound)={id,；,)','

FOLLOW(Sign)=