1編譯原理及實現(xiàn)課后題及答案

1編譯原理及實現(xiàn)課后題及答案編譯原理及實現(xiàn)

2.1設字母表A={a}，符號串x=aaa，寫出下列符號串及其長度：x0,xx,x5以及A+和A*.

x0=(aaa)0=ε|x0|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}

2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，寫出如下符號串及它們的長度：xy，xyz，（xy）3

12

|=(xy)3|cbabcbabcbab=(abcb)3=(xy)37

|=xyz|abcbaab=xyz4|=xy|abcb=xy

2.3設有文法G：S∷=SS*|SS+|a，寫出符號串a(chǎn)a+a*規(guī)范推導，

并構(gòu)造語法樹。

S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

2.4已知文法G：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,請寫出全部由此文法描述的只含有四個符號的句子。

0101

=>V101=>Z01=>V1=>Z1001=>U001=>Z01=>V1=>Z0110=>V110=>Z10=>U0=>Z1010=>U010=>Z10=>U0=>Z

2.5已知文法G：S∷=ABA∷=aA︱εB∷=bBc︱bc,寫出該文法描述的語言。

1}

>=m0,>=n|{anbmcm=L(G)1}>=n|{bncn描述的語述的bc︱bBc=∷B0}>=n|{an:描述的語述ε︱aA=∷A2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，寫出該文法的開頭符號、終結(jié)符號集合VT、非終結(jié)符號集合VN。

開頭符號：E

Vt={+,-,*,/,（,）,i}Vn={E,F,T}

2.7對2.6題的文法，寫出句型T+T*F+i的短語、簡潔短語以及句柄。

短語：T+T*F+iT+T*FiiTT*F簡潔短語：iT*FT句柄：T

2.8設有文法G：S∷=S*S|S+S|(S)|a，該文法是二義性文法嗎？

依據(jù)所給文法推導出句子a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。

2.9寫一文法，使其語言是奇正整數(shù)集合。A::=1|3|5|7|9|NA

N::=0|1|2|3|4|5|6|7|8|9

2.10給出語言{anbm|n,m≥1}的文法。

G:S::=AB

A::=aA|a

B::=bB|b

3.1有正則文法G：Z::=Ua|Vb，U::=Zb|b，V::=Za|a，畫出該文法的狀態(tài)圖，并檢查句子abba是否合法。

解：該文法的狀態(tài)圖如下：

句子abba合法。

3.2狀態(tài)圖如圖3.35所示，S為開頭狀態(tài)，Z為終止狀態(tài)。寫出相應的正則文法以及V，Vn和Vt。

圖3-35狀態(tài)圖

解：左線性文法G:右線性文法G’:Z::=Ab|bS::=aA|b

A::=Aa|aA::=aA|bV={Z,A,a,b}V={S,A,a,b}

Vn={Z,A}Vn={S,A}

Vt={a,b}Vt={a,b}

3.3構(gòu)造下列正則表達式相應的NFA：

1(1|0)*|0

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

解：正則表達式：1(1|0)*|0

1、

2、

3、

4、

正則表達式：1(1010*|1(010)*1)*0

3.4將圖3.36的NFAM確定化

圖3.36狀態(tài)圖

解：

DFA:

3.5將圖3.37的DFA化簡。

解：

q0={0,1}q1={2,4}q2={3,5}

化簡后的DFA：

4.1對下面文法，設計遞歸下降分析程序。

S→aAS|(A),A→Ab|c

解：首先將左遞歸去掉，將規(guī)章A→Ab|c改成A→c非終結(jié)符號S的分析程序如下：

非終結(jié)符號A的分析程序如下：

4.2設有文法G：

Z∷=(A),A∷=a|Bb,B∷=Aab

若采納遞歸下降分析方法，對此文法來說，在分析過程中，能否避開回溯？為什么？

解：若采納遞歸下降分析方法，對此文法來說，在分析過程中不能避開回朔。由于規(guī)章A∷=a|Bb和規(guī)章B∷=Aab構(gòu)成了間接左遞歸，不滿意實現(xiàn)沒有回溯的遞歸下降分析方法的條件（1）（書P67），且規(guī)章A::=a|Bb，F(xiàn)IRST(a)={a}，F(xiàn)IRST(Bb)={a}，即此規(guī)章候選式的首符號集有相交，不滿意實現(xiàn)沒有回溯的遞歸下降分析方法的條件（2）（書P67），在分析過程中，將造成回溯。改寫文法可避開回溯：

將規(guī)章B∷=Aab代入規(guī)章A∷=a|Bb得：A∷=a|Aabb，再轉(zhuǎn)換成：A∷=a{abb}，可避開回溯。

4.3若有文法如下，設計遞歸下降分析程序。

>)

表達達(|+|-改為：

|*|/改為：的分析程序如下：

非終結(jié)符號的分析程序如

下：

非終結(jié)符號

的分析程序

如下：

下：

非終結(jié)符號

的分析程序如

下：

4.4有文法G：A::=aABe|ε，B::=Bb|b

（1）求每個非終結(jié)符號的FOLLOW集。

（2）該文法是LL(1)文法嗎？

（3）構(gòu)造LL(1)分析表。

解：

（1）FOLLOW(A)=First(B)∪{#}={b,#}

FOLLOW(B)={e,b}

（2）該文法中的規(guī)章B::=Bb|b為左遞歸，因此該文法不是LL(1)文法

（3）先消退文法的左遞歸（轉(zhuǎn)成右遞歸），文法變?yōu)椋篈::=aABe|ε，B::=bB’，B’::=bB’|ε，該文法的LL(1)分析表為：

更常用且簡潔的LL(1)分析表：

4.5若有文法A→(A)A|ε

（1）為非終結(jié)符A構(gòu)造FIRST集合和FOLLOW集合。

（2）說明該文法是LL(1)的文法。

解：

（1）FIRST(A)＝｛(,ε｝

FOLLOW(A)＝｛)，#｝

（2）

該文法不含左遞歸；

FIRST（(A)A）={(}，F(xiàn)IRST（ε）={ε}，F(xiàn)IRST（(A)A）∩FIRST（ε）=Φ，

且FOLLOW(A)＝｛)，#｝，F(xiàn)IRST（(A)A）∩FOLLOW(A)=Φ，

因此，該文法滿意LL(1)文法的條件，是LL(1)文法。

4.6利用分析表4-1，識別以下算術(shù)表達式，請寫出分析過程。（1）i+i*i+i

（2）i*(i+i+i)

解：

（1）i+i*i+i

（2）i*(i+i+i)

4.7考慮下面簡化了的C聲明文法：→；

→int|float|char

→ID,|ID

（1）在該文法中提取左因子。

（2）為所得的文法的非終結(jié)符構(gòu)造FIRST集合和FOLLOW集合。（3）說明所得的文法是LL(1)文法。

（4）為所得的文法構(gòu)造LL(1)分析表。

（5）假設有輸入串為“charx，y，z；”，寫出相對應的LL(1)分析過程。

解：

（1）規(guī)章→ID,|ID提取公因子如下：→ID（,|ε）

增加新的非終結(jié)符，規(guī)章變?yōu)椋?/p>

→ID

→，|ε

C聲明文法轉(zhuǎn)變?yōu)椋?/p>

→；

→int|float|char

→ID

→，|ε

（2）FIRST()＝FIRST()＝｛int，float，char｝FIRST()＝｛ID｝

FIRST()＝｛，，ε｝

FOLLOW()＝｛#｝

FOLLOW()＝FIRST()＝｛ID｝

FOLLOW()＝FOLLOW()＝｛；｝

（3）所得文法無左遞歸，且

FIRST（int）∩FIRST（float）∩FIRST（char）＝ΦFIRST（，）∩FIRST（ε）＝Φ

FIRST（，）∩FOLLOW()＝Φ

因此，所得文法為LL(1)文法。

（4）所得的文法構(gòu)造LL(1)分析表如下所示：

更常用且簡潔的LL(1)分析表：

（5）輸入串“charx，y，z；”相對應的LL(1)分析過程如下：

5.1考慮以下的文法：

S→S;T|T

T→a

（1）為這個文法構(gòu)造LR(0)的項目集規(guī)范族。

（2）這個文法是不是LR(0)文法？假如是，則構(gòu)造LR(0)分析表。（3）對輸入串“a;a”進行分析。

解：

（1）拓廣文法G：

0：S’→S

1：S→S;T

2：S→T

3：T→a

構(gòu)造LR(0)項目集規(guī)范族

（2）該文法不存在“歸約－歸約”和“歸約－移進”沖突，因此是LR(0)文法。LR(0)分析表如下：

（3）對輸入串“a;a”進行分析如下：

5.2證明下面文法是SLR(1)文法，但不是LR(0)文法。S→A

A→Ab|bBa

B→aAc|a|aAb

解：文法G：

0：S→A

1：A→Ab

2：A→bBa

3：B→aAc

4：B→a

5：B→aAb

構(gòu)造LR(0)項目集規(guī)范族：

狀態(tài)5存在“歸約－移進”沖突，狀態(tài)9存在“歸約－歸約”沖突，因此該文法不是LR(0)文法。

狀態(tài)5：

FOLLOW(B)＝｛a｝，因此，F(xiàn)OLLOW(B)∩｛b｝＝Φ

狀態(tài)9：

FOLLOW(B)＝｛a｝，F(xiàn)OLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ

狀態(tài)5和狀態(tài)9的沖突均可用SLR(1)方法解決，構(gòu)造SLR(1)分析表如下：

該SLR(1)分析表無重定義，因此該文法是SLR(1)文法，不是LR(0)文法。

5.3證明下面文法是LR(1)文法，但不是SLR(1)文法。S→AaAb|BbBa

A→ε

B→ε

解：拓廣文法G：

0：S’→S

1：S→AaAb

2：S→BbBa

3：A→ε

4：B→ε

構(gòu)造LR(0)項目集規(guī)范族：

狀態(tài)0存在“歸約－歸約”沖突，且FOLLOW(A)＝｛a,b｝，F(xiàn)OLLOW(B)＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以該文法不是SLR(1)文法。

構(gòu)造LR(1)項目集規(guī)范族：

LR(1)分析表：

分析表無重定義，說明該文法是LR(1)文法，不是SLR(1)文法。

5.4考慮以下的文法：

E→EE＋

E→EE*

E→a

（1）為這個文法構(gòu)造LR(1)項目集規(guī)范族。

（2）構(gòu)造LR(1)分析表。

（3）為這個文法構(gòu)造LALR(1)項目集規(guī)范族。

（4）構(gòu)造LALR(1)分析表。

（5）對輸入符號串“aa*a+”進行LR(1)和LALR(1)分析。解：

（1）拓廣文法G：

0：S→E

1：E→EE＋

2：E→EE*

3：E→a

構(gòu)造LR(1)項目集規(guī)范族：

（2）構(gòu)造LR(1)分析表

（3）構(gòu)造LALR(1)項目集規(guī)范族:

（4）構(gòu)造LALR(1)分析表。

（5）對輸入符號串“aa*a+”進行LR(1)分析:

對輸入符號串“aa*a+”進行LALR(1)分析:

5.5說明以下的文法是LR(1)文法，但不是LALR(1)文法。S→aAd|bBd|aBe|bAe

A→c

B→c

解：

拓廣文法：

0：S’→S

1：S→aAd

2：S→bBd

3：S→aBe

4：S→bAe

5：A→c

6：B→c

構(gòu)造LR(1)項目集規(guī)范族

構(gòu)造LR(1)分析表：

同核項目集合并，構(gòu)造LALR(1)項目集規(guī)范族：

構(gòu)造LALR(1)分析表：

從LR(1)分析表可以看出，分析表無重定義，因此該文法是LR(1)文法。

從LALR(1)分析表可以看出，分析表ACTION和ACTION存在重定義，因此該文法不是LALR(1)文法。

7.1給出編譯下面程序的有序符號表。

main()

{

intm,n;

realx;

charname;

}

解：

7.2按“質(zhì)數(shù)除余法”，給出編譯上題程序的散列符號表。

解：正整數(shù)H＝ASC函數(shù)（字符串），質(zhì)數(shù)＝5，散列符號表如下所示：

7.3給出編譯到下面程序a、b、c處的棧式符號表。

realx,y;

charstr;………………a

intfun1(intind)

{

intx;……………b

x=m2(ind+1);

}

main()

{

chary;…………c

x=2;y=5;printf("%d\n",fun1(x/y));

}

解：

10.1對下列基本塊應用DAG進行優(yōu)化：

M)

，，L，(=L)，J，K，(+K)，5，B，(*J)，I，H，

(+I)，C，A，(*H)，C，A，(+G)

，F(xiàn)，B，(*

F)