編譯原理作業(yè)答案

《編譯原理》習(xí)題解答：

第一次作業(yè)：

P142、何謂源程序、目標(biāo)程序、翻譯程序、匯編程序、編譯程序和解釋程序？它們之間

可能有何種關(guān)系？

答：被翻譯的程序稱(chēng)為源程序；

翻譯出來(lái)的程序稱(chēng)為目標(biāo)程序或目標(biāo)代碼；

將匯編語(yǔ)言和高級(jí)語(yǔ)言編寫(xiě)的程序翻譯成等價(jià)的機(jī)器語(yǔ)言，實(shí)現(xiàn)此功能的程序稱(chēng)為翻

譯程序；

把匯編語(yǔ)言寫(xiě)的源程序翻譯成機(jī)器語(yǔ)言的目標(biāo)程序稱(chēng)為匯編程序；

解釋程序不是直接將高級(jí)語(yǔ)言的源程序翻譯成目標(biāo)程序后再執(zhí)行，而是一個(gè)個(gè)語(yǔ)句讀

入源程序，即邊解釋邊執(zhí)行；

編譯程序是將高級(jí)語(yǔ)言寫(xiě)的源程序翻譯成目標(biāo)語(yǔ)言的程序。

關(guān)系：匯編程序、解釋程序和編譯程序都是翻譯程序，具體見(jiàn)P4圖1.3。

P143、編譯程序是由哪些部分組成？試述各部分的功能？

答：編譯程序主要由8個(gè)部分組成：（1）詞法分析程序；（2）語(yǔ)法分析程序；（3）語(yǔ)義分

析程序；（4）中間代碼生成；（5）代碼優(yōu)化程序；（6）目標(biāo)代碼生成程序；（7）錯(cuò)誤檢查

和處理程序；（8）信息表管理程序。具體功能見(jiàn)P7-9。

P144、語(yǔ)法分析和語(yǔ)義分析有什么不同？試舉例說(shuō)明。

答：語(yǔ)法分析是將單詞流分析如何組成句子而句子又如何組成程序，看句子乃至程序是否

符合語(yǔ)法規(guī)則，例如：對(duì)變量x：=y符合語(yǔ)法規(guī)則就通過(guò)。語(yǔ)義分析是對(duì)語(yǔ)句意義進(jìn)行檢

查，如賦值語(yǔ)句中x與y類(lèi)型要一致，否則語(yǔ)法分析正確，語(yǔ)義分析則錯(cuò)誤。

補(bǔ)充：為什么要對(duì)單詞進(jìn)行內(nèi)部編碼？其原則是什么？對(duì)標(biāo)識(shí)符是如何進(jìn)行內(nèi)部編碼的？

答：內(nèi)部編碼從''源字符串”中識(shí)別單詞并確定單詞的類(lèi)型和值；原則：長(zhǎng)度統(tǒng)一，即刻

畫(huà)了單詞本身，也刻畫(huà)了它所具有的屬性，以供其它部分分析使用。對(duì)于標(biāo)識(shí)符編碼，先

判斷出該單詞是標(biāo)識(shí)符，然后在類(lèi)別編碼中寫(xiě)入相關(guān)信息，以表示為標(biāo)識(shí)符，再根據(jù)具體

標(biāo)識(shí)符的含義編碼該單詞的值。

第二次作業(yè)：

+

P381、設(shè)%={11,010},T2={0,01,1001},計(jì)算：T2TpT/，T2?

T2Tl={011,0010,0111,01010,100111,1001010}

T/={e,11,010,1111,11010,01011,010010........}

+

T2={0,01,1001,00,001,01001,010,0101........}

P38-398、設(shè)有文法G網(wǎng)：

S：：=aAb

A：：=BcA|B

B：：=idt|e

試問(wèn)下列符號(hào)串(1)aidtcBcAb(2)aidtccb(4)abidt是否為該文法的句型或句子。

(1)S=>aAbaBcAb=>aidtcAb=>aidtcBcAb句型但不是句子；

(2)S=>aAb=>aBcAb=>aidtcAb=>aidtcBcAb=>aidtccAb=>aidtccBb=>aidtccb；是句

型也是句子；

(4)該文法的句子或句型的最后一個(gè)字符串一定是字符“b”；

第三次作業(yè)：

P3911、試分別描述下列文法所產(chǎn)生的語(yǔ)言(文法開(kāi)始符號(hào)為S)：

(1)S：：=OSI01

(2)S：：=aaS|bc

n

(1)L(G)={0l|n^l};{解題思路：將文法轉(zhuǎn)換為正規(guī)表達(dá)式}

(2)L(G)={a2nbc|n^0}?

P3912、試分別構(gòu)造產(chǎn)生下列語(yǔ)言的文法：

(1){abna|n=0,1,2,3........}

(3){aban|n^l)

(5){anbmcp|n,m,p》0}

(1)G={VN，VT，P，S},VN={S,A},VT={a,b},

P：S：：=aAa

A：：=bA|￡

(3)G={VN,VT,P,S},VN={S,A},VT={a,b},

P：S：：=abA

A：：=aA|a

(5)?G={VN,VT,P,S},VN={S,A,B,C},VT={a,b,c},

P：S：：=ABC

A：：=aA|￡

B：：=bB|￡

C：：=cC|e

?G={VN,VT,P,S},VN={S},VT={a,b,c},

P：S：：=aS|bS|cS|e

P3915.設(shè)文法G規(guī)則為：

S：：=AB

B：：=a|Sb

A：：=Aa|bB

對(duì)下列句型給出推導(dǎo)語(yǔ)法樹(shù)，并求出其句型短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄。

(2)baabaab(3)bBABb

句型baabaab的短語(yǔ)a,ba,baa,baab,baabaab,簡(jiǎn)單短語(yǔ)a,句柄

(3)

短語(yǔ)bB,AB,ABb,bBABb

簡(jiǎn)單短語(yǔ)bB,AB,

句柄bB

第四次作業(yè)

P4124.下面文法那些是短語(yǔ)結(jié)構(gòu)文法,上下文有關(guān)文法，上下文無(wú)關(guān)文法，及正規(guī)文法?

l.S::=aBB::=cBB::=bC::=c

2.S::=aBB::=bCC::=cC：：=E

3.S::=aAbaA::=aBaA::=aaAB::=bA::=a

4.S::=aCdaC::=BaC::=aaAB::=b

5.S::=ABA::=aB::=bCB::=bC::=c

6.S::=ABA::=aB::=bCC::=cC：：=￡

7.S::=aAS::=￡A::=aAA::=aBA::=aB:::

8.S::=aAS::=EA::=bAbA::=a

短語(yǔ)結(jié)構(gòu)文法（0）4

上下文有關(guān)文法（1）3

上下文無(wú)關(guān)文法（2）568或者25678

正規(guī)文法(3)127或者1

P4229.用擴(kuò)充的BNF表示以下文法規(guī)則:

1.Z::=AB|AC|A

2.A::=BC|BCD|AXZ|AXY

3.S::=aABb|ab

4.A::=Aab|c

解:

1.Z::=A(B|C|E)::=A[B|C]

2.A::=BC(E|D)|{X(Z|Y)}::=BC[D]|{X(Z|Y)}

3.A::=a((AB|c)b)::=a[AB]b

4.A::={ab|c}::={ab}

第五次作業(yè)：

P744.畫(huà)出下列文法的狀態(tài)圖：

Z：：=Be

B：：=Af

A：：=e|Ae并使用該狀態(tài)圖檢查下列句子是否該文法的合法句子：f,eeff,eefe。

由狀態(tài)圖可知只有eefe是該文法的合法句子。

P745.設(shè)右線性文法G=({S,A,B}9{a,b},S,P),其中P組成如下：

S：：=bAA：：=bBA：：=aAA：：=bB：：=a

畫(huà)出該文法的狀態(tài)轉(zhuǎn)換圖。

P746.構(gòu)造下述文法G[Z]的自動(dòng)機(jī)，該自動(dòng)機(jī)是確定的嗎？它相應(yīng)的語(yǔ)言是什么？

Z：：=A0A：：=AO|Z1|O

解1：將左線性文法轉(zhuǎn)換為右線性文法，由于在規(guī)則中出現(xiàn)了識(shí)別符號(hào)出現(xiàn)在規(guī)則右

部的情形，因此不能直接使用書(shū)上的左右線性文法對(duì)應(yīng)規(guī)則，可以引入非終結(jié)符號(hào)B,將

左線性文法變?yōu)閆：：=A0A：：=AO|B1|OB：：=A0,具體為：

rA：=Z1rA：=B1

-I--------A:=A01I------------

、Z:=AOLB:=A0

將所得的新左線性文法轉(zhuǎn)換成右線性文法：

此時(shí)利用書(shū)上規(guī)則，其對(duì)應(yīng)的右線性文法為：A：：=OA|OB|OZ：：=0AB：：=1A

解2：先畫(huà)出該文法狀態(tài)轉(zhuǎn)換圖：

NFA=({S,A,Z},{0,1},M,{S},{Z})

其中M：M(S,0)={A}M(S,1)=0

M(A,0)={A,Z}M(A,1)=0

M(Z,0)=0M(Z,1)={A}

顯然該文法的自動(dòng)機(jī)是非確定的；它相應(yīng)的語(yǔ)言為：｛0,1｝上所有滿(mǎn)足以00開(kāi)頭以0

結(jié)尾且每個(gè)1必有0直接跟在其后的字符串的集合;那么如何構(gòu)造其相應(yīng)的有窮自動(dòng)機(jī)呢？

根據(jù)其轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示:

IIolis01

{S',S}{A}01①

{A}{A,Z,7?}12①

{A,Z,Z){A,Z,7?}{A}221

則其相應(yīng)的DFA為:

P748.設(shè)(NFA)M=({A,B},{a,b},M,{A},{B}),其中M定義如下：

M(A,a)={A,B}M(A,b)={B}M(B,a)=0M(B,b)={A,B}

請(qǐng)構(gòu)造相應(yīng)確定有窮自動(dòng)機(jī)(DFA)M，o

解：構(gòu)造一個(gè)如下的自動(dòng)機(jī)(DFA)M，，(DFA)M9={K,{a,b},S,Z}

K的元素是[A][B][A,B]

由于M(A,a)={A,B}>故有([A],a)=[A,B]

同樣M5([A],b)=[B]

AT([B],a)=0

([B],b)=[A,B]

由于M({A,B},a)=M(A,a)UM(B,a)={A,B}U0={A,B}

故M,([A,B],a)=[A,B]

由于M({A,B},b)=M(A,b)UM(B,b)={B}U{A,B}={A,B}

故M,([A,B],b)=[A,B]

S=[A],終態(tài)集Z={[A,B],[B]}

重新定義：令0=[A]1=[B]2=[A,B],則DFA如下所示:

可以進(jìn)一步化簡(jiǎn)，把的狀態(tài)分成終態(tài)組{1,2}和非終態(tài)組{0}

由于{1,2￡={1,2}b={2}u{l,2},不能再劃分。至此，整個(gè)劃分含有兩組{1,2}{0}

令狀態(tài)1代表{1,2},化簡(jiǎn)如圖：

第六次作業(yè)：

P7411(1)(0|11*0)*0

解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng):

由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集K={S,1,2,3,4,Z},

狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：

IIoIiK01

{S,1,Z){1,Z}{2,3,4}012

{1,Z}{1,Z}{2,3,4)112

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

{3,4}{1,Z}{3,4}313

由狀態(tài)子集轉(zhuǎn)換矩陣可知，

狀態(tài)0和1是等價(jià)的，而狀態(tài)2

和3是等價(jià)的，因此，合并等價(jià)

狀態(tài)之后只剩下2個(gè)狀態(tài)，也即

是最少狀態(tài)的DFA。

P7412.將圖3.24非確定有窮自動(dòng)機(jī)NFA確定化和最少化。

a

圖3.24NFA狀態(tài)轉(zhuǎn)換圖

解：設(shè)(DFA)M={K,VT,M,S,Z},其中,K={[0],[0,1],[1]},VT={a,b},M：

11

M([1],a)=[0]M([l],b)=①M(fèi)([0,1],a)=[0,1]M([0,1],b)=[1]

M([0],a)=|0,1]M(|0],b)=[l]

S=[lbZ={[0],[0,1]}

令[0,1]=2,則其相應(yīng)的狀態(tài)轉(zhuǎn)換圖為：

現(xiàn)在對(duì)該DFA進(jìn)行化簡(jiǎn)，先把狀態(tài)分為兩組：

終態(tài)組｛0,2｝和非終態(tài)組｛1｝,易于發(fā)現(xiàn)｛0,2｝

不可以繼續(xù)劃分，因此化簡(jiǎn)后的狀態(tài)轉(zhuǎn)換圖如下:

P7418.根據(jù)下面正規(guī)文法構(gòu)造等價(jià)的正規(guī)表達(dá)式:

S::=cC|a........①

A::=cA|aB........②

B::=aB|c........(3)

C::=aS|aA|bB|cC|a.......④

解：由③式可得B=aB+c—B=a*c

由②式可得A=cA+aBfA=c*aa*c

由①式可得S=cC+a

由④式可得C=aS+aA+bB+cC+aC=c*(aS+aA+bB+a)

C=c*(aS+ac*aa*c+ba*c+a)-S=cc*(aS+ac*aa*c+ba*c+a)+a=cc*aS+

cc*(ac*aa*c+ba*c+a)+a=(cc*a)*(cc*(ac*aa*c+ba*c+a)+a)=(cc*a)*(cc*(ac*aa*c|

ba*c|a)|a)另一種答案是S=c(ac|c)*(ac*aa*c|ba*c|aa|a)|a

第七次作業(yè)：

P1421.試分別消除下列文法的直接左遞歸(采用兩種方法一一重復(fù)法和改寫(xiě)法)

(1)G[E]:

E::=T|EAT........①

T::=F|TMF........②

F::=(E)|i........(3)

A::=+|-........④

/.......⑤

解：先采用“重復(fù)法”：再采用“改寫(xiě)法一

E::=T{AT}E::=TE'

T::=F{MF}E，::=ATE，|e

F::=(E)|iT::=FT9

A::=+|-TF=MFF|e

M::=*|/F::=(E)|i

A::=+|-

M::=*|/

P1422.試分別消除下列文法的間接左遞歸

(2)G[Z]:

Z::=AZ|b①.

A::=ZA|a........②

解：將②式代入①式可得，Z::=ZAZ|aZ|b消除左遞歸后得到:

Z::=(aZ|b)Z'

Z，::=AZZ，|￡

A::=ZA|a

P1435.對(duì)下面的文法G[E]:

E::=TE9

E，::=+E|￡

T::=FT'

T9::=T|e

F::=PF'

F'::=*F'|￡

P：：=(E)|a|b|A

(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符號(hào)的FIRST和FOLLOW；

(2)證明這個(gè)文法是LL(1)文法；

(3)構(gòu)造它的LL(1)分析表并分析符號(hào)串a(chǎn)*b+b;

解：(1)構(gòu)造FIRST集：

FIRST(E,)={+,e}

FIRST(F，)={*,e}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A}

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

構(gòu)造FOLLOW集：

規(guī)則一

#eFOLLOW(E)FOLLOW(E)={#}

規(guī)則二

)GFOLLOW?FOLLOE(E)={),#}

FIRST(E){e}^FOLLOW(T)FOLLOW(T)={+}

FIRST(T){e}^FOLLOW(F)FOLLOW(F)={(,a,b,A}

FIRST(F,)-{e}^FOLLOW(P)FOLLOW(P)={*}

規(guī)則三

FOLLOW(E)^FOLLOW(E,)FOLLOW(E,)={#,)}

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

FOLLOW(T)GFOLLOWCT)FOLLOWfT尸{+,#,)}

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

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

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

最后結(jié)果為：

FIRST(E,)={+,e}

FIRST(F,)={*,e}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A}

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

FOLLOE(E)={),#}

FOLLOW(E,)={#,)}

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

FOLLOWfT尸{+,#,))

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

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

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

(2)證明該文法是LL(1)文法：

證明：對(duì)于規(guī)則E，::=+E|e,T，::=T|e,F,::=*F,|e(僅有一邊能推出空串)

有FIRST(+E)={+}AFIRST(e)=0,FIRST(T尸{(,a,b,八}nFIRST(e)=0

FIRST(*F,)={*}AFIRST(e)=0,FIRST(+E)={+}AFOLLOW(E,)={#,)}=o

FIRST(T)={(,a,b,A}HFOLLOW(T,)={+,#,)}=0

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

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

(3)構(gòu)造文法分析表

*

ab+()A#

EE—TE，E-TE'E-TE，EfTE，

E，E'f+EE'feE'—e

TT—FT，T-FT，T—FT'TfFT，

T，T，-TT，-TT'—￡T，-TT'—eT，->Trf

e

FF—PFF—PF'F—PFF—PP

F9F，一￡F'—￡F，-eF'_*F'F'—eF'—￡F'—￡F，一

e

PPfaP—bP-(E)P-A

下面分析符號(hào)串a(chǎn)*b+b

步驟分析棧余留輸入串所用的產(chǎn)生式

1#Ea*b+b#ETE'

2#E5Ta*b+b#T—FT'

3#ETFa*b+b#F—PF'

4#ETFPa*b+b#Pfa

5#ETFaa*b+b#

6#ETF*b+b#F，—

7#ETP**b+b#

8#ETF，b+b#F，一￡

9#ETb+b#T，T

10#E，Tb+b#T—FT'

11#ETFb+b#F—PF'

12#ETF，Pb+b#Pfb

13#ETPbb+b#

14#ETF，+b#F，一￡

15#ET+b#T，-e

16#E'+b#E'f+E

17#E++b#

18#Eb#EfTE'

19#E，Tb#T—FT'

20#ETFb#F—PF'

21#ETF，Pb#Pfb

22#ETF，bb#

23#ETF#F，一￡

24#ET#T，一￡

25#E'#E'f￡

26##成功

所以符號(hào)串a(chǎn)*b+b是該文法的句子；

P1446.對(duì)下列文法，構(gòu)造相應(yīng)的FIRST和FOLLOW：

(1)S：：=aAd

A：：=BC

B：：=b|e

(2)A：：=BCc|gDB

B：：=e|bCDE

C：：=DaB|ca

D：：=€|dD

E：：=gAf|c

解：⑴

構(gòu)造FIRST集

FIRST(S)={a}

FIRST(B)={b,e}

FIRST(C)={c,e}

FIRST(A)={b,c,￡}

構(gòu)造FOLLOW集

規(guī)則一

#GFOLLOW(S)FOLLOW(S)={#}

規(guī)則二

deFOLLOW(A)FOLLOE(A)=uae2qs2

FIRST(C)-{e}^FOLLOW(B)FOLLOW(B)={c}

規(guī)則三

FOLLOW(A)GFOLLOW(B)FOLLOW(B)={d,c}

FOLLOW(A)^FOLLOW(C)FOLLOW(C)=mqgu0eq

最后結(jié)果為：

FIRST(S)={a}

FIRST(A)={b,c,e)

FIRST(B)={b,e}

FIRST(C)={c,e}

FOLLOW(S)={#}

FOLLOW(A)=okyemua

FOLLOW(B)={d,c}

FOLLOW(C)=gaqeuwm

(2)

構(gòu)造FIRST集

規(guī)則二

FIRST(A)={g},

FIRST(B)={b,e},

FIRST(C)={c},

FIRST(D)={d,e},

FIRST(E)={g,c}.

規(guī)則三

FIRST(A)={g,b,c},

FIRST(C)={a,c,d},

FIRST(A)={a,b,c,d,g}.

構(gòu)造FOLLOW集

規(guī)則一

#eFOLLOW(A)FOLLOW(A)={#}

規(guī)則二

fGFOLLOW(A)FOLLOE(A)={f,#}

ceFOLLOW(C)FOLLOE(C)={c}

aeFOLLOW(D)FOLLOE(D)={a}

FIRST(Cc)-{e}^FOLLOW(B)FOLLOW(B)={c,d,a}

FIRST(B)-{e}^FOLLOW(D)FOLLOW(D)={b,a}

FIRST(DE)-{e}^FOLLOW(C)FOLLOW(C)={d,g,c}

FIRST(E)^FOLLOW(D)FOLLOW(D)={b,c,a,g}

規(guī)則三

FOLLOW(A)^FOLLOW(B)FOLLOW(B)={a,c,d,f,#}

FOLLOW(A)^FOLLOW(D)FOLLOW(D)={a,b,c,f,g,#}

FOLLOW(B)GFOLLOW?FOLLOW(E)={a,c,d,f,#}

FOLLOW(C)GFOLLOW(B)FOLLOW(B)={a,c,d,g,f,#)

FOLLOW(B)GFOLLOW?FOLLOW(E)={a,c,d,g,f,#}

最后結(jié)果為：

FIRST(A)={a,b,c,d,g},

FIRST(B)={b,e},

FIRST(C)={a,c,d},

FIRST(D)={d,e},

FIRST(E)={g,c},

FOLLOE(A)={f,#}

FOLLOW(B)={a,c,d,g,f,機(jī)

FOLLOW(C)={d,g,c},

FOLLOW(D)={a,b,c,f,g,#},

FOLLOW(E)={a,c,d,g,f,#}.

P1449.設(shè)已給文法G[S]:

S：：=SaB|bB

A：：=Sa

B：：=Ac

(1)將此文法改寫(xiě)為L(zhǎng)L(1)文法

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

解：此題消除左遞歸之后，構(gòu)造LL(1)分析表存在“多重入口”問(wèn)題，故采用以下方法:

(1)改寫(xiě)為L(zhǎng)L(1)文法:

S：：=bB{aB}

A：：=Sa

B：：=Ac

(4)

FIRST(S)=,

FIRST(A)=,

FIRST(B)=,

FOLLOE(S)={a,#},

FOLLOW(A)={c},

FOLLOW(B)={a,#}.

abc#

sS：：=bB{aB}

AA：：=Sa

BB：：=Ac

P14410.證明下述文法不是簡(jiǎn)單優(yōu)先文法：

(1)S：：=bEb

E：：=E+T|T

(2)S：：=bEb

E：：=F|F+T|T|i

T：：=i|(E)

證明：

(1)畫(huà)語(yǔ)法樹(shù)：S

/I\

bEb

/I\

E+T

可以得出b=E和b〈E,因此該文法不是簡(jiǎn)單優(yōu)先文法。

⑵因該文法中含

E：：=i

T：：=i

右部?jī)蓚€(gè)產(chǎn)生式相同，故該文法不是簡(jiǎn)單優(yōu)先文法.

P14511.構(gòu)造下述文法的優(yōu)先關(guān)系矩陣，它們是簡(jiǎn)單優(yōu)先文法嗎？

S：：=M|U

M：：=iEtMeM|a

U：：=iEtS|iEtMeU

E：：=b

解:

SMUEiteabSMUEiteab

s^OOOOOOOO'xsx-011000000-x

M000000100M000010010

U000000000u000010000

Br二E000001000BL二E000000001

i000100000i000000000

t110000000t000000000

e011000000e000000000

a000000000a000000000

00000000)

b\oooooooo)b

SMUEiteabSMUEiteab

SZ0OOOOOOOO-^S「011010010、

M000000100M000010010

U000000000u000010000

BL2=E000001000BL=E000000001

i000100000i000000000

t110000000t000000000

e011000000e000000000

a000000000a000000000

00000000)

b%oooooooo-^b

+

B<=BrxBL

SMUEiteabSMUEiteab

s/00000000、S「011000000、

M000000000M010000010

U000000000U101000000

B<?=E000000000BR=E000000001

i000000001i000000000

t011010010t000000000

e000010010e000000000

a000000000a000000000

00000000)

b%oooooooo-^b

SMUEiteabSMUEiteab

s11000010-xsz-111000010

M010000010M010000010

u111000000u111000010

BR2二E000000000BR3二E000000000

i000000000i000000000

t000000000t000000000

JJ

A

00I000000

000000000a

000000000

000000000I

000000000a

000000000n

00I000000w

00000000rs

qgeiianws

10000000(kqX-O00I0000(Kq

010000000p001000000p

00I000II0a000000000a

0001000II000000000

0000I0000I000000000T

T0000I000ax000000000a=JHxHHx[(+x)H=氣

0000I0I00n000000000n

0100I00I0w001000000w

【0IIJ

0T00s0000000(Ks

quaq.TanKsq13anws

00T00000xq廠10000000名q

001000000T3010000000p

000000000d0010000000

000000000000T000004-

000000000T000010000T

000000000aI0000T0003=*^9

000000000n二節(jié)x(x)8000010100n

001000000w0I00I00I0w

lo00J

00000siooioiirs

qpa4-T9flws

「00000I000、q廠00000000名q

000000IT

00000000000000000000

000000000]0000000004-

000000000T000000000T

a=工(+N)H

000000000100000000a二十阻

000000I0In0I0000IIIn

000000IIIw010000010w

I00000J^-oiooooiTr

00Iss

qgajianwsqga—anws

000000000q000000000q

000000000000000000g

000000000d0000000000

b000001000

優(yōu)先關(guān)系矩陣如下:

SMUiEteab

S

M=>

U

i=<-

E=

t==<<<<

e==<<

a>

b

其中含多重定義的表項(xiàng)，因而該文法不是簡(jiǎn)單優(yōu)先文法。

P14512.根據(jù)圖4.25的語(yǔ)法樹(shù)，確定全部?jī)?yōu)先關(guān)系:

(a)E=++=TT=**二F(=EE=)

*<(+<F+<iF>*i>*)>+T>+F>+

(b)〈說(shuō)明表＞=；BEGIN=＜說(shuō)明表＞REAL=v標(biāo)識(shí)符表》

〈變量＞=：=;=＜語(yǔ)句表＞:==i

BEGINw說(shuō)明〉BEGIN＜REALREAL<i

;?語(yǔ)句〉；《變量〉；＜i

〈說(shuō)明＞＞；＜標(biāo)識(shí)符表》；i＞；i>:=

P14513.利用表4.6文法G[E]的優(yōu)先關(guān)系矩陣，來(lái)分析符號(hào)串#b(((aa)a)a)b#和#((aa)a)#。

(1)

步驟符號(hào)棧關(guān)系輸入串規(guī)則

1#<b(((aa)a)a)b#

2#b<(((aa)a)a)b#

3#b(<((aa)a)a)b#

4#b((<(aa)a)a)b#

5#b(((<aa)a)a)b#

6#b(((a>a)a)a)b#

7#b(((M=a)a)a)b#M：：=a

8#b(((Ma=)a)a)b#

9#b(((Ma)>a)a)b#

10#b(((L>a)a)b#L：：=Ma)

11#b((M=a)a)b#M：：=(L

12#b((Ma=)a)b#

13#b((Ma)>a)b#

14#b((L>a)b#L：：=Ma)

15#b(M=a)b#M：：=(L

16#b(Ma=)b#

17#b(Ma)>b#

18#b(L>b#L：：=Ma)

19#bM=b#M：：=(L

20#bMb>#

21#Z>#Z：：=bMb

⑵

步驟符號(hào)棧關(guān)系輸入串規(guī)則

1#<((aa)a)#

2#(<(aa)a)#

3#((<aa)a)#

4#((a>a)a)#

5#((M=a)a)#M：：=a

6#((Ma=