語法分析(二)

1、2021-7-9西北工業(yè)大學(xué)軟件與微電子學(xué)院 machunyan 1 o 課程內(nèi)容課程內(nèi)容 第第1 1章章 概論概論 第第2 2章章 詞法分析詞法分析 第第3 3章上下文無關(guān)文法章上下文無關(guān)文法 第第4 4章語法分析章語法分析 n 第第4 4章語義分析章語義分析 n 第第6 6章運行時環(huán)境章運行時環(huán)境 n 第第7 7章代碼生成章代碼生成 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院2 第四章 自下而上的語法分析 4.1 自下而上的語法分析概覽 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)

2、分析 4.7 語法分析器自動生成工具YACC 作業(yè) machunyan 西北工業(yè)大學(xué)軟件與微電子學(xué)院3 4.1 自下而上的語法分析概覽自下而上的語法分析概覽 自下而上語法分析方法自下而上語法分析方法： 從輸入單詞序列開始，自左至右逐步進行歸 約，試圖將其歸約為文法的開始符號。 從輸入單詞序列開始，以單詞做為語法樹的 葉節(jié)點，自底向上地構(gòu)造語法分析的結(jié)果- -語法樹。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院4 例:文法G： S cAd A ab A a 試采用自下而上的語法分析方法識別輸入串cabd是 否是該文法所定義的句子？ 4.1 自下而上的語法分析概覽自下而上的語法分析概覽(續(xù)續(xù))

3、 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院5 b d c a 自左至右規(guī)約的過程： c a A b d S A c a b d cabd cAd cAd S 4.1 自下而上的語法分析概覽(續(xù)) 自左至右規(guī)約是規(guī)范推導(dǎo)的逆過程, 所以稱之 為規(guī)范規(guī)約。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院6 S r aAcBe r aAcde r aAbcde r abbcde 建立輸入串a(chǎn)bbcde的規(guī)范推導(dǎo)： 規(guī)范歸約是規(guī)范推導(dǎo)的逆過程： abbcde aAbcde aAcde aAcBe S 對于文法GS:SaAcBe Ab AAb Bd 4.1 自下而上的語法分析概覽(續(xù)) machu

4、nyan西北工業(yè)大學(xué)軟件與微電子學(xué)院7 4.1 自下而上的語法分析概覽(續(xù)) o 在自下而上語法分析工作的每一步，都是從在自下而上語法分析工作的每一步，都是從 當前串中選擇一個子串，將它歸約到某個非當前串中選擇一個子串，將它歸約到某個非 終結(jié)符號；終結(jié)符號； o 為了方便對自下而上的語法分析方法進行描為了方便對自下而上的語法分析方法進行描 述，本章將每次述，本章將每次規(guī)約的子串規(guī)約的子串稱為稱為句柄句柄； machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院8 n句型的直接短語： 若有S =*A ， 、(VNVT)* 則稱是句型相對于非終結(jié)符A 的直接短語; 文法GS n句型的句柄： 句型的最左直接

5、短語（在規(guī)范推導(dǎo)中，最先被歸約 的子串），稱為該句型的句柄; 理解句柄 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院9 求句型i*i+i 的直接短語和句柄 例4.1:已知文法GE：EE+T|T TT*F|F F(E)|i 直接短語： i1 ， i2 ， i3 句柄： i1 E E + T F i3 T * T F i2F i1 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院10 o 總結(jié)本節(jié)內(nèi)容：總結(jié)本節(jié)內(nèi)容： o 自下而上的語法分析算法通常采用自下而上的語法分析算法通常采用規(guī)范規(guī)范 歸約歸約，即規(guī)范推導(dǎo)的逆過程；，即規(guī)范推導(dǎo)的逆過程； n 規(guī)范規(guī)約的每一步是從當前的規(guī)范句 型中將句柄歸約為

6、相應(yīng)的非終結(jié)符； 4.1 自下而上的語法分析概覽(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院11 第4章 自下而上的語法分析 4.1 自下而上的語法分析概覽 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 語法分析器自動生成工具YACC 作業(yè) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院12 4.2 LR 分析概覽 o LR分析法分析法是一種有效的自下而上的語法分是一種有效的自下而上的語法分 析技術(shù)，它能適用于大部分上下文無關(guān)文法析技術(shù)，它能適用于大部分上下文無關(guān)文法

7、 的分析，一般叫的分析，一般叫LR(k)分析方法，其中分析方法，其中 n L是指自左(Left)向右分析輸入單詞序列， n R是指分析過程都是構(gòu)造最右(Right)推導(dǎo) 的逆過程(規(guī)范歸約)， n 括號中的k是指在決定當前分析動作時向 右看的單詞個數(shù)。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院13 4.2 LR 分析概覽(續(xù)) o 有以下原因使得有以下原因使得 LR分析法分析法與其它語法分析方法相與其它語法分析方法相 比，應(yīng)用更廣泛，具有更強的吸引力。比，應(yīng)用更廣泛，具有更強的吸引力。 n 應(yīng)用面廣：能夠通過LR分析程序識別所有采 用上下文無關(guān)文法描述的程序設(shè)計語言的語 法結(jié)構(gòu)； n 能

8、有效實現(xiàn)：是無回溯的移進歸約方法； n 容易查錯：LR分析器能夠及時發(fā)現(xiàn)語法錯誤 和準確指出錯誤位置。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院14 例4.2 考慮以下文法： abbcde對應(yīng)的規(guī)范規(guī)約： 構(gòu)造規(guī)范規(guī)約的語法分析程序要解決的問題？ 對于文法GS:SaAcBe Ab AAb Bd abbcde aAbcde aAcde aAcBe S machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院15 移進 $abbcde$1 下表給出了使用該文法對串a(chǎn)cbc的LR分析。 分析棧輸入動作步驟 $a bbcde$移進 2 $ab bcde$用Ab歸約 3 $aA bcde$移進 4 $aAb

9、 cde$用AAb歸約 5 $aA cde$移進 6 $aAc de$移進 7 8$aAcd e$用Bd歸約 $aAcB e$移進 9 $aAcBe $ 用SaAcBe歸約10 11$ S $接受 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院16 分析棧輸入動作 步驟 移進 $abbcde$10 $a bbcde$移進 202 $ab bcde$用Ab歸約 3 025 $aA bcde$移進 4023 $aAb cde$用AAb歸約 50236 $aA cde$移進 6023 $aAc de$移進 70234 8$aAcd e$用Bd歸約02347 $aAcB e$移進 9 02348 $a

10、AcBe $ 用SaAcBe歸約10 023489 11$ S $接受01 狀態(tài)棧 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院17 o 為了描述何時移進，何時規(guī)約，現(xiàn)將為了描述何時移進，何時規(guī)約，現(xiàn)將分分 析棧中存儲的符號串稱之為活前綴析棧中存儲的符號串稱之為活前綴； o 符號串前綴的定義符號串前綴的定義：符號串的前綴是指從符號符號串的前綴是指從符號 串的尾部刪去若干串的尾部刪去若干(包括包括0個個)個符號之后所余下個符號之后所余下 的部分。的部分。 n 若 x，y，z是字母表上的符號串，且z=xy, 則x是符號串z的前綴，y是符號串z的后綴。 4.2 LR 分析概覽(續(xù)) machuny

11、an西北工業(yè)大學(xué)軟件與微電子學(xué)院18 當前規(guī)范句型() 的句柄是什么？ o 活前綴和可歸前綴活前綴和可歸前綴： n 設(shè)有文法GS，若S =* A = 是 文法G的一個規(guī)范推導(dǎo)，(， (VT VN)+，VT*，AVN)， o的一個前綴稱為文法G的一個活前綴 o稱為文法G的可歸前綴。 n 包含句柄的活前綴是可歸前綴？ 4.2 LR 分析概覽(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院19 在對文法句型規(guī)范歸約的過程中，自左向右分析輸 入串的任何時刻，在符號棧中的符號串均為規(guī)范句 型的活前綴。 如果符號棧的內(nèi)容是當前句型的可歸前綴，那么 棧頂已經(jīng)形成當前句型的句柄，進行歸約，否則繼 續(xù)移進

12、。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院20 規(guī)范句型當前句柄可歸前綴 abbcdebab aAbcde Ab aAb aAcde d aAcd aAcBeaAcBe aAcBe SS S 例，對于GS SaAcBe Ab AAb Bd 輸入串:abbcde machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院21 LR分析算法的關(guān)鍵技術(shù)：分析算法的關(guān)鍵技術(shù)： o 如何識別如何識別(符號棧符號棧)棧頂?shù)姆柦M成的符號串棧頂?shù)姆柦M成的符號串 是否是是否是可歸前綴，是可歸前綴就規(guī)約，否則可歸前綴，是可歸前綴就規(guī)約，否則 移進移進 o 分析表指導(dǎo)，分析表如何構(gòu)造分析表指導(dǎo)，分析表如何構(gòu)造 n

13、求文法中的所有可歸前綴 n 識別可歸前綴和活前綴 分析表的構(gòu)造1 2 3 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院22 1.求文法中的所有可歸前綴 方法：對任一文法，若已知它有可歸前綴xUy， UVN，且文法中有產(chǎn)生式Uu，則有xUy xuy, 則xu也是文法的可歸前綴。 例：對文法 (1) SaAcBe (2) Ab (3) AAb (4) Bd 例：對拓廣文法 (0) SS (1) SaAcBe (2) Ab (3) AAb (4) Bd machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院23 據(jù)拓廣文法有：S S r S為當前句型S的句柄，故S為可歸前綴。 因S為可歸前綴，且有產(chǎn)生式S

14、aAcBe，故 aAcBe是可歸前綴 因aAcBe 為可歸前綴，且有產(chǎn)生式AAb，故 aAb是可歸前綴 因aAcBe 為可歸前綴，且有產(chǎn)生式Ab，故ab是 可歸前綴 1.求文法中的所有可歸前綴(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院24 因aAb 為可歸前綴，且有產(chǎn)生式AAb，故aAb是 可歸前綴(重復(fù)) 因aAb 為可歸前綴，且有產(chǎn)生式Ab，故ab是可 歸前綴(重復(fù)) 因aAcBe 為可歸前綴，且有產(chǎn)生式Bd，故 aAcd是可歸前綴 1.求文法中的所有可歸前綴(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院25 因aAcd 為可歸前綴，且有產(chǎn)生式AAb，故aAb是 可歸前

15、綴(重復(fù)) 因aAcd 為可歸前綴，且有產(chǎn)生式Ab，故ab是可 歸前綴(重復(fù)) 所以文法的可歸前綴有：S , aAcBe , aAb , ab , aAcd 1.求文法中的所有可歸前綴(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院26 2.識別可歸前綴和活前綴 o 可以證明一個文法可以證明一個文法G的所有可歸前綴是一個的所有可歸前綴是一個 正規(guī)集，它可以由正規(guī)集，它可以由DFA加以識別。加以識別。 每個終態(tài)都 是可歸前綴 的識別態(tài)。 23 4 ab 467 8 baA 9101112 13 aAcd 141416171819 aAcBe 01 S *終結(jié)符和非終結(jié)符 都看成是有限自動

16、機的輸入符號。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院27 將以上有限自動機合并： 23 4 ab 467 8 baA 9101112 13 aAcd 141416171819 aAcBe 01 S * x 從初態(tài)到任一終 態(tài)形成的符號串 構(gòu)成了文法的可 歸前綴 o 可以指導(dǎo)可以指導(dǎo)移進移進-規(guī)約規(guī)約動作動作? machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院28 2 5 b b A cd B e 1 * 0 S a 3 4 8 6 7 9 識別上述文法所有可歸前綴的DFA 輸入串:abbcde machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院29 2.識別可歸前綴和活前綴(續(xù)) o 上述

17、有限自動機就是識別該文法所有活前綴上述有限自動機就是識別該文法所有活前綴 和可歸前綴的有限自動機。和可歸前綴的有限自動機。 n 中間狀態(tài)為活前綴識別態(tài)（移進）； n 所有終態(tài)都是可歸前綴的識別態(tài)，此時分 析棧中形成句柄（規(guī)約）； n 帶星號（*）的狀態(tài)為唯一的句子識別態(tài)， 這次歸約到開始符號； machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院30 3.分析表的構(gòu)造 n 分析表分析表由由動作表動作表和和狀態(tài)轉(zhuǎn)換表組成狀態(tài)轉(zhuǎn)換表組成： n 動作表(Action)以一個二維數(shù)組表示，列 代表識別活前綴的狀態(tài)，行代表當前的 輸入符號，數(shù)組元素Actioni，a表示所 執(zhí)行的分析動作，即：當前識別活前綴

18、的狀態(tài)為i，而輸入符號為a時所執(zhí)行的動 作。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院31 3.分析表的構(gòu)造(續(xù)) Action Action a ab bc cd de e $ $ 0 0S S 1 1 成功成功 2 2S S 3 3S SS S 4 4r rr rr rr rr r 4 4S S 6 6r rr rr rr rr r 7 7r rr rr rr rr r 8 8S S 9 9r rr rr rr rr r machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院32 o 共有共有4種動作：種動作： n 移進：輸入符號進符號棧； n 歸約：用相應(yīng)的產(chǎn)生式進行歸約； n 接受：當文

19、法符號歸約到只剩下開始符號， 且輸入串結(jié)束時(當前輸入為$)，分析成 功； n 報警：當狀態(tài)棧頂為某一狀態(tài)下，出現(xiàn)了 不該出現(xiàn)的文法符號時，報錯。 3.分析表的構(gòu)造(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院33 p 分析表分析表由由動作表動作表和和狀態(tài)轉(zhuǎn)換表組成狀態(tài)轉(zhuǎn)換表組成： n 狀態(tài)轉(zhuǎn)換表用一個二維數(shù)組表示，列代 表識別活前綴的狀態(tài)，行代表文法符號， 數(shù)組元素表示當前識別活前綴的狀態(tài)為i 面對文法符號為X時，應(yīng)轉(zhuǎn)去的新狀態(tài) Gotoi,X。 3.分析表的構(gòu)造(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院34 3.分析表的構(gòu)造(續(xù)) Goto Goto a ab bc c

20、d de e $ $ S S A A B B 0 02 2 1 1 1 1 2 25 5 3 3 3 36 64 4 4 47 7 5 5 8 8 6 6 7 7 8 89 9 9 9 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院35 ActionGoto ab$S 0S21 1acc 2S4 4r2r2r2r2 動作表和狀態(tài)轉(zhuǎn)換表的合并 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院36 LR分析算法的邏輯結(jié)構(gòu)： 總控程序 a1a2aiai+1an$ 動作表狀態(tài)轉(zhuǎn)換表 分析表 輸出 Xm . . . X1 $ 狀 態(tài) 棧 符號棧 m . . . 1 0 識別活前 綴的自動 機狀態(tài) mach

21、unyan西北工業(yè)大學(xué)軟件與微電子學(xué)院37 o 在總控程序的控制下，從左到右處理詞法分析輸入串，在總控程序的控制下，從左到右處理詞法分析輸入串， 根據(jù)分析棧和輸入符號的情況，查分析表確定分析動作；根據(jù)分析棧和輸入符號的情況，查分析表確定分析動作； n 分析棧包括文法符號棧Xi和相應(yīng)的狀態(tài)棧Si兩部分 (狀態(tài)是指識別活前綴的自動機狀態(tài)) 。 n 分析表是LR分析器的核心，它包括動作表(Action)和 狀態(tài)轉(zhuǎn)換表(Goto)兩部分; n 根據(jù)識別文法所有活前綴和可歸前綴的有限自動機， 可以構(gòu)造分析表來指導(dǎo)移進-規(guī)約動作； 4.2 LR 分析概覽(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)

22、院38 第4章 自下而上的語法分析 4.1 自下而上的語法分析 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 語法分析器自動生成工具YACC 作業(yè) o 1. 構(gòu)造識別活前綴的構(gòu)造識別活前綴的NFA o 2. 構(gòu)造識別活前綴的構(gòu)造識別活前綴的DFA o 3. LR(0)分析表的構(gòu)造分析表的構(gòu)造 o 4 . LR(0)分析算法分析算法 o 4. 項目的分類項目的分類 o 6. LR(0)文法的定義文法的定義 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院39 4.3 LR(0)分析

23、算法 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院40 4.3 LR(0)分析算法分析算法 o 為了由文法為了由文法G的產(chǎn)生式直接構(gòu)造識別活前綴的的產(chǎn)生式直接構(gòu)造識別活前綴的 DFA，首先給出項目的定義。，首先給出項目的定義。 o 定義：對于文法G，其產(chǎn)生式的右部添加一 個特殊符號“.”就構(gòu)成文法的一個LR(0)項 目，簡稱項目。 n 若A是產(chǎn)生式，其中和是任意符號串（包 括空串），那么A. 就是LR(0)項目。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院41 例對于文法：SS S( S ) S | 有以下LR(0)項目： S.S SS. S. S. ( S ) S S( .S ) S

24、S( S. )S S( S ) .S S( S )S. 每個項目中圓點的左部表示在分析過程中，要 用該產(chǎn)生式歸約時，句柄已識別的部分(進入符 號棧)，右部表示等待識別的部分。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院42 o NFA的構(gòu)造原則的構(gòu)造原則:為了確保有唯一的接受項目，首為了確保有唯一的接受項目，首 先拓廣文法先拓廣文法G為為G,引進一新的產(chǎn)生式引進一新的產(chǎn)生式S S ， S是新是新 增加的非終結(jié)符作為增加的非終結(jié)符作為G的開始符。的開始符。 n NFA的狀態(tài)集：每個項目對應(yīng)一個NFA狀態(tài)， 所有項目對應(yīng)的狀態(tài)的集合； n 輸入字符集合：包括終結(jié)符、非終結(jié)符和； n 初態(tài)：對于

25、文法GS的拓廣文法GS,有項 目S . S ,由于S僅在第一個產(chǎn)生式的左部 出現(xiàn)，規(guī)定它為初態(tài)； 終態(tài)：對于拓廣文法GS，有項目Uu. (即圓點在最后的項目)，作為NFA的終態(tài)； 1. 構(gòu)造識別活前綴的NFA machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院43 轉(zhuǎn)換函數(shù)f： 若文法中有項目i為：Xx1xi-1.xixn 項目j為：Xx1xi.xi+1xn 1) 則有轉(zhuǎn)換函數(shù)GO(i，xi)=j 2) 若xi為非終結(jié)符號，則還有轉(zhuǎn)換函數(shù)GO (i, )=k 項目k為：xi . 1. 構(gòu)造識別活前綴的NFA(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院44 S(.S )S S S(S .)

26、S S. S.(S)S 例如：項目 S( .S ) S 的轉(zhuǎn)換有： 1. 構(gòu)造識別活前綴的NFA(續(xù)) 考慮文法： SS S( S ) S | 對應(yīng)的LR(0)項目的NFA， 見下頁所示。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院45 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院46 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院47 例：對拓廣文法 (0) SS (1) SaAcBe (2) Ab (3) AAb (4) Bd 求出其對應(yīng)的LR(0)項目的NFA 1. 構(gòu)造識別活前綴的NFA(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院48 SaAc.Be c S .S B

27、SaAcB.e B.d S S S. S .aAcBe a S a .AcBe ASaA .cBe A.bA.Ab Ab . Bd .SaAcBe . b d e A AA.b b AAb . machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院49 上述文法的可歸前綴有：？ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院50 2. 構(gòu)造識別活前綴的DFA o 基于閉包函數(shù)基于閉包函數(shù)CLOSURE(I)以及轉(zhuǎn)移函數(shù)以及轉(zhuǎn)移函數(shù) GO(I，x)構(gòu)造識別活前綴的構(gòu)造識別活前綴的DFA; nCLOSURE(I)的定義 nGO(I，x)的定義 n構(gòu)造識別活前綴的DFA 注：由上述定義知，CLOSURE(I

28、)是一個LR(0)項 目集合。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院51 步驟1：令 CLOSURE(I)=I； 步驟2：若項目A.B CLOSURE(I), BVN ,則 CLOSURE(I) = CLOSURE(I) B.； 步驟3：重復(fù)步驟2直至CLOSURE(I) 不增加新的項 目為止。 n 拓廣文法G的一個LR(0)項目集合I的閉包函數(shù) CLOSURE(I)的定義如下： 2. 構(gòu)造識別活前綴的DFA(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院52 o I是一個項目集，是一個項目集， x VNVT，狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù) GO(I，x)的定義如下：的定義如下： n

29、 GO(I，x)= CLOSURE(J)，其中： o J是I識別輸入符號x后所到達的項目集， J= Ax. | A.x I 2. 構(gòu)造識別活前綴的DFA(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院53 2. 構(gòu)造識別活前綴的DFA(續(xù)) o基于閉包函數(shù)基于閉包函數(shù)CLOSURE(I)和轉(zhuǎn)移函數(shù)和轉(zhuǎn)移函數(shù)GO(I，x)構(gòu)構(gòu) 造識別文法活前綴的造識別文法活前綴的DFA的算法如下：的算法如下： n令項目集CLOSURE(S .S )為DFA的初態(tài)； n輸入字符集合：包括終結(jié)符、非終結(jié)符； n設(shè)I是DFA中一個已存在的狀態(tài)(項目集)，若存在 A.xI，則對xVNVT ， o 計算GO(I，x

30、)= CLOSURE(J)，將項目集 CLOSURE(J) 作為DFA的一個新狀態(tài)加入DFA的狀 態(tài)集； 1. 同時將轉(zhuǎn)移函數(shù)GO(I，x)= CLOSURE(J)作為DFA 的轉(zhuǎn)換函數(shù)。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院54 o重復(fù)重復(fù)2直至的直至的DFA的狀態(tài)集中不產(chǎn)生新的狀態(tài)的狀態(tài)集中不產(chǎn)生新的狀態(tài)(項項 目集目集)為止；為止； o含有項目含有項目Uu. 的項目集的項目集,作為作為DFA的終態(tài)。的終態(tài)。 2. 構(gòu)造識別活前綴的DFA(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院55 例：對拓廣文法 (0) SS (1) SaAcBe (2) Ab (3) AAb (

31、4) Bd 求出其對應(yīng)的LR(0)項目集合的DFA CLOSURE(S .S ) ? machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院56 S S .S S .aAcBe 0 S S . 1 a A S a .AcBe A .b A .Ab 2 S aA .cBe A A .b 3 b A b . 4 b c AAb . 6 S aAc.Be B.d 4 B d. 7 B SaAcB.e 8 e S aAcBe. 9 d machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院57 求文法:SS S(S) S | 對 應(yīng)的LR(0)項目 集合的DFA machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院58 3

32、. LR(0)分析表的構(gòu)造 設(shè)狀態(tài)i、j，若有GO(i，x)=j ，對于狀態(tài) i中的項目A.x, 若xVN,則置Gotoi，x=j; 則置Actioni，x=Sj;若xVT, 由識別活前綴的DFA構(gòu)造LR(0)分析表的方法： machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院59 (2) 對于終態(tài)對于終態(tài)i中的項目中的項目A. ，若，若A 是是G中中 第第k個產(chǎn)生式，則個產(chǎn)生式，則對所有輸入符號對所有輸入符號x VT(包括包括 $), 均置均置Actioni,x=rk ; (3)若終態(tài)若終態(tài)i中含中含項目項目SS. 則置則置Actioni,$=acc ($表示輸入串結(jié)束符表示輸入串結(jié)束符); (4

33、) 其它情況均置錯。其它情況均置錯。 3. LR(0)分析表的構(gòu)造(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院60 例1：文法A(A)| a 對應(yīng)的LR(0)項目集合的DFA machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院61 文法A(A)|a 對應(yīng)的LR(0)分析表 ActionGoto a（）$A 0 1 2 3 4 4 S2S31 acc r2r2r2r2 S2S3 S4 r1r1r1r1 4 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院62 4. LR(0)分析算法 (1) 將輸入串的左邊界($)進符號棧和初始狀態(tài)0進 狀態(tài)棧； (2) 根據(jù)狀態(tài)棧棧頂狀態(tài)i和當前輸入符號a

34、查Action 表進行如下工作： 移進:若Actioni，a=Sj ，當前輸入符號a進符號 棧，并將輸入符號所對應(yīng)的新的狀態(tài)j進狀態(tài)棧， 繼續(xù)處理下一個輸入符號； machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院63 歸約:若Actioni，a=rj ，按指定產(chǎn)生式進行歸約， 假設(shè)產(chǎn)生式右部的符號串長度為n，則 符號棧棧頂?shù)膎個符號為句柄，所以符號棧棧頂n個符號 出棧，同時，狀態(tài)棧棧頂?shù)膎個元素也出棧； 歸約后的文法符號A(非終結(jié)符)進符號棧； 假設(shè)當前符號棧棧頂為j，若Gotoj，A=k，則將文法符 號A所對應(yīng)的新狀態(tài)k進狀態(tài)棧。 4. LR(0)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)

35、軟件與微電子學(xué)院64 接受:若動作表中對應(yīng)“acc”，則分析成功； 出錯:若動作表中對應(yīng)空白，則報告錯誤信息。 (3) 重復(fù)以上(2)的工作直到接受或出錯為止。 考慮文法A(A)|a的輸入串(a) LR(0)分析算法對輸入串(a)的分析步驟如下： 4. LR(0)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院65 步驟 狀態(tài)棧S符號棧X動作輸入符號 10$S3(a)$ 203$(S3(a)$ 3033$(S2a)$ 40332$(ar2(Aa)$ 40334$(AS4)$ 603344$(A)r1(A(A)$ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院66 7034$(AS

36、4)$ 80344$(A)r1(A(A)$ 901$A接受$ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院67 4. 項目的分類 項目分類的原則是根據(jù)圓點所在位置和圓點之后是終 結(jié)符還是非終結(jié)符進行的。 移進項目：圓點之后為終結(jié)符的項目， A.a, ,V*, aVT,它對應(yīng)的狀態(tài)為移進狀態(tài)； 例如SaA.cBe 待約項目：圓點之后為非終結(jié)符的項目， A.B ， ,V*,BVN ,它對應(yīng)的狀態(tài)為待約 狀態(tài)；例如 SaAc.Be machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院68 歸約項目：圓點之后沒有符號(圓點在最后)的 項目，A. V*,它對應(yīng)的狀態(tài)為歸約狀態(tài)； 例如：SaAcBe. 接受項

37、目：對于拓廣文法GS,有項目SS.它 是一個特殊的歸約項目，稱它為接受項目，它 所對應(yīng)的狀態(tài)為接受狀態(tài)。 4. 項目的分類(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院69 6. LR(0)文法的定義 項目集的相容性：在一個項目集(對應(yīng)DFA的一個 狀態(tài))中，若能滿足下述條件，則稱該項目集是 相容的項目集。 (1)移進項目和歸約項目不并存，否則是移進-規(guī)約沖突； (2)多個歸約項目不并存，否則稱規(guī)約-規(guī)約沖突； 2）LR(0)文法：若一個文法G的任一項目集中的 所有項目都是相容的（即LR(0)分析表表項的 元素至多只有一個）， 則稱文法G為LR(0)文 法。 machunyan西北工業(yè)

38、大學(xué)軟件與微電子學(xué)院70 第4章 自下而上的語法分析 4.1 自下而上的語法分析 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.5 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 語法分析器自動生成工具YACC 作業(yè) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院71 4.5 SLR(1)分析算法 問題的提出： 通常的程序設(shè)計語言一般不能滿足LR(0) 文法的要求。 例如：文法：SS S(S)S| 對應(yīng)的 LR(0)項目集合的DFA如下圖： machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院72 machunyan西北工業(yè)大學(xué)軟件與

39、微電子學(xué)院73 若為上述文法構(gòu)造LR(0)分析表，則： 狀態(tài)狀態(tài) Action Goto （）$S 0S2 , r2r2r21 1acc 2S2 , r2r2r23 3S4 4S2 , r2r2r24 4r1r1r1 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院74 4.4 SLR(1)分析算法(續(xù)) o 從分析表可以發(fā)現(xiàn)：表中從分析表可以發(fā)現(xiàn)：表中Action0 ,(出現(xiàn)了出現(xiàn)了 多重定義的元素，即沖突。多重定義的元素，即沖突。 o 對于狀態(tài)對于狀態(tài)0，當輸入當輸入“（”時，既要進行歸時，既要進行歸 約又要進行移進，因而不能做唯一選擇，從約又要進行移進，因而不能做唯一選擇，從 而發(fā)生沖突。

40、而發(fā)生沖突。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院75 對LR(0)分析的構(gòu)造算法進行改造，以避免分 析表中分析動作的沖突。當分析表出現(xiàn)沖突動 作時，觀察下一個輸入符號是什么，從而確定 該采用什么動作。 問題的解決 o 先求先求Follow(S)= ),$，對于狀態(tài)對于狀態(tài)2 2，如果要做歸如果要做歸 約動作，這時約動作，這時S S之后的下一個輸入符號可以時之后的下一個輸入符號可以時 ）或或$ $。( (即文法中含有即文法中含有S S的句型中，的句型中，S S之后只之后只 能是能是) )或或$ $，而不能含有其他輸入符號，而不能含有其他輸入符號) ) o 對于移進項對于移進項S S.

41、(S)S,.(S)S,它所期待的移進符號為它所期待的移進符號為 ( (，而不是其它符號。，而不是其它符號。 o 所以可以這樣處理：當下一個輸入符號所以可以這樣處理：當下一個輸入符號( (時時 ，做移進動作，當下一個輸入符號，做移進動作，當下一個輸入符號) )和和$ $ 時做歸約動作。時做歸約動作。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院76 4.4 SLR(1)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院77 這樣，消除沖突的分析表為(SLR(1)分析表)： 狀態(tài)狀態(tài) Action Goto （）$S 0S2r2r21 1acc 2S2r2r23 3S4 4S2r2r

42、24 4r1r1r1 o 在在SLR(1)SLR(1)文法中，向右看一個符號，所以屬于文法中，向右看一個符號，所以屬于 LR(1)LR(1)方法。而它僅在發(fā)生沖突時才向右看一個方法。而它僅在發(fā)生沖突時才向右看一個 符號，為了與普通的符號，為了與普通的LR(1)LR(1)方法區(qū)別，將其稱為方法區(qū)別，將其稱為 簡單的簡單的LR(1)LR(1)方法方法- -SLR(1)SLR(1)方法。方法。 o SLR(1)SLR(1)文法與文法與LR(0)LR(0)文法識別其活前綴項目集合文法識別其活前綴項目集合 的的DFADFA是一樣的，是一樣的，區(qū)別在于它們構(gòu)造分析表的規(guī)區(qū)別在于它們構(gòu)造分析表的規(guī) 則不一樣

43、。則不一樣。 o SLR(1)SLR(1)分析與分析與LR(0)LR(0)分析的算法步驟一致分析的算法步驟一致。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院78 4.4 SLR(1)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院79 SLR(1)分析表的構(gòu)造 任意文法GS的SLR(1)分析表的構(gòu)造規(guī)則如下： 設(shè)狀態(tài)j是狀態(tài)i輸入符號x后到達的狀態(tài),即： GO(i,x)=j 對于狀態(tài)i中的項目A.x, 若xVN,則置Gotoi,x=j; 則置Actioni,x=Sj;若xVT, machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院80 3.若S.i,則置Actioni,$=acc(

44、S為開始符號)； 4.其他情況均置出錯。 對于給定的文法G,若按上述方法所構(gòu)造的分析表不 含多重定義的元素(無沖突動作)。則稱文法G為 SLR(1)文法。 2.對于狀態(tài)i中的歸約項目：A.i 若A為文法的 第j個產(chǎn)生式，則對于任意輸入符號a,aFollow(A),則 置Actioni,a=rj machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院81 En SLR(1)分析算法 考慮以下基本算術(shù)表達式的擴充文法： EE EE+n 識別其活前綴項目集合的DFA如下圖所示： machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院82 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院83 狀態(tài)狀態(tài) Action G

45、oto +n$E 0S21 1S3acc 2r2r2 3S4 4r1r1 構(gòu)造SLR(1)分析表如下： Follow(E)=$ Follow(E)=$,+ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院84 用SLR(1)分析算法對輸入串n+n+n的分析步驟： 步驟 狀態(tài)棧S符號棧X動作輸入符號 10$S2n+n+n$ 202$nr2(En)+n+n$ 301$ES3+n+n$ 4013$ E+S4n+n$ 40134$ E+nr1(EE+n)+n$ 601$ES3+n$ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院85 7013$E+S4n$ 80134$E+nr1(EE+n)$ 901$

46、E接受$ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院86 第4章 自下而上的語法分析 4.1 自下而上的語法分析 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.4 SLR(1) 分析 4.4 一般的LR(1) 4.6 LALR(1)分析 4.7 語法分析器自動生成工具YACC 作業(yè) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院87 4.5 LR（1）分析算法 o 問題的提出：問題的提出： 例如：有文法GS (0)SS (3)Saec (1)SaAd (4)Sbed (2)SbAc (4)Ae machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院88 Sb.Ac

47、Sb.ed A.e 3 S a b Sa.Ad Sa.ec A.e Ae SaA.dSae.c Ae. A e SbA.cSbe.d Ae. d cc d SaAd.Saec.SbAc.Sbed. S.S S.aAd S.bAc S.aec S.bed 0 2 4 8 9 10 11 4 67 S1: SS. 1 移進歸約沖突 Follow(A)=c,d First(d)=d相交 移進歸約沖突 Follow(A)=c,d First(c)=c相交 結(jié)論：沖突不能用SLR(1) 方法解決！ 4.5 LR（1）分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院89 4.5 LR（1）分

48、析算法(續(xù)) o LR(1)項目：項目：在在LR(0)項目中放置一個向右項目中放置一個向右 搜索符號搜索符號a，成為成為LR(1)項目：項目：A. ，a o LR(1)分析過程中的每個狀態(tài)，就是包含若分析過程中的每個狀態(tài)，就是包含若 干干LR(1)項目的一個項目的一個LR(1)項目集；項目集； o 構(gòu)造構(gòu)造 LR(1)項目集合的項目集合的DFA的算法的算法與與LR(0) 類似，也需求兩個函數(shù)類似，也需求兩個函數(shù)CLOSURE和和GO。 步驟3：重復(fù)步驟2直至CLOSURE(I) 不增加新項目 為止。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院90 步驟1：CLOSURE(I)=I； 步驟2

49、：若存在A.B，a CLOSURE(I), BVN , 則CLOSURE(I) = CLOSURE(I) B., b ， 其中 bFirst(a) 設(shè)I是拓廣文法G的一個LR(1)項目集，定義和構(gòu)造I的 閉包函數(shù)CLOSURE(I)如下： 4.5 LR(1)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院91 I是一個LR(1)項目集， xVNVT，狀態(tài)轉(zhuǎn)移函數(shù) GO(I,x)定義如下： GO(I，x)= CLOSURE(J) 其中J是I識別輸入符號x后所到達的項目集，后跟符 號不變。 J=Ax.，a | A.x, a I 基于閉包函數(shù)和轉(zhuǎn)移函數(shù)構(gòu)造文法G的LR(1)項目集 的識

50、別文法活前綴的DFA，算法如下： 4.4 LR(1)分析算法(續(xù)) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院92 令DFA的初態(tài)為項目集CLOSURE(S .S, $ ) 設(shè)I是一個DFA中的狀態(tài)(已存在的項目集)，對 xVNVT ， 產(chǎn)生新的項目集CLOSURE(J) 作為DFA的一個新狀態(tài)加 入DFA的狀態(tài)集中： GO(I,x)= CLOSURE(J) 同時將轉(zhuǎn)移函數(shù)GO(I,x)= CLOSURE(J)作為DFA的轉(zhuǎn)換 函數(shù)。 重復(fù)2)直至DFA中不產(chǎn)生新的(項目集)為止； 含有項目Uu. (即圓點在最后的項目)的項目集， 作為DFA的終態(tài)； 4.5 LR(1)分析算法(續(xù)) ma

51、chunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院93 構(gòu)造文法A(A)|a 的 LR(1)項目集合的DFA ; 首先擴展該文法： AA A(A) A a CLOSURE( A . A，$ ) ? machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院94 A.A , $ A.(A), $ A.a, $ 0 AA. , $ 1 A Aa. , $ 3 a A(.A) , $ A.(A), ) A.a , ) 2 ( A(A.), $ 4 A ( A(.A) , ) A.(A), ) A.a , ) 4 a Aa. , ) 6 a ) A(A)., $ 7 ( A(A.), ) 8 A ) A(A)., ) 9

52、 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院95 LR(1)分析表構(gòu)造規(guī)則： 對于文法GS，其LR(1)分析表的構(gòu)造規(guī)則為： 1. 對于A.x, a狀態(tài)i,且GO(i，x)=j. 若xVT,則置Actioni，x=Sj 若xVN ,則置Gotoi，x=j 2. 對于A. , a狀態(tài)i，若A是文法的第j個產(chǎn)生 式，則置 Actioni，a=rj 3.對于S.，$狀態(tài)i，則actioni，$=acc 4.其它情況置錯。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院96 根據(jù)文法A(A)|a 的 LR(1)項目集合的DFA ， 構(gòu)造其對應(yīng)的LR(1)分析表: 給產(chǎn)生式編號： (0) AA (1

53、) A(A) (2) A a machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院97 A.A , $ A.(A), $ A.a, $ 0 AA. , $ 1 A Aa. , $ 3 a A(.A) , $ A.(A), ) A.a , ) 2 ( A(A.), $ 4 A ( A(.A) , ) A.(A), ) A.a , ) 4 aAa. , ) 6 a ) A(A)., $ 7 ( A(A.), ) 8 A ) A(A)., ) 9 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院98 狀態(tài)狀態(tài)ActionGoto ()a$A 0S2S31 1acc 2S4S64 3r2 4S7 4S4S68

54、 6r2 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院99 用LR(1)分析算法對輸入串(a)的分析步驟： 步驟 狀態(tài)棧S符號棧X動作輸入符號 10$S2(a)$ 202$(S6a)$ 3026$(ar2(Aa)$ 4024$(AS7)$ 40247$(A)r1(A(A)$ 601$Aacc$ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院100 (0)EE (1)E(L) (2)E a (3)LL,E (4)LE 構(gòu)造下面文法的LR(1)分析表： 首先構(gòu)造其LR(1)項目的DFA machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院101 (0)EE (1)E(L) (2)E a (3)LL,E

55、 (4)LE E .E , $ E .(L) , $ E.a , $ 0 E E E.,$ 1 ( 2 E a. , $ 3 a L E ( a E (.L) , $ machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院102 E (.L) , $ L .E ，) L .L,E , ) E .(L) , ) E. a , ) L .L,E ，, L .E ，, E .(L) ， , E. a ，, 2 (0)EE (1)E(L) (2)E a (3)LL,E (4)LE E (.L) ， $ L .L,E ， )/, L .E ，)/, E .(L)， )/, E. a ，)/, 2 machuny

56、an西北工業(yè)大學(xué)軟件與微電子學(xué)院103 (0)EE (1)E(L) (2)E a (3)LL,E (4)LE E .E , $ E .(L) , $ E.a , $ 0 EE E. , $ 1 ( E (.L) , $ L .L,E , )/, L .E ,)/, E .(L) , )/, E. a , )/, 2 E a . , $ 3 a L E (L.) , $ L L.,E , )/, 4 E L E.,)/, 4 ( E (.L) , )/, L .L,E , )/, L .E ,)/, E .(L) , )/, E. a , )/, 6 a E a . , )/, 7 ) E (L

57、)., $ 8 , L L, .E , )/, E .(L) , )/, E. a , )/, 9 L E (L.) , )/, L L.,E , )/, 10 E L L, E . , )/, 11 E (L)., )/, 12 ) E( a ( a , machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院104 狀態(tài)狀態(tài) ActionGoto a（），$EL 0S3S21 1acc 2S7S644 3r2 4S8S9 4r4r4 6S7S6410 7r2r2 8r1 9S7S6 11 10S12S9 11r3r3 12r1r1 (0)EE (1)E(L) (2)E a (3)LL,E (4)LE

58、 基于DFA構(gòu)造的LR(1)分析表 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院105 第4章 自下而上的語法分析 4.1 自下而上的語法分析 4.2 LR分析概覽 4.3 LR(0)項目的有窮自動機與LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 語法分析器自動生成工具YACC 作業(yè) machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院106 4.6 LALR（1）分析算法 o LR(1)分析比分析比SLR(1)分析的能力有明顯的提高，但是分析的能力有明顯的提高，但是 LR(1)也有缺點：分析表狀態(tài)數(shù)過大，使分析的效率降也有缺點：分析表狀

59、態(tài)數(shù)過大，使分析的效率降 低。為解決二者之間的能力與效率之間的矛盾，目前最低。為解決二者之間的能力與效率之間的矛盾，目前最 流行的流行的LALR(1)分析是最佳方案。分析是最佳方案。 n LALR(1)分析(Lookahead-LR)的基本思想是將LR(1) 項目集中的同心集合并，將其壓縮為較小的DFA， 若壓縮過程并未帶來新的沖突，則分析表可大大地 簡化(狀態(tài)數(shù)與SLR(1)，LR(0)的DFA相同)。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院107 4.6 LALR（1）分析算法(續(xù)) o LALR(1)項目集（狀態(tài)）通過同心集合并構(gòu)造項目集（狀態(tài)）通過同心集合并構(gòu)造: n 同心集：

60、LR(1)的兩個項目集的LR(0)項目全部相同， 則稱兩個LR(1)項目集具有相同的心，具有相同心的 項目集稱為同心集。 n 同心集合并： o 相同的心(LR(0)項目)不變； o 合并后項目集的搜索符等于合并前LR(1)項目搜 索符的并集。 machunyan西北工業(yè)大學(xué)軟件與微電子學(xué)院108 A.A , $ A.(A), $ A.a, $ 0 AA. , $ 1 A Aa. , $ 3 a A(.A) , $ A.(A), ) A.a , ) 2 ( A(A.), $ 4 A ( A(.A) , ) A.(A), ) A.a , ) 4 aAa. , ) 6 a ) A(A)., $ 7