第4章 語法分析和語法分析程序

1、編編 譯譯 原原 理理第四章 語法分析和語法分析程序本章內(nèi)容本章內(nèi)容v自頂向下分析和自底向上分析自頂向下分析和自底向上分析v圍繞分析器的自動(dòng)生成展開圍繞分析器的自動(dòng)生成展開難難 重重 點(diǎn)點(diǎn)語法分析是編譯程序的核心部分。語法分析是編譯程序的核心部分。 語法分析的作用是識別由詞法分析給出的單語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子（程詞符號序列是否是給定文法的正確句子（程序）序） 目前語法分析常用的方法有自頂向下（自上目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩而下）分析和自底向上（自下而上）分析兩大類。大類。v自頂向下分析法：自頂向

2、下分析法：從文法的開始符號出發(fā)，反復(fù)使用文法從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。導(dǎo)。v自底向上分析法：自底向上分析法：從輸入符號串開始，逐步進(jìn)行歸約，直至從輸入符號串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號。歸約到文法的開始符號。自底向上的語法分析自底向上的語法分析v例：文法例：文法G： S cAd A ab A a識別輸入串識別輸入串w=cabd是否是該文法的句子是否是該文法的句子 S AA c a b d c a b d c a b dv關(guān)?。壕浔拇_定關(guān)?。壕浔拇_定自頂向下分析的語法分析 例：例： 文法文法S a

3、Cb C cd | c 為輸入串為輸入串w = acb建立分析樹建立分析樹SSSaCbaaCCbbcdc試探試探的過程的過程v問題：會(huì)產(chǎn)生回溯問題：會(huì)產(chǎn)生回溯 導(dǎo)致效率低導(dǎo)致效率低自自頂向下分析法的另一問題下分析法的另一問題 若有文法若有文法G6S: (1) SSa (2) Sb推導(dǎo)推導(dǎo)baa#v問題：左問題：左遞歸遞歸可可能導(dǎo)致死能導(dǎo)致死循環(huán)循環(huán)SbSSaSSabSSaSaSSaSab自自頂向下分析法需要解決的問題 左遞歸左遞歸 對文法進(jìn)行改造對文法進(jìn)行改造 回溯回溯 如何唯一地確定所采用的產(chǎn)生式？如何唯一地確定所采用的產(chǎn)生式？ LL(1)文法文法 當(dāng)拒絕當(dāng)拒絕w時(shí)時(shí),只能知道只能知道w不是

4、句子不是句子,不知出何錯(cuò)不知出何錯(cuò)及出在何處及出在何處v本節(jié)將主要介紹確定的自頂向下分析思想和本節(jié)將主要介紹確定的自頂向下分析思想和對文法的要求。確定的自頂向下分析要求文對文法的要求。確定的自頂向下分析要求文法滿足法滿足LL(1)文法。文法。本節(jié)主要介紹內(nèi)容為：本節(jié)主要介紹內(nèi)容為： LL(1) 文法的定義和判別文法的定義和判別 非非LL(1)文法的等價(jià)變換文法的等價(jià)變換 確定的自頂向下分析方法確定的自頂向下分析方法 遞歸子程序法遞歸子程序法 預(yù)測分析方法預(yù)測分析方法4.1 自頂向下的語法分析自頂向下的語法分析 消除文法的左遞歸消除文法的左遞歸 帶回溯的遞歸子程序帶回溯的遞歸子程序 回溯的消除及

5、回溯的消除及LL（1）文法）文法4.1.1 消除文法的左遞歸消除文法的左遞歸 例：例：AA | A的解是：的解是： * 引入新的非終結(jié)符引入新的非終結(jié)符A,令其產(chǎn)生令其產(chǎn)生 *,則有則有: A AA A| 4.1.2 帶回溯的遞歸子程序帶回溯的遞歸子程序 對于文法的每個(gè)非終結(jié)符，根據(jù)其各候選式的結(jié)構(gòu)對于文法的每個(gè)非終結(jié)符，根據(jù)其各候選式的結(jié)構(gòu),為其建立一個(gè)遞歸的子程序?yàn)槠浣⒁粋€(gè)遞歸的子程序(函數(shù)函數(shù))，用于識別該非，用于識別該非終結(jié)符所表示的語法范疇終結(jié)符所表示的語法范疇 例如例如,產(chǎn)生式產(chǎn)生式E+TE ，相應(yīng)的子程序相應(yīng)的子程序(函數(shù)函數(shù))為為expr_prime( )expr_prime

6、( ) if(match(PLUS) if(match(PLUS)advance( );advance( );term( );term( );expr_prime( );expr_prime( ); 4.1.3 回溯的消除及回溯的消除及LL（1）文法）文法 基本原理基本原理 First集及集及Follow集的構(gòu)造集的構(gòu)造 分析器的構(gòu)造分析器的構(gòu)造 例：例： ETE E ATE| TFT T MFT| F(E)|i A+|- M* | / (4.1) 對對i+ii進(jìn)行預(yù)測分析的過程進(jìn)行預(yù)測分析的過程4.1.4 某些非某些非LL(1)文法的改造文法的改造 方法：方法： 消除左遞歸消除左遞歸 反復(fù)提

7、取左因子反復(fù)提取左因子 例：例： EE+T | TT(E) | a(E) | a 經(jīng)改造后可得文法經(jīng)改造后可得文法： ETE E+TE| TaT | (E)T (E) | 這是一個(gè)這是一個(gè)LL(1)文法文法關(guān)于關(guān)于LL(1)的一些結(jié)論的一些結(jié)論 能由能由LL(1)文法產(chǎn)生的語言稱為文法產(chǎn)生的語言稱為LL(1)語言。它們已被證明具語言。它們已被證明具有許多重要特性，主要有：有許多重要特性，主要有： (1) 任何LL(1)文法都是無二義性的； (2) 左遞歸文法是非LL(1)的； (3) 存在一種算法,它能判定任意文法是否為LL(1)的； (4) 存在一種算法,它能判定任意兩個(gè)LL(1)文法是否等

8、價(jià)； (5) CFL是否是LL(1)語言是不可判定的； (6) 非LL(1)語言是存在的。 若在分析過程中，每步向前掃描若在分析過程中，每步向前掃描k個(gè)符號來確定選用的產(chǎn)生個(gè)符號來確定選用的產(chǎn)生式，此分析方法稱為是式，此分析方法稱為是LL(k)分析分析。此法極少用此法極少用，故從略故從略。習(xí)題習(xí)題判斷下列文法是否是判斷下列文法是否是LL(1)文法，如果是，請文法，如果是，請寫出寫出LL(1)分析表；如果不是，請改造成分析表；如果不是，請改造成LL(1)文法文法。S aFA | +aFAA +aFA |+B| F *aBB F | 4.2 自底向上的語法分析自底向上的語法分析 優(yōu)先分析法及優(yōu)先分

9、析法及LR分析法分析法 問題：問題： 如何確定句型的句柄如何確定句型的句柄 如何正確地選擇產(chǎn)生式進(jìn)行歸約如何正確地選擇產(chǎn)生式進(jìn)行歸約 建立語法樹建立語法樹4.2.1 優(yōu)先文法優(yōu)先文法 簡介簡介4.2.2 LR分析法分析法: 自左至右掃描的自底向上的分析自左至右掃描的自底向上的分析 LR分析對文法要求很少分析對文法要求很少,效率極高效率極高,且能及時(shí)且能及時(shí)發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤,是目前最廣泛使用的方法是目前最廣泛使用的方法;一般用一般用CFG描述的語言均可用描述的語言均可用LR分析法 先介紹先介紹LR分析器的邏輯結(jié)構(gòu)及工作原理分析器的邏輯結(jié)構(gòu)及工作原理,再再分別介紹幾種分別介紹幾種LR分析器分析器(

10、即即LR(0),SLR(1)和和LR(1)的構(gòu)造的構(gòu)造（一）（一）LR分析器的邏輯結(jié)構(gòu)及工作原理分析器的邏輯結(jié)構(gòu)及工作原理 LR分析器分析器=輸入符號串輸入符號串+分析棧分析棧+總控程序總控程序+分析表分析表 例：文法例：文法GL: 1. LE,L 2. LE3. Ea4. Eb 分析表分析表狀態(tài)狀態(tài)ACTIONGOTOab，#LE0s3s4 121 acc 2 s5r2 3 r3r3 4 r4r4 5s3s4 626 r1 v例：對符號串例：對符號串“a,b,a”的分析過的分析過程程v四個(gè)四個(gè)分析動(dòng)作分析動(dòng)作：移進(jìn)、移進(jìn)、歸約、接受、報(bào)錯(cuò)歸約、接受、報(bào)錯(cuò)對符號串對符號串“a,b,a”的分析過

11、程的分析過程步驟步驟狀態(tài)狀態(tài)棧中符號棧中符號余留符號余留符號分析動(dòng)作分析動(dòng)作下一狀態(tài)下一狀態(tài)10#a,b,a#s33203#a,b,a#r3GOTO0,E=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r4GOTO5,E=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO5,E=29025252#E,E,E#r2GOTO5,L=610025256#E,E,L#r1GOTO5,L=6110256#E,L#r1GOTO0,L=11201#E# （二）（二）LR(0)分析表的構(gòu)造分析表的構(gòu)造 一些術(shù)語一些術(shù)語 規(guī)

12、范句型的活前綴規(guī)范句型的活前綴 將棧內(nèi)符號與未掃描的輸入串拼接起來將棧內(nèi)符號與未掃描的輸入串拼接起來,可得一可得一規(guī)范規(guī)范句型句型.即棧內(nèi)符號串總是即棧內(nèi)符號串總是規(guī)范句型的前綴規(guī)范句型的前綴,且且不含句柄不含句柄右側(cè)的符號右側(cè)的符號. 把具有上述性質(zhì)的符號串稱為把具有上述性質(zhì)的符號串稱為 LR(0)項(xiàng)目（看詳細(xì)內(nèi)容）項(xiàng)目（看詳細(xì)內(nèi)容）LR(0)項(xiàng)目項(xiàng)目 活前綴：活前綴： 包含全部句柄，則：進(jìn)行歸約包含全部句柄，則：進(jìn)行歸約: A, 記為記為A ; 句柄中，則：句柄中，則：應(yīng)移進(jìn)應(yīng)移進(jìn)(句柄的后半部分句柄的后半部分), A1 2 不含句柄，則：不含句柄，則：期望移進(jìn)一產(chǎn)生式的右部期望移進(jìn)一產(chǎn)生

13、式的右部: A 我們把右部添加了一個(gè)我們把右部添加了一個(gè)“ ”的產(chǎn)生式的產(chǎn)生式,稱為稱為 LR(0)項(xiàng)目：項(xiàng)目： 歸約項(xiàng)目：歸約項(xiàng)目： A 接受項(xiàng)目：接受項(xiàng)目： SS 移進(jìn)項(xiàng)目：移進(jìn)項(xiàng)目： A X , ( X VT, 可以是空串可以是空串) 待約項(xiàng)目：待約項(xiàng)目： A X , ( X VN, 可以是空串可以是空串)識別所有規(guī)范句型全部活前綴的識別所有規(guī)范句型全部活前綴的DFA 例：文法例：文法GS： SA|B AaAb|c, BaBb|d LR(0)分析表的構(gòu)造分析表的構(gòu)造I0:SSSASBAaAbAcBaBbBdI1: SSSI2: SAAI3: SBBI4:AaAbAaAbAcBaBbBaB

14、bBdaI5: AcccI6: AdddaI7: AaAbI9: BaBbI8: AaAbI10: BaBbBAbb識別識別全部活前綴的全部活前綴的GS的的LR(0)分析表分析表 ACTIONGOTOabcd#SAB0s4 s5s6 1231 acc 2r1r1r1r1r1 3r2r2r2r2r2 4s4 s5s6 795r4r4r4r4r4 6r6r6r6r6r6 7 s8 8r3r3r3r3r3 9 s10 10r5r5r5r5r5 習(xí)題習(xí)題 文法文法GB是否是是否是LR(0)文法？如果是，請畫文法？如果是，請畫出出LR(0)分析表；如果不是，請說明原理：分析表；如果不是，請說明原理： B

15、bD;SeDD;d|d Ss;S|sSLR(1)分析表的構(gòu)造分析表的構(gòu)造習(xí)題習(xí)題 文法文法GS是否是是否是LR(0)文法？如果是，請畫文法？如果是，請畫出出LR(0)分析表；如果不是，請說明原理：分析表；如果不是，請說明原理： SCbBA AAab|ab BC|Db Ca Da LR(1)分析表的構(gòu)造分析表的構(gòu)造I0:S S, #SCbBA, #C a, bI1: S S , #SI3: Ca , baI2: S CbBA, #CI4:SCbBA, #BC, aB Db, aC a, aD a, bbI5:SCbBA, #AAab, #/aA ab, #/aI6: BC , aBCI8: Ca , aD a , baI7: BD b, aI9: BDb ,