《編譯原理教程》課件第三章

第三章語法分析3.1完成下列選擇題：

(1)程序語言的語義需要

用來描述。

A．上下文無關(guān)文法 B．上下文有關(guān)文法

C．正規(guī)文法 D．短語文法

(2)2型文法對應(yīng)

。

A．圖靈機(jī) B．有限自動機(jī)

C．下推自動機(jī) D．線性界限自動機(jī)

(3)下述結(jié)論中，

是正確的。

A．1型語言

0型語言 B．2型語言

1型語言

C．3型語言

2型語言 D．A～C均不成立(4)有限狀態(tài)自動機(jī)能識別_________。

A．上下文無關(guān)文法 B．上下文有關(guān)文法

C．正規(guī)文法 D．短語文法

(5)文法G[S]：S→xSx|y所識別的語言是

。

A．xyx B．(xyx)*

C．xnyxn(n≥0) D．x*yx*

(6)只含有單層分枝的子樹稱為“簡單子樹”，則句柄的直觀解釋是

。

A．子樹的末端結(jié)點(即樹葉)組成的符號串

B．簡單子樹的末端結(jié)點組成的符號串

C．最左簡單子樹的末端結(jié)點組成的符號串

D．最左簡單子樹的末端結(jié)點組成的符號串且該符號串必須含有終結(jié)符(7)下面對語法樹錯誤的描述是

。

A．根結(jié)點用文法G[S]的開始符S標(biāo)記

B．每個結(jié)點用G[S]的一個終結(jié)符或非終結(jié)符標(biāo)記

C．如果某結(jié)點標(biāo)記為ε，則它必為葉結(jié)點

D．內(nèi)部結(jié)點可以是非終結(jié)符

(8)由文法開始符S經(jīng)過零步或多步推導(dǎo)產(chǎn)生的符號序列是

。

A．短語 B．句柄

C．句型 D．句子

(9)設(shè)文法G[S]：S→SA|A

A→a|b

則對句子aba的規(guī)范推導(dǎo)是

。

A．S

SA

SAA

AAA

aAA

abA

aba

B．S

SA

SAA

AAA

AAa

Aba

aba

C．S

SA

SAA

SAa

Sba

Aba

aba

D．S

SA

Sa

SAa

Sba

Aba

aba(10)如果文法G[S]是無二義的，則它的任何句子α其

。

A．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同

B．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同

C．最左推導(dǎo)和最右推導(dǎo)必定相同

D．可能存在兩個不同的最右推導(dǎo)，但它們對應(yīng)的語法樹相同

(11)一個句型的分析樹代表了該句型的

。

A．推導(dǎo)過程 B．歸約過程

C．生成過程 D．翻譯過程(12)規(guī)范歸約中的“可歸約串”由

定義。

A．直接短語 B．最右直接短語

C．最左直接短語 D．最左素短語

(13)規(guī)范歸約是指

。

A．最左推導(dǎo)的逆過程 B．最右推導(dǎo)的逆過程

C．規(guī)范推導(dǎo) D．最左歸約的逆過程

(14)文法G[S]：S→aAcB|Bd

A→AaB|c

B→bScA|b

則句型aAcbBdcc的短語是

。

A．Bd B．cc C．a(chǎn) D．b(15)文法G[E]：E→E+T|T

T→T*P|P

P→(E)|i

則句型P+T+i的句柄和最左素短語是

。

A．P+T和T B．P和P+T

C．i和P+T+i D．P和P

(16)采用自頂向下分析，必須

。

A．消除左遞歸 B．消除右遞歸

C．消除回朔 D．提取公共左因子(17)對文法G[E]：E→E+S|S

S→S*F|F

F→(E)|i

則FIRST(S)=

。

A．{(}

B．{(,i} C．{i}

D．{(,)}

(18)確定的自頂向下分析要求文法滿足

。

A．不含左遞歸 B．不含二義性

C．無回溯 D．A～C項

(19)遞歸下降分析器由一組遞歸函數(shù)組成，且每一個函數(shù)對應(yīng)文法的

。

A．一個終結(jié)符 B．一個非終結(jié)符

C．多個終結(jié)符 D．多個非終結(jié)符(20)?LL(1)分析表需要預(yù)先定義和構(gòu)造兩族與文法有關(guān)的集合

。

A．FIRST和FOLLOW B．FIRSTVT和FOLLOW

C．FIRST和LASTVT D．FIRSTVT和LASTVT

(21)設(shè)a、b、c是文法的終結(jié)符且滿足優(yōu)先關(guān)系ab和bc,則

。

A．必有ac B．必有ca

C．必有ba D．A～C都不一定成立(22)算符優(yōu)先分析法要求

。

A．文法不存在…QR…的句型且任何終結(jié)符對(a,b)滿足ab、a?b和a?b三種關(guān)系

B．文法不存在…QR…的句型且任何終結(jié)符對(a,b)至多滿足ab、a?b和a?b三種關(guān)系之一

C．文法可存在…QR…的句型且任何終結(jié)符對(a,b)至多滿足ab、a?b和a?b三種關(guān)系之一

D．文法可存在…QR…的句型且任何終結(jié)符對(a,b)滿足ab、a?b和a?b三種關(guān)系(23)任何算符優(yōu)先文法

優(yōu)先函數(shù)。

A．有一個 B．沒有

C．有若干個 D．可能有若干個

(24)在算符優(yōu)先分析中，用

來刻畫可歸約串。

A．句柄 B．直接短語

C．素短語 D．最左素短語

(25)下面最左素短語必須具備的條件中有錯誤的是

。

A．至少包含一個終結(jié)符 B．至少包含一個非終結(jié)符

C．除自身外不再包含其他素短語 D．在句型中具有最左性(26)對文法G[S]：S→b|∧|(T)

T→T，S|S

其FIRSTVT(T)為

。

A．{b,∧,(} B．{b,∧,)}

C．{，,b,∧,(} D．{，,b,∧,)}

(27)對文法G[E]：E→E*T|T

T→T+i|i

句子1+2*8+6歸約的值為

。

A．23 B．42 C．30 D．17(28)下述FOLLOW集構(gòu)造方法中錯誤的是

。

A．對文法開始符S有#∈FOLLOW(S)

B．若有A→αBβ，則有FIRST(β)\{ε}FOLLOW(B)

C．若有A→αB，則有FOLLOW(B)FOLLOW(A)

D．若有A→αB，則有FOLLOW(A)FOLLOW(B)

(29)若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則對A求FOLLOW集正確的是

。

A．FOLLOW(B)FOLLOW(A)

B．FIRSTVT(B)FOLLOW(A)

C．FIRST(B)\{ε}FOLLOW(A)

D．LASTVT(B)FOLLOW(A)(30)下面

是自底向上分析方法。

A．預(yù)測分析法 B．遞歸下降分析法

C．LL(1)分析法 D．算符優(yōu)先分析法

(31)下面

是采用句柄進(jìn)行歸約的。

A．算符優(yōu)先分析法 B．預(yù)測分析法

C．SLR(1)分析法 D．LL(1)分析法

(32)一個

指明了在分析過程中某時刻能看到產(chǎn)生式多大一部分。

A．活前綴 B．前綴 C．項目 D．項目集

(33)若B為非終結(jié)符，則A→α·Bβ為

項目。

A．接受 B．歸約 C．移進(jìn) D．待約(34)在LR(0)的ACTION子表中，如果某一行中存在標(biāo)記為“rj”的欄，則

。

A．該行必定填滿rj B．該行未填滿rj

C．其他行也有rj D．GOTO子表中也有rj

(35)?LR分析法解決“移進(jìn)/歸約”沖突時，左結(jié)合意味著

。

A．打斷聯(lián)系實行移進(jìn) B．打斷聯(lián)系實行歸約

C．建立聯(lián)系實行移進(jìn) D．建立聯(lián)系實行歸約

(36)?LR分析法解決“移進(jìn)/歸約”沖突時，右結(jié)合意味著

。

A．打斷聯(lián)系實行歸約 B．建立聯(lián)系實行歸約

C．建立聯(lián)系實行移進(jìn) D．打斷聯(lián)系實行移進(jìn)(37)若項目集Ik含有A→α??，則在狀態(tài)k時，僅當(dāng)面臨的輸入符號a∈FOLLOW(A)才采取“將α歸約為A”動作的一定是

。

A．LALR(1)?文法 B．LR(0)?文法

C．LR(1)?文法 D．SLR(1)?文法

(38)同心集合并又可能產(chǎn)生新的

沖突。

A．歸約/接受 B．移進(jìn)/移進(jìn)

C．移進(jìn)/歸約 D．歸約/歸約

【解答】

(1)通常用正規(guī)文法來描述詞法，用上下文無關(guān)文法來描述語法，而用上下文有關(guān)文法來描述語義(參見第四章4.1.1節(jié))。此外，短語文法就是0型文法。由于語義是上下文有關(guān)的，因此語義分析須用上下文有關(guān)文法描述。即選B。

(2)圖靈機(jī)對應(yīng)0型文法，有限自動機(jī)對應(yīng)3型文法，下推自動機(jī)對應(yīng)2型文法，線性界限自動機(jī)對應(yīng)1型文法。故選C。

(3)不能主觀認(rèn)定文法限制越大則語言越小，也即下述結(jié)論是不成立的：

3型語言?

2型語言?

1型語言?

0型語言

故選D。

(4)?3型文法即正規(guī)文法，它的識別系統(tǒng)是有限自動機(jī)。故選C。

(5)由S→xSx∣y可知該文法所識別的語言一定是：y左邊出現(xiàn)的x與y右邊出現(xiàn)的x相等。故選C。

(6)子樹的末端結(jié)點(即樹葉)組成的符號串構(gòu)成了語法樹的短語，簡單子樹的末端結(jié)點組成的符號串構(gòu)成了語法樹的直接短語，最左簡單子樹的末端結(jié)點組成的符號串構(gòu)成了語法樹的句柄，最左簡單子樹的末端結(jié)點組成的符號串且該字符串必須含有終結(jié)符并不一定構(gòu)成了語法樹的最左素短語，因為一則構(gòu)成最左素短語的子樹不一定是簡單子樹，二則構(gòu)成最左素短語的子樹中不得再含有包含終結(jié)符的更小子樹。故選C。

(7)樹葉結(jié)點可以是終結(jié)符或非終結(jié)符，但內(nèi)部結(jié)點(指非樹葉結(jié)點)一定是非終結(jié)符。故選D。

(8)由文法開始符S經(jīng)過零步或多步推導(dǎo)產(chǎn)生的符號序列一定是句型，僅當(dāng)推導(dǎo)產(chǎn)生的符號序列全部由終結(jié)符組成時才是句子，即句子是句型的特列。故選C。

(9)規(guī)范推導(dǎo)即最右推導(dǎo)，也即每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換。故選D。

(10)文法G[S]的一個句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或存在兩棵不同的語法樹，則它的任何句子α其最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同。故選A。

(11)一個句型的分析樹代表了該句型的歸約過程。故選B。

(12)規(guī)范歸約中的“可歸約串”即為句柄，也就是最左直接短語。故選C。

(13)規(guī)范歸約的逆過程是規(guī)范推導(dǎo)，而規(guī)范推導(dǎo)即為最右推導(dǎo)。故選B。

(14)由圖3-1可知應(yīng)選A。圖3-1句型aAcbBdcc對應(yīng)的語法樹

(15)由圖3-2可知，句柄(最左直接短語)為P，最左素短語為P+T。故選B。

(16)回溯使自頂向下分析效率降低，左遞歸使得自頂向下的分析無法實現(xiàn)；二者相比消除左遞歸更為重要。故選A。

(17)?FIRST(F)={(,i}，而由S→F可知FIRST(F)\{ε}

FIRST(S)，即FIRST(S)={(,i}。故選B。

(18)左遞歸和二義性將無法實現(xiàn)自頂向下分析，回溯則使自頂向下分析效率下降。故選D。

(19)遞歸下降分析器由一組遞歸函數(shù)組成，并且每一個函數(shù)對應(yīng)文法的一個非終結(jié)符。故選B。圖3-2句型P+T+i對應(yīng)的語法樹及優(yōu)先關(guān)系示意

(20)?LL(1)分析表需要預(yù)先定義和構(gòu)造兩族與文法有關(guān)的集合FIRST和FOLLOW。故選A。

(21)由于ab和bc并不能使選項A、B、C成立。故選D。

(22)算符優(yōu)先文法首先是一個算符文法，即文法的產(chǎn)生式中不含兩個及兩個以上相繼在一起的非終結(jié)符；且文法中的任何兩個終結(jié)符a和b之間至多滿足ab、a?b和a?b三種關(guān)系之一。由此可知應(yīng)選B。

(23)有些算符優(yōu)先文法不存在優(yōu)先函數(shù)；有些算符優(yōu)先文法存在優(yōu)先函數(shù)，且只要存在一對優(yōu)先函數(shù)，就存在無窮多對優(yōu)先函數(shù)。故選D。

(24)在算符優(yōu)先分析中是以“最左素短語”來刻畫可歸約串的。故選D。

(25)最左素短語必須具備的三個條件是：①至少包含一個終結(jié)符；②除自身外不得包含其他素短語；③在句型中具有最左性。故選B。

(26)?FIRSTVT(T)={，}，F(xiàn)IRSTVT(S)={b,∧,(}；由T→S可知FIRSTV(S)

FIRSTVT(T)，即FIRSTVT(T)={，,b,∧,(}。故選C。

(27)由圖3-3可知應(yīng)選B。另外，從構(gòu)造的語法樹可以看出相鄰兩個終結(jié)符之間的優(yōu)先關(guān)系，即層次在上的優(yōu)先級低，層次在下的優(yōu)先級高；呈現(xiàn)在文法的產(chǎn)生式中，就是離開始符近的終結(jié)符優(yōu)先級低，離開始符遠(yuǎn)的終結(jié)符優(yōu)先級高。對本題來說，“*”離開始符E近而“+”離開始符E遠(yuǎn)，即“+”的優(yōu)先級高于“*”。圖3-3句子1+2*8+6的語法樹及值變化示意

(28)若有A→αB則有FOLLOW(A)

FOLLOW(B)，即選項C錯。故選C。

(29)若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則有FIRST(B)\{ε}

FOLLOW(A)。故選C。

(30)自頂向下的分析方法有遞歸下降分析法和LL(1)分析法(又稱預(yù)測分析法)，自底向上的分析方法有算符優(yōu)先分析法和LR分析法。故選D。

(31)自底向上分析采用歸約方法，而自底向上的分析方法有算符優(yōu)先分析法和LR分析法兩種，但算符優(yōu)先分析用“最左素短語”歸約，而LR分析用“句柄”歸約。SLR(1)是LR分析法的一種，故選C。

(32)在LR分析中，一個項目指明了在分析過程的某個時刻所看到產(chǎn)生式的多大一部分。故選C。

(33)對文法G[S’]，S'→α·稱為“接受”項目；形如A→α·aβ的項目(其中a為終結(jié)符)稱為“移進(jìn)”項目；形如A→α·Bβ的項目(其中B為非終結(jié)符)稱為“待約”項目。故選D。

(34)在LR(0)的ACTION子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行必定填滿rj，而在SLR(1)的ACTION子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行可能未填滿rj。因此選A。

(35)?LR分析法解決“移進(jìn)/歸約”沖突時，左結(jié)合意味著打斷聯(lián)系而實行歸約，右結(jié)合意味著維持聯(lián)系而實行移進(jìn)。故選B。

(36)由(35)可知應(yīng)選C。

(37)在LR(0)?方法中，若項目集Ik含有A→α??，則在狀態(tài)k時，無論面臨什么輸入符號都采取“A→α歸約”的動作。在SLR(1)?方法中，若項目集Ik含有A→α??，則在狀態(tài)k時，僅當(dāng)面臨的輸入符號為a∈FOLLOW(A)?時，才確定采取“A→α歸約”的動作。在LR(1)?方法中，只有當(dāng)輸入符號是歸約項目的向前搜索符時才進(jìn)行歸約的操作。如果把所有同心的LR(1)?項目集合并為一，將看到這個心就是一個LR(0)項目集，這種LR分析法稱為LALR(1)?方法；也即，LALR(1)?方法的歸約操作與LR(1)?方法相同。由此可知應(yīng)

選D。

(38)同心集的合并有可能產(chǎn)生新的“歸約/歸約”沖突。故選D。

3.2令文法G[N]為

G[N]:N→D?|?ND

D→0?|?1?|?2?|?3?|?4?|?5?|?6?|?7?|?8?|?9

(1)?G[N]的語言L(G)是什么?

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

【解答】

(1)?G[N]的語言L(G[N])是非負(fù)整數(shù)。

3.3已知文法G[S]為S→aSb?|?Sb?|?b，試證明文法G[S]為二義文法。

【解答】

由文法G[S]：S→aSb?|?Sb?|?b，對句子aabbbb可對應(yīng)如圖3-4所示的兩棵語法樹。

因此，文法G[S]為二義文法(對句子abbb也可畫出兩棵不同的語法樹)。圖3-4句子aabbbb對應(yīng)的兩棵不同語法樹

3.4已知文法G[S]為S→SaS?|?ε，試證明文法G[S]為二義文法。

【解答】

由文法G[S]：S→SaS?|?ε，句子aa的語法樹如圖3-5所示。

由圖3-5可知，文法G[S]為二義文法。圖3-5句子aa對應(yīng)的兩棵不同的語法樹

3.5按指定類型，給出語言的文法。

(1)?L={aibj|j＞i≥0}的上下文無關(guān)文法；

(2)字母表Σ={a,b}上的同時只有奇數(shù)個a和奇數(shù)個b的所有串的集合的正規(guī)文法；

(3)由相同個數(shù)a和b組成句子的無二義文法。

【解答】(1)由L={aibj|j＞i≥0}知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有S→aSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有S→Sb或S→b型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)。因此，所求上下文無關(guān)文法G[S]為

G[S]：S→aSb?|?Sb?|?b

(2)為了構(gòu)造字母表Σ={a,b}上同時只有奇數(shù)個a和奇數(shù)個b的所有串集合的正規(guī)式，我們畫出如圖3-6所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個a到達(dá)狀態(tài)A，或經(jīng)過奇數(shù)個b到達(dá)狀態(tài)B；而由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過奇數(shù)個a到達(dá)終態(tài)C。

由圖3-6可直接得到正規(guī)文法G[S]如下：

G[S]：S→aA?|?bB

A→aS?|?bC?|?b

B→bS?|?aC?|?a

C→bA?|?aB?|?ε圖3-6習(xí)題3.5的DFA

(3)我們用一個非終結(jié)符A代表一個a(即有A→a)，用一個非終結(jié)符B代表一個b(即有B→b)；為了保證a和b的個數(shù)相同，則在出現(xiàn)一個a時應(yīng)相應(yīng)地出現(xiàn)一個B，出現(xiàn)一個b時則相應(yīng)出現(xiàn)一個A。假定已推導(dǎo)出bA，如果下一步要推導(dǎo)出連續(xù)兩個b，則應(yīng)有bA

bbAA。也即為了保證b和A的個數(shù)一致，應(yīng)有A→bAA；同理有B→aBB。此外，為了保證遞歸地推出所要求的ab串，應(yīng)有S→aBS和S→bAS。由此得到無二義文法G[S]為

G[S]：S→aBS?|?bAS?|?ε

A→bAA?|?a

B→aBB?|?b

3.6有文法G[S]:S→aAcB?|?Bd

A→AaB?|?c

B→bScA?|?b

(1)試求句型aAaBcbbdcc和aAcbBdcc的句柄；

(2)寫出句子acabcbbdcc的最左推導(dǎo)過程。

【解答】(1)分別畫出對應(yīng)句型aAaBcbbdcc和aAcbBdcc的語法樹如圖3-7的(a)、(b)所示。

圖3-7(a)對應(yīng)的樹中，直接短語有3個：AaB、b和c，而AaB為最左直接短語(即為句柄)。圖3-7(b)對應(yīng)的樹中，直接短語有兩個：Bd和c，而Bd為最左直接短語。圖3-7習(xí)題3.6的語法樹(a)?aAaBcbbdcc;(b)?aAcbBdcc能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個產(chǎn)生式的候選式這樣一個最左子串(即句柄)呢？例如，對句型aAaBcbbdcc，我們可以由左至右掃描找到第一個子串AaB，它恰好是滿足A→AaB右部的子串；與圖3-7(a)對應(yīng)的樹進(jìn)行對照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續(xù)檢查句型aAcbBdcc，由左至右找到第一個子串c，這是滿足A→c右部的子串，但由圖3-7(b)對應(yīng)的樹可知，c不是該句型的句柄。由此可知，畫出對應(yīng)句型的語法樹然后尋找最左直接短語是確定句柄的好方法。

【解答】(1)句型(S,(a))的語法樹如圖3-8所示。

(2)由圖3-8可知：

短語：S、a、(a)、S,(a)、(S,(a))；

直接短語：a、S；

句柄：S；

素短語：素短語可由圖3-8中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即：

#?(?，?(?a?)?)?#

因此，素短語為a。圖3-8句型(S,(a))的語法樹

3.8下述文法描述了C語言整數(shù)變量的聲明語句：

G[D]:D→TL

T→int?|?long?|?short

L→id?|?L,id

(1)改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；

(2)分別以上述文法G[D]和改造后的文法G′[D]為輸入序列inta,b,c構(gòu)造分析樹。

【解答】(1)消除左遞歸后，文法G′[D]如下：

D→TL

T→int?|?long?|?short

L→idL′

L′→,idL′|?ε

(2)未消除左遞歸的文法G(D)和消除左遞歸的文法G′[D]為輸入序列inta,b,c構(gòu)造的分析樹分別如圖3-9的(a)、(b)所示。圖3-9兩種文法為inta,b,c構(gòu)造的分析樹(a)文法G(D)；(b)文法G′(D)

3.9考慮文法G[S]:S→(T)|a+S|a

T→T,S|S

消除文法的左遞歸及提取公共左因子，然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。

【解答】

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

S→(T)|a+S|a

T→ST′

T′→,ST′|ε

提取公共左因子：

S→(T)|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε對于文法G[S]中的產(chǎn)生式：T→T,S|S，即將非終結(jié)符T由下面的正規(guī)表達(dá)式定義：

T→S{,S}

然后將其用狀態(tài)轉(zhuǎn)換圖表示為圖3-10。

這個狀態(tài)轉(zhuǎn)換圖的作用就如同一個遞歸過程(函數(shù))，并借助于這種轉(zhuǎn)換圖來得到遞歸過程(函數(shù))下降分析器。因此，前面的遞歸下降分析器程序可刪除函數(shù)T(?)和T'(?)，而將T(?)和T'(?)改為圖3-10非終結(jié)符T的狀態(tài)轉(zhuǎn)換圖

3.10已知文法G[A]:A→aABl?|?a

???B→Bb?|?d

(1)試給出與G[A]等價的LL(1)文法G′[A]；

(2)構(gòu)造G[A′]的LL(1)分析表；

(3)給出輸入串a(chǎn)adl#的分析過程。

【解答】(1)文法G[A]存在左遞歸和回溯，故其不是LL(1)文法。要將G[A]改造為LL(1)文法，首先要消除文法的左遞歸，即將形如P→Pα|β的產(chǎn)生式改造為

P→βP′

P→αP′|ε

來消除左遞歸。由此，將產(chǎn)生式B→Bb?|?d改造為 B→dB′

B′→bB′|ε

其次，應(yīng)通過提取公共左因子的方法來消除G[A]中的回溯，即將產(chǎn)生式A→aABl?|?a改造為

A→aA′

A′→ABl|ε

最后得到改造后的文法為

G′[A]：??A→aA′

A′→ABl|ε

B→dB′

B′→bB′|ε求得：

FIRST(A)={a}FIRST(A′)={a,ε}

FIRST(B)=rctoqesFIRST(B′)={b,ε}

對文法開始符號A，有FOLLOW(A)={#}。

由A′→ABl得FIRST(B)\{ε}

FOLLOW(A)，即FOLLOW(A)={#,d}；

由A′→ABl得FIRST(′l′)

FOLLOW(B)，即FOLLOW(B)={l}；

由A→aA′得FOLLOW(A)

FOLLOW(A′)，即FOLLOW(A′)={#,d}；

由B→dB′得FOLLOW(B)

FOLLOW(B′)，即FOLLOW(B′)={l}。對A′→ABl來說，F(xiàn)IRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]為所求等價的LL(1)文法。

(2)構(gòu)造預(yù)測分析表的方法如下：

①對文法G′[A]的每個產(chǎn)生式A→α執(zhí)行②、③步。

②對每個終結(jié)符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α為含有首字符a的候選式或為唯一的候選式。

③若ε∈FIRST(A)，則對任何屬于FOLLOW(A)的終結(jié)符b，將A→ε加入到M[A,b]中。把所有無定義的M[A,a]標(biāo)記上“出錯”。

由此得到G′[A]的預(yù)測分析表，見表3-1。表3-1預(yù)?測?分?析?表

(3)輸入串a(chǎn)adl的分析過程見表3-2。表3-2輸入串a(chǎn)adl的分析過程

3.11將下述文法改造為LL(1)文法：

G[V]:?V→N|N[E]

E→V|V+E

N→i

【解答】LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G′[V]：

G′[V]：V→NV′

V′→ε|[E]

E→VE′

E′→ε|+E

N→i一個LL(1)文法的充要條件是：對每一個終結(jié)符A的任何兩個不同產(chǎn)生式A→α?|?β有下面的條件成立：

(1)?FIRST(α)∩FIRST(β)=Φ；

(2)?假若βε，則有FIRST(α)∩FOLLOW(A)=Φ。

即求出G′[V]的FIRSTVT和LASTVT集如下：

FIRST(N)=FIRST(V)=FIRST(E)={i}

FIRST(V′)={[,ε}

FIRST(E′)={+,ε}

FOLLOW(V)={#}由V′→…E]得FIRST(‘))’)

FOLLOW(E)，即FOLLOW(E)={]}；

由V→NV′得FIRST(V′)\{ε}

FOLLOW(N)，即FOLLOW(N)={[}；

由E→VE′得FIRST(E′)\{ε}

FOLLOW(V)，即FOLLOW(V)={#,+}；

由V→NV′得FOLLOW(V)

FOLLOW(V′)，即FOLLOW(V′)={#,+}；

由V→NV′且V′→ε得FOLLOW(V)

FOLLOW(N)，即FOLLOW(N)={[,#,+}；

由E→VE′得FOLLOW(E)

FOLLOW(E′)，即FOLLOW(E′)={]}；則，對V′→ε|[E]有：FIRST(ε)∩FIRST(′[′)=Φ；

對E′→ε|+E有：FIRST(ε)∩FIRST(′+′)=Φ；

對V′→ε|[E]有：FIRST('[')∩FOLLOW(V′)={[}∩{#,+}=Φ；

對E′→ε|+E有：FIRST('+')∩FOLLOW(E′)={+}∩{]}=Φ。

故文法G′[V]為LL(1)文法。

3.12對文法G[E]：E→E+T?|?T

T→T*P?|?P

P→i

(1)構(gòu)造該文法的優(yōu)先關(guān)系表(不考慮語句括號#)，并指出此文法是否為算符優(yōu)先文法；

(2)構(gòu)造文法G[E]的優(yōu)先函數(shù)。

【解答】(1)?FIRSTVT集構(gòu)造方法：

①由P→a…或P→Qa…，則a∈FIRSTVT(P)。

②若a∈FIRSTVT(Q)，且P→Q…，則a∈FIRSTVT(P),也即FIRSTVT(Q)

FIRSTVT(P)。

由①得：由E→E+…得FIRSTVT(E)={+}；

由T→T*…得FIRSTVT(T)={*}；

由P→i得FIRSTVT(P)={i}。由②得：由T→P得FIRSTVT(P)

FIRSTVT(T)，即FIRSTVT(T)={*，i}；

由E→T得FIRSTVT(T)

FIRSTVT(E)，即FIRSTVT(E)={+，*，i}。

LASTVT集構(gòu)造方法：

①由P→…a或P→…aQ,則a∈LASTVT(P)。

②若a∈LASTVT(Q)，且P→…Q，則a∈LASTVT(P)，也即LASTVT(Q)

LASTVT(P)。

由①得：E→…+T，得LASTVT(E)={+}；

T→…*P，得LASTVT(T)={*}；

P→i，得LASTVT(P)={i}。由②得：由T→P得LASTVT(P)

LASTVT(T)，即LASTVT(T)={*，i}；

由E→T得LASTVT(T)

LASTVT(E)，即LASTVT(E)={+，*，i}。

優(yōu)先關(guān)系表構(gòu)造方法：

①對P→…ab…或P→…aQb…，有ab；

②對P→…aR…而b∈FIRSTVT(R)，有a?b；

③對P→…Rb…而a∈LASTVT(R)，有a?b。

解之無①。由②得：E→…+T，即+?FIRSTVT(T)，有+?*，+?i；

T→…*P，即*?FIRSTVT(P)，有*?i。

由③得：E→E+…，即LASTVT(E)?+，有+?+，*?+，i?+；

T→T*…，即LASTVT(T)?*，有*?*，i?*。

得到優(yōu)先關(guān)系表見表3-3。表3-3習(xí)題3.12的優(yōu)先關(guān)系表圖3-11習(xí)題3.12關(guān)系圖

表3-4習(xí)題3.12的優(yōu)先函數(shù)表表3-5優(yōu)先函數(shù)的計算過程表3-6習(xí)題3.13的算符優(yōu)先關(guān)系表圖3-12句型(SdSdS)的語法樹圖3-13句型(SdSdS)的優(yōu)先關(guān)系表3-7輸入串(adb)#的分析過程圖3-14(adb)的語法樹則當(dāng)從左至右掃描到第一個“?”時，再由此從右至左掃描到第一個“?”，它們之間(當(dāng)然不包含第一個“?”前的一個終結(jié)符和第一個“?”后的一個終結(jié)符)即為最左素短語。

如果由左至右掃描到第一個“?”，可以看出這并不一定是最左素短語的開頭，因為由它開始并不一定是素短語(在其內(nèi)部還可能包含其他更小的素短語)。因此，在算符優(yōu)先分析算法中，只有先找到最左素短語的尾(即“?”)，才返回來確定與其對應(yīng)的頭(即“?”)；而不能按掃描順序先找到頭然后再找到對應(yīng)的尾。由于在優(yōu)先關(guān)系中同時出現(xiàn)了a?a和a?a以及b?b和b?b，故文法G[S]不是算符優(yōu)先文法。表3-8習(xí)題3.16的優(yōu)先關(guān)系表

LR分析器用規(guī)范歸約的方法尋找句柄，其基本思想是：在規(guī)范歸約的過程中，一方面記住已經(jīng)歸約的字符串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入字符串，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于棧頂時，則可根據(jù)歷史、展望以及現(xiàn)實的輸入符號等三方面的材料，來確定棧頂?shù)姆柎欠駱?gòu)成相對某一產(chǎn)生式的句柄。事實上，規(guī)范歸約的中心問題恰恰是如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法也就給出了不同的規(guī)范歸約方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在歸約方法上進(jìn)行區(qū)別的。算符優(yōu)先分析不是規(guī)范歸約，因為它只考慮了終結(jié)符之間的優(yōu)先關(guān)系，而沒有考慮非終結(jié)符之間的優(yōu)先關(guān)系。此外，算符優(yōu)先分析比規(guī)范歸約要快得多，因為算符優(yōu)先分析跳過了所有單非產(chǎn)生式所對應(yīng)的歸約步驟。這既是算符優(yōu)先分析的優(yōu)點，同時也是它的缺點，因為忽略非終結(jié)符在歸約過程中的作用存在某種危險性，可能導(dǎo)致把本來不成句子的輸入串誤認(rèn)為是句子，但這種缺陷容易從技術(shù)上加以彌補(bǔ)。為了區(qū)別于規(guī)范歸約，算符優(yōu)先分析中的“句柄”被稱為最左素短語。

3.18什么是規(guī)范句型的活前綴？引進(jìn)它的意義何在？

【解答】

在討論LR分析器時，需要定義一個重要概念，這就是文法的規(guī)范句型的“活前綴”。

字的前綴是指該字的任意首部，例如，字abc的前綴有ε、a、ab或abc。所謂活前綴，是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。之所以稱為活前綴，是因為在其右邊增添一些終結(jié)符號后，就可以使它成為一個規(guī)范句型。

引入活前綴的意義在于它是構(gòu)造LR(0)項目集規(guī)范族時必須用到的一個重要概念。對于一個文法G[S]，首先要構(gòu)造一個NFA，它能識別G[S]的所有活前綴，這個NFA的每個狀態(tài)即為一個“項目”。文法G[S]每一個產(chǎn)生式的右部添加一個圓點稱為G[S]的一個LR(0)項目(簡稱項目)，可以使用這些項目狀態(tài)構(gòu)造一個NFA。我們能夠把識別活前綴的NFA確定化，使之成為一個以項目集為狀態(tài)的DFA，這個DFA就是建立LR分析算法的基礎(chǔ)。構(gòu)成識別一個文法活前綴的DFA項目集(狀態(tài))的全體稱為這個文法的LR(0)項目集歸范族。文法G[E′]?的DFA如圖3-15所示。圖3-15文法G[E′]?的DFA最后得到LR(0)?分析表見表3-9。表3-9習(xí)題3.19的LR(0)?分析表文法G[S′]?的DFA如圖3-16所示。

注意，在比較熟練的情況下，也可以不構(gòu)造LR(0)?項目集規(guī)范族而直接畫出文法G[S′]?的DFA。圖3-16文法G′[S′]?的DFA故文法G[S]?是SLR(1)?文法。最后得到SLR(1)?分析表見表3-10。表3-10SLR(1)?分析表文法G[S′]的DFA如圖3-17所示。圖3-17文法G[S′]的DFA表3-11SLR(1)分析表

3.22LR(0)、SLR(1)、LR(1)及LALR有何共同特征？它們的本質(zhì)區(qū)別是什么？

【解答】LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用規(guī)范歸約的方法尋找句柄，即LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決定的。它們的本質(zhì)區(qū)別是尋找句柄的方法不同。如果當(dāng)前的棧頂狀態(tài)為歸約狀態(tài)(即有形如A→α·的項目屬于棧頂狀態(tài))，則：

(1)對LR(0)來說，無論現(xiàn)行輸入符號是什么，都認(rèn)為棧頂?shù)姆柎疄榫浔M(jìn)行歸約。

(2)對SLR(1)來說，則對現(xiàn)行輸入符號加了一點限制，即該輸入符號必須屬于允許跟在句柄之后的字符，才認(rèn)為棧頂?shù)姆柎疄榫浔M(jìn)行歸約。

(3)對LR(1)來說，對現(xiàn)行輸入符號的限制則更加嚴(yán)格，它在該輸入符號跟在棧頂符號串后形成一個規(guī)范句型的前綴時，才認(rèn)為棧頂?shù)倪@個符號串為句柄，從而進(jìn)行歸約。由于要對不同的輸入符號進(jìn)行判斷，因此LR(1)的狀態(tài)數(shù)要比LR(0)、SLR(1)多。

(4)?LALR從本質(zhì)上講與LR(1)相同，只不過它把那些棧頂符號串相同但現(xiàn)行輸入符號不同(即認(rèn)為這個相同的棧頂符號串為同心)的判斷合一(使?fàn)顟B(tài)數(shù)又減少到與LR(0)、SLR(1)一樣)，只有輸入符號跟在棧頂符號串后面形成一規(guī)范句型前綴時，才認(rèn)為棧頂?shù)倪@個符號串為句柄而進(jìn)行歸約。對于同心的棧頂符號串而言，由于面對不同的輸入符號將形成不同規(guī)范句型的前綴，這就給歸約帶來一些困難；也即，當(dāng)輸入串有誤時，LR(1)能夠及時地發(fā)現(xiàn)錯誤，而LALR則可能還繼續(xù)執(zhí)行一些多余的歸約動作，但決不會執(zhí)行新的移進(jìn)，即LALR能夠像LR(1)一樣準(zhǔn)確地指出出錯的地點。此外，LALR這種同心集的合并有可能帶來新的“歸約/歸約”沖突。圖3-18習(xí)題3.22的LR分析表圖3-19習(xí)題3.24中文法G[S]的DFA表3-12習(xí)