編譯原理課件語(yǔ)法分析總結(jié)

1、確定的自上而下分析法 自下而上分析法 遞歸下降分析法預(yù)測(cè)分析法 本章介紹了四種典型的語(yǔ)法分析方法算符優(yōu)先分析法LR分析法 LR(0)分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法 確定的自上而下分析法要求描述 語(yǔ)言的文法是 LL(1)文法。 1. LL(1)文法的判別方法。 (1) 求文法每個(gè)產(chǎn)生式右部符號(hào)串的 FIRST集。(2)求文法各個(gè)非終結(jié)符的FOLLOW集。一.確定的自上而下分析法(3)求文法每個(gè)產(chǎn)生式的SELECT集。(4)求相同左部產(chǎn)生式的SELECT交集。對(duì)文法G的每一個(gè)非終結(jié)符A的產(chǎn)生式SELECT(A i)SELECT(A j)= (ij)則文法G是一個(gè)

2、LL(1)文法A 1 | 2 | n下面條件成立:2. LL(1)文法是無(wú)左遞歸、無(wú)二義性文 法。3. 將非LL(1)文法改寫為L(zhǎng)L(1)文法的方 法。(1) 消除文法直接左遞歸PP | 改寫為 PP , P P | 或 P(2) 提取公共左因子若 A 1 | 2 | | n 提取公共左因子將文法改寫成: A AA 1| 2| | n4.根據(jù)文法規(guī)則構(gòu)造遞歸下降分析程序 和預(yù)測(cè)分析表的方法5. 注意LL(1)分析法與LR分析法的區(qū)別LL(1)分析法(預(yù)測(cè)分析法)是自上而下的語(yǔ)法分析法,要求文法為L(zhǎng)L(1)文法LR分析法是自下而上的語(yǔ)法分析法, 只要文法是上下文無(wú)關(guān)文法例1 設(shè)有文法GE：為消除

3、文法直接左遞規(guī),請(qǐng)改寫文法,改 寫后的文法為:E E+T | ET | TT T*F | T/F | FF (E) | id T +T | T E E E+T | ET | TT T*F | T/F | FF (E) | id F *F | /F T (E) | id F 例2 設(shè)有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 計(jì)算文法GS每個(gè)非終結(jié)符的FIRST集 和FOLLOW集 。2. 判斷文法GS 是否LL(1)文法。 對(duì)每一文法符號(hào)XV, 求FIRST(X)的規(guī)則: FIRST() = a | a且 aVT *,則規(guī)定 FIRST()若 *1.

4、 若 XVT , 則FIRST(X) =X2. 若 XVN 且有 X a, 則把 a 加入 FIRST(X)中 ,若 X , 則把 加入FIRST(X)中 3. 若 XY, YVN ,則把 FIRST(Y)中所有 非 元素加入FIRST(X)中 FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) =FIRST(S)FIRST(cD)e= a,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 問(wèn): 能否 因?yàn)閺?A */ , 所以 FIRST(A) FIRST(B)=FIRST(S)FIRST

5、(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, FOLLOW(A) = a | S Aa 且aVT *若有S A ,*則規(guī)定 $FOLLOW(A)。 求FOLLOW(A)的規(guī)則:1. 對(duì)文法的開(kāi)始符號(hào)S , 令$FOLLOW(S)2.若 AB是一條規(guī)則, 則將FIRST() 加到FOLLOW(B)中3.若 AB是一條規(guī)則, 或 AB是一條規(guī)則而 , 則把FOLLOW(A)加到FOLLOW(B)中* FOLLOW(S)=$,a,b,c,d,eFOLLOW(A)=b,cFOLLOW(B)=a,dFOLLOW(D)=a,b,c,d,eSaAbDe | dABSD | e

6、BSAc | cD | DSe | FIRST(D)= a, d, FIRST(S)= a,d FIRST(A)= a,d,c,e 根據(jù)LL(1)文法的定義有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=SaAbDe | dABSD | eBSAc | cD | DSe | SELECT(BSAc)SELECT(BcD)=FIRST(SAc)FIRST(cD)=SELECT(BSAc)SELECT(B)=FIRST(SAc) , a, d FOLLOW(B)=a,

7、d所以該文法不是LL(1)文法(二) LR分析法大多數(shù)用上下文無(wú)關(guān)文法描述的語(yǔ)言都可以用相應(yīng)的LR分析器予以識(shí)別。1. LR分析法是一種規(guī)范歸約分析法，2. 從給定的上下文無(wú)關(guān)文法構(gòu)造LR分析表的方法是： 對(duì)LR(1)或 LALR(1)分析表，構(gòu)造 LR(1)項(xiàng)目集規(guī)范族。(1)對(duì)LR(0)或 SLR(1)分析表，構(gòu)造 LR(0)項(xiàng)目集規(guī)范族;(2)構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA。 (3)將DFA轉(zhuǎn)換成相應(yīng)的LR分析表。 注意文法一定要拓廣注意文法一定要拓廣。 四種分析表的構(gòu)造基本相同，僅對(duì)含僅對(duì)含歸約項(xiàng)目的項(xiàng)目集構(gòu)造分析表元素不同歸約項(xiàng)目的項(xiàng)目集構(gòu)造分析表元素不同。 3. 四種LR文法的

8、判別方法 (1)任何的二義性文法都不是LR類文法。 SLR(1)文法是文法是LR(0)項(xiàng)目集中所有項(xiàng)目集中所有含沖突的項(xiàng)目集都能用含沖突的項(xiàng)目集都能用SLR規(guī)則解決沖規(guī)則解決沖突突。 (或SLR(1)分析表中不含多重定義) (2)根據(jù)項(xiàng)目集中是否含沖突項(xiàng)目項(xiàng)目集中是否含沖突項(xiàng)目或相應(yīng)分析表中是否含多重定義元素進(jìn)行判斷： LR(0)文法是所有的所有的LR(0)項(xiàng)目集中項(xiàng)目集中沒(méi)有移進(jìn)一歸約沖突或歸約一歸約沖突沒(méi)有移進(jìn)一歸約沖突或歸約一歸約沖突。(或LR(0)分析表中不含多重定義) SLR規(guī)則：規(guī)則： I: A .b B 1 1. B2 2. b FOLLOW(B1)= FOLLOW(B1)FOL

9、LOW(B2)= b FOLLOW(B2)= a b 移進(jìn)移進(jìn) a FOLLOW(B1) 用用B 1 1 歸約歸約 a FOLLOW(B2) 用用B2 2 歸約歸約 LR(1)項(xiàng)目集中無(wú)移進(jìn)一歸約沖突或歸約一歸約沖突。（或LR(1)分析表中不含多重定義） LALR(1)項(xiàng)目集中無(wú)歸約一歸約沖突。(或LALR(1) 分析表中不含多重定義）4.四種LR類文法之間的關(guān)系注意搜索符只對(duì)歸約項(xiàng)目起作用。注意搜索符只對(duì)歸約項(xiàng)目起作用。 一個(gè)文法是一個(gè)文法是LR(0)文法一定也是文法一定也是SLR(1)文法文法，也是LR(1)、LALR(1)文法，反之則不一定成立。即LR(0)SLR(1)LALR(1)LR

10、(1)例1 考慮文法SAS | bASA | a(1) 構(gòu)造識(shí)別文法活前綴的DFA。(3) 該文法是SLR(1)的嗎？若是，構(gòu)造它 的SLR(1)分析表。(2) 該文法是LR(0)文法嗎？請(qǐng)說(shuō)明理由。(4) 該文法是LR(1)或LALR(1)文法嗎？請(qǐng) 說(shuō)明理由。解：首先將文法拓廣，并對(duì)規(guī)則進(jìn)行編號(hào) 0. S S1. S AS2. S b3. A SA4. A a(1) 識(shí)別文法活前綴的DFA如下圖所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:S ASS bA SAA aA SAS ASI5:I3: S

11、bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaA識(shí)別文法GS活前綴DFA(1) 識(shí)別文法活前綴的DFA如下圖所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:A SAS bA SAA aS ASI7:S ASS bA SAA aA SAS ASI5:I3: S bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaASSbASa識(shí)別文法GS活前綴DFA(2) 由上圖不難看出，項(xiàng)目集I1, I5, I6

12、中存在著移進(jìn)歸約沖突，所以該文法不是LR(0)文法。 (3) 由于對(duì)該文法句子abab對(duì)應(yīng)下面兩棵不同的語(yǔ)法樹(shù)：(見(jiàn)下圖) SSAaSASAbabSSAaSASAbab 所以該文法為二義性文法，任何二義性所以該文法為二義性文法，任何二義性文法絕不是文法絕不是SLR(1)文法，也不是文法，也不是LALR(1)或或LR(1)文法。文法。 0. SS1. S AS2. S b3. A SA4. A a 例2 設(shè)有文法GS:S (S) | 試判斷該文法是否SLR(1)文法，若不是，請(qǐng)說(shuō)明理由；若是，請(qǐng)構(gòu)造SLR(1)分析表。 解：首先將文法拓廣，并給出每條規(guī)則編號(hào) 0. SS1. S (S)2. S

13、I0:SSS (S)S I3: S (S) 構(gòu)造該文法的LR(0)項(xiàng)目集族和轉(zhuǎn)換函數(shù)如下圖所示。 該文法不是LR(0)文法。因?yàn)镮0，I2中含有移進(jìn)歸約的沖突。 I1: SS.I2:S (S)S (S)S I4: S (S)S(S()0. S S1. S (S)2. S 見(jiàn)表但是I0，I2中的移進(jìn)歸約的沖突可以用SLR(1)方法解決：FOLLOW(S)=), $(=所以該文法是SLR(1)文法。其SLR(1)分析表如下表：ACTIONGOTO( ) $SO1234S2 r2 r2acc1S2 r2 r23S4r1 r1文法GS的SLR(1)分析表0. S S1. S (S)2. S 見(jiàn)圖例3

14、設(shè)有文法GS:試證明該文法是SLR(1)文法，但不是LR(0)文法。解：首先將文法拓廣，并對(duì)規(guī)則進(jìn)行編號(hào) 直接構(gòu)造LR(0)項(xiàng)目集如下： S aSb | aSd | 0. S S1. S aSb2. S aSd3. S I0:S SS aSbS aSdS I1:SSI2:S aSbS aSdS aSbS aSdS I3:S aSbS aSdI4:S aSbI5:S aSd0. S S 2. S aSb1. S aSd 3. S 檢查每個(gè)項(xiàng)目集可知，項(xiàng)目集I0和I2中有移進(jìn)一歸約沖突，因此該文法不是LR(0)文法。 又因?yàn)?所以項(xiàng)目集I0和I2中移進(jìn)一歸約沖突可以用SLR(1)方法解決。因此該文

15、法是SLR(1)文法，但不是LR(0)文法。 FOLLOW(S)=b,d,$a= 例4 設(shè)有文法GS:2.試判斷該文法是否SLR(1)文法, 若不是, 請(qǐng)說(shuō)明理由；若是，請(qǐng)構(gòu)造出SLR(1)分析表, 并給出符號(hào)串( )$的分析過(guò)程。1.構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA( LR(0)項(xiàng)目集族和GO函數(shù) )。S S(S) | 3. 試判斷該文法是否LR(1)文法，若不是，請(qǐng)說(shuō)明理由；若是，請(qǐng)構(gòu)造LR(1)分析表。4. 試判斷該文法是否LALR(1)文法，請(qǐng)說(shuō)明理由。分析 首先將文法拓廣，并對(duì)規(guī)則編號(hào):0. SS1. S S(S) 2. S 構(gòu)造LR(0)項(xiàng)目集規(guī)范族和轉(zhuǎn)換函數(shù)如下圖所示:S S(

16、S.)S S.(S)I0:SSS S(S)S I1: SS.I2:I4: S S(S)S(S()0. SS1. S S(S) 2. S S S.(S)S S(S)S S S(.S)I3:S S(S)S S(S)I0:SSS S(S)S I1: SSI2:I4: S S(S)S(S()0. SS1. S S(S) 2. S S S(S)S S(S)S S S(S)I3:I1中的移進(jìn)歸約的沖突可以用SLR(1)方法解決：FOLLOW(S)=$(=所以該文法是SLR(1)文法。其SLR(1)分析表如下表：ACTIONGOTO( ) $SO1234r2 r2 r2acc1r2 r2 r23S4r1 r

17、1 r1 S2S2FOLLOW(S)= $, (, ) 符號(hào)串( )$的分析過(guò)程如下：501232$S(S()$用第2條規(guī)則S 歸約40123$S(S( )$S23012$S( )$用第2條規(guī)則S 歸約201$S( )$S2步驟 棧中狀態(tài) 棧中符號(hào) 輸入串分析動(dòng)作10$( )$用第2條規(guī)則S 歸約1001$S$acc用第1條規(guī)則SS(S)歸約$S(S)01234980123$S(S)$S4用第1條規(guī)則SS(S)歸約)$S(S(S)012323476012323$S(S(S)$S40. SS1. S S(S) 2. S 構(gòu)造LR(1)項(xiàng)目集規(guī)范族和轉(zhuǎn)換函數(shù)如下圖所示:I0:SS, $SS(S), $/(S , $/(I1: SS , $I2:S(S()0. SS1. S S(S) 2. S SS.(S), $/(SS(S), )/(S , )/(SS(S), $/