1、編譯原理編譯原理第五章第五章 語法分析語法分析(自下而上分析自下而上分析)王金偉計算機與信息工程學(xué)院天津師范大學(xué)TJNU-COCIE-WJW22022-2-13第五章第五章 語法分析語法分析(自下而上分析自下而上分析)從輸入符號串開始從輸入符號串開始，逐步進行，逐步進行“歸約歸約”，直到歸約到直到歸約到文法的開始符號文法的開始符號。即從語法樹的末端開始即從語法樹的末端開始，逐步向逐步向上上“歸約歸約”，直到根節(jié)點，直到根節(jié)點。 1.算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。質(zhì)進行語法分析。適合分析表達式。 2.LR分析法

2、：規(guī)范歸約分析法：規(guī)范歸約TJNU-COCIE-WJW32022-2-13第五章第五章 語法分析語法分析(自下而上分析自下而上分析)n5.1 自下而上語法分析基本問題自下而上語法分析基本問題n5.2 算符優(yōu)先分析法算符優(yōu)先分析法n5.3 LR分析法分析法n5.4 LR(0)項目集族和項目集族和LR(0)分析表的構(gòu)造分析表的構(gòu)造n5.5 SLR分析表的構(gòu)造分析表的構(gòu)造n5.6 規(guī)范規(guī)范LR分析表的構(gòu)造分析表的構(gòu)造TJNU-COCIE-WJW42022-2-135.1 自下而上語法分析基本問題自下而上語法分析基本問題1.基本思想基本思想用一個寄存符號的先進后出棧，把輸入符號一個用一個寄存符號的先進

3、后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產(chǎn)生式的候一個地移進到棧里，當棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成選式時，即把棧頂?shù)倪@一部分替換成(歸約歸約為為)該該產(chǎn)生式的左部符號。產(chǎn)生式的左部符號。2.歸約歸約是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。換成左部符號。一、移進歸約一、移進歸約TJNU-COCIE-WJW52022-2-13：設(shè)文法：設(shè)文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試對試對abbcde進行進行“移進歸約移進歸約”分析。分析。a bbcdeba

4、 bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa eTJNU-COCIE-WJW62022-2-13步步驟驟: :1 12 23 34 45 56 67 78 89 91 10 0動動作作: : 進進a a進進b b 歸歸( (2 2) ) 進進b b 歸歸( (3 3) ) 進進c c進進d d 歸歸( (4 4) ) 進進e e 歸歸( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS S：設(shè)文法：設(shè)文法G

5、(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試對試對abbcde進行進行“移進歸約移進歸約”分析。分析。：1.何時進行歸約？何時進行歸約？2.“可歸約串可歸約串”的定義方法？的定義方法？(5步，為什么用步，為什么用(3)不用不用(2)TJNU-COCIE-WJW72022-2-13bdbaceSABA自下而上分析過程：邊輸入單詞符號，邊歸約。自下而上分析過程：邊輸入單詞符號，邊歸約。核心問題：識別可歸約串核心問題：識別可歸約串步步驟驟: :1 12 23 34 45 56 67 78 89 91 10 0動動作作: : 進進a a進進b b 歸歸( (2

6、2) ) 進進b b 歸歸( (3 3) ) 進進c c進進d d 歸歸( (4 4) ) 進進e e 歸歸( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS STJNU-COCIE-WJW82022-2-131.短語短語定義定義:令令G是一個文法，是一個文法，S是文法的開始符號，假定是文法的開始符號，假定是文法是文法G的一個句型的一個句型其中其中, (V VN NV VT T)*，AV VN N ，如果有，如果有則則 稱是句型稱是句型相對于非終結(jié)符相對于非終結(jié)符A的的

7、短語短語。：因為句型是由開始符號推出來的，而短語是由非終因為句型是由開始符號推出來的，而短語是由非終結(jié)符號推出來的。所以，短語是句型的一部份或全結(jié)符號推出來的。所以，短語是句型的一部份或全部符號串。部符號串。AS*A且且二、二、規(guī)范歸約規(guī)范歸約TJNU-COCIE-WJW92022-2-132.直接短語直接短語特別是，如果有特別是，如果有A,則稱則稱 是句型是句型相對于規(guī)則相對于規(guī)則A 的的直接短語直接短語。3.句柄句柄一個句型的最左直接短語稱為該句型的一個句型的最左直接短語稱為該句型的句柄句柄。TJNU-COCIE-WJW102022-2-13：考慮文法：考慮文法G ： E T | E+T

8、T F | T*F F (E) | i求證求證i1*i2+i3是是G的一個句型，并找出該句型的全的一個句型，并找出該句型的全部短語、直接短語和句柄部短語、直接短語和句柄解：證明解：證明i1*i2+i3是是G的一個句型的一個句型E E+T T+T T*F+T F*F+T i1*F+T i1*i2+T i1*i2+F i1*i2+i3TJNU-COCIE-WJW112022-2-13找找i1*i2+i3的所有短語的所有短語(1)假設(shè)假設(shè)i1*i2+i3是一個短語是一個短語因為因為E E 且且 E i1*i2+i3所以所以i1*i2+i3是句型是句型i1*i2+i3關(guān)于關(guān)于E的一個短語的一個短語(2

9、)假設(shè)假設(shè)i1*i2是一個短語是一個短語因為因為E T+i3 且且 T i1*i2所以所以i1*i2是句型是句型i1*i2+i3關(guān)于關(guān)于T的一個短語的一個短語(3)假設(shè)假設(shè)i1是一個短語是一個短語因為因為E F*i2+i3 且且 F i1所以所以i1是句型是句型i1*i2+i3關(guān)于關(guān)于F的一個短語的一個短語AS*A且且* E T | E+T T F | T*F F (E) | iTJNU-COCIE-WJW122022-2-13找找i1*i2+i3的所有短語的所有短語(4)假設(shè)假設(shè)i2是一個短語是一個短語因為因為E i1*F+i3 且且 F i2所以所以i2是句型是句型i1*i2+i3關(guān)于關(guān)于

10、F的一個短語的一個短語(5)假設(shè)假設(shè)i3是一個短語是一個短語因為因為E i1*i2+F且且 F i3所以所以i3是句型是句型i1*i2+i3關(guān)于關(guān)于F的一個短語的一個短語(6)假設(shè)假設(shè)i2+i3是一個短語是一個短語因為因為E i1*E不成立，不成立， 且且 E i2+i3成立成立所以所以i2+i3不是句型不是句型i1*i2+i3的一個短語的一個短語AS*A且且* E T | E+T T F | T*F F (E) | iTJNU-COCIE-WJW132022-2-13：缺一不可缺一不可所以短語有：所以短語有：i1*i2+i3， i1*i2， i1，i2，i3找直接短語：找直接短語：根據(jù)定義，

11、如果有根據(jù)定義，如果有A,則稱則稱 是句型是句型相對于規(guī)則相對于規(guī)則A 的的直接短語直接短語因為有：因為有：F i所以所以i1、i2、i3是直接短語是直接短語找句柄：找句柄：根據(jù)定義，一個句型的最左直接短語稱為該句型的根據(jù)定義，一個句型的最左直接短語稱為該句型的句柄句柄。 i1是句型是句型i1*i2+i3的句柄的句柄AS*A和和TJNU-COCIE-WJW142022-2-134.規(guī)范歸約規(guī)范歸約定義：假定定義：假定 是文法是文法G的一個句子，我們稱序列的一個句子，我們稱序列 n， n-1， ， 0 是是 的一個的一個規(guī)范歸約規(guī)范歸約，如果此序列滿足：，如果此序列滿足： (1) n= (2)

12、0為文法的開始符號，即為文法的開始符號，即 0=S (3) 對任何對任何i，0 .b 表示表示a的優(yōu)先性大于的優(yōu)先性大于ba . . 不同于數(shù)學(xué)上的不同于數(shù)學(xué)上的 = a =.b 不一定對應(yīng)著不一定對應(yīng)著 b =. aa .b 不一定對應(yīng)著不一定對應(yīng)著 b . aa . a TJNU-COCIE-WJW292022-2-131.算符優(yōu)先文法算符優(yōu)先文法(1)算符文法算符文法一個文法，如果它的任一產(chǎn)生式的右部都不含兩個一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼相繼(并列并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：右部：QR 則我們稱該文法為則我們稱該文法

13、為算符文法算符文法，也稱，也稱OG文法文法 (Operater Grammar) 。約定：約定：a、b代表任意終結(jié)符；代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；代表任意非終結(jié)符；代表由終結(jié)符和非終結(jié)符組成的任意序列，代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字包括空字二、二、算符優(yōu)先文法及優(yōu)先表構(gòu)造算符優(yōu)先文法及優(yōu)先表構(gòu)造TJNU-COCIE-WJW302022-2-131. a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R aQ。(2)定義終

14、結(jié)符之間的優(yōu)先關(guān)系定義終結(jié)符之間的優(yōu)先關(guān)系假定假定G是一個不含是一個不含 產(chǎn)生式的算符文法。對于任何產(chǎn)生式的算符文法。對于任何一對終結(jié)符一對終結(jié)符a、b，我們說：，我們說：TJNU-COCIE-WJW312022-2-13(3)如果一個算符文法如果一個算符文法G中的任何終結(jié)符對中的任何終結(jié)符對(a，b)至多至多只滿足下述三關(guān)系之一：只滿足下述三關(guān)系之一：a=.ba.ba.b 則稱則稱G是一個是一個算符優(yōu)先文法算符優(yōu)先文法(OPG文法文法)。TJNU-COCIE-WJW322022-2-13:考慮下面的文法考慮下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i

15、試問：文法試問：文法G是一個是一個OPG文法嗎？文法嗎？解解: (1)G中沒有形如中沒有形如P QR 的產(chǎn)生式的產(chǎn)生式所以所以G是一個是一個OG文法文法TJNU-COCIE-WJW332022-2-13(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i(2)找出找出G中任意兩個非終結(jié)符號的優(yōu)先關(guān)系中任意兩個非終結(jié)符號的優(yōu)先關(guān)系因為因為P(E) aQb由由(1)和和(2)EE + TTT * F a R Q b由由(2)和和(3)TT * F FP F a R Q b1.a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；

16、的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R aQ。所以所以 ( =. ) 所以所以 + . * 所以所以 * . TJNU-COCIE-WJW342022-2-13(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(1)和和(3)EE + TTFP F a R Q b所以所以 + . + 1.a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R

17、aQ。TJNU-COCIE-WJW352022-2-13(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(2)TT * FT T * FR b a Q所以所以 * . * 由由(3)FP FFP F a R Q b所以所以 . 1.a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R aQ。TJNU-COCIE-WJW362022-2-13(1)EE+T | T(2)TT*F | F(3)FP F | P(4

18、)P(E) | i由由(4)P( E )a R且且EE+TT+TT*F+TF*F+TP F*F+T(E) F*F+T Qb Qb Qb b i F*F+T b所以所以( . + , * , , ( , i 1.a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R aQ。TJNU-COCIE-WJW372022-2-13(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(4)P( E ) Rb且且EE+TE+T*

19、FE+T*P F E+T*P P E+T*P (E) aQ aQ aQ a E+T*P i a所以所以 + , * , , ) , i . ) 以下略以下略在該文法中任意兩個終結(jié)符號之間在在該文法中任意兩個終結(jié)符號之間在.中只有一種關(guān)系成中只有一種關(guān)系成立，所以，立，所以，G是一個是一個OPG文法。文法。1.a =. b 當且僅當文法當且僅當文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；2. a .b 當且僅當當且僅當G中含有形如中含有形如PRb的產(chǎn)生式，的產(chǎn)生式，而而 R a或或R aQ。TJNU-COCIE-WJW382022-2-132.構(gòu)造算符優(yōu)先關(guān)系表構(gòu)造算符優(yōu)先關(guān)

20、系表(1)通過檢查產(chǎn)生式的每一個候選式可以找出滿足通過檢查產(chǎn)生式的每一個候選式可以找出滿足a=.b （即（即Pab或或PaQb的產(chǎn)生式）的產(chǎn)生式）(2)為了滿足為了滿足.，需對，需對G中每個非終結(jié)符中每個非終結(jié)符P構(gòu)造兩構(gòu)造兩個集合個集合FIRSTVT(P)和和LASTVT(P)：FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或TJNU-COCIE-WJW392022-2-13(3)構(gòu)造集合構(gòu)造集合FIRSTVT(P)的算法的算法按其定義，可用下面兩條規(guī)則來構(gòu)造集合按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)： 若有產(chǎn)生

21、式若有產(chǎn)生式Pa或或PQa，則則a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式PQ，則則a FIRSTVT(P)。TJNU-COCIE-WJW402022-2-13(4)同理構(gòu)造構(gòu)造集合同理構(gòu)造構(gòu)造集合LASTVT(P)的算法的算法按其定義，可用下面兩條規(guī)則來構(gòu)造集合按其定義，可用下面兩條規(guī)則來構(gòu)造集合LASTVT(P)： 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ ，則則a LASTVT(P)； 若若a LASTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式P Q ，則則a LASTVT(P)。TJNU-COCIE-WJW412022-2-13 (5)有了這兩個集合之后，就

22、可以通過檢查每個產(chǎn)生有了這兩個集合之后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關(guān)系式的候選式確定滿足關(guān)系.的所有終結(jié)符對。的所有終結(jié)符對。(1)(1)假定有個產(chǎn)生式的一個候選形為假定有個產(chǎn)生式的一個候選形為aPaP 那么，對任何那么，對任何b b FIRSTVT(P)FIRSTVT(P)，有，有a a . b b。FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或TJNU-COCIE-WJW422022-2-13:考慮下面的文法考慮下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i構(gòu)造該文法構(gòu)造該

23、文法G的每個非終結(jié)符的的每個非終結(jié)符的FIRSTVT和和LASTVT集合集合解解: (1)構(gòu)造構(gòu)造FIRSTVT集合集合FIRSTVT(P)= FIRSTVT(F)= FIRSTVT(T)= FIRSTVT(E)= 若有產(chǎn)生式若有產(chǎn)生式Pa或或PQa，則則a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式PQ，則，則a FIRSTVT(P)。( , i ,( , i*, ,( , i+,*, ,( , iTJNU-COCIE-WJW432022-2-13:考慮下面的文法考慮下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i構(gòu)造該

24、文法構(gòu)造該文法G的每個非終結(jié)符的的每個非終結(jié)符的FIRSTVT和和LASTVT集合集合解解: (1)構(gòu)造構(gòu)造LASTVT集合集合LASTVT(P)= LASTVT(F)= LASTVT(T)= LASTVT(E)= ), i ,) , i*, ,), i+,*, ,) , i 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ ，則則a LASTVT(P)； 若若a LASTVT(P)，且有產(chǎn)生式，且有產(chǎn)生式P Q ，則，則a LASTVT(P)。TJNU-COCIE-WJW442022-2-13:G:EE+T | TTT*F | FF(E) | i求出該文法每個終結(jié)符號的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表求出該

25、文法每個終結(jié)符號的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表(1)EE+T，且，且*, (, i FIRSTVT(T) aP所以所以+ . +FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有個產(chǎn)生式的一個候選形為假定有個產(chǎn)生式的一個候選形為aP 那么，對任何那么，對任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW452022-2-13:G:EE+T | TTT*F | FF(E) | I(3

26、)TT*F，且，且 (, i FIRSTVT(F) aP所以所以* . *FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有個產(chǎn)生式的一個候選形為假定有個產(chǎn)生式的一個候選形為aP 那么，對任何那么，對任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW462022-2-13:G:EE+T | TTT*F | FF(E) | i(5)F(E) ，且，且+,*, (, i FIRSTV

27、T(E) aP所以所以( . )(7)F(E) ，所以所以( =. )(0)通過檢查產(chǎn)生式的每一個候選式可以找通過檢查產(chǎn)生式的每一個候選式可以找出滿足出滿足a=.b （即（即Pab或或PaQb的產(chǎn)生式）的產(chǎn)生式）FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有個產(chǎn)生式的一個候選形為假定有個產(chǎn)生式的一個候選形為aP 那么，對任何那么，對任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-

28、WJW472022-2-13+* i()#+.*. .i.EE.(.EE.#.E=.構(gòu)造分析表如下：構(gòu)造分析表如下：其中，其中，E=ERRORTJNU-COCIE-WJW482022-2-13：對于對于#號，相當于在文法開始符號號，相當于在文法開始符號S前加一個前加一個額外的開始符號，比如為額外的開始符號，比如為Z然后，把然后，把Z #S#添加到原文法中，再進行分析。添加到原文法中，再進行分析。TJNU-COCIE-WJW492022-2-13:G:EE+T | TTT*F | FF(E) | I(1)因為因為Z#E#所以所以# =. #(2)因為因為FIRSTVT(E)=+, *, , (,

29、 i Z #E# aP所以所以# . #Z #E#EE+T | TTT*F | FF(E) | i(1)假定有個產(chǎn)生式的一個候選形為假定有個產(chǎn)生式的一個候選形為aP 那么，對任何那么，對任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW502022-2-13# . #+* i()#+.*. .i.EE.(.EE.#.E=.TJNU-COCIE-WJW512022-2-131.問題的提出問題的提出自下而上分析自下而上分析移進移進-歸約法：句柄為可歸納串歸約法：句柄為可歸納串算符優(yōu)先分析法：最左素短語為可歸納串算符優(yōu)先分析法：最左素短語為可歸納串2.素短語素短語指一個句型

30、的短語，它至少包括有一個終結(jié)符指一個句型的短語，它至少包括有一個終結(jié)符號且除去它本身之外不再含任何更小的素短語號且除去它本身之外不再含任何更小的素短語3.最左素短語最左素短語處在句型最左端那個素短語成為最左素短語處在句型最左端那個素短語成為最左素短語三、算符優(yōu)先分析算法的設(shè)計三、算符優(yōu)先分析算法的設(shè)計TJNU-COCIE-WJW522022-2-13:考慮下面的文法考慮下面的文法G： EE+T | T TT*F | F F(E) | i求句型求句型E+T*F+i的素短語和最左素短語的素短語和最左素短語解解: 構(gòu)造一個推導(dǎo)構(gòu)造一個推導(dǎo)EE+TE+T+TE+T+TE+T*F+FE+T*F+i素短語

31、：素短語：T*F，i最左素短語：最左素短語：T*F短語：短語：E+T*F+iE+T*FT*FiTJNU-COCIE-WJW532022-2-134.算符優(yōu)先分析算法和設(shè)計算符優(yōu)先分析算法和設(shè)計(1)句型的一般表示形式：句型的一般表示形式： #N1a1N2a2NnanNn+1#其中，每個其中，每個ai都是終結(jié)符，都是終結(jié)符，Ni是可有可無的非終結(jié)符是可有可無的非終結(jié)符(2)定理：定理：一個算符優(yōu)先文法一個算符優(yōu)先文法G的任何句型的最左素短語是滿足的任何句型的最左素短語是滿足如下條件的最左子串如下條件的最左子串 NjajNiaiNi+1， aj-1 . ai+1：出現(xiàn)在左端或右端的非終結(jié)符一定屬于

32、這個素短語出現(xiàn)在左端或右端的非終結(jié)符一定屬于這個素短語TJNU-COCIE-WJW542022-2-13:EE+T | TTT*F | FF(E) | i句型句型關(guān)系關(guān)系 最左素短語最左素短語歸約符號歸約符號#i#.i#i+#.+i F#F+#F+i#. + . i #F+i*#. + . *i F#F+F*#F+F*i#. + . * . i #F+F*i#. + . * . #i F#F+F*F#. + . #F*F T#F+T# #.# F+T E#E#對句子對句子 i + i * i 進行分析進行分析TJNU-COCIE-WJW552022-2-13算符優(yōu)先分析一般不等于規(guī)范歸約算符優(yōu)

33、先分析一般不等于規(guī)范歸約:文法文法G：EE+T | T TT*F | F FP F | P P(E) | i解解:#.+.#P+i#.+.#P+P#.#E#右邊是規(guī)范歸約右邊是規(guī)范歸約對句型對句型 “#i+i#” 進行分析進行分析TJNU-COCIE-WJW562022-2-131.優(yōu)先函數(shù)的定義優(yōu)先函數(shù)的定義把每個終結(jié)符把每個終結(jié)符 與兩個自然數(shù)與兩個自然數(shù)f( )與與g( )相對應(yīng)，使得相對應(yīng)，使得若若 1 . 2，則，則f( 1) . 2，則，則f( 1) g( 2)f稱為入棧優(yōu)先函數(shù)，稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。稱為比較優(yōu)先函數(shù)。(1)優(yōu)點優(yōu)點:便于比較，節(jié)省空間；便于比較，

34、節(jié)省空間；(2)缺點缺點:原來不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于自原來不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于自然數(shù)相對應(yīng)，變成可以比較的。要進行一些特殊的然數(shù)相對應(yīng)，變成可以比較的。要進行一些特殊的判斷。判斷。四、優(yōu)先函數(shù)四、優(yōu)先函數(shù)TJNU-COCIE-WJW572022-2-13：文法：文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的優(yōu)先函數(shù)如下表的優(yōu)先函數(shù)如下表：(1)對應(yīng)一個優(yōu)先關(guān)系表的優(yōu)先函數(shù)對應(yīng)一個優(yōu)先關(guān)系表的優(yōu)先函數(shù)f和和g并不唯并不唯一，只要存在一對，就存在無窮多對一，只要存在一對，就存在無窮多對+* ()i#F24

35、40660G 1355050TJNU-COCIE-WJW582022-2-13注意注意：(2) 許多優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)許多優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)：不存在對應(yīng)的優(yōu)先函數(shù)不存在對應(yīng)的優(yōu)先函數(shù)f f和和g g假定存在假定存在f f和和g g，則有，則有 f(a)=g(a)f(a)=g(a)，f(a)g(b)f(a)g(b)， f(b)=g(a)f(b)=g(a)，f(b)=g(b)f(b)=g(b)導(dǎo)致如下矛盾導(dǎo)致如下矛盾: : f(a) g(b) = f(b) = g(a) = f(a) f(a) g(b) = f(b) = g(a) = f(a)aba=.b=.=.TJNU-COCIE-

36、WJW592022-2-132.優(yōu)先函數(shù)的構(gòu)造方法優(yōu)先函數(shù)的構(gòu)造方法如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù)先表構(gòu)造優(yōu)先函數(shù):(1)對于每個終結(jié)符對于每個終結(jié)符a，令其對應(yīng)兩個符號，令其對應(yīng)兩個符號fa和和ga，畫一張以所有符號畫一張以所有符號fa和和ga為結(jié)點的方向圖。為結(jié)點的方向圖。如果如果a.=.b，則從，則從fa畫一條弧至畫一條弧至gb如果如果a.=.b，則從，則從gb畫一條弧至畫一條弧至fa 。(2)對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達的結(jié)點出發(fā)所能到達的結(jié)點(包括

37、出發(fā)點自身包括出發(fā)點自身)。賦給賦給fa的數(shù)作為的數(shù)作為f(a)賦給賦給ga的數(shù)作為的數(shù)作為g(a)。(3)檢查所構(gòu)造出來的函數(shù)檢查所構(gòu)造出來的函數(shù)f和和g是否與原來的關(guān)系是否與原來的關(guān)系矛盾。若沒有矛盾，則矛盾。若沒有矛盾，則f和和g就是要求的優(yōu)先函數(shù)，就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。若有矛盾，則不存在優(yōu)先函數(shù)。TJNU-COCIE-WJW602022-2-13gifif*g*g+f+f#g#:取前面文法取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) F (E) | i的終結(jié)符的終結(jié)符+，*，i，#i+*#fg74662151TJNU-COCI

38、E-WJW612022-2-133.構(gòu)造方法證明構(gòu)造方法證明現(xiàn)在必須證明：現(xiàn)在必須證明：若若a=.b，則，則f(a)g(b)；若若a.b，則，則f(a).b，則，則f(a) g(b)。第一個關(guān)系可從函數(shù)的構(gòu)造直接獲得。因為，若第一個關(guān)系可從函數(shù)的構(gòu)造直接獲得。因為，若a=.b，則既有從，則既有從fa到到gb的弧，又有從的弧，又有從gb到到fa的弧。的弧。所以，所以，fa和和gb所能到達的結(jié)是全同的。所能到達的結(jié)是全同的。至于至于a.b的情形，只須證明其一。的情形，只須證明其一。如果如果a.b，則有從，則有從fa到到gb的弧。也就是的弧。也就是gb能到達能到達的任何結(jié)的任何結(jié)fa也能到達。因此，

39、也能到達。因此，f(a) g(b)。所需。所需證明的是，在這種情況下，證明的是，在這種情況下，f(a)=g(b)不應(yīng)成立。不應(yīng)成立。TJNU-COCIE-WJW622022-2-13我們將指出，如果我們將指出，如果f(a)=g(b)，則根本不存在優(yōu)先函，則根本不存在優(yōu)先函數(shù)。假若數(shù)。假若f(a)=g(b)，那么必有如下的回路：，那么必有如下的回路：fa1fafamgb1gbgbm因此有因此有a.b, aa.b, a1 1.=.b, a.=.b.=.b1 1, , , a, am m.=.b.=.bm m, a.=.b, a g(b) f(a1) g(b1) f(am) g(bm) f(a)從而

40、導(dǎo)致從而導(dǎo)致f(a) f(a)，產(chǎn)生矛盾。因此，不存在優(yōu)先函，產(chǎn)生矛盾。因此，不存在優(yōu)先函數(shù)數(shù)f和和g。TJNU-COCIE-WJW632022-2-135.3 LR分析法分析法L指從左到右掃描輸入指從左到右掃描輸入R指構(gòu)造最右推導(dǎo)的逆指構(gòu)造最右推導(dǎo)的逆k指的是在決定分析動作時向前看的符號個數(shù)指的是在決定分析動作時向前看的符號個數(shù)一、一、LR(k)分析法分析法TJNU-COCIE-WJW642022-2-131.分析能力強大分析能力強大nLR分析器能夠構(gòu)造識別所有上下文無關(guān)文法寫分析器能夠構(gòu)造識別所有上下文無關(guān)文法寫的程序設(shè)計語言的結(jié)構(gòu)的程序設(shè)計語言的結(jié)構(gòu)nLR分析方法是已知的最一般的無回溯移

41、進分析方法是已知的最一般的無回溯移進-歸約歸約方法，它能夠和其他移進方法，它能夠和其他移進-歸約方法一樣有效地歸約方法一樣有效地實現(xiàn)實現(xiàn)nLR方法能分析的文法類是預(yù)測分析法能分析的方法能分析的文法類是預(yù)測分析法能分析的文法類的真超集文法類的真超集nLR分析器能及時察覺語法錯誤分析器能及時察覺語法錯誤TJNU-COCIE-WJW652022-2-132.LR分析器的組成分析器的組成總控程序總控程序一張分析表一張分析表LRLR分析分析總控程序總控程序分析表分析表輸入輸入輸出輸出TJNU-COCIE-WJW662022-2-133. LR分析表的種類分析表的種類LR(0)分析表分析表功能較弱，但是它

42、是建立功能較弱，但是它是建立LR分析的基礎(chǔ)分析的基礎(chǔ)SLR(簡單簡單LR)分析表分析表功能一般，但容易實現(xiàn)，使用價值比較高功能一般，但容易實現(xiàn)，使用價值比較高規(guī)范規(guī)范LR分析表分析表功能強，應(yīng)用范圍比較廣，但實現(xiàn)代價高功能強，應(yīng)用范圍比較廣，但實現(xiàn)代價高LALR(向前向前LR)分析表分析表功能介于功能介于SLR與規(guī)范與規(guī)范LR之間。之間。TJNU-COCIE-WJW672022-2-134.LR分析法的基本思想分析法的基本思想使用的最右推導(dǎo)的逆過程，就是使用的最右推導(dǎo)的逆過程，就是規(guī)范歸約規(guī)范歸約在規(guī)范歸約中，記住已移進和歸約出的整個符號串在規(guī)范歸約中，記住已移進和歸約出的整個符號串(記住歷史

43、記住歷史)根據(jù)產(chǎn)生式，推測未來可能碰到的輸入符號根據(jù)產(chǎn)生式，推測未來可能碰到的輸入符號(展望未來展望未來)根據(jù)當前正在要進棧的輸入符號根據(jù)當前正在要進棧的輸入符號(面對現(xiàn)實面對現(xiàn)實)最終是為了尋找最終是為了尋找句柄句柄(可歸約串可歸約串)TJNU-COCIE-WJW682022-2-13LRLR分析分析程程 序序狀態(tài)狀態(tài)符號符號分析棧分析棧action gotoaction goto LR LR分析表分析表a a1 1a a2 2a ai ia an n# #輸入串輸入串 輸出輸出二、二、 LR分析器的結(jié)構(gòu)分析器的結(jié)構(gòu)TJNU-COCIE-WJW692022-2-131.LR分析器棧的結(jié)構(gòu)分析

44、器棧的結(jié)構(gòu)(1)把歷史和展望材料抽象成某些狀態(tài)。分析棧用把歷史和展望材料抽象成某些狀態(tài)。分析棧用來存放這些狀態(tài)。棧頂?shù)臓顟B(tài)都代表了整個歷史來存放這些狀態(tài)。棧頂?shù)臓顟B(tài)都代表了整個歷史和已經(jīng)推測出的展望。和已經(jīng)推測出的展望。(2)為了有助于明確規(guī)約手續(xù)，將已規(guī)約出的文法為了有助于明確規(guī)約手續(xù)，將已規(guī)約出的文法符號串也同時放到棧里。符號串也同時放到棧里。狀態(tài)狀態(tài)符號符號分析棧分析棧TJNU-COCIE-WJW702022-2-132.LR分析表的結(jié)構(gòu)分析表的結(jié)構(gòu)動作表：動作表：ACTIONs，a：當狀態(tài)當狀態(tài)s面臨輸入符號面臨輸入符號a時，應(yīng)采取什么動作時，應(yīng)采取什么動作狀態(tài)轉(zhuǎn)換表：狀態(tài)轉(zhuǎn)換表：GO

45、TOs，X：狀態(tài)狀態(tài)s面對文法符號面對文法符號X時，下一狀態(tài)是什么時，下一狀態(tài)是什么TJNU-COCIE-WJW712022-2-13(1)動作表動作表ACTIONs，a：當狀態(tài)：當狀態(tài)s面臨輸入符號面臨輸入符號a時，應(yīng)采時，應(yīng)采取什么動作取什么動作每一項每一項ACTIONs，a所規(guī)定的四種動作所規(guī)定的四種動作:. 移進移進. 歸約歸約. 接受接受. 報錯報錯TJNU-COCIE-WJW722022-2-13. 移進移進 把把(s，a)的下一狀態(tài)的下一狀態(tài)s=GOTOs,a 和輸入符號和輸入符號a推進棧，下一輸入符號變推進棧，下一輸入符號變成現(xiàn)行輸入符號成現(xiàn)行輸入符號.狀態(tài)狀態(tài)符號符號分析棧分

46、析棧asTJNU-COCIE-WJW732022-2-13. 歸約歸約 指用某產(chǎn)生式指用某產(chǎn)生式A進行歸約進行歸約. 假若假若 的長度為的長度為r， 歸約動作歸約動作是是A， 去除棧頂去除棧頂r個項，使狀個項，使狀態(tài)態(tài)sm-r變成棧頂狀態(tài)，然后把變成棧頂狀態(tài)，然后把(sm-r, A)的下一狀態(tài)的下一狀態(tài)s=GOTOsm-r, A和文法符和文法符號號A推進棧推進棧.狀態(tài)狀態(tài)符號符號分析棧分析棧 r個個AsTJNU-COCIE-WJW742022-2-13. 接受接受 宣布分析成功，停止分析器工作。宣布分析成功，停止分析器工作。. 報錯報錯 發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序發(fā)現(xiàn)源程序含有錯誤，

47、調(diào)用出錯處理程序TJNU-COCIE-WJW752022-2-13可以看成是一個三元式的變化過程可以看成是一個三元式的變化過程(狀態(tài)序列，已規(guī)約串，輸入串狀態(tài)序列，已規(guī)約串，輸入串)n分析開始時分析開始時:狀態(tài)序列狀態(tài)序列 已歸約串已歸約串 輸入串輸入串 (s0， #， a1a2 an #)n以后每步的結(jié)果可以表示為以后每步的結(jié)果可以表示為: (s0 s1 sm ，# X1 Xm ，aiai+1 an #)分析器下一步的動作由分析器下一步的動作由ACTIONsm ，ai所規(guī)定的。所規(guī)定的。三、三、 LR分析器的工作過程分析器的工作過程TJNU-COCIE-WJW762022-2-13 (s0

48、s1 sm ，# X1 Xm ，aiai+1 an #).若若ACTION(sm , ai)為移進，且為移進，且s=GOTOsm , ai ，則三元式格局變?yōu)閯t三元式格局變?yōu)? (s0 s1 sms ，# X1 Xm ai ， ai+1 an #).若若ACTION(sm , ai)為按為按A歸約，三元式變?yōu)闅w約，三元式變?yōu)? (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #)此處此處, s=GOTO(sm-r, A), r為為 的長度的長度, = Xm-r+1 Xm.若若ACTION(sm , ai)為為接受接受，則三元式不再變，則三元式不再變化，變化過程終止，宣布

49、分析成功化，變化過程終止，宣布分析成功.若若ACTION(sm , ai)為為報錯報錯，則三元式變化過，則三元式變化過程終止，報告錯誤程終止，報告錯誤.TJNU-COCIE-WJW772022-2-13文法文法G(E)： (1) EET(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi分析分析i*i+i四、四、LR分析器示例分析器示例TJNU-COCIE-WJW782022-2-13ACTIONGOTO狀態(tài)狀態(tài)i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r

50、1r110r3r3r3r311r5r5r5r5其其LRLR分析表為（書分析表為（書P101P101）: :TJNU-COCIE-WJW792022-2-13假定輸入串為假定輸入串為i*i+i， LR分析器的工作過程分析器的工作過程:步驟步驟狀態(tài)狀態(tài)符號符號輸入串輸入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#TJNU-COCIE-WJW802022-2-13步驟步驟狀態(tài)狀態(tài)符號符號輸入串輸入串(9)01#E+i#(10)016#E+i#(1

51、1)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15) 接受接受TJNU-COCIE-WJW812022-2-13(1)定義：對于一個文法，如果能夠構(gòu)造一張分析表，定義：對于一個文法，如果能夠構(gòu)造一張分析表，使得它的每個入口均是唯一確定的，則這個文法就使得它的每個入口均是唯一確定的，則這個文法就稱為稱為LR文法文法：不是所有上下文無關(guān)文法都是：不是所有上下文無關(guān)文法都是LR文法，但多文法，但多數(shù)程序設(shè)計語言都可用數(shù)程序設(shè)計語言都可用LR文法描述文法描述(2)定義：一個文法，如果能用一個每步頂多向前檢定義：一個文法，如果能用一個每步頂多向前檢查查k個

52、輸入符號的個輸入符號的LR分析器進行分析，則這個文法分析器進行分析，則這個文法就稱為就稱為LR(k)文法文法：對于多數(shù)程序設(shè)計語言，：對于多數(shù)程序設(shè)計語言，k=0或或1，足夠了。，足夠了。五、五、LR文法文法TJNU-COCIE-WJW822022-2-13(3)非非LR結(jié)構(gòu)結(jié)構(gòu)LR文法不是二義的，二義文法肯定不會是文法不是二義的，二義文法肯定不會是LR的。的。 S iCtS | iCtSeS 棧棧 輸入輸入 iCtS e#iCtS是否為句柄？是規(guī)約還是繼續(xù)移進？是否為句柄？是規(guī)約還是繼續(xù)移進？TJNU-COCIE-WJW832022-2-135.4 LR(0)項目集族和項目集族和LR(0)分

53、析表的構(gòu)造分析表的構(gòu)造1.字的前綴字的前綴是指字的任意首部是指字的任意首部.如如:字字abc的前綴有的前綴有 ，a，ab，abc2.活前綴活前綴是指規(guī)范句型的一個前綴，這種前綴不含句柄之是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。即，對于規(guī)范句型后的任何符號。即，對于規(guī)范句型， 為句柄，為句柄，如果如果=u1u2ur，則符號串，則符號串u1u2ui(1 i r)是是的的活前綴活前綴。( 必為終結(jié)符串必為終結(jié)符串)一、規(guī)范句型活前綴的概念一、規(guī)范句型活前綴的概念TJNU-COCIE-WJW842022-2-13：1.在在LR分析工作過程中的任何時候，棧里的文法分析工作過程中的任何時候

54、，棧里的文法符號符號X1 X2 Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后，即應(yīng)成為規(guī)范句型余部分配上之后，即應(yīng)成為規(guī)范句型(如果整個如果整個輸入串確實是一個句子輸入串確實是一個句子)。因此，只要輸入串的。因此，只要輸入串的已掃描部分保持可歸約為一個活前綴，則意味著已掃描部分保持可歸約為一個活前綴，則意味著掃描過的部分沒有錯。掃描過的部分沒有錯。2.LR分析器的工作實質(zhì)上就是一個逐步產(chǎn)生或識分析器的工作實質(zhì)上就是一個逐步產(chǎn)生或識別所給文法規(guī)范句型活前綴的過程。別所給文法規(guī)范句型活前綴的過程。3.對于一個文法對于一個文法G, 可以構(gòu)造一個可以構(gòu)造一個DFA,它能識

55、別它能識別G的所有活前綴的所有活前綴.然后我們可以將該然后我們可以將該DFA轉(zhuǎn)變成轉(zhuǎn)變成LR分析表分析表TJNU-COCIE-WJW852022-2-131.LR(0)項目的提出項目的提出(1)活前綴與句柄的關(guān)系活前綴與句柄的關(guān)系A(chǔ).活前綴中已含有句柄的全部活前綴中已含有句柄的全部(句柄在最右邊句柄在最右邊)B.活前綴中只含句柄的一部分符號活前綴中只含句柄的一部分符號C.活前綴中全然不含句柄的任何符號活前綴中全然不含句柄的任何符號分析一下：分析一下：從從A看出看出A的右部的右部 已出現(xiàn)在棧頂，用產(chǎn)生式已出現(xiàn)在棧頂，用產(chǎn)生式A進進行歸約行歸約.從從B看出看出A1 2，已經(jīng)看到，已經(jīng)看到 1，期待

56、看到，期待看到 2從從C看出看出A，產(chǎn)生式的右部，產(chǎn)生式的右部一點都沒看到一點都沒看到二、構(gòu)造識別文法二、構(gòu)造識別文法G的所有活前綴的的所有活前綴的NFATJNU-COCIE-WJW862022-2-13(2)LR(0)項目概念項目概念文法文法G的每個產(chǎn)生式的右部添加一個圓點稱為的每個產(chǎn)生式的右部添加一個圓點稱為G的的LR(0)項目項目:AXYZ有四個項目：有四個項目：A.XYZ AX.YZ AXY.Z AXYZ. TJNU-COCIE-WJW872022-2-132.構(gòu)造識別文法所有活前綴的構(gòu)造識別文法所有活前綴的NFA方法方法文法文法G(SG(S ) ) S S EE EaA|bB EaA

57、|bB AcA|d AcA|d BcB|d BcB|d 構(gòu)造識別該文法所有活前綴的構(gòu)造識別該文法所有活前綴的NFATJNU-COCIE-WJW882022-2-13(1)求出該文法的求出該文法的LR(0)LR(0)項目項目S S EEEaA|bBEaA|bBAcA|dAcA|dBcB|dBcB|d1.S1.S E E2.S2.S EE3.E3.EaA aA 4.Ea4.EaA A5.EaA5.EaA6.A6.AcAcA7.Ac7.AcA A8.AcA8.AcA9.A9.Ad 10.Add 10.Ad11.E11.EbBbB 12.Eb12.EbB B 13.EbB13.EbB14.B14.Bc

58、BcB 15.Bc15.BcB B 16.BcB16.BcB17.B17.Bd d18.Bd18.BdTJNU-COCIE-WJW892022-2-13(2)構(gòu)造識別文法的構(gòu)造識別文法的NFA為為M = (S, , f, S0, Z)其中其中S=s|s是文法是文法G的的18個個LR(0)項目項目=S,E, A, B, a, b, c, dS0= S S E EZ:規(guī)定每個狀態(tài)都是識別活前綴的終態(tài)規(guī)定每個狀態(tài)都是識別活前綴的終態(tài)(18個個)TJNU-COCIE-WJW902022-2-13f: 若狀態(tài)若狀態(tài)i為為XX1 Xi-1Xi Xn ， 狀態(tài)狀態(tài)j為為XX1 Xi-1Xi Xi+1 Xn

59、，則從狀態(tài)則從狀態(tài)i畫一條標志為畫一條標志為Xi的有向邊到狀態(tài)的有向邊到狀態(tài)j； 若狀態(tài)若狀態(tài)i為為X .A ，A為非終結(jié)符，為非終結(jié)符， 則從狀態(tài)則從狀態(tài)i畫一條畫一條 邊到所有狀態(tài)邊到所有狀態(tài)j：A. 。 ： 狀態(tài)狀態(tài)i：S S E E 狀態(tài)狀態(tài)j j：EEaAaAijXiijTJNU-COCIE-WJW912022-2-13678910453121112131415161817 a AEbBBcAcd識別活前綴的識別活前綴的NFANFA15. S E2. S E16. EaA 17. EaA5. EaA18. AcA19. AcA8. AcA20. Ad 10. Ad21. EbB22.

60、 EbB13. EbB23. BcB24. BcB 16. BcB25. Bd18. BddTJNU-COCIE-WJW922022-2-13用子集法，把項目集變?yōu)闋顟B(tài)用子集法，把項目集變?yōu)闋顟B(tài)IIaIbIcISIAIB1,3,114,6,9三、三、把識別文法所有活前綴的把識別文法所有活前綴的NFA確定化確定化TJNU-COCIE-WJW932022-2-13識別活前綴的識別活前綴的DFADFA0: S E EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: