第3章 語法分析.ppt

1、第3章 語法分析,3.1 文法和語言 3.2 推導(dǎo)與語法樹 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法,3.1 文法和語言,文法、自動機和編譯程序 文法是程序語言的生成系統(tǒng)，而自動機則是程序語言的識別系統(tǒng)；用文法可以精確地定義一個語言，并依據(jù)該文法構(gòu)造出識別這個語言的自動機。 文法對程序語言和編譯程序的構(gòu)造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關(guān)文法描述，而語義則要借助于上下文有關(guān)文法描述。,3.1.1 文法和語言的概念 1語言 字母表 ：程序語言的字母表通常是ASCII字符集。 字符(符號)：字母表中的每個元素稱為字符或符號。 字符串(字

2、)：由字母表中的字符所組成的有窮系列。 *： 字母表上的所有字符串(包括空串)組成的集合用*表示。 語言： *上的任意一個子集都稱為上的一個語言，記為L。 句子(語句)： 語言L中的每一個字符串稱為語言L的一個語句或句子。,2文法 文法的形式定義： 文法通常表示成四元組G=(VT，VN，S，)，其中： (1)VT為終結(jié)符號集，這是一個非空有限集，它的每個元素稱為終結(jié)符號； (2)VN為非終結(jié)符集，它也是一個非空有限集，其每個元素稱為非終結(jié)符號，且有VTVN=； (3)S為一文法開始符，是一個特殊的非終結(jié)符號，即SVN； (4)是產(chǎn)生式的非空有限集，其中每個產(chǎn)生式(或稱規(guī)則)是一序偶(，)，通常

3、寫作或:=?；?=：為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結(jié)符和非終結(jié)符組成的符號串，(VTVN)+且至少有一個非終結(jié)符，而(VTVN)*。,文法定義的一些說明： 終結(jié)符號：代表了語法的最小元素，是一種個體記號 非終結(jié)符號：語法變量，代表一個一定的語法概念，一個非終結(jié)符是一個類、一個集合。 文法開始符號：一個特殊的非終結(jié)符，它代表文法所定義的語言中我們最終感興趣的語法實體。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則) ： 是定義語法實體(變量)的一種書寫規(guī)則。一個語法實體的相關(guān)規(guī)則可能不止一個?？蓪⑦@些有相同左部的產(chǎn)生式合并為一個，如縮寫成P12n 其中，每個i(i=1,2,n)稱為P的一個候選式,例3

4、.1試構(gòu)造產(chǎn)生標(biāo)識符的文法。 解答 分析“標(biāo)識符” 或者是一單個字母，或者為一字母后跟字母數(shù)字串。 標(biāo)識符的構(gòu)成規(guī)則可通過以下產(chǎn)生式描述： Labz /* L是一字母*/ D019 /* D是一數(shù)字*/ TLD/* T是一字母或數(shù)字*/ STST /* S是字母數(shù)字串,左遞歸形式*/ ILLS /* I是一單個字母，或者為一字母后跟字母數(shù)字串*/,標(biāo)識符的文法GI為： G=(a,b,z,0,9,I,S,T,L,D,I,) : ILLS STST TLD Labz D019,例3.2寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。 解答根據(jù)題意，我們可以將奇數(shù)劃分為如圖31所示的三個部

5、分。,圖31奇數(shù)劃分示意,中間部分可出現(xiàn)任意位，引入了一個非終結(jié)符M，它包括最高位和中間位部分,假定開始符為N，則可得到文法GN為： G=(0,1,9,N,A,M,B,D,N,) : NAMA/*一位數(shù)字多位數(shù)字*/ MBMD/*僅兩位數(shù)字(無中間位)多于兩位數(shù)字*/ A13579 B123456789 D0B,3文法產(chǎn)生的語言 概念：推導(dǎo) 設(shè)文法G=(VT,VN,S,)且、(VTVN)* =: 表示推導(dǎo)。 直接推導(dǎo): A = 當(dāng)且僅當(dāng)A是一個產(chǎn)生式,(VTVN)*。 一步或多步推導(dǎo): 1 n 0步或多步推導(dǎo): 1 n,+ ,* ,例如，對下面的文法GE： EE+EE*E(E)i(3.1) E

6、可以看成是代表一類算術(shù)表達(dá)式。表達(dá)式i+i*i的推導(dǎo)如下：,概念：句型 S ， 是文法GS的一個句型； 概念：句子 S , VT* ,是文法GS的一個句子； i+i*i是文法GE的一個句子，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。 概念：語言 對于文法GS，它所產(chǎn)生的句子的全體稱為由文法GS產(chǎn)生的語言，記為LG，即有 L(G)=S且VT*,* ,* ,3.1.2 形式語言分類 語言學(xué)家NoamChomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，并分別與相應(yīng)的識別系統(tǒng)相聯(lián)系，它對程序語言的設(shè)計、編譯方法、計算復(fù)雜性等方面都產(chǎn)生了重大影響。

7、0型文法與0型語言(對應(yīng)圖靈機) G的每一個產(chǎn)生式具有下列形式： V*VNV，至少含有一個非終結(jié)符；V*；則稱文法G為0型文法或短語文法，記為PSG。 0型文法相應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機。,1型文法與1型語言(對應(yīng)線性界限自動機，自然語言) 文法G的每一個產(chǎn)生式，均在0型文法的基礎(chǔ)上增加了字符長度上滿足的限制，則稱文法G為1型文法或上下文有關(guān)文法，記為CSG。 1型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動機。 另一種定義方法是文法G的每一個產(chǎn)生式具有下列形式：A 其中，、V*，AVN，V+；顯然它滿足前述定義的長度

8、限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。,2型文法與2型語言(對應(yīng)下推自動機，程序設(shè)計語言) 產(chǎn)生式具有下列形式：A AVN，V*，則稱文法G為2型文法或上下文無關(guān)文法，記為CFG。 2型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)是下推自動機。,3型文法與3型語言(對應(yīng)有限自動機) 產(chǎn)生式具有下列形式：Aa或AbA(右線性文法) A、BVN，aVT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。 3型文法相應(yīng)的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機。 3型文法還可以呈左線性形式：Aa或ABa,四類文法的關(guān)系與區(qū)別 關(guān)

9、系： 13型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。 區(qū)別： (1)1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則允許形如“A”的產(chǎn)生式存在； (2)0、1型文法的產(chǎn)生式左部存在含有終結(jié)符號的符號串或兩個以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個的非終結(jié)符號。,例3.3試判斷下列產(chǎn)生式集所對應(yīng)的文法和產(chǎn)生的語言： (1)SACaB (2)SaSBC (3)SAc (4)SaS CaaaCSaBCSScSaA CBDBCBDBAabAbA CBEDBDCAaAbAbB aDDaDCBCBcB ADACaBabBc aEEabBbb AEbC

10、bc cCcc,解答 由四類文法的定義與區(qū)別可知，14分別為03型文法。 (1) 該0型文法產(chǎn)生的0型語言為L0(G)=a2nn0。例如：當(dāng)n=2時，句子a22= aaaa ,與G(S): SAA AaA | a 等價,(2) 該1型文法產(chǎn)生的1型語言為L1(G)=anbncnn1。例如，當(dāng)n=2時，句子a2b2c2=aabbcc是通過下列推導(dǎo)得到的：,(3) 該2型文法產(chǎn)生的2型語言為L2(G)=anbncmm、n1。例如當(dāng)n=2、m=3時，句子a2 b2 c3=aabbccc是通過下列推導(dǎo)得到的：,(4) 該3型文法產(chǎn)生的3型語言為L3(G)=ambnckm、n、k1。例如當(dāng)m=2、n=3

11、、k=4時，句子a2b3c4=aabbbcccc是通過下列推導(dǎo)得到的：,3型文法(正規(guī)文法)來描述高級程序語言的詞法部分，然后用有限自動機FA來識別高級語言的單詞； 2型文法(上下文無關(guān)文法)來描述高級語言的語法部分，然后用下推自動機PDA來識別高級語言的各種語法成分。,例3.4 給出字母表=a,b上的同時只有奇數(shù)個a和奇數(shù)個b的所有字符串集合的正規(guī)文法。 解答,圖32 例3.4的DFA,正規(guī)文法GS如下： GS: SaAbB AaSbCb BbSaCa CbAaB,3.1.3 正規(guī)表達(dá)式與上下文無關(guān)文法 1正規(guī)表達(dá)式到上下文無關(guān)文法(右線性文法)的轉(zhuǎn)換 (1) 構(gòu)造正規(guī)表達(dá)式的NFA； (2

12、) 若0為初始狀態(tài)，則A0為開始符號； (3) 如果存在映射關(guān)系f(i, a)= j，則定義產(chǎn)生式Ai aAj； (4) 如果存在映射關(guān)系f(i, )= j，則定義產(chǎn)生式Ai Aj； (5) 若i為終態(tài)，則定義產(chǎn)生式Ai 。,解答 1.構(gòu)造識別正規(guī)表達(dá)式(ab)*abb的NFA M。 2. GA0如下： GA0: A0aA0bA0aA1 A1bA2 A2bA3 A3,例3.5 用上下文無關(guān)文法描述正規(guī)表達(dá)式(ab)*abb。,2正規(guī)表達(dá)式與上下文無關(guān)文法描述的對象 上下文無關(guān)文法既可以描述程序語言的語法，又可以描述程序語言的詞法，但基于下述原因，應(yīng)采用正規(guī)表達(dá)式描述詞法： (1) 詞法規(guī)則簡單

13、，采用正規(guī)表達(dá)式已足以描述； (2) 正規(guī)表達(dá)式的表示比上下文無關(guān)文法更加簡潔、直觀和易于理解； (3) 有限自動機的構(gòu)造比下推自動機簡單且分析效率高。,結(jié)論： 貫穿詞法分析和語法分析始終如一的思想是： 語言的描述和語言的識別是表示一個語言的兩個不同的側(cè)面，二者缺一不可。 正規(guī)表達(dá)式適合于描述線性結(jié)構(gòu)，如標(biāo)識符、關(guān)鍵字和注釋等； 而上下文無關(guān)文法則適合于描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的語句if-else、while等。,3.2 推導(dǎo)與語法樹,3.2.1 推導(dǎo)與短語 1規(guī)范推導(dǎo) 最左推導(dǎo):每一步推導(dǎo)都是對句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換。 規(guī)范推導(dǎo)(最右推導(dǎo)):每

14、一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換。 規(guī)范歸約:規(guī)范推導(dǎo)的逆過程。 例：,2短語 短語 ： 是文法GS的一個句型， S A 且 A 。短語的兩個條件缺一不可。 直接短語：有A產(chǎn)生式時，為句型的一個直接短語或簡單短語。 3句柄 句柄：一個句型的最左直接短語稱為該句型的句柄，最左直接短語是惟一的。 規(guī)范歸約：將句型中的句柄用產(chǎn)生式的左部符號代替便得到新句型A，這是一次規(guī)范歸約，恰好與規(guī)范推導(dǎo)相反。,* , ,4素短語 素短語：含有終結(jié)符的短語，如果它不存在也具有同樣性質(zhì)的真子串，則該短語為素短語。 例， 在E E+E*i中， 短語：i、E*i和E+E*i； 素短語：i。,

15、 ,3.2.2 語法樹與二義性 1 GS的語法樹：以圖示化的形式把句子分解成各個組成部分來描述或分析句子的語法結(jié)構(gòu)。 (1) 結(jié)點：用GS的一個終結(jié)符或非終結(jié)符標(biāo)記； (2) 根結(jié)點：用文法開始符S標(biāo)記； (3) 內(nèi)部結(jié)點：非終結(jié)符，如果某內(nèi)部結(jié)點A的所有子結(jié)點從左至右依次標(biāo)記為x1、x2、xn，則Ax1x2xn一定是文法GS的一條產(chǎn)生式； (4) 結(jié)點必為葉結(jié)點且是其父結(jié)點的惟一子結(jié)點。,語法樹的生成： S作為根結(jié)點，并隨著推導(dǎo)逐步展開； 非終結(jié)符被它對應(yīng)的產(chǎn)生式右部的某個候選式所替換時，這個非終結(jié)符所對應(yīng)的結(jié)點就產(chǎn)生出下一代新結(jié)點。 注： 1、一棵語法樹生長過程中的任何時刻，所有那些沒有后

16、代的樹葉結(jié)點自左至右排列起來就是一個句型。 2、一棵語法樹表示了一個句型種種可能的不同推導(dǎo)過程，如不事先說明推導(dǎo)方式是最左還是最右，從語法樹看不出推導(dǎo)過程是怎樣的。,圖3-4 句子i+i*i的語法樹,例如，與文法(3.1)的句子i+i*i相應(yīng)的語法樹如圖34所示。,2子樹和短語 子樹：語法樹的某個結(jié)點連同它的所有后代組成了一棵子樹，只含有單層分枝的子樹稱為簡單子樹。 短語、直接短語、句柄和素短語的直觀解釋如下： 短語：子樹的末端結(jié)點(即樹葉)組成的符號串是相對于子樹根的短語； 直接短語：簡單子樹的末端結(jié)點組成的符號串是相對于簡單子樹根的直接短語； 句柄：最左簡單子樹的末端結(jié)點組成的符號串為句柄

17、； 素短語：子樹的末端結(jié)點組成的符號串含終結(jié)符，且在該子樹中不再有包含含有終結(jié)符的更小子樹。,圖35 E+E*i的語法樹,對圖35所示的關(guān)于句型E+E*i的語法樹： 3棵子樹：3個短語，分別為i、E*i和E+E*i； 直接短語、句柄和素短語均為i。,3文法的二義性 文法的二義性：文法GS的一個句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語法樹，則稱這個句子是二義性的。一個文法如果包含二義性的句子，則這個文法是二義文法，否則是無二義文法。,圖36 句子i+i*i的兩棵不同語法樹,例如，對文法(3.1)：EE+EE*E(E)i,再如，條件語句的文法GS為： GS: Sif B

18、 S Sif B S else S SA /*A指其它語句*/ VN = B,S,A，VT = if , else，則 分析句型if B if B S else S：,圖37 句型 if B if B S else S 的兩棵不同語法樹,4文法二義性的消除 文法二義性消除：對于一個二義性文法GS，如果能找到一個非二義性文法GS，使得L(G)=L(G)。如果找不到這樣的GS，則二義性文法描述的語言為先天二義性的。 文法二義性消除的方法如下： (1) 不改變文法中原有的語法規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。 (2) 構(gòu)造一個等價的無二義性文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。

19、,例如，我們可以將文法(3.1)改寫為無二義性的文法G E如下： GE: EE+TT TT*FF F(E)i 分析句子i+i*i：,圖38 句子i+i*i的語法樹,例3.6 試將如下的二義性文法GS的二義性消除: GS: Sif b Sif b S else SA 解答 消除GS的二義性可采用如下兩種方法： (1) 不改變已有規(guī)則，僅加進(jìn)一項非形式的語法規(guī)定：else與離它最近的if匹配(即最近匹配原則)，這樣，文法GS的句子if b if b A else A只對應(yīng)惟一的一棵語法樹(見圖39)。,(2) 改寫文法GS為GS: SS1S2 S1if b S1 else S1A S2if b S

20、if b S1 else S2 這是因為引起二義性的原因是if-else語句的if后可以是任意if型語句，所以改寫文法時規(guī)定if和else之間只能是if-else語句或其它語句。這樣，改寫后文法GS的句子if b if b A else A只對應(yīng)惟一的一棵語法樹(如圖310所示)。,圖39 復(fù)合if語句的語法樹,圖310 GS的復(fù)合if語句的語法樹,關(guān)于二義性的說明： 文法是無二義性的，句子的分析可以按惟一確定的方式進(jìn)行。 文法的二義性是不可判定的 有時候，二義性文法也可帶來一定的好處。,3.3 自上而下分析方法,自上而下分析語法分析思想： 從文法的開始符出發(fā)并尋找出這樣一個推導(dǎo)序列：推導(dǎo)出的

21、句子恰為輸入符號串；或者說，能否從根結(jié)點出發(fā)向下生長出一棵語法樹，其葉結(jié)點組成的句子恰為輸入符號串。顯然，語法樹的每一步生長(每一步推導(dǎo))都以能否與輸入符號串匹配為準(zhǔn)，如果最終句子得到識別，則證明輸入符號串為該文法的一個句子；否則，輸入符號串不是該文法的句子。,3.3.1 遞歸下降分析法 遞歸下降分析法是一種自上而下的分析方法，文法的每個非終結(jié)符對應(yīng)一個遞歸過程。 分析過程就是從文法開始符出發(fā)執(zhí)行一組遞歸過程，這樣向下推導(dǎo)直到推出句子；或者說從根結(jié)點出發(fā)，自上而下為輸入串尋找一個最左匹配序列，建立一棵語法樹。,1自上而下分析存在的不確定性 假定文法GS為： SxAy Aaba 若輸入串為xay

22、，則其分析過程如下：,圖311 試探分析對應(yīng)的語法樹,推導(dǎo)過程中采用試探的方法選擇一個產(chǎn)生式往下推導(dǎo)，若發(fā)現(xiàn)無法與輸入串匹配，回溯，選用另一個產(chǎn)生式往下推導(dǎo),注銷已生長的子樹及將匹配指針調(diào)回到失敗前的狀態(tài)。,2確定的自上而下分析 為了實現(xiàn)確定的(即無回溯的)自上而下分析，則要求文法滿足下述三個條件： (1) 文法不含左遞歸，即不存在這樣的非終結(jié)符號A：有AA存在或者有A A； 如： EE+T /* 簡單表達(dá)式簡單表達(dá)式+項 */ (2) 無回溯 (2.1)對文法的任一非終結(jié)符號A，當(dāng)其產(chǎn)生式右部有多個候選式1,i,可供選擇時，各候選式i所推出的終結(jié)符號串的首字符集合FIRST(i)要兩兩不相交

23、。 定義FIRST()a a, aVT， (VTVN)*,+ ,* ,(2.2)如 FIRST(A),則A的首字符集合FIRST(i)和A的后跟符號集FOLLOW(A)不相交。 定義FOLLOW(A) = a | SAa, aVT 例：給定文法GS:SaAb Ab | ,分析輸入ab 滿足以上條件的上下文文法為LL(1)文法。,3消除左遞歸 消除直接左遞歸：引入一個新的非終結(jié)符，把含有左遞歸的產(chǎn)生式改為右遞歸。 把 AA 改寫為如下的右遞歸形式： 改寫后的形式與原形式等價，即從A推出的符號串的集合相同。,例如，含有直接左遞歸的表達(dá)式文法GE為： GE: EE+TT TT*FF F(E)i 經(jīng)過

24、消去直接左遞歸后得到文法GE為： GE: ETE E+TE TFT T*FT F(E) i (3.2),一般情況，對于 AA1A2Am12n 每個都不等于且每個都不以A開頭，則消除A的直接左遞歸性就是將其改寫為：,例如，對產(chǎn)生式EE+TETT，消除直接左遞歸后為： ETE E+TETE,消除文法的左遞歸: 間接左遞歸 算法分3步 (1) 將文法GS的所有非終結(jié)符按一給定的順序排列：A1、A2、An ； (2) 執(zhí)行下述循環(huán)語句將間接左遞歸改為直接左遞歸： for (i=1;i=n;i+) for (j=1;j=i1;j+) 把一個形如： 的產(chǎn)生式改寫為：Ai12k12n； 按消除直接左遞歸的方

25、法消除Ai的直接左遞歸； ,(3) 化簡由(2)所得的文法，即去掉那些從開始符號S出發(fā)，在推導(dǎo)中無法出現(xiàn)的非終結(jié)符的產(chǎn)生式(去掉多余產(chǎn)生式)。,例如， (1)將文法(3.3)的非終結(jié)符排序為R、Q、S。 (2) R代入到Q的有關(guān)候選后得到改變后的Q產(chǎn)生式為 QSababb Q代入到S的有關(guān)候選后得到改變的S產(chǎn)生式為 SSabcabcbcc 消除了S的直接左遞歸后，即得到了整個文法GS為： GS: SabcSbcScS SabcS QSababb (多余) RSaa (多余) (3) 化簡,4消除回溯 回溯發(fā)生的原因在于候選式存在公共的左因子。,設(shè)文法中關(guān)于A的產(chǎn)生式為 A12ii+1j (3.

26、5) 那么，可以把這些產(chǎn)生式改寫為：,(3.6),用數(shù)學(xué)中提取公共因子的辦法來提取公共左因子。如對式(3.5)提取公共(左)因子: (1)A(12 i)i+1j (2) A A i+1j A 12 i,5遞歸下降分析器 構(gòu)造遞歸下降分析器的前提條件：描述語言語法結(jié)構(gòu)的文法為LL(1)文法： 文法不含左遞歸 文法的每個非終結(jié)符的所有候選終結(jié)首符集FIRST(i)都兩兩不相交。 如 FIRST(A),則A的首字符集合FIRST(i)和A的后跟符號集FOLLOW(A)不相交。,構(gòu)造方法(1)： 遞歸下降分析器是由一組遞歸過程(或函數(shù))組成，是一個不帶回溯的自上而下的分析程序。 從描述語言的文法出發(fā)，

27、文法的一個非終結(jié)符E對應(yīng)一個過程(或函數(shù)) ，該非終結(jié)符的產(chǎn)生式的右部與函數(shù)體對應(yīng)： 一個候選式對應(yīng)一個條件分支； 候選式中的一個非終結(jié)符對應(yīng)一個函數(shù)調(diào)用； 侯選式中的一個終結(jié)符對應(yīng)一個輸入匹配 (調(diào)用MATCH()； 候選式在其他條件分支都無法進(jìn)入的條件下，自動進(jìn)入，不對應(yīng)任何語句，說明E自動匹配輸入。,例如，文法(3.2)對應(yīng)的遞歸下降分析器如下： void match (token t) if (lookahead = t) lookahead = nexttoken; else error (); void E() T(); E(); ,void E() if (lookahead =

28、 +) match (+); T(); E(); ,void T() F(); T(); void T() if (lookahead =*) match (*); F(); T(); ,void F() if (lookahead = i) match (i); else if (lookahead =() match (); E (); if (lookahead =) match (); else error (); else error (); ,遞歸函數(shù)的調(diào)用可以以棧的形式模擬(遞歸函數(shù)的等價非遞歸實現(xiàn)，參見清華大學(xué)嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)一書)分析器相當(dāng)于一個帶有下推棧的自動機。 分析輸入

29、串 # i1*(i2+i3)# 的語法分析過程； “#”為輸入串i1*( i2+i3)的分隔符。分析過程如圖312所示。,圖312 輸入串i1*( i2+i3)的語法分析,遞歸下降分析器的另一種構(gòu)造方法：將文法的每一個非終結(jié)符用VTVN上的一個正規(guī)表達(dá)式來定義，然后將其用狀態(tài)轉(zhuǎn)換圖表示，并借助于這種轉(zhuǎn)換圖來得到遞歸下降分析器。例： (1)文法(3.2)的每個非終結(jié)符可由下面的正規(guī)表達(dá)式定義： ET+T TF*F/* “”表示閉包運算* */ Fi( E ) (3.7) (2)根據(jù)文法(3.7)可得到圖313所示的一組描述非終結(jié)符E、T和F的狀態(tài)轉(zhuǎn)換圖。,圖313 非終結(jié)符對應(yīng)的轉(zhuǎn)換圖,(3)

30、為每個轉(zhuǎn)換圖的構(gòu)造一個遞歸過程(函數(shù))。函數(shù)構(gòu)造方法綜合遞歸下降分析器的構(gòu)造方法(1)和第二章的狀態(tài)轉(zhuǎn)換圖的軟件實現(xiàn)。,void E( ) T( ); while (lookahead = +) match (+); T( ); ,void T() F(); while (lookahead = *) match (*); F(); ,3.3.2 LL(1)分析法 1)LL(1)分析法又稱預(yù)測分析法，是一種不帶回溯的非遞歸自上而下分析法。 LL(1)分析法的基本思想 根據(jù)輸入串的當(dāng)前輸入符號來惟一確定選用某條規(guī)則(產(chǎn)生式)來進(jìn)行推導(dǎo)；當(dāng)這個輸入符號與推導(dǎo)的第一個符號相同時，再取輸入串的下一個符

31、號，繼續(xù)確定下一個推導(dǎo)應(yīng)選的規(guī)則；如此下去，直到推導(dǎo)出被分析的輸入串為止。,LL(1)分析器結(jié)構(gòu) 一個LL(1)分析器由一張LL(1)分析表(也稱預(yù)測分析表)、一個先進(jìn)后出分析棧和一個控制程序(表驅(qū)動程序)組成，如圖314所示。,圖314 LL(1)分析器,LL(1)分析器說明： (1) 輸入串:待分析的符號串，以界符“#”作為結(jié)束標(biāo)志。 (2) 分析棧中存放分析過程中的文法符號。分析開始時棧底先放入一個“#”，然后再壓入文法的開始符號；當(dāng)分析棧中僅?！?”，輸入串指針也指向串尾的“#”時，分析成功。 (3) 分析表用一個矩陣(或二維數(shù)組)M表示，它概括了相應(yīng)文法的全部信息。矩陣的每一行與文法

32、的一個非終結(jié)符相關(guān)聯(lián)，而每一列與文法的一個終結(jié)符或界符“#”相關(guān)聯(lián)。如分析表元素MA,a中的內(nèi)容為一條關(guān)于A的產(chǎn)生式，表明當(dāng)A面臨輸入符號a時當(dāng)前推導(dǎo)所應(yīng)采用的候選式；當(dāng)元素內(nèi)容為空白(空白表示“出錯標(biāo)志”)時，則表明A不應(yīng)該面臨這個輸入符號a，即輸入串含有語法錯誤。,(3) 分析表用一個矩陣(或二維數(shù)組)M表示，它概括了相應(yīng)文法的全部信息。矩陣的每一行與文法的一個非終結(jié)符相關(guān)聯(lián)，而每一列與文法的一個終結(jié)符或界符“#”相關(guān)聯(lián)。對MA,a來說，A為非終結(jié)符，而a為終結(jié)符或“#”。分析表元素MA,a中的內(nèi)容為一條關(guān)于A的產(chǎn)生式，表明當(dāng)A面臨輸入符號a時當(dāng)前推導(dǎo)所應(yīng)采用的候選式；當(dāng)元素內(nèi)容為空白(空

33、白表示“出錯標(biāo)志”)時，則表明A不應(yīng)該面臨這個輸入符號a，即輸入串含有語法錯誤。,(4) 控制程序：根據(jù)分析棧頂符號x和當(dāng)前輸入符號a來決定分析器的動作： 若xa“#”，則分析成功，分析器停止工作。 若xa“#”，即棧頂符號x與當(dāng)前掃描的輸入符號a匹配；則將x從棧頂彈出，輸入指針指向下一個輸入符號，繼續(xù)對下一個字符進(jìn)行分析。 若x為一非終結(jié)符A，則查MA,a： i若MA,a中為一個A的產(chǎn)生式，則將A自棧頂彈出，并將MA,a中的產(chǎn)生式右部符號串按逆序逐一壓入棧中；如果MA,a中的產(chǎn)生式為A，則只將A自棧頂彈出。 ii若MA,a中為空，則發(fā)現(xiàn)語法錯誤，調(diào)用出錯處理程序進(jìn)行處理。,控制程序?qū)崿F(xiàn)算法：

34、 將“#”和文法開始符依次壓入棧中； 把第一個輸入符號讀入a； do 把棧頂符號彈出并放入x中； if(xVT) if(xa) 將下一輸入符號讀入a; else error(); ,else if(Mx,a“xy1y2yk”) 按逆序依次把yk、yk1、y1壓入棧中; 輸出“xy1y2yk”; else error(); while(x!=“#”),表3.1 例3.7的LL(1)分析表,例3.7 一文法的LL(1)分析表如表3.1所示，試給出輸入串a(chǎn)adl的分析過程。,表3.2 輸入串a(chǎn)adl的分析過程,2)LL(1)分析表的構(gòu)造 表驅(qū)動的LL(1)分析器中，除了分析表因文法的不同而異之外，分

35、析棧、控制程序都是相同的。構(gòu)造一個文法的表驅(qū)動LL(1)分析器關(guān)鍵在于構(gòu)造該文法的分析表。 為了構(gòu)造分析表M，需要先求與文法有關(guān)的集合FIRST和FOLLOW。,FIRST集構(gòu)造方法：對文法中的每一個非終結(jié)符X構(gòu)造FIRST(X)，其方法是連續(xù)使用下述規(guī)則，直到每個集合的FIRST不再增大為止。(注：對終結(jié)符a而言，F(xiàn)IRST(a)=a，因而無需構(gòu)造。) 若有產(chǎn)生式Xa，且aVT ，則把a加入到FIRST(X)中；若存在X，則將也加入到FIRST(X)中。 若有XY，且YVN，則將FIRST(Y)中的所有非元素(記為“”)都加入到FIRST(X)中；若有XY1Y2Yk，且Y1Yi1都是非終結(jié)符

36、，而Y1Yi1的候選式都有存在，則把FIRST(Yj)的所有非元素都加入到FIRST(X)中(j=1,2,i)；特別是當(dāng)Y1Yk均含有產(chǎn)生式時，應(yīng)把也加到FIRST(X)中。,FOLLOW集構(gòu)造方法：對文法GS的每個非終結(jié)符A構(gòu)造FOLLOW(A)的方法是連續(xù)使用下述規(guī)則，直到每個FOLLOW不再增大為止。 對文法開始符號S，置#于FOLLOW(S)中(由語句括號“#S#”中的S#得到)。 若有AB(可為空)，則將FIRST()加入到FOLLOW(B)中。 若有AB或AB，且(即FIRST()，則把FOLLOW(A)加到FOLLOW(B)中(此處的也可為空)。,構(gòu)造分析表M。 對文法GS的每個

37、產(chǎn)生式A執(zhí)行以下、步。 對每個終結(jié)符aFIRST(A)，把A加入到MA,a中，其中為含有首字符a的候選式或為惟一的候選式。 若FIRST(A),則對任何屬于FOLLOW(A)的終結(jié)符b，將A( =)加入到MA,b中。 把所有無定義的MA,a標(biāo)記為“出錯”。,LL(1)文法：一個文法GS，若它的分析表M不含多重定義入口，則是一個LL(1)文法。 LL(1)文法必須滿足3個條件(書中只列出兩個),例3.8 試構(gòu)造表達(dá)式文法GE的LL(1)分析表，其中： GE: ETE E+TE TFT T*FT F(E)i 解答,表3.3 例3.8的LL(1)分析表,例3.9 程序語言中if-else語句的文法G

38、S為： GS: SiESeSiESa Eb 其中，e遵從最近匹配原則。試改造文法GS并為之構(gòu)造LL(1)分析表。 解答,表3.4 例3.9的分析表,我們看到，分析表M含有多重入口沖突項MS,e，因此文法GS不是LL(1)文法。但遵從e的最近匹配原則，則應(yīng)在MS,e欄置SeS，由此得到無二義的LL(1)分析表見表3.5。,表3.5 例3.9的LL(1)分析表,表3.5 例3.9的LL(1)分析表,3.4 自下而上分析方法,3.4.1 自下而上分析原理 所謂自下而上分析就是自左至右掃描輸入串，自下而上進(jìn)行分析；通過反復(fù)查找當(dāng)前句型的句柄(最左直接短語)，并使用產(chǎn)生式規(guī)則將找到的句柄歸約為相應(yīng)的非終

39、結(jié)符。這樣逐步進(jìn)行“歸約”，直到歸到文法的開始符號；或者說，從語法樹的末端開始，步步向上“歸約”，直到根結(jié)點。,“移進(jìn)歸約”: 自下而上分析法是一種“移進(jìn)歸約”法 自下而上分析過程采用了一個先進(jìn)后出的分析棧 把輸入符號自左至右逐個移進(jìn)分析棧，并且邊移入邊分析，一旦棧頂?shù)姆柎纬赡硞€句型的句柄時就進(jìn)行一次歸約(用相應(yīng)產(chǎn)生式的左部非終結(jié)符替換當(dāng)前句柄) 整個輸入串處理完畢。若此時分析棧只剩有文法的開始符號則分析成功,例： 假設(shè)一文法GS為： GS: SaAbB AcAc Bd 試對輸入串a(chǎn)ccbd進(jìn)行分析，檢查該符號串是否是GS的一個句子。 具體分析過程如表3.6所示。,表3.6 對輸入串a(chǎn)cc

40、bd自下而上的分析過程,圖315 自下而上構(gòu)造分析樹的過程,上述語法分析過程可以用一棵分析樹來表示。在自下而上分析過程中，每一步歸約都可以畫出一棵子樹來，隨著歸約的完成，這些子樹被連成一棵完整的分析樹。根據(jù)表3.6構(gòu)造分析樹的過程如圖315所示。,修剪語法樹 為了加深對“句柄”和“歸約”這些重要概念的理解，我們使用修剪語法樹的辦法來進(jìn)一步闡明自下而上的分析過程。 每次尋找當(dāng)前語法樹的句柄(在語法樹中用虛線勾出)，然后將句柄中的樹葉剪去(即實現(xiàn)一次歸約)；這樣不斷地修剪下去，當(dāng)剪到只剩下根結(jié)時，就完成了整個歸約過程。,圖316 修剪語法樹實現(xiàn)歸約,例如，對圖3-15(d)所示的語法樹，我們采用修

41、剪語法樹的方法來實現(xiàn)歸約。,從建立分析樹和剪枝的過程可以清楚地看出： 如何確定棧頂?shù)哪男┓栃纬?“可歸約串” 是分析的關(guān)鍵問題。 對于“移進(jìn)歸約”來說，因為句柄的“最左”性和分析棧的棧頂兩者是相關(guān)的，句柄總是出現(xiàn)在分析棧的棧頂，因此，每一步歸約都是歸約當(dāng)前句型的句柄。 規(guī)范歸約的實質(zhì)是，在移進(jìn)過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時就用相應(yīng)產(chǎn)生式的左部符號進(jìn)行替換(即歸約),小結(jié)：規(guī)范歸約的中心問題就是如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法就給出了不同的規(guī)范歸約方法，這一點我們將在LR分析器中討論。,3.5 LR分 析 法,LR分析法：一種自下而上進(jìn)行規(guī)范歸約的語法分析方法，LR指“自左

42、向右掃描和自下而上進(jìn)行歸約”。LR分析法比遞歸下降分析法、LL(1)分析法和算符優(yōu)先分析法對文法的限制要少得多，對大多數(shù)用無二義的上下文無關(guān)文法描述的語言都可以用LR分析器予以識別，而且速度快，并能準(zhǔn)確、及時地指出輸入串的任何語法錯誤及出錯位置。,3.5.1 LR分析器的工作原理 我們知道，規(guī)范歸約(最左歸約，即最右推導(dǎo)的逆過程)的關(guān)鍵問題是尋找句柄。LR分析法的基本思想是：在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約出的整個符號串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能遇到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時，我們希望能夠根據(jù)所記載的“歷史”

43、和“展望”以及“現(xiàn)實”的輸入符號等三方面的材料，來確定棧頂?shù)姆柺欠駱?gòu)成相對某一產(chǎn)生式的句柄。,圖321 LR分析器結(jié)構(gòu)示意,一個LR分析器實質(zhì)上是一個帶先進(jìn)后出存儲器(棧)的確定有限狀態(tài)自動機。一個LR分析器包括控制分析棧、控制程序、LR分析表三部分： 分析棧:分析棧的每一項內(nèi)容包括狀態(tài)s和文法符號X兩部分，狀態(tài)s概括了從分析開始直到某一歸約階段的全部“歷史”和“展望”資料。任何時候，棧頂?shù)臓顟B(tài)都代表了整個“歷史”和已推測出的“展望”。LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所惟一決定的。 (s0，#)為分析開始前預(yù)先放入棧里的初始狀態(tài)和句子括號；棧內(nèi)符號串X1X2Xm是至今已移進(jìn)

44、歸約出的文法符號串。,LR分析表:LR分析表是LR分析器的核心部分。一張LR分析表包括兩部分：一部分是“動作”(ACTION)表，另一部分是“狀態(tài)轉(zhuǎn)換”(GOTO)表；它們都是二維數(shù)組。ACTIONs,a規(guī)定了當(dāng)狀態(tài)s面臨輸入符號a時應(yīng)采取什么動作。而GOTOs, X規(guī)定了狀態(tài)s面對文法符號X(終結(jié)符或非終結(jié)符)時的下一狀態(tài)是什么。顯然，GOTOs, X定義了一個以文法符號為字母表的DFA。 每一項ACTIONs, a所規(guī)定的動作是以下四種情況之一： (1) 移進(jìn)：使(s, a)的下一狀態(tài)s=ACTIONs, a和輸入符號a進(jìn)棧(注：對終結(jié)符a來說，下一狀態(tài)s=GOTOs, a的值實際上是放在

45、ACTIONs, a中的)，下一輸入符號變成現(xiàn)行輸入符號。,(2) 歸約：指用某一產(chǎn)生式A進(jìn)行歸約。假若的長度為，則歸約的動作是去掉棧頂?shù)膫€項，即使?fàn)顟B(tài)sm-變成棧頂狀態(tài)，然后使(sm-,A)的下一狀態(tài)s=GOTOsm-,A 和文法符號(非終結(jié)符)A進(jìn)棧。歸約的動作不改變現(xiàn)行輸入符號，執(zhí)行歸約的動作意味著呈現(xiàn)于棧頂?shù)姆柎?Xm-+1Xm是一個相對于A的句柄。 (3) 接受：宣布分析成功，停止分析器的工作。 (4) 報錯：報告發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序。,總控程序：LR分析器的總控程序本身的工作十分簡單，它的任何一步只需按分析棧的棧頂狀態(tài)s和現(xiàn)行輸入符號a執(zhí)行ACTIONs,a所規(guī)定

46、的動作即可。 LR分析過程 例如，表達(dá)式文法GE如下，它對應(yīng)的LR分析表見表3.13，則語句i+i*i的LR分析過程如表3.14所示： GE: (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,表3.13 LR分析表,表3.14 i+i*i的LR分析過程,LR文法： 對于一個文法，如果能夠構(gòu)造一張分析表，使得它的每個入口均是惟一確定的，則稱這個文法為LR文法。對于一個LR文法，當(dāng)分析器對輸入串進(jìn)行自左至右掃描時，一旦句柄呈現(xiàn)于棧頂，就能及時對它實行歸約。 LR文法肯定是無二義的。 LR(k)文法： 在有些情況下，LR分析器需要“展望”和實際檢查未來

47、的k個輸入符號才能決定應(yīng)采取什么樣的“移進(jìn)歸約”決策。一般而言，一個文法如果能用一個每步最多向前檢查k個輸入符號的LR分析器進(jìn)行分析，則這個文法就稱為LR(k)文法。 LR分析關(guān)鍵問題： 如何由文法構(gòu)造LR分析表。,四種分析表的構(gòu)造方法，它們是： (1) LR(0)表構(gòu)造法：這種方法局限性很大，但它是建立一般LR分析表的基礎(chǔ)； (2) SLR(1)表(即簡單LR表)構(gòu)造法：這種方法較易實現(xiàn)又極有使用價值； (3) LR(1)表(即規(guī)范LR表)構(gòu)造法：這種表適用大多數(shù)上下文無關(guān)文法，但分析表體積龐大； (4) LALR表(即向前LR表)構(gòu)造法：該表能力介于SLR(1)和LR(1)之間。,3.5.

48、2 LR(0)分析表的構(gòu)造 LR(0)項目集： 一個LR(0)項目集代表LR(0)分析表中的狀態(tài)， LR(0)分析表中的狀態(tài)是一種簡單狀態(tài)，只概括“歷史”資料而不包含推測性“展望”材料，通過該狀態(tài)就能識別呈現(xiàn)在棧頂?shù)哪承┚浔?字的前綴：字的任意首部，例如字abc的前綴有、a、ab或abc。 活前綴：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。在LR分析工作過程中的任何時候，棧里的文法符號(自棧底而上)X1X2Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分匹配于其后即應(yīng)成為規(guī)范句型(如果整個輸入串確為一個句子的話)。因此，只要輸入串的已掃描部分保持可歸約成一個活前綴，就意味著所掃描的部分沒

49、有錯誤。,識別GS的所有活前綴的NFA： 對于一個文法GS，構(gòu)造一個NFA，它能識別GS的所有活前綴。這個NFA的每個狀態(tài)就是一個“項目”。 LR(0)項目：文法GS中每一個產(chǎn)生式的右部添加一個圓點，稱為GS的一個LR(0)項目(簡稱項目)。一個項目指明了在分析過程的某個時刻我們看到產(chǎn)生式的多大一部分。可以使用這些項目狀態(tài)構(gòu)造一個NFA用來識別文法的所有活前綴。,例如，產(chǎn)生式AXYZ對應(yīng)有四個項目： AX Y Z A XY Z A X YZ A X Y Z 但是產(chǎn)生式A只對應(yīng)一個項目A。 “歸約”項目：圓點在最右端的項目A ，稱為一個 ； “接受”項目：拓廣文法開始符號S的歸約項目S 稱為；

50、“移進(jìn)”項目：形如Aa的項目(a為終結(jié)符)，稱為 ； “待約”項目：形如AB的項目(B為非終結(jié)符)，稱為 。,例：文法GS的NFA：GS AXY 項目: AXY AXY AXY Xa項目: Xa Xa XZ項目: XZ XZ Yc項目: Yc Yc Zb項目: Zb Zb * 注意NFA的狀態(tài)與活前綴規(guī)約項目狀態(tài)與句柄的關(guān)系。 使用第二章講述的子集方法，就能夠把識別活前綴的NFA確定化，使之成為一個以項目集合為狀態(tài)的DFA，這個DFA就是建立LR分析算法的基礎(chǔ)。 LR(0)項目集：一個就是NFA確定化過程中形成的一個狀態(tài)子集I，該子集對應(yīng)DFA的一個狀態(tài)，子集中的一個元素就是一個LR(0)的項

51、目。,1LR(0)項目集規(guī)范族的構(gòu)造 將文法GS進(jìn)行拓廣： 假定文法GS以S為開始符號，我們構(gòu)造一個GS，它包含了整個GS并引進(jìn)了一個不出現(xiàn)在GS中的非終結(jié)符S，同時加進(jìn)了一個新產(chǎn)生式SS，這個S是GS的開始符號。稱GS是GS的拓廣文法，并且會有一個僅含項目SS的狀態(tài)，這就是惟一的“接受”態(tài)。 用第二章所引進(jìn)的_CLOSURE(閉包)來構(gòu)造一個文法GS的LR(0)項目集規(guī)范族。每個LR(0)項目集為DFA的一個狀態(tài)。,假定I是文法GS的任一項目集，則定義和構(gòu)造I的閉包CLOSURE(I)的方法是： (1) I的任何項目都屬于CLOSURE(I)； (2) 若AB屬于CLOSURE(I)，那么對

52、任何關(guān)于B的產(chǎn)生式B，其項目B也屬于CLOSURE(I)(設(shè)AB的狀態(tài)為i，則i到所有含B的狀態(tài)都有一條有向邊，即此規(guī)則仍與第二章的_CLOSURE(I)定義一樣)； (3) 重復(fù)執(zhí)行上述(1)(2)步直至CLOSURE(I)不再增大為止。,DFA的狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X)： GO(I,X)的第一個變元I是一個項目集，第二個變元X是一個文法符號(終結(jié)符或非終結(jié)符)，函數(shù)GO(I,X)定義為 GO(I,X)=CLOSURE(J) 其中，如果AX屬于I，則J=任何形如AX的項目。如果由I項目集發(fā)出的字符為X的有向邊，則到達(dá)的狀態(tài)即為CLOSURE(J)(這也類同于第二章Ia=_CLOSURE(J

53、)的定義，但這里相當(dāng)于輸入的字符是X)。直觀上說，若I是對某個活前綴有效的項目集(狀態(tài))，則GO(I,X)就是對X有效的項目集(狀態(tài))。,構(gòu)造拓廣文法GS的LR(0)項目集規(guī)范族和GS 的DFA： 通過函數(shù)CLOSURE和GO很容易構(gòu)造一個文法GS的拓廣文法GS的LR(0)項目集規(guī)范族和GS 的DFA 。 例：3.16 P70,2LR(0)分析表的構(gòu)造 LR(0)文法: 假若一個文法GS的拓廣文法GS的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況：既含移進(jìn)項目又含歸約項目或者含有多個歸約項目，則稱GS是一個LR(0)文法。換言之，LR(0)文法規(guī)范族的每個項目集不包含任何沖突項目。 構(gòu)

54、造LR(0)分析表的算法: 對于LR(0)文法，我們可直接從它的項目集規(guī)范族C和活前綴自動機的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR(0)分析表的算法。,假定C=I0，I1，In。令每個項目集Ik的下標(biāo)k作為分析器的狀態(tài)，特別地，令包含項目SS(表示整個句子還未輸入)的集合Ik的下標(biāo)k為分析器的初態(tài)。分析表的ACTION子表和GOTO子表可按如下方法構(gòu)造： (1) 若項目Aa屬于Ik且GO(Ik,a)=Ij，a為終結(jié)符，則置ACTIONk,a為“將(j,a)移進(jìn)?！?，簡記為“sj”。 (2) 若項目A屬于Ik，則對任何終結(jié)符a(或結(jié)束符#)，置ACTIONk,a為“用產(chǎn)生式A進(jìn)行歸約

55、”，簡記為“rj”( A是文法GS的第j個產(chǎn)生式)。 (3) 若項目SS屬于Ik(S表示整個句子已輸入并歸約結(jié)束)，則置ACTIONk,#為“接受”，簡記為“acc”。 (4) 若GO(Ik,A)=Ij，A為非終結(jié)符，則置GOTOk,A=j。 (5) 表中空白格均置為“出錯標(biāo)志”。,LR(0)表和LR(0)分析器: 由于假定LR(0)文法規(guī)范族的每個項目集不含沖突項目，因此按上述方法構(gòu)造的分析表的每個入口都是惟一的(即不含多重定義)。我們稱如此構(gòu)造的分析表是一張LR(0)表，使用LR(0)表的分析器叫做一個LR(0)分析器。 例3.16 已知文法GS如下，試構(gòu)造該文法的LR(0)分析表： GS: SBB BaBb,解答 將文法GS拓廣為文法GS： GS: (0) SS (1) SBB (2) BaB (3) Bb,列出LR(0)的所有項目： 1SS 5SBB 9Bb 2SS 6BaB 10Bb 3SBB 7BaB 4SBB 8BaB,用_CLOSURE辦法構(gòu)造文法GS的LR(0)項目集規(guī)范族如下： I0: SS I1: SS I3: BaB I5: SBB SBB I2: SBB BaB I6: BaB BaB BaB Bb Bb Bb I4: Bb