編譯原理試卷與復(fù)習(xí)

《編譯原理》期終考卷2010

學(xué)號(hào)：姓名：

說(shuō)明:1、本考卷中大寫字母CVN，其他符號(hào)CVT，

2、試卷中一、二兩題請(qǐng)作在考卷上

一、填空題（20分）

1、一般說(shuō)來(lái)編譯系統(tǒng)的編譯過(guò)程分五步，它們分別

為、、、、o

2、計(jì)算機(jī)三大系統(tǒng)軟件分別、、。

3、自上而下分析法的典型算法是、兩類。

二、判斷題（10分。注：每答對(duì)一題得+2分；答錯(cuò)一題得-2分；不答者得。分）

1、設(shè)E為{a,b},則a,ba,{￡},。都是Z上的正規(guī)式。（）

2、對(duì)于上下文無(wú)關(guān)文法G[S],若S=>aAB=aBy則A—'一定是一條產(chǎn)生式規(guī)則，

其中a,p,yG（VTWN）*（）

3、對(duì)于逆波蘭后綴式，無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解。（）

4、LR（0）分析法是--種規(guī)范歸約法。（）

5、算符優(yōu)先分析法只能用來(lái)分析算符優(yōu)先文法。（）

三、（20分）

1、設(shè)E={a,b,c）,設(shè)計(jì)一個(gè)DFAM,它識(shí)別所有以b開(kāi)頭且只允許出現(xiàn)一個(gè)b的

字。

2、用程序?qū)崿F(xiàn)DFAM的功能。

四、下列文法如果是LL⑴文法，請(qǐng)求其預(yù)測(cè)分析表；如果不是，請(qǐng)說(shuō)明理由（本題20分）

A—AaBlB

B—BeFlF

F->f

六、（30分）有作控制用的布爾表達(dá)式文法G[E]及其語(yǔ)義動(dòng)作如下:

文法G[E]：

⑴卜尸產(chǎn)。{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J<,ENTRY(i'7),ENTRY(i10,0);GEN(J,0)}

(2)E->AEW{E.FC:=EW.FC;E.TC:=MERGE(A.TC,EW.TC))

(3)A->BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC)

⑷B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY0);GEN(J,0)}

1、構(gòu)造SLR（1）分析表（若不是SLR（l））的，則說(shuō)明理由）

2、使用語(yǔ)法制導(dǎo)翻譯法分析作控制用的布爾表達(dá)式a<bVc的四元式生成過(guò)程，并畫(huà)

出最后的真假鏈表。

3、給出語(yǔ)句IFa<bVcTHENI:=m*nELSEI:=m+n的完整四元式序列。

《編譯原理》軟件工程2005級(jí)期終考卷

學(xué)號(hào)：姓名：

說(shuō)明：1.本考卷中大寫字母GVN，其他符號(hào)GVT，2、試卷中一、二兩題請(qǐng)作在考卷上

一、概念題（15分）

1、編譯過(guò)程一般分為幾個(gè)階段？各階段的輸入輸出分別為什么？

2、對(duì)下列狀態(tài)轉(zhuǎn)換圖，寫出狀態(tài)0的處理過(guò)程:

字母

其中：狀態(tài)2的過(guò)程為proc2.

3、文法G為：

S—aAB

A—a

B-、切，

則判斷G為L(zhǎng)L（1）文法的條件是：

二、判斷題（10分。注：每答對(duì)一題得+2分；答錯(cuò)一題得-2分；不答者得0分）

1、設(shè)Z為{a,b},貝Ua,ba,{￡},。都是E上的正規(guī)式。（）

2、對(duì)于上下文無(wú)關(guān)文法G[S],若S=aAB=apY則A->7一定是一條產(chǎn)生式規(guī)則，

其中a，B，yG（VTVVN）*（）

3、對(duì)于逆波蘭后綴式，無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解。（）

4、LR（0）分析法是一種規(guī)范歸約法。（）

5、算符優(yōu)先分析法只能用來(lái)分析算符優(yōu)先文法。（）

三、（10分）設(shè)文法G3為：S—AaBc

A—Aala

B-*b

求句型AaBc的最左素語(yǔ)。

四、（20分）設(shè)文法G[S]為

S—aAcB問(wèn)：1、該文法是否為算符文法，為什么？

A->Ab|b2、構(gòu)造算符優(yōu)先關(guān)系表。

B->d3、該文法是否可改造為L(zhǎng)L（1）文法，為什么？

五、（本題20分）設(shè)文法G為：E—eAfleBg

A—aA|a

B—Bb|a

對(duì)于輸入串eaaaf,采用LR（0）、LL（1）、SLR（1）等方法中合適的一種進(jìn)行分析。

六、（25分）有作控制用的布爾表達(dá)式文法G［E］及其語(yǔ)義動(dòng)作如下：

1、構(gòu)造SLR（1）分析表（若不是SLR（l））的，則說(shuō)明理由）

2、分析布爾式aVb<c的四元式生成過(guò)程，并畫(huà)出最后的真假鏈表。

3、給出語(yǔ)句IFaVb<cTHENI:=m*nELSEI:=m+n的完整四元式序列。

文法G［法:

⑴「嚴(yán)0⑵{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J〈,ENTRY(i?),ENTRY(i(2)),0);GEN(J,0)}

(2)E->AE(I){E.FC:=EW.FC;E.FC:=MERGE(A.TC,EW.TC)}

(3)A—BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}

(4)B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY(i),_,0);GEN(J,0)}

常見(jiàn)問(wèn)題

自頂向下分析算法

帶回溯的自頂向下分析

主旨：對(duì)任何輸入串試圖用一切可能的方法，從根節(jié)點(diǎn)（文法開(kāi)始符號(hào)）出發(fā)，自上而下地

為輸入串建立一棵語(yǔ)法樹(shù)。其本質(zhì)是一種試探法。

S——>cAd

例.A輸入串0=

存在的問(wèn)題：

1.若文法是左遞歸的（沏使P=pa）則分析會(huì)陷入死循環(huán)

2.存在回溯

3.效率低

自下向上分析基本問(wèn)題

歸約

我們所討論的自下而上分析法是一種“移進(jìn)-歸約”法。這種方法的大意是，用一個(gè)寄

存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)侯

選式時(shí)，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號(hào)。

例：假定文法G為：

(1)S-*aAcBe

(2)A-b

(3)A-Ab

(4)B-d

我們希望把輸入串a(chǎn)bbcde歸約到S,則符號(hào)棧的變化情形如下：

步驟：12345678910

動(dòng)作：進(jìn)進(jìn)歸進(jìn)歸進(jìn)進(jìn)歸進(jìn)歸

ab(2)b(3)cd(4)e(1)

e

dBB

bcccc

bAAAAAAA

aaaaaaaaaS

SLR分析表的構(gòu)造

—.LR(0)存在的問(wèn)題

LR(0)雖簡(jiǎn)單，但很少見(jiàn)，如叫不是LR(0)的。

解決辦法

A->a?

若項(xiàng)目集4中有：CTa?3，分析所有含A和B的句型，考察所有可能直接跟在

A和B之后的終結(jié)符，如果它們不相交且都不含b,那么當(dāng)狀態(tài)I面臨任何輸入符號(hào)a時(shí),

可采取如下移進(jìn)一歸約策略。

1.a=b時(shí),移進(jìn)

2,若"及亞的則用d?歸約。

3,若ae7fos獷(也則用3Ta?歸約。

4.其他，出錯(cuò)。

一般而言，如果某LR(0)項(xiàng)目集I中含有m個(gè)移進(jìn)項(xiàng)目，

AT同時(shí)有0個(gè)歸約項(xiàng)目&TG-,Ba。若

{.,-一-=,1?國(guó)皿。鵬)，….質(zhì)龍〃溜(紇)兩兩不相交，則動(dòng)作沖突可通過(guò)檢查當(dāng)前輸入

符號(hào)a屬于哪個(gè)集合而決定。

因?yàn)橹豢匆粋€(gè)符號(hào)，所以稱為SLR⑴方法(簡(jiǎn)單LR(1))

總結(jié)性習(xí)題一

第一章編譯程序概述

1.1什么是編譯程序

編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一，而且多數(shù)計(jì)算機(jī)系統(tǒng)都含有不止一個(gè)

高級(jí)語(yǔ)言的編譯程序。對(duì)有些高級(jí)語(yǔ)言甚至配置了幾個(gè)不同性能的編譯程序。

1.2編譯過(guò)程概述和編譯程序的結(jié)構(gòu)

編譯程序完成從源程序到目標(biāo)程序的翻譯工作，是一個(gè)復(fù)雜的整體的過(guò)程。從概念上來(lái)

講，一個(gè)編譯程序的整個(gè)工作過(guò)程是劃分成階段進(jìn)行的，每個(gè)階段將源程序的一種表示形式

轉(zhuǎn)換成另一種表示形式，各個(gè)階段進(jìn)行的操作在邏輯匕是緊密連接在一起的。■般一個(gè)編譯

過(guò)程劃分成詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成，代碼優(yōu)化和目標(biāo)代碼生成六個(gè)

階段,這是一種典型的劃分方法。事實(shí)上，某些階段可能組合在一起，這些階段間的源程序

的中間表示形式就沒(méi)必要構(gòu)造出來(lái)了。我們將分別介紹各階段的任務(wù)。另外兩個(gè)重要的工作:

表格管理和出錯(cuò)處理與上述六個(gè)階段都有聯(lián)系。編譯過(guò)程中源程序的各種信息被保留在種種

不同的表格里，編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格

管理的工作；如果編譯過(guò)程中發(fā)現(xiàn)源程序有錯(cuò)誤，編譯程序應(yīng)報(bào)告錯(cuò)誤的性質(zhì)和錯(cuò)誤發(fā)生的

地點(diǎn)，并且將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被

編譯下去，有些編譯程序還能自動(dòng)校正錯(cuò)誤，這些工作稱之為出錯(cuò)處理。圖1.1表示了編譯

的各個(gè)階段。

圖1.1編譯的各個(gè)階段

1.3高級(jí)語(yǔ)言解釋系統(tǒng)

為了實(shí)現(xiàn)在一個(gè)計(jì)算機(jī)上運(yùn)行高級(jí)語(yǔ)言的程序，主要有兩個(gè)途徑：第一個(gè)途徑是把該程

序翻譯為這個(gè)計(jì)算機(jī)的指令代碼序列，這就是我們已經(jīng)描述的編譯過(guò)程。第二個(gè)途徑是編寫

一個(gè)程序，它解釋所遇到的高級(jí)語(yǔ)言程序中的語(yǔ)句并且完成這些語(yǔ)句的動(dòng)作，這樣的程序就

叫解釋程序。從功能上說(shuō)，一個(gè)解釋程序能讓計(jì)算機(jī)執(zhí)行高級(jí)語(yǔ)言。它與編譯程序的主要不

同是它不生成目標(biāo)代碼，它每遇到一個(gè)語(yǔ)句，就要對(duì)這個(gè)語(yǔ)句進(jìn)行分析以決定語(yǔ)句的含義,

執(zhí)行相應(yīng)的動(dòng)作。

第二章：高級(jí)語(yǔ)言及其語(yǔ)法描述

問(wèn)答第1題

寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求:

(1)允許0打頭；

(2)不允許0打頭。

答：(1)允許0開(kāi)頭的偶正整數(shù)集合的文法

E-*NT|D

T-NT|D

N-Dl1|3|5|7|9

Df0|2|4|6|8

(2)不允許0開(kāi)頭的偶正整數(shù)集合的文法

E-NT|D

T-FT|G

N-*D|1|3|5|7|9

D-2|4|6|8

F-N|O

G-D|O

問(wèn)答第2題

證明下述文法G［〈表達(dá)式〉］是二義的。

〈表達(dá)式〉：:=a|（〈表達(dá)式〉）|〈表達(dá)式〉

〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉：：=+IT*M

答：可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo)：

最右推導(dǎo)1〈表達(dá)式〉n〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉

n〈表達(dá)式〉〈運(yùn)算符〉.a

n〈表達(dá)式〉*:a

n〈表達(dá)式〉（運(yùn)算符〉〈表達(dá)式〉*a

n〈表達(dá)式〉〈運(yùn)算符〉a*a

n〈表達(dá)式〉4a*a

na+a*a

最右推導(dǎo)2〈表達(dá)式〉n〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉

n〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉

n〈表達(dá)式〉（運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符）a

n〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a

n〈表達(dá)式〉〈運(yùn)算符〉a*a

n〈表達(dá)式〉」a*a

na+a*a

問(wèn)答第3題

令文法G［E］為:

E—T|E+T|E-T

…F|T*F|T/F

Ff（E）|i

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

答：因?yàn)榇嬖谕茖?dǎo)序列：E=E+T=E+n*F所以E+T*F是文法G[E]的一個(gè)句

句型E+T*F的

短語(yǔ)有:E+T*F,T*F

直接短語(yǔ)有：T*F

句柄為：T*F

問(wèn)答第4題

給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法:

(1){a"b"a°b°|n,m>=0}

(2){1"OB1°0"n,m>=0}

答：⑴S-AA

A-?-aAb|e

(2)

S-*1SO|A

A-OA1|e

問(wèn)答第5題

給出生成下述語(yǔ)言的三型文法：

(1){anbm|n,m>=l}

(2){anbBckIn,m,k>=0}

答：⑴S-aA

AfaA|B

B->bB|b

(2)A-aA|B

B-*bB|C

C-*cC|￡

問(wèn)答第6題

給出下述文法所對(duì)應(yīng)的正規(guī)式：

S-OA|1B

A-1S|1

B-OS0

答：R=(01|10)(01|10)”

第三章：詞法分析

問(wèn)答第1題

構(gòu)造正規(guī)式1(01)*101相應(yīng)的DFA.

答：先構(gòu)造NFA：

用子集法將NFA確定化

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

除X,A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D,因?yàn)镈含有Y(NFA的

終態(tài))，所以D為終態(tài)。

01

XA

AAB

BCB

CAD

DCB

DFA的狀態(tài)圖：：

問(wèn)答第2題

將下圖確定化:

解：

用子集法將NFA確定化:

01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ

QUZVZQUZ

ZZZ

重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為I）、QUZ為E、Z為F。

01

SAB

ACB

BDE

CFF

DF

ECE

FFF

no：終態(tài)組{0},非終態(tài)組{1,2,3,4,5}

對(duì)非終態(tài)組進(jìn)行審查：

{1,2,3,4,5}aU{0,1,3,5}

而{0,1,3,5}既不屬于{0},也不屬于{1,2,3,4,5}

???{4}aU{0},所以得到新分劃

ni：{0},⑷，{1,2,3,5}

對(duì){1,2,3,5}進(jìn)行審查：

V{1,5}bC{4}

{2,3}bu{l,2,3,5},故得到新分劃

112：{0},{4},{1,5},{2,3}

{115}aC{1,5}

{2,3}ac{l,3},故狀態(tài)2和狀態(tài)3不等價(jià)，得到新分劃

H3：{0},{2},{3},{4},{1,5}

這是最后分劃了

最小DFA：

問(wèn)答第4題

構(gòu)造一個(gè)DFA,它接收￡={0,1}上所

有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。并給出該語(yǔ)言的正規(guī)式。

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

造NFA為

用子集法確定化:

I1011

{X,0,1,3,Y)(0,1,3,Y){2}

(0.1.3.Y){0,1,3,Y){2}

{2}{1,3,Y}

{1.3.Y}{1,3,Y)⑵

重新命名狀態(tài)集:

S01

123

223

34

443

DFA的狀態(tài)圖:

可將該DFA最小化：

終態(tài)組為（1,2,4},非終態(tài)組為{3},{1,2,4}0{1,2,4},

{1.2.4J1{3},所以1,2,4為等價(jià)狀態(tài)，可合并。

第四章語(yǔ)法分析一自上而下分析

（一）

問(wèn)答第1題

對(duì)于文法正,輸入串GF+G的分析步驟如下:

步驟符號(hào)棧輸入串動(dòng)作

0#預(yù)備

1F+G#進(jìn)

2#EF+G#歸，用芭—

3#E*進(jìn)

4#E*G+G#進(jìn)

5#E*E+G#歸，用E---->x

6#E+G#歸，用石----

7#E+Q#進(jìn)

8#E+Gn進(jìn)

9#E+E#歸，用芭----

10#E#歸，用E

11ttE#接受

問(wèn)答第2題

文法的另一種表示法

優(yōu)點(diǎn)：便于消除左遞歸

I.用㈤

2.用㈤"表示口可重復(fù)0~17次

3,用時(shí)"用

4,用㈤：=￡

用這種表示法，寫出算術(shù)表達(dá)式文法的遞歸下降子程序

E->{*7}

T->用仔尸}

解：文法為尸T㈤W,遞歸子程序?yàn)椋?/p>

PROCEDUREE;

BEGIN

T;

whilesym='+'do[advance;T]

END;

PROCEDURE?;

BEGIN

F;

whilesym='*'do[advance;F]

END;

PROCEDUREF;

BEIGN

ifsym='i'then

[advance;E;

ifsym=^)^thenladvance;return]

elseerror;]

elseerror;

END;

問(wèn)答第3題

文法，

T->T*F|F

尸T(功i

有FIRST(+T)={+},FIRST(f)={(,i),FIRST(E)=FIRST(T)=FIRST(F)

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

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

問(wèn)答第4題

文法有HRST(E)=HRST(T)=FIRST(F)={(,i),

E'+TE'|E

T

產(chǎn)-

FIRST(E')={+,￡},FIRST(T')={*,￡}

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

FOLLOW(T,)=FOLLOE(T)=FIRST(E,)\{c}+FOLLOW(E,)={+,#,}),

FOLLOE(F)=FIRST(T,)\{￡}+FOLLOE(T)={*,+,#,),}

問(wèn)答第5題

S—>aAcBe

A-^Ab\b

文法B—d,試用LL(1)分析法分析輸入串a(chǎn)bbcde.

S—>aAcBe

A-^hA

解：①消除左遞歸得文法(無(wú)公共左因子)：3Td

②求必要的FIRST和FOLLOWo

FIRST(aAcBe)={a}

FIRST(bA')=

FIRST(￡)={￡}

FIRST(d)=2swi6sa

FOLLOW(A,)=FOLLOW(A)={c}

③構(gòu)造LL⑴分析表

abcde#

SAA'BaAcBebA'￡d

④分析

aabbbb0cdd,0

323232323221

第四章語(yǔ)法分析一自上而下分析(二)

問(wèn)答第1題

對(duì)文法G[S]

S-a|Al(T)

T-T,S|S

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

(2)對(duì)文法G,進(jìn)行改寫，然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序。

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

(4)給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G的句子。

答：文法

S-a|Al(T)

T-T,S|S

(1)對(duì)(a,(a,a)的最左推導(dǎo)為：

sn(T)

N(T,s)

n(s,s)

n(a,s)

n(a,Cr))

n(a,(T,S))

(a,(S,S))

n(a,(a,S))

(a,(a,a))

對(duì)(((a,a),八，(a)),a)的最左推導(dǎo)為：

sn(T)

N(T,s)

n(s,s)

n((D,s)

N((T,s),s)

n((T,s,s),s)

n((s,s,s),s)

=>(((T),S,S),S)

n(((T,s),s,s),s)

n(((s,s),s,s),s)

=H((a,S),S,S),S)

n(((a,a),S,S),S)

n(((a,a),A,S),S)

n(((a,a),A,(T)),S)

=>(((a,a),A,(S)),S)

=H((a,a),A,(a)),S)

n(((a,a),A,(a)),a)

(2)改寫文法為：

0)S-a

1)S-A

2)S-(T)

3)T->SN

4)N-,SN

5)N-*e

非終結(jié)符FIRST集FOLLOW集

S{a,A,(){#,,,)}

T{a,A,(){)}....

N{,,e}.{)}....

對(duì)左部為N的產(chǎn)生式可知：

FIRST,SN)={,}

FIRSTe)={e}

FOLLOW(N)={)}

由于SELECT(NSN)ASELECT(N-e)={,}n{)}=0

所以文法是LL(1)的。

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

aA()#

—?

s-a-A

(T)

fsfs

TfSN

NN

-A―?>

N

ESN

也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。

(3)對(duì)輸入串(a,a)井的分析過(guò)程為:

棧當(dāng)前輸入符剩余輸入符所用產(chǎn)生式

(STACK)(CUR.CHAR)(IN0UT_STRING)(OPERATION)

#S(a,a)#...

#)T((a,a)#...S-(T)

#)Ta,a)#...

tt)NSa,a)#...T-SN

#)Naa,a)#...Sfa

tt)Na)#…?

#)NS,a)#...Nf,SN

tt)NSa)#...?

#)Naa)#...S-a

#)N)#...*

#))#??.Nf￡

##

可見(jiàn)輸入串(a,a)#是文法的句子。

問(wèn)答第2題

已知文法G[S]：

S-MH|a

H-LSo|E

KfdML|e

L-*eHf

MT|bLM

判斷G是否是LL(D文法，如果是，構(gòu)造LL(1)分析表。

答：文法：

S-MH|a

H-LSo|e

K-dML|e

L-eHf

MT|bLM

展開(kāi)為：

0)S-MH

1)S—a

2)H-LSo

3)-e

4)K-*dML

5)"￡

6)LfeHf

7)M-K

8)M-bLM

非終

FIRST集FOLLOW集

結(jié)符

{a,d,b,{#,。}......

S

￡,e}

{d,{e,tt,o}.........

M

￡,b}….

{￡,e}???.{#,f.o}……

H

{e}..............{a,d,b,e,o,#

L

}

{d,{e,#,o).........

K

e)............

對(duì)相同左部的產(chǎn)生式可知:

SELECT(S-MII)ASELECT(S-a)={d,b,e,#,o}A{a}=0

SELECT(H-LSo)nSELECT(H-e)={e}n{#,f,o}=0

SELECT(K-dML)nSELECT(K-e)=4m0m24kC{e,#,o}=0

SELECT(M-K)nSELECT(M-bLM)={d,e,tt,o}n=0

所以文法是LL(1)的。

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

a0defbn

―?―?

S—MHTHfMH

aMHMH

-A

M-K-K-K一K

bLM

II―?-A--A

ELSo￡e

―?

L

eHf

―?—?—?

K—e

￡dMLe

由預(yù)測(cè)分析表中無(wú)多重入口也可判定文法是LL⑴的。

問(wèn)答第3題

對(duì)于一?個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(1)文法?試對(duì)下面

文法進(jìn)行改寫，并對(duì)改寫后的文法進(jìn)行判斷。

(1)A-aABe|a

B-Bb|d

(3)S-Aa|b

AfSB

Bfab

答：(1)文法：

AfaABe|a

B-*Bb|d

提取左公共因子和消除左遞歸后文法變?yōu)椋?/p>

0)A-aN

1)N-ABe

2)N-e

3)B-dN1

4)Nl-bN1

5)Nl-E

非終結(jié)FIRST

FOLLOW集

符集

A{a}...{#,d}

Biwwaack...{e}..

N{a,e}{#,d}

Nl{b,e}{e}?.

對(duì)相同左部的產(chǎn)生式可知：

SELECT(N-ABe)nSELECT(N-e)={a}n{禮d}=0

SELECT(Nl-bNl)nSELECT(Nl-c)=D{e}=0

所以文法是LL⑴的。

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

aebd#

AfaN

—?d

B

N1

N一b

1eN1

—?

Nfe

ABee

也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(D的。

(2)文法:

S-*Aa|b

A-SB

B-ab

第1種改寫：

用A的產(chǎn)生式右部代替S的產(chǎn)生式右部的A得：

S-SBa|b

B—ab

消除左遞歸后文法變?yōu)椋?/p>

0)S-bN

1)NTaN

2)N-e

3)B-ab

非終結(jié)FIRST

FOLLOW集

符集

s??.{?}

B{a}...{a}

N{e,a}{#}

對(duì)相同左部的產(chǎn)生式可知：

SELECT(N-BaN)nSELECT(N->e)={a}n(#}=0

所以文法是LL(1)的。

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

也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。

第2種改寫：

用S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得：

S-Aa|b

A-AaB|bB

B-*ab

消除左遞歸后文法變?yōu)椋?/p>

0)AAa

1)S->b

2)AiBN

3)N-aBN

4)N-e

5)Bfab

非終結(jié)FIRST

FOLLOW集

符集

s...{#}

A...{a}

B{a}...{a}

N{a,￡}{a}

對(duì)相同左部的產(chǎn)生式可知：

SELECT(S-Aa)ASELECT(S-b)=n=W0

SELECT(N-aBN)nSELECT(N->e)={a}n{a}={a}W0

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

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

ab

sfAa..

fb....

AfbBN

fa

B

b..

NfaBN

-A

e...

也可由預(yù)測(cè)分析表中含有多重入口判定文法不是LL(1)的。

第五章語(yǔ)法分析一自下而上分析

問(wèn)答第1題

已知文法G[S]為：

S-a|Al(T)

T-T,S|S

(1)計(jì)算G[S]的FIRSTVT和LASTVTo

(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說(shuō)明G[S]是否為算符優(yōu)先文法。

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

答：文法：

S--a|A|(T)

T-T,S|S

展開(kāi)為：

Sfa

S-A

SfCD

T-*T,S

T-S

(1)FIRSTVT—LASTVT表

非終結(jié)

FIRSTVT集LASTVT集

符

{aA(a

s

()..A)}..

{aA(a

T

(,}A),}

(2)算符優(yōu)先關(guān)系表(OPERATERPRIORITYRELATIONTABLE)

aA()>#

>>>

A<<<>>>

(■<

)<<<

<<<>>>

>>

—

表中無(wú)多重人口所以是算符優(yōu)先(OPG)文法。

(3)對(duì)輸入串(a,a)#的算符優(yōu)先分析過(guò)程為

當(dāng)前輸

棧剩余輸入串動(dòng)作

入字符

(STACK)(INPUT_STRING)(ACTION)

(CHAR)

a,a)#...Movein

,3.).Movein

#(

a)#...Reduce:S

#(a

a)#...-*a

#(a

)#,?.Movein

#(N

#.?.Movein

?(N,a

Reduce:S

#(N,a)

a

#(N,N)

Reduce:T

#(N)

-T,S

#(N)#

Movein

#N#

Reduce:S

f⑴