編譯原理及實(shí)現(xiàn)技術(shù)：第五章 語(yǔ)法分析-自底向上分析方法

1、第五章 自底向上分析方法主要內(nèi)容自底向上分析的基本思想簡(jiǎn)單優(yōu)先分析方法LR類分析方法基本思想 從待分析的符號(hào)串開(kāi)始，自左向右進(jìn)行掃描，自下而上進(jìn)行分析，通過(guò)反復(fù)查找當(dāng)前句型的句柄，并使用產(chǎn)生式規(guī)則將找到的句柄歸約為相應(yīng)產(chǎn)生式的左部非終極符，直到將輸入串歸約為文法的開(kāi)始符。(移入-歸約分析)兩種分析方法 簡(jiǎn)單優(yōu)先和LR類分析方法自底向上語(yǔ)法分析方法介紹例：S aAcBe 1 A b 2 A Ab 3 B d 4輸入流：abbcde。規(guī)范推導(dǎo)過(guò)程為： 逆過(guò)程:(符號(hào)棧，輸入流)( -, abbcde)(a,bbcde)(ab,bcde) (aA,bcde)(aAb,cde)(aA,cde)(aAc

2、,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-) S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1簡(jiǎn)單優(yōu)先分析一種shift-reduce分析方法根據(jù)文法符號(hào)的優(yōu)先關(guān)系確定句柄文法符號(hào)的優(yōu)先關(guān)系的確定簡(jiǎn)單優(yōu)先分析中的三種關(guān)系X Y ：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式AXYX Y ：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式AXB 并有B+Y。X Y ：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式ABC 并有B+X，C*Y。 文法G為簡(jiǎn)單優(yōu)先文法如果滿足： 對(duì)于任意兩個(gè)語(yǔ)法符號(hào)X和Y，至多成立一種 優(yōu)先關(guān)系； 任意兩個(gè)產(chǎn)生式都具有不同的右部。 文法優(yōu)先關(guān)系的確定 FIRST(W) =S | W + S

3、，S(VNVT) LAST(W) =S | W + S，S(VN VT) 若有USiSj: 則有Si Sj ;若有USiW:任SjFIRST(W),有Si Sj若有UVW:任SiLAST(V), Sj(FIRST(W) W)則有Si Sj 輸入流的開(kāi)始和結(jié)束標(biāo)志 ，文法的開(kāi)始符為Z，SFIRST(Z),有# S，; 且 ZSLAST(Z)，有S #，; 且Z 優(yōu)先關(guān)系矩陣 一個(gè)文法的全部?jī)?yōu)先關(guān)系可以用矩陣來(lái)表示，稱作優(yōu)先關(guān)系矩陣。 例： Z bMb M a M (L L Ma)#)a(bLMZ#)a(bLMZ)a L )bM ( a a ( bLMZFIRST LAST定理：設(shè)X1XiXi+1

4、XjXn是一個(gè)句型，若有Xi Xi+1 Xi+2 Xj-1 Xj Xj+1則Xi+1Xi+2Xj-1Xj一定是該句型的簡(jiǎn)單短語(yǔ)。結(jié)論： 用來(lái)確定句柄的頭； 用來(lái)確定句柄的內(nèi)部； 用來(lái)確定句柄的結(jié)束。簡(jiǎn)單優(yōu)先分析算法要點(diǎn)找第一個(gè)使SjSj+1的Sj從Sj開(kāi)始往前(左)找第一個(gè)使Si-1Si的Si用SiSi+1Sj去查產(chǎn)生式的右部，并用相應(yīng)的左部符號(hào)代替句柄SiSi+1Sj (歸約) 。重復(fù)上述過(guò)程，直至輸入符結(jié)束。如果歸約出文法的開(kāi)始符號(hào)則成功。否則失敗。簡(jiǎn)單優(yōu)先分析實(shí)例符號(hào)棧 關(guān)系 輸入流 # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( a a

5、) b # b ( M a ) b # b ( M a ) b # b ( M a ) b # b ( L b # b M b # b M b # Z # 規(guī)范句型：用最右推導(dǎo)導(dǎo)出的句型(也稱右句型）。 規(guī)范前綴：若存在規(guī)范句型，且是終極符串或空串，則稱為規(guī)范前綴。 規(guī)范活前綴：若規(guī)范前綴不含句柄或含一個(gè)句柄并且具有形式=(是句柄)，則稱規(guī)范前綴為規(guī)范活前綴(簡(jiǎn)稱活前綴）。 歸約規(guī)范活前綴：若活前綴是含句柄的活前綴，即有=，且是句柄，則稱活前綴為歸約規(guī)范活前綴（簡(jiǎn)稱歸約活前綴）。LR類分析方法活前綴的描述性定義：形成可歸前綴之前，包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴?；钋熬Y 為一個(gè)或

6、若干規(guī)范句型的前綴。在規(guī)范歸約過(guò)程中的任何時(shí)刻已分析過(guò)的部分，即在分析棧（符號(hào)棧）中的符號(hào)串均為規(guī)范句型的活前綴，表明輸入串的已被分析過(guò)的部分是該文法某規(guī)范句型的一個(gè)正確部分。派生定理 開(kāi)始符產(chǎn)生式的右部是歸約活前綴。 如果A是歸約活前綴，且A是產(chǎn)生式， 則也是歸約活前綴。 任何歸約活前綴，都可按上述方式被派生。 設(shè)文法開(kāi)始符的產(chǎn)生式是： S 1|2|n RPSG=1,n|ARPSG,AP 識(shí)別規(guī)約活前綴的LRSM的構(gòu)造 例有文法GS: S aAc 1 A Abb 2 A b 3 可歸前綴集： aAc aAbb ab LR(0)項(xiàng)目：若A是產(chǎn)生式， 則稱A為L(zhǎng)R(0)項(xiàng)目(簡(jiǎn)稱項(xiàng)目），也 寫(xiě)作

7、p形式。 項(xiàng)目集的投影：假設(shè)IS是LR(0)項(xiàng)目集，則 稱下面IS(X) 為IS關(guān)于X的投影集： IS(X) = AX |AXIS, X(VTVN). 項(xiàng)目集的閉包：假設(shè)IS是LR(0)項(xiàng)目集，則 稱下面CLOSURE(IS)為IS的閉包集： CLOSURE(IS)= IS A | YACLOSURE(IS) A是產(chǎn)生式 構(gòu)造LR(0)活前綴狀態(tài)機(jī)LRSM的算法要點(diǎn) 構(gòu)造初始狀態(tài)IS0：IS0=CLOSURE(ZS)，并給IS0標(biāo)上NO。從已構(gòu)造的LRSM部分圖選擇被標(biāo)為NO的任一狀態(tài)IS，并做 1 對(duì)每個(gè)符號(hào)XVTVN，做下面動(dòng)作： 1) 令I(lǐng)Sj = CLOSURE( IS(X)。 2)

8、若在LRSM部分圖中已有ISk與ISj有相同項(xiàng)目 集，則令m=k；否則構(gòu)造ISj的狀態(tài)點(diǎn)ISj， 并給ISj標(biāo)上NO，同時(shí)令m=j。 3) 在IS和ISm之間畫(huà)有向X邊：IS ISm 。 2 給IS標(biāo)上OK。重復(fù)上一步驟，直至沒(méi)有被標(biāo)記為NO的狀態(tài)結(jié)點(diǎn)為止。x 例：構(gòu)造LR(0)狀態(tài)機(jī) S E $ E E + T E T T id T ( E )0 S E $ E E+T E T T id T ( E )1 SE $ EE +T 5 Tid 3 EE+ T T id T (E) 4 EE+T 9 ET 6 T( E) E E+T E T T id T ( E )7 T(E ) EE +T 8

9、T(E) TT(idETid)E+id(GE的LRSM+2 SE $ $ LRSM給出了所有的可歸活前綴 LRSM中的每個(gè)狀態(tài)將對(duì)應(yīng)一個(gè)飽和項(xiàng)目集： （1）其中一部分是由先驅(qū)狀態(tài)分出來(lái) (稱為基本項(xiàng)目)； （2）一部分則是由基本項(xiàng)目擴(kuò)展出來(lái)的 (稱為擴(kuò)展項(xiàng)目或派生項(xiàng)目)。派生部 分項(xiàng)目的特點(diǎn)是其中的“”出現(xiàn)在產(chǎn) 生式右部的最左側(cè)。 形如A P的項(xiàng)目稱為歸約型項(xiàng)目 形如A P的項(xiàng)目稱為移入型項(xiàng)目 移入歸約沖突 歸約歸約沖突 LRSM不能直接用于LR分析 LRSM提供的信息： （1）合法性檢查信息Aa （2）移入/歸約信息 Aa A （3）移入/歸約后的轉(zhuǎn)向狀態(tài)信息#X1X2XkXtSi0Si1S

10、i2SikSit aiai+1an #移入動(dòng)作：設(shè)Sit的ai輸入邊所指向的狀態(tài)為S*#X1X2XkXtSi0Si1Si2SikSitaiS*歸約動(dòng)作：設(shè)按AXk+1Xk+2Xt進(jìn)行歸約，則首先歸約為ASik的A輸出邊所指向的狀態(tài)設(shè)為S*，則格局變?yōu)椋?X1X2XkSi0Si1Si2SikAS*設(shè)當(dāng)前格局是：#X1X2XkSi0Si1Si2SikALR分析模型OutputStack#anaia1LR分析驅(qū)動(dòng)器gotoactionInputStXt LR(0)分析LR分析表Action矩陣：行代表狀態(tài)，列代表輸入符，而矩陣元素則表示相應(yīng)的分析動(dòng)作：Shift / Reduce / Accept

11、/ Error GoTo矩陣：行代表狀態(tài)，而列則代表語(yǔ)法符號(hào)（非終極符，終極符），而矩陣元素則表示移入或歸約后的轉(zhuǎn)向狀態(tài)。定義 若IS是一個(gè)LR(0)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù)GO（IS, X）定義為GO（IS, X）=CLOSURE（IS(X)），其中IS(X)為L(zhǎng)R(0)項(xiàng)目集IS的投影。 假設(shè)ISk為L(zhǎng)R(0)項(xiàng)目集，則 若AaISk，且GO(ISk, a)= ISi，aVT，則action(ISk, a)=Si，表示把狀態(tài)ISi和展望符a入棧。若AISk，則對(duì)任意aVT#，令action(ISk, a)=Rj，其中產(chǎn)生式A的編號(hào)為j，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若ZISk，且Z

12、為拓廣產(chǎn)生式的左部非終極符，則action(ISk, #)=Accept。若GO(ISk, A)=ISi，AVN，則goto(ISk, A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。LR(0)分析表的構(gòu)造LR(0)分析例文法如下：S E $E E+T | TT id | (E)$+id()#ETS0S5S619S1S2S3S2AccS3S5S64S4R2 R2R2R2R2R2S5R4R4R4R4R4R4S6S5S679S7S3S8S8R5R5R5R5R5R4S9R3R3R3R3R3R3GoTo表Action表LR(0)驅(qū)動(dòng)程序首先置狀態(tài)棧、符號(hào)棧和輸入流的開(kāi)始格局為：（#S1

13、,#,a1a2an#），則：若當(dāng)前格局為（#S1S2Sn,#X1X2Xn,aiai+1an#），且action(Sn, ai)=Sj，aiVT，則ai入符號(hào)棧，第j個(gè)狀態(tài)Sj入狀態(tài)棧。即移入后的格局變?yōu)椋海?S1S2Sn Sj,#X1X2Xnai,ai+1an#）若當(dāng)前格局為（#S1S2Sn,#X1X2Xn,aiai+1an#），且action(ISn, a)=Rj，aVT#，則按照第j個(gè)產(chǎn)生式進(jìn)行歸約，符號(hào)棧和狀態(tài)棧相應(yīng)元素退棧，歸約后的文法符號(hào)入棧。假設(shè)第j個(gè)產(chǎn)生式為A，k=| (=Xn-k+1Xn)，則歸約后的格局變?yōu)椋海?S1S2Sn-kS,#X1X2Xn-kA,aiai+1an#）其

14、中S=goto(Sn-k, A)。若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為#，且action(Si, #)=Accept，則分析成功。若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為a，且action(Si, a)=Error或空，則轉(zhuǎn)向出錯(cuò)處理程序。 LR(0)分析實(shí)例狀態(tài)棧 符號(hào)棧 輸入串 Action Goto0 id+id$# shift 505 id +id$# reduce4 909 T +id$# reduce3 101 E +id$# shift 3013 E+ id$# shift 50135 E+id $# reduce4 40134 E+T $# reduce2 101 E $#

15、 shift 2012 E$ # accept id+id$ 文法G： Z aAc1 A bB 2 | ba3 B dB 4 | e 5 構(gòu)造文法的LR(0)狀態(tài)機(jī)，Action表和 goto表，并給出符號(hào)串a(chǎn)bdec的LR(0) 分析過(guò)程。 SLR(1)分析方法LR(0)分析方法的不足LR(0)方法對(duì)文法的要求嚴(yán)格。LR(0)方法容易出現(xiàn)沖突狀態(tài)。一個(gè)文法例: GE: SE $ 1EE + T 2ET 3TT P 4 TP 5Pid 6 P( E ) 7 圖 GE 的LRSM0 +EPid$+Pid(TTid( idE(P ) 4 E T T T P 7 P id 5 E E + T T T

16、 P T P P id P (E) 3 T P 4 S E $ E E + T 1 S E $ 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E $ 2如果某個(gè)狀態(tài)有如下項(xiàng)目集： A , B , D d ，則存在著歸約-歸約，移入-歸約沖突 若用A 歸約，則當(dāng)前輸入符應(yīng)在A的Follow集中 若用B 歸約，則當(dāng)前輸入

17、符應(yīng)在B 的Follow集 若移入，則當(dāng)前輸入符應(yīng)為d。SLR(1)分析條件LRSM0中存在著狀態(tài) A1 1，An n， B11 a1r1，Bm mamrm則集合： Follow(A1)、Follow(An)、a1,am 兩兩相交為空SLR(1)分析表的構(gòu)造假設(shè)ISk為L(zhǎng)R(0)項(xiàng)目集，則若AaISk，且GO(ISk, a)= ISi，aVT，則action(ISk, a)=Si，表示把狀態(tài)ISi和展望符a入棧。若AISk，則對(duì)任意aVT，aFollow(A)，令action(ISk, a)=Rj，其中產(chǎn)生式A的編號(hào)為j，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若ZISk，且Z為拓廣產(chǎn)生式的左部非終極

18、符，則action(ISk, #)=Accept。若GO(ISk, A)=ISi，AVN，則goto(ISk, A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。 SLR(1)文法定義對(duì)于一個(gè)文法，若按照上述算法構(gòu)造的分析表中沒(méi)有沖突動(dòng)作，則稱該文法為SLR(1)文法。從定義可以看出SLR(1)分析方法是用LR(0)項(xiàng)目構(gòu)成的LRSM0來(lái)識(shí)別活前綴，因此它們的狀態(tài)數(shù)相同，但是，由于LR(0)方法只看狀態(tài)棧的內(nèi)容而SLR(1)方法還要向前看展望符，因此SLR(1)文法要比LR（0）文法廣。 圖 GE 的LRSM0 +EPid$+Pid(TTid( idE(P ) 4 E T T T

19、 P 7 P id 5 E E + T T T P T P P id P (E) 3 T P 4 S E $ E E + T 1 S E $ 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E $ 2Follow(S)=#Follow(E)=$,+,)Follow(T)=$,+,),*Follow(P) =$,+,),

20、*#id()$ ETP0S5S6 1741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S6 12747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10State Action Lookahead GoToSLR(1)驅(qū)動(dòng)器初始格局(#S0,#,a1a2an#)若當(dāng)前格局為 (#S0S1Sn,#X1X2Xn, aiai+1an#)，則若action(Sn, ai)=Sk，則當(dāng)前格局變?yōu)椋?#S0S1Sn Sk,#X1X2Xnai, ai+1an#)若action(Sn, ai)=Rp，則當(dāng)前格局變?yōu)椋?#S0Sn-

21、kS,#X1X2Xn-kA,aiai+1an#)其中g(shù)oto(Sn-k, A)=S若action(Sn, ai)=Accept，則成功其它情形，出錯(cuò)。 分析棧 符號(hào)棧 輸入串 分析動(dòng)作 轉(zhuǎn)向狀態(tài) 0 id id+id$# S50,5 id id+id$# R6 40,4 P id+id$# R5 70,7 T id+id$# S80,7,8 T id+id$# S50,7,8,5 Tid +id$# R6 90,7,8,9 TP +id$# R4 70,7 T +id$# R3 10,1 E +id$# S30,1,3 E+ id$# S50,1,3,5 E+id $# R6 40,1,3,4

22、 E+P $# R5 110,1,3,11 E+T $# R2 10,1 E $# S20,1,2 E$ # AcceptSLR(1)與LR(0)SLR(1)和LR(0)具有相同的狀態(tài)機(jī)LR(0)只看分析棧的內(nèi)容，不考慮當(dāng)前輸入符 SLR(1)考慮輸入符，用follow集來(lái)解決沖突，因此SLR(1)要比LR(0)分析能力強(qiáng) 括號(hào)文法定義如下： Z S$ S (S) S | 構(gòu)造該文法的SLR(1)分析表，并給出輸入流( )( )$的SLR(1)分析過(guò)程。主要內(nèi)容： LR(1)分析方法 Z E E (L,E) E S L L,E L E S id S (S)Z EE(L,E)ESSidS (S)

23、0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S狀態(tài)2存在移入-歸約沖突LR(0)方法不依賴輸入流，直接判定歸約，容易出現(xiàn)沖突。SLR(1)方法簡(jiǎn)單的把非終極符的follow集做為可歸約的依據(jù)，并不精確。一個(gè)非終極符在不同的位置上出現(xiàn)，它所允許的后繼符是不同的。LR(1)針對(duì)不同產(chǎn)生式上的非終極符，分別定義其后繼符集（展望符集Reducelookup），減少了移入/歸約沖突。LR(1)項(xiàng)目：A, a 。LR(0)項(xiàng)目及一個(gè)VT#的展望符集合IS:LR(1)項(xiàng)目集IS(X): IS(X) = AX,a |AX,aIS CLOSURE ( IS ) = IS B

24、,b |AB,a CLOSURE(IS), B是產(chǎn)生式 , bFirst(a) GO:若IS是一個(gè)LR(1)項(xiàng)目集，X是一個(gè)文法符號(hào),則GO（IS, X）=CLOSURE（IS(X)），其中IS(X)為L(zhǎng)R(1)項(xiàng)目集IS的投影。 LRSM1的構(gòu)造算法初始項(xiàng)目集： ISS=CLOSURE( Z S, # )若所有狀態(tài)都處理完，則結(jié)束選一未處理完?duì)顟B(tài)IS，對(duì)所有語(yǔ)法符號(hào) X（VTVN #),求ISX,令 IS = CLOSURE(ISX)，若IS不為空： 若IS為新?tīng)顟B(tài)，則增加IS IS,把IS加 入LRSM1中；否則為圖中某個(gè)狀態(tài)ISj，則在IS 和ISj之間增加一條轉(zhuǎn)換邊：IS ISj轉(zhuǎn)到步

25、驟2XX 非SLR(1)文法： Z S S L= R S R L aR L b R L 0ZSSL=RSRLaRLbRL#= #= #1ZS#2SL=RRL#6SL= RR LLaRLb#7SL=R #3SR#4Lb=#10LaR#=5LaRRLLaRLb# =# =# =# =11RL# =8LaRRLLaRLb#9RL#12Lb#13LaR#SLabRb=RLRLabaaLRbLR(1) 分析表的構(gòu)造假設(shè)ISk為L(zhǎng)R(1)項(xiàng)目集則：若Z, #ISk，且Z為拓廣產(chǎn)生式的左部非終極符，則action(ISk, #)=Accept。若A, aISk，且產(chǎn)生式A的編號(hào)為j，則action(ISk,

26、 a)=Rj，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若Aa, bISk，且GO(ISk, a)=ISi，aVT，則action(ISk, a)=Si，表示把狀態(tài)ISi和展望符a入棧。若GO(ISk, A)= ISi，AVN，則goto(ISk, A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。 LR(1)文法的定義對(duì)于一個(gè)文法，若按照上述算法構(gòu)造的分析表中沒(méi)有沖突動(dòng)作，則稱該文法為L(zhǎng)R(1)文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=baLR(1)驅(qū)動(dòng)程序LR(1

27、)的驅(qū)動(dòng)程序與SLR(1)的驅(qū)動(dòng)程序是相同的，可共用一個(gè)。狀態(tài)棧 符號(hào)棧 輸入串 Action GoTo0 aab=b# S5 0,5 a ab=b# S50,5,5 aa b=b# S4 0,5,5,4 aab =b# R5 110,5,5,11 aaL =b# R6 100,5,5,10 aaR =b# R4 110,5,11 aL =b# R6 10 0,5,10 aR =b# R4 20,2 L =b# S60,2,6 L= b# S120,2,6,12 L=b # R5 9 0,2,6,9 L=L # R6 70,2,6,7 L=R # R2 10,1 S # A設(shè)文法GS為：SAS

28、 | A aA | b 證明GS是LR(1)文法；構(gòu)造它的LR(1)分析表；給出符號(hào)串a(chǎn)bab#的分析過(guò)程LALR(1)方法它具有SLR(1)的狀態(tài)數(shù)少的優(yōu)點(diǎn)和LR(1)的適用范圍廣的優(yōu)點(diǎn)。 LALR(1)方法的功能介于SLR(1)和LR(1)之間。LALR(1)狀態(tài)機(jī)的狀態(tài)個(gè)數(shù)和LR(0)狀態(tài)機(jī)的狀態(tài)個(gè)數(shù)相同，而其展望符則即不采用SLR(1)的Follow集方法，也不采用LR(1)的完全精確法。 LALR(1)的思想來(lái)源LR(1)狀態(tài)機(jī)和LR(0)狀態(tài)機(jī)從它們所表示的自動(dòng)機(jī)角度來(lái)看是等價(jià)的 ；自動(dòng)機(jī)可通過(guò)合并等價(jià)狀態(tài)來(lái)減少狀態(tài)個(gè)數(shù)。 在LR(1)狀態(tài)機(jī)出現(xiàn)很多同心狀態(tài)，而LALR(1)狀態(tài)機(jī)則不產(chǎn)生同心的狀態(tài)， 從而大大減少狀態(tài)數(shù)，這就是LALR(1)和LR(1)的主要差別。 LALR(1)狀態(tài)機(jī)的定義方式：用LR(1)狀態(tài)機(jī)來(lái)定義；用LR(0)狀態(tài)機(jī)來(lái)定義。LALR(1)狀態(tài)機(jī)的構(gòu)造方法：先構(gòu)造LR(1)狀態(tài)機(jī)，后構(gòu)造LALR(1)狀態(tài)機(jī)按LR(1)狀態(tài)機(jī)的方式構(gòu)造，但發(fā)現(xiàn)同心狀態(tài) 時(shí)不產(chǎn)生新?tīng)顟B(tài)，而是采用合并狀態(tài)的方法。先構(gòu)造LR(0)狀態(tài)機(jī)，而后用傳播方式求出每 個(gè)項(xiàng)目的展望符集。相關(guān)的術(shù)語(yǔ)