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

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

第一次作業(yè)：

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

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

答：被翻譯的程序稱為源程序；

翻譯出來的程序稱為目標程序或目標代碼；

將匯編語言和高級語言編寫的程序翻譯成等價的機器語言，實現(xiàn)此功能的程序稱為翻

譯程序；

把匯編語言寫的源程序翻譯成機器語言的目標程序稱為匯編程序；

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

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

編譯程序是將高級語言寫的源程序翻譯成目標語言的程序。

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

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

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

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

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

P144、語法分析和語義分析有什么不同？試舉例說明。

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

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

查，如賦值語句中x與y類型要一致，否則語法分析正確，語義分析則錯誤。

補充：為什么要對單詞進行內(nèi)部編碼？其原則是什么？對標識符是如何進行內(nèi)部編碼的？

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

畫了單詞本身，也刻畫了它所具有的屬性，以供其它部分分析使用。對于標識符編碼，先

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

標識符的含義編碼該單詞的值。

第二次作業(yè)：

+

P381、設(shè)%={11,010},T2={0,01,1001},計算：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

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

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

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

型也是句子；

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

第三次作業(yè)：

P3911、試分別描述下列文法所產(chǎn)生的語言(文法開始符號為S)：

(1)S：：=OSI01

(2)S：：=aaS|bc

n

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

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

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

(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

對下列句型給出推導(dǎo)語法樹，并求出其句型短語，簡單短語和句柄。

(2)baabaab(3)bBABb

句型baabaab的短語a,ba,baa,baab,baabaab,簡單短語a,句柄

(3)

短語bB,AB,ABb,bBABb

簡單短語bB,AB,

句柄bB

第四次作業(yè)

P4124.下面文法那些是短語結(jié)構(gòu)文法,上下文有關(guān)文法，上下文無關(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

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

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

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

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

P4229.用擴充的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.畫出下列文法的狀態(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

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

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

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

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

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

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

rA：=Z1rA：=B1

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

、Z:=AOLB:=A0

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

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

解2：先畫出該文法狀態(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}

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

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

根據(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}

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

解：構(gòu)造一個如下的自動機(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如下所示:

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

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

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

第六次作業(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是等價的，而狀態(tài)2

和3是等價的，因此，合并等價

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

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

P7412.將圖3.24非確定有窮自動機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([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)在對該DFA進行化簡，先把狀態(tài)分為兩組：

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

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

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

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ù)法和改寫法)

(1)G[E]:

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

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

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

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

/.......⑤

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

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.對下面的文法G[E]:

E::=TE9

E，::=+E|￡

T::=FT'

T9::=T|e

F::=PF'

F'::=*F'|￡

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

(1)計算這個文法的每個非終結(jié)符號的FIRST和FOLLOW；

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

(3)構(gòu)造它的LL(1)分析表并分析符號串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)文法：

證明：對于規(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

下面分析符號串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##成功

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

P1446.對下列文法，構(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)=qdzamtt

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

規(guī)則三

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

FOLLOW(A)^FOLLOW(C)FOLLOW(C)=orqbnno

最后結(jié)果為：

FIRST(S)={a}

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

FIRST(B)={b,e}

FIRST(C)={c,e}

FOLLOW(S)={#}

FOLLOW(A)=tneaozh

FOLLOW(B)={d,c}

FOLLOW(C)=xntslld

(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,機

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)將此文法改寫為LL(1)文法

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

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

(1)改寫為LL(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.證明下述文法不是簡單優(yōu)先文法：

(1)S：：=bEb

E：：=E+T|T

(2)S：：=bEb

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

T：：=i|(E)

證明：

(1)畫語法樹：S

/I\

bEb

/I\

E+T

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

⑵因該文法中含

E：：=i

T：：=i

右部兩個產(chǎn)生式相同，故該文法不是簡單優(yōu)先文法.

P14511.構(gòu)造下述文法的優(yōu)先關(guā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

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

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

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

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

(b)〈說明表＞=；BEGIN=＜說明表＞REAL=v標識符表》

〈變量＞=：=;=＜語句表＞:==i

BEGINw說明〉BEGIN＜REALREAL<i

;?語句〉；《變量〉；＜i

〈說明＞＞；＜標識符表》；i＞；i>:=

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

(1)

步驟符號棧關(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

⑵

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

1#<((aa)a)#

2#(<(aa)a)#

3#((<aa)a)#

4#((a>a)a)#

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

6#((Ma=