1、第五章 語法分析自下而上分析,語法分析方法： 自上而下分析法(Top-down) 自下而上分析法(Bottom-up),自上而下分析法(Top-down) 基本思想 它從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找匹配的推導。 遞歸下降分析法 對每一語法變量(非終結符)構造一個相應的子程序，每個子程序識別一定的語法單位，通過子程序間的相互調(diào)用實現(xiàn)對輸入串的識別。 預測分析程序 非遞歸實現(xiàn) 優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。,語法分析方法：,自下而上分析法(Bottom-up) 基本思想 從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式

2、規(guī)則，把產(chǎn)生式的右部替換成左部符號。 算符優(yōu)先分析法 按照算符的優(yōu)先關系和結合性質(zhì)進行語法分析。適合分析表達式。 LR分析法 規(guī)范歸約,語法分析方法：,G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,第五章 語法分析自下而上分析,自下而上分析的基本問題 算符優(yōu)選分析算法 LR分析法,一、自下而上分析的基本問題,采用“移進歸約”思想進行自下而上分析。 基本思想 用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生

3、式的左部符號。,例：設文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d 試對abbcde進行“移進歸約”分析。,b,d,b,a,c,e,自下而上分析過程：邊輸入單詞符號，邊歸約。 核心問題：識別可歸約串,短語,短語,特別是，如果有A,則稱是句型相對于規(guī)則A 的直接短語。一個句型的最左直接短語稱為該句型的句柄。,考慮文法G(E)： E T | E+T T F | T*F F (E) | i 和句型i1*i2+i3：,示例：短語、直接短語和句柄,E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3,* + E

4、 F*i2+i3 F i1 i1*i2+i3 短 語： i1 E i1 *F+i3 F i2 i1*i2+i3 短 語： i2 E i1*i2+F F i3 i1*i2+i3 短 語： i3 E E+ i3 E i1*i2 i1*i2+i3 短 語： i1*i2 E E E i1*i2+i3 i1*i2+i3 短 語：i1*i2+i3,G(E)： E T | E+T T F | T*F F (E) | i,E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3,考慮文法G(E)： E T | E+T T F | T*F F (E) | i 和句型

5、i1*i2+i3：,示例：短語、直接短語和句柄,E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3,短語： i1，i2，i3， i1*i2， i1*i2+i3 直接短語： i1，i2，i3 句柄： i1,在一個句型對應的語法樹中： 以某非終結符為根的兩代以上的子樹的所有末端結點從左到右排列就是相對于該非終結符的一個短語 如果子樹只有兩代，則該短語就是直接短語。,短語、直接短語和句柄,可用句柄來對句子進行歸約 句型 歸約規(guī)則 abbcde (2) A b,短語、直接短語和句柄,b,d,b,a,c,e,可用句柄來對句子進行歸約 句型 歸約規(guī)則 a

6、bbcde (2) A b aAbcde (3) A Ab,短語、直接短語和句柄,可用句柄來對句子進行歸約 句型 歸約規(guī)則 abbcde (2) A b aAbcde (3) A Ab aAcde (4) B d,短語、直接短語和句柄,d,a,c,e,A,可用句柄來對句子進行歸約 句型 歸約規(guī)則 abbcde (2) A b aAbcde (3) A Ab aAcde (4) B d aAcBe (1) S aAcBe S,短語、直接短語和句柄,a,c,e,A,B,定義：假定是文法G的一個句子，我們稱序列 n， n-1， ，0 是一個規(guī)范歸約，如果此序列滿足： 1 n= 為句子 2 0為文法的

7、開始符號，即0=S 3 對任何i，0 i n， i-1是從i經(jīng)把句柄替換成為相應產(chǎn)生式左部符號而得到的。,規(guī)范歸約,把上例倒過來寫，則得到： S aAcBe aAcde aAbcde abbcde 顯然這是一個最右推導。 規(guī)范歸約是最右推導的逆過程 最左歸約 規(guī)范推導 由規(guī)范推導推出的句型稱為規(guī)范句型。,規(guī)范歸約與規(guī)范推導,符號棧的使用,棧是語法分析的一種基本數(shù)據(jù)結構。#作為棧底符號 自下而上的語法分析器的工作過程是：自左至右把輸入串的符號一一移進符號棧里，一旦發(fā)現(xiàn)棧頂出現(xiàn)可歸約串就歸約，這種替換可能出現(xiàn)多次，直至棧頂不再出現(xiàn)可歸約串為止。然后繼續(xù)移進符號，重復整個過程，直至棧里只含有#和文法

8、開始符號、且輸入串全被吸收，僅剩下#。這種格局表示分析成功，否則，就說明輸入串有語法錯誤,符號棧的使用,例：文法G(E)： E T | E+T T F | T*F F (E) | i 輸入串為i1*i2+i3 ，分析步驟為：,步驟 符號棧輸入串動作 0 #i1*i2+i3#預備 1 #i1*i2+i3#進 2 #F*i2+i3#歸，用Fi 3 #T*i2+i3#歸，用TF 4 #T*i2+i3#進,G(E)： E T | E+T T F | T*F F (E) | i,步驟 符號棧輸入串動作 4 #T*i2+i3#進 5 #T*i2+i3#進 6 #T*F+i3#歸，用Fi 7 #T+i3#歸

9、，用TT*F 8 #E+i3# 歸，用ET 9 #E+i3# 進,G(E)： E T | E+T T F | T*F F (E) | i,步驟 符號棧輸入串動作 9 #E+ i3#進 10#E+i3#進 11#E+F#歸，用Fi 12#E+T#歸，用TF 13#E#歸，用EE+T 14#E#接受,G(E)： E T | E+T T F | T*F F (E) | i,語法分析的方法： 自下而上分析法(Bottom-up) 基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構造語法樹。所謂 歸約 ，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。,回顧,歸約,

10、采用“移進歸約”思想進行自下而上分析。 基本思想：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號。,規(guī)范歸約,定義：令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 且,則稱是句型相對于非終結符A的短語。 特別是，如果有A,則稱是句型相對于規(guī)則A 的直接短語。一個句型的最左直接短語稱為該句型的句柄。,定義：假定是文法G的一個句子，我們稱序列 n， n-1， ，0 是的一個規(guī)范歸約，如果此序列滿足： 1 n= 2 0為文法的開始符號，即0=S 3 對任何i，0 i n， i-1是從

11、i經(jīng)把句柄替換成為相應產(chǎn)生式左部符號而得到的。,第五章 語法分析自下而上分析,自下而上分析的基本問題 算符優(yōu)選分析算法 LR分析法,二、算符優(yōu)先分析,四則運算的優(yōu)先規(guī)則： 先乘除后加減，同級從左到右 考慮二義文法文法G(E)： G(E)： E i| E+E|E-E|E*E|E/E|(E) 它的句子有幾種不同的規(guī)范規(guī)約。 歸約即計算表達式的值。歸約順序不同，則計算的順序也不同，結果也不一樣。 如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是唯一的。,例如：句子i+i-i*(i+i),G(E)： E i| E+E|E-E|E*E|E/E|(E),返回,G(E)： E i| E+E|E-E

12、|E*E|E/E|(E),句子i+i-i*(i+i)的歸約過程是： (1) i+i-i*(i+i) (2) E+i-i*(i+i) (3) E+E-i*(i+i) (4) E-i*(i+i) (5) E-E*(i+i) (6) E-E*(E+i) (7) E-E*(E+E) (8) E-E*(E) (9) E-E*E (10) E-E (11) E,G(E)： E i| E+E|E-E|E*E|E/E|(E),句子i+i-i*(i+i)的歸約過程是： (1) i+i-i*(i+i) (2) F+i-i*(i+i) (3) T+i-i*(i+i) (4) E+i-i*(i+i) (5) E+F-

13、i*(i+i) (6) E+T-i*(i+i) (7) E-i*(i+i) (8) E-F*(i+i) (9) E-T*(i+i) (10) E-T*(F+i) (11) E-T*(T+i) (12) E-T*(E+i) (13) E-T*(E+F) (14) E-T*(E+T) (15) E-T*(E) (16) E-T*F (17) E-T (18) E,無二義文法： G(E)： E T |E+T|E-T T F |T*F|T/F F (E)|i,G(E)： E i| E+E|E-E|E*E|E/E|(E),起決定作用的是相鄰的兩個算符（終結符）之間的優(yōu)先關系。 所謂算符優(yōu)先分析法就是定義

14、算符（終結符）之間的某種優(yōu)先關系，借助于這種關系尋找“可歸約串”和進行歸約。,算符優(yōu)先分析的基本思想,定義任何兩個可能相繼出現(xiàn)的終結符a與b的三種優(yōu)先關系 a b a的優(yōu)先級低于b a b a的優(yōu)先級等于b a b a的優(yōu)先級高于b 注意：與數(shù)學上的=不同 + + （先歸約右邊的+） a b并不意味著b a，如 ( + 和 + (,優(yōu)先關系,算符優(yōu)先文法及優(yōu)先表構造,一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼(并列)的非終結符，即不含如下形式的產(chǎn)生式右部： QR 則我們稱該文法為算符文法。 約定： a、b代表任意終結符； P、Q、R代表任意非終結符； 代表由終結符和非終結符組成的任意序列

15、，包括空字。,假定G是一個不含-產(chǎn)生式的算符文法。對于任何一對終結符a、b，我們說： 1. a b，當且僅當文法G中含有形如Pab或PaQb的產(chǎn)生式；,2. a b，當且僅當G中含有形如PaR的產(chǎn)生式， 而R b或R Qb；,3. a b ，當且僅當G中含有形如PRb的產(chǎn)生式，而 R a或R aQ。,如果一個算符文法G中的任何終結符對(a，b)至多只滿足下述三關系之一： a b，a b， a b 則稱G是一個算符優(yōu)先文法。,G(E)： E i| E+E|E-E|E*E|E/E|(E) 不是一個算符優(yōu)先文法,G(E)： E T |E+T|E-T T F |T*F|T/F F (E)|i 是一個算

16、符優(yōu)先文法,例:考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 由規(guī)則(4)P(E) ，有 ( )； 由規(guī)則(1)EET和(2)TT*F， 有 *； 由(2) TT*F 和(3) FP F ，可得* ； 由(1)EE + T和E E+T，可得+ +； 由(3)FPF和F PF，可得 。 由(4)P(E)和 EE+TT+TT*F+TF*F+T PF*F+TiF*F+T 有 ( + ( * ( ( i。,優(yōu)先關系表,從算符優(yōu)先文法G構造優(yōu)先關系表的算法。 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a b的終結

17、符對。,確定滿足關系 和 的所有終結符對：,1. a b，當且僅當文法G中含有形如Pab或PaQb的產(chǎn)生式；,從算符優(yōu)先文法G構造優(yōu)先關系表的算法 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a b的終結符對。 為確定滿足關系 和 的所有終結符對： 首先需要對G的每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P)：,從算符優(yōu)先文法G構造優(yōu)先關系表的算法。 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a b的終結符對。 為確定滿足關系 和 的所有終結符對： 首先需要對G的每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P)：,從算符優(yōu)先文法G構造優(yōu)先關系

18、表的算法。 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a b的終結符對。 確定滿足關系 和 的所有終結符對： 首先需要對G的每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P)：,比較,比較,有了這兩個集合之后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關系 和 的所有終結符對。 假定有個產(chǎn)生式的一個候選形為 aP 那么，對任何bFIRSTVT(P)，有 a b。 假定有個產(chǎn)生式的一個候選形為 Pb 那么，對任何aLASTVT(P)，有 a b。,首先討論構造集合FIRSTVT(P)的算法。 按其定義，可用下面兩條規(guī)則來構造集合FIRSTVT(P)： 1. 若有產(chǎn)生式Pa或

19、PQa，則aFIRSTVT(P)；（直接從產(chǎn)生式看） 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。,構造集合FIRSTVT(P) 的算法,將對推導的遍歷轉(zhuǎn)換成對產(chǎn)生式的反復遍歷,數(shù)據(jù)結構： 布爾數(shù)組FP，a，使得FP，a為真的條件是，當且僅當aFIRSTVT(P)。開始時，按上述的規(guī)則(1)對每個數(shù)組元素FP，a賦初值。 棧STACK，把所有初值為真的數(shù)組元素FP，a的符號對(P，a)全都放在STACK之中。,構造集合FIRSTVT(P) 的算法,1. 若有產(chǎn)生式Pa或PQa，則aFIRSTVT(P)；（直接從產(chǎn)生式看） 2. 若aFIRSTVT(Q)，且有產(chǎn)生式

20、PQ，則aFIRSTVT(P)。,運算： 如果棧STACK不空，就將頂項逐出，記此項為(Q，a)。對于每個形如 PQ 的產(chǎn)生式，若FP，a為假，則變其值為真且將(P，a)推進STACK棧。 上述過程必須一直重復，直至棧STACK拆空為止。,1. 若有產(chǎn)生式Pa或PQa，則aFIRSTVT(P)；（直接從產(chǎn)生式看） 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。,構造集合FIRSTVT(P) 的算法,程序(包括一個過程和主程序)： PROCEDURE INSERT(P，a)； IF NOT FP，a THEN BEGIN FP，a:=TRUE； 把(P，a)下推進ST

21、ACK棧 END；,構造集合FIRSTVT(P) 的算法,1. 若有產(chǎn)生式P a或PQa，則aFIRSTVT(P)；（直接從產(chǎn)生式看） 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。,主程序： BEGIN FOR 每個非終結符P和終結符a DO FP，a:=FALSE； FOR 每個形如Pa或PQa的產(chǎn)生式 DO INSERT(P，a)； WHILE STACK 非空 DO BEGIN 把STACK的頂項，記為(Q，a)，上托出去； FOR 每條形如PQ的產(chǎn)生式 DO INSERT(P，a)； END OF WHILE； END,若有產(chǎn)生式Pa或PQa，則 aFIR

22、STVT(P)； 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ， 則 aFIRSTVT(P)。,這個算法的工作結果得到一個二維數(shù)組F，從它可得任何非終結符P的FIRSTVT。 FIRSTVT(P)a | FP，a=TRUE 同理，可構造計算LASTVT的算法。,構造集合LASTVT(P)的算法。 按其定義，可用下面兩條規(guī)則來構造集合LASTVT(P)： 1. 若有產(chǎn)生式P a或P aQ，則a LASTVT(P)； 2. 若a LASTVT(Q)，且有產(chǎn)生式P Q ，則a LASTVT(P)。,構造集合LASTVT(P) 的算法,例: 考慮下面的文法G(E)： (1) EE+T | T (2)

23、 TT*F | F (3) FP F | P (4) P(E) | i 計算文法G的FIRSTVT和LASTVT;,1. 若有產(chǎn)生式P a或PQa，則aFIRSTVT(P)；（直接從產(chǎn)生式看） 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。,1. 若有產(chǎn)生式P a或P aQ，則a LASTVT(P)； 2. 若a LASTVT(Q)，且有產(chǎn)生式P Q ，則a LASTVT(P)。,使用每個非終結符P的FIRSTVT(P)和LASTVT(P)，就能夠構造文法G的優(yōu)先關系表。構造優(yōu)先關系表的算法是： 通過檢查G的每個產(chǎn)生式的每個候選式，可找出所有滿足a b的終結符對；

24、通過檢查每個產(chǎn)生式的候選式確定滿足關系 和 的所有終結符對： 假定有個產(chǎn)生式的一個候選形為 aP 那么，對任何bFIRSTVT(P)，有 a b。 假定有個產(chǎn)生式的一個候選形為 Pb 那么，對任何aLASTVT(P)，有 a b。,構造優(yōu)先關系表的算法,如果考慮#，則考慮句型#S#,FOR 每條產(chǎn)生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均為終結符 THEN 置Xi Xi+1 IF in-2且Xi和Xi+2都為終結符 但Xi+1為非終結符 THEN 置Xi Xi+2； IF Xi為終結符而Xi+1為非終結符 THEN FOR FIRSTVT

25、(Xi+1)中的每個a DO 置 Xi a； IF Xi為非終結符而Xi+1為終結符 THEN FOR LASTVT(Xi)中的每個a DO 置 a Xi+1 END,例: 考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 1. 計算文法G的FIRSTVT和LASTVT; 2. 構造優(yōu)先關系表; 3. G是算符優(yōu)先文法嗎?,(1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i,結論: G是算符優(yōu)先文法,G的算符優(yōu)先關系表,第五章 語法分析自下而上分析,自下而上分析的

26、基本問題 算符優(yōu)選分析算法 計算FIRSTVT(P)和LASTVT(P)集合 構造算符優(yōu)先關系表 LR分析法,算符優(yōu)先分析算法,可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。 一個文法G的句型的素短語是指這樣一個短語，它至少含有一個終結符，并且，除它自身之外不再含任何更小的素短語。 最左素短語是指處于句型最左邊的那個素短語。,考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i,對于句型：T+F*P+i,短語： 直接短語： 句柄： 素短語： 最左素短語：, T+F*P+i,T, F, P, F*P, i,T+F*P,

27、T, F, P, i,T,F*P, i,F*P,算符優(yōu)先文法句型(括在兩個之間)的一般形式寫成： #N1a1N2a2NnanNn+1# 其中，每個ai都是終結符，Ni是可有可無的非終結符。 定理：一個算符優(yōu)先文法G的任何句型的最左素短語是滿足如下條件的最左子串 NjajNiaiNi+1， aj-1 aj aj aj+1，ai-1 ai ai ai+1,算符優(yōu)先分析算法 使用一個符號棧S，用它寄存終結符和非終結符，k代表符號棧S的使用深度。,k:=1; Sk:=#; REPEAT 把下一個輸入符號讀進a中； IF SkVT THEN j:=k ELSE j:=k-1; WHILE Sj a DO

28、 BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把Sj+1Sk歸約為某個N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*調(diào)用出錯診察程序*/ UNTIL a=#,自左至右，終結符對終結符，非終結符對非終結符，而且對應的終結符相同。 N X1 X2 Xk-j Sj+1 Sj+2 Sk,在算法的工作過程中，若出現(xiàn)j減1后的值小于等于0時，則意味著輸入串有錯。在正確的情況下，算法工作完畢時

29、，符號棧S應呈現(xiàn)：# N #。 由于非終結符對歸約沒有影響，因此，非終結符根本可以不進符號棧S。,算符優(yōu)先分析算法,對于文法的句子來說，它的算符優(yōu)先分析的結果(移進歸約所得到的分析樹)就是語法樹。 A.正確 B.錯誤 答案：B,分析樹 vs. 語法樹,自左至右，終結符對終結符，非終結符對非終結符，而且對應的終結符相同。 N X1 X2 Xk-j Sj+1 Sj+2 Sk,算符優(yōu)先分析一般并不等價于規(guī)范歸約。,考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的句子i+i*i+i,算符優(yōu)先分析法特點： 優(yōu)點: 簡單，

30、快速 缺點: 可能錯誤接受非法句子，能力有限. 算符優(yōu)先分析法是一種廣為應用、行之有效的方法。 用于分析各類表達式 ALGOL 60,算符優(yōu)先分析算法,優(yōu)先函數(shù),把每個終結符與兩個自然數(shù)f()與g()相對應，使得 若1 2，則f(1) g(2) f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。 優(yōu)點: 便于比較，節(jié)省空間； 缺點: 原來不存在優(yōu)先關系的兩個終結符，由于自然數(shù)相對應，變成可以比較的。要進行一些特殊的判斷。,文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的優(yōu)先函數(shù)如下表,討論：優(yōu)先函數(shù),對于任何無沖突優(yōu)先關系表都存在優(yōu)

31、先函數(shù)嗎？ A.是 B.不是,有許多優(yōu)先關系表不存在優(yōu)先函數(shù)，如：,不存在對應的優(yōu)先函數(shù)f和g 假定存在f和g，則有 f(a)=g(a)，f(a)g(b)， f(b)=g(a)，f(b)=g(b) 導致如下矛盾: f(a) g(b) = f(b) = g(a) = f(a),討論：優(yōu)先函數(shù),優(yōu)先函數(shù)如果存在，唯一嗎？ A.是 B.不是,如果優(yōu)先函數(shù)存在，則不唯一(無窮多),如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構造優(yōu)先函數(shù): 1 畫圖：對于每個終結符a，令其對應兩個符號fa和ga，畫一以所有符號和為結點的方向圖。如果a b，則從fa畫一條弧至gb，如果a b，則畫一條弧從gb至fa

32、。 2 數(shù)數(shù)：對每個結點都賦予一個數(shù)，此數(shù)等于從該結點出發(fā)所能到達的結點(包括出發(fā)點自身)。賦給fa的數(shù)作為f(a)，賦給ga的數(shù)作為g(a)。 3 驗證：檢查所構造出來的函數(shù)f和g是否與原來的關系矛盾。若沒有矛盾，則f和g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。,例:取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的終結符+，*，i,小結：,算符優(yōu)先分析算法 最左素短語 算符優(yōu)先函數(shù)及其構造方法,作業(yè)：,自學P121 典型例題及解答 作業(yè)：p122 ： 第 1題（前3小問必做，第4小問選擇其中一個輸入串的算符

33、優(yōu)先分析過程即可）； 第2題 第3題的第(2)小問 第4題的第（2）小問,第五章 語法分析自下而上分析,自下而上分析的基本問題 算符優(yōu)選分析算法 LR分析法,語法分析的方法： 自下而上分析法(Bottom-up) 基本思想： 從輸入串開始，逐步進行“歸約”，直到文 法的開始符號。即從樹末端開始，構造語法樹。 核心問題：確定可歸約串 算符優(yōu)先分析法：按照算符的優(yōu)先關系和結合性質(zhì)進行語法分析。適合分析表達式。 LR分析法：規(guī)范歸約(句柄作為可歸約串),回顧,LR分析法,LR分析法：1965年 由Knuth提出,分析表產(chǎn)生器,產(chǎn)生分析表,LR分析器工作,主要介紹,1. 總控程序(LR分析器)的處理思

34、想 2. LR分析表的構造方法及原理,短語、直接短語、句柄,定義：令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 且,則稱是句型相對于非終結符A的短語。 特別是，如果有A,則稱是句型相對于規(guī)則A 的直接短語。一個句型的最左直接短語稱為該句型的句柄。,在一個句型對應的語法樹中 以某非終結符為根的兩代以上的子樹的所有末端結點從左到右排列就是相對于該非終結符的一個短語 如果子樹只有兩代，則該短語就是直接短語。,短語、直接短語和句柄,定義：假定是文法G的一個句子，我們稱序列 n， n-1， ，0 是的一個規(guī)范歸約，如果此序列滿足： 1 n= 2 0為文法的開始符號，即0=S 3 對

35、任何i，0 i n， i-1是從i經(jīng)把句柄替換成為相應產(chǎn)生式左部符號而得到的。,規(guī)范歸約,LR分析器,規(guī)范歸約的關鍵問題是尋找句柄. “歷史”：已移入符號棧的內(nèi)容 “展望”：根據(jù)產(chǎn)生式推測未來可能遇到的輸入符號 “現(xiàn)實”：當前的輸入符號,LR分析方法：把歷史及展望綜合抽象成狀態(tài)；由棧頂?shù)臓顟B(tài)和現(xiàn)行的輸入符號唯一確定每一步工作,LR分析 程 序,LR分析器的核心是一張分析表： ACTIONs，a：當狀態(tài)s面臨輸入符號a時，應采取什么動作. GOTOs，X：狀態(tài)s面對文法符號X時，下一狀態(tài)是什么,LR分析器,LR分析器,移進(shift) 把(s，a)的下一狀態(tài)s和輸入符號a推進棧，下一輸入符號變

36、成現(xiàn)行輸入符號.,LR分析器,歸約(reduce)指用某產(chǎn)生式A進行歸約. 假若的長度為r， 歸約動作是， 去除棧頂r個項，使狀態(tài)sm-r變成棧頂狀態(tài)，然后把(sm-r, A)的下一狀態(tài)s=GOTOsm-r, A和文法符號A推進棧.,LR分析器,接受(acc)宣布分析成功，停止分析器工作.,LR分析器,報錯,分析開始時: 狀態(tài) 已歸約串 輸入串 (s0， #， a1a2 an #) 以后每步的結果可以表示為: (s0 s1 sm ，# X1 Xm ，aiai+1 an #),(s0 s1 sm ，# X1 Xm ，aiai+1 an #) 分析器根據(jù)ACTION(sm , ai)確定下一步動作

37、 1. 若ACTION(sm , ai)為移進，且s=GOTO(sm, ai),，則三元式格局變?yōu)? (s0 s1 sms ，# X1 Xm ai，ai+1 an #) 2. 若ACTION(sm , ai)為按A歸約，三元式變?yōu)? (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #) 此處, s=GOTO(sm-r, A), r為的長度, = Xm-r+1 Xm 3. 若ACTION(sm , ai)為接受，則三元式不再變化，變化過程終止，宣布分析成功. 4. 若ACTION(sm , ai)為報錯，則三元式變化過程終止，報告錯誤.,(s0 s1 sm-r sm-r+

38、1 sm ，# X1 Xm-r Xm-r+1 Xm ，aiai+1 an #) (s0 s1 sm-r ，# X1 Xm-r，aiai+1 an #) (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #),LR分析器示例：,文法G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,其LR分析表為:,假定輸入串為i*i+i， LR分析器的工作過程: 步驟狀態(tài)符號輸入串 (1)0#i*i+i# (2)05#i*i+i# 0 # *i+i# (3)03#F*i+i# 0 # *i+i# (4)02#T*i+i# (5)027

39、#T*i+i#,i,*,G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,假定輸入串為i*i+i， LR分析器的工作過程: 步驟狀態(tài)符號輸入串 (5)027#T*i+i# (6)0275#T*i+i# 027 #T*+i# (7)02710#T*F+i# 0 # +i# (8)02#T+i#,i,G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,假定輸入串為i*i+i， LR分析器的工作過程: 步驟狀態(tài)符號輸入串 (8)02#T+i# 0#+i# (9)01#E+i# (10)016

40、#E+i# (11)0165#E+i#,+,i,i,G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,步驟狀態(tài)符號輸入串 (11) 0165#E+i# 016#E+# (12)0163#E+F# 016#E+# (13)0169#E+T#,+,i,i,G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,步驟狀態(tài)符號輸入串 (13)0169#E+T# 0 # # (14)01#E# (15) 接受,+,i,i,G(E)： (1) EET,定義：對于一個文法，如果能夠構造一張分析表，使得它

41、的每個入口均是唯一確定的，則這個文法就稱為LR文法。 定義：一個文法，如果能用一個每步頂多向前檢查k個輸入符號的LR分析器進行分析，則這個文法就稱為LR(k)文法.,LR文法,LR文法不是二義的，二義文法肯定不會是LR的。 非LR結構 S iCtS | iCtSeS 棧 輸入 iCtS e#,LR文法與二義文法,LR分析器的工作原理 LR分析器的性質(zhì) 棧內(nèi)的符號串和掃描剩下的輸入串構成了一個規(guī)范句型； 一旦棧的頂部出現(xiàn)可歸約串(句柄)，則進行歸約；,小結,第五章 語法分析自下而上分析,自下而上分析的基本問題 算符優(yōu)選分析算法 LR分析法 LR分析器的工作原理 LR(0)項目集規(guī)范族的構造,回顧

42、,假定是文法G的一個句子，我們稱序列 n， n-1， ，0 是的一個規(guī)范歸約，如果此序列滿足： 1 n= 2 0為文法的開始符號，即0=S 3 對任何i，0 i n， i-1是從i經(jīng)把句柄替換成為相應產(chǎn)生式左部符號而得到的。,回顧,規(guī)范歸約過程中 棧內(nèi)的符號串和掃描剩下的輸入符號串構成了一個規(guī)范句型 規(guī)范歸約過程中，下面哪種格局不會出現(xiàn)？ 棧內(nèi)的如果出現(xiàn)句柄，句柄一定在棧的頂部,棧內(nèi)永遠不會出現(xiàn)句柄之后的符號！,字的前綴、活前綴,字的前綴：是指字的任意首部，如字abc的前綴有，a，ab，abc 活前綴：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。即，對于規(guī)范句型，為句柄，如果=u1

43、u2ur，則符號串u1u2ui(1ir)是的活前綴。(必為終結符串)。 規(guī)范歸約過程中，保證分析棧中總是活前綴，就說明分析采取的移進/歸約動作是正確的,指導思想目標驅(qū)動,踢足球 “如果你不知道怎樣踢球，就往球門方向踢 ” 施拉普納 LR分析 “如果你不知道怎樣分析，就保證棧中總是活前綴”,哪些字符串是活前綴? 能不能構造一個DFA來識別活前綴? 回答：對于一個文法G，可以構造一個DFA，它能識別G的所有活前綴。,文法G的每個產(chǎn)生式的右部添加一個圓點稱為G的LR(0)項目 如:AXYZ有四個項目： A.XYZ AX.YZ AXY.Z AXYZ. A . 稱為歸約項目 歸約項目 S . 稱為接受項

44、目 A .a (aVT) 稱為移進項目 A .B (BVN) 稱為待約項目. 項目表示我們在分析過程中看到了產(chǎn)生式多大部分,LR(0)項目集族和LR(0)分析表的構造,文法G(S) SE EaA|bB AcA|d BcB|d 該文法的項目有： 1. SE2. SE3. EaA 4. EaA5. EaA6. AcA 7. AcA8. AcA9. Ad 10. Ad11. EbB12. EbB 13. EbB14. BcB15. BcB 16. BcB17. Bd18. Bd,構造識別文法所有活前綴的NFA方法 1. 若狀態(tài)i為XX1 Xi-1.Xi Xn ， 狀態(tài)j為XX1 Xi-1Xi .Xi

45、+1 Xn ， 則從狀態(tài)i畫一條標志為Xi的有向邊到狀態(tài)j； 2. 若狀態(tài)i為X .A ，A為非終結符， 則從狀態(tài)i畫一條邊到所有狀態(tài)A.。 把識別文法所有活前綴的NFA確定化。,識別活前綴的NFA,識別活前綴的DFA,構成識別一個文法活前綴的DFA的項目集(狀態(tài))的全體稱為文法的LR(0)項目集規(guī)范族。,LR(0)項目集規(guī)范族,有效項目,我們說項目A 1.2對活前綴1是有效的，其條件是存在規(guī)范推導,在任何時候，分析棧中的活前綴X1X2 Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。也正是從識別活前綴的DFA的初態(tài)出發(fā)，讀出X1X2 Xm后到達的那個項目集(狀態(tài))。,結論: 若項目A .B

46、對活前綴=是有效的且B 是一個產(chǎn)生式，則項目B .對=也是有效的。,文法G(S) SE EaA|bB AcA|d BcB|d 考慮： 項目：B c.BB . cB B . d 活前綴：bc S E bB bcB S E bB bcB bccB S E bB bcB bcd,項目A 1.2對活前綴1是有效的，其條件是存在規(guī)范推導,LR(0)項目集規(guī)范族的構造,假定文法G，以S為開始符號 構造一個G，它包含了整個G，但它引進了一個不出現(xiàn)在G中的非終結符S，并加進一個新產(chǎn)生式SS，S是G的開始符號。 稱G是G的拓廣文法。 G唯一的“接受”態(tài)：僅含項目SS.的狀態(tài),假定I是文法G的任一項目集，定義和構

47、造I的閉包CLOSURE(I)如下： 1. I的任何項目都屬于CLOSURE(I)； 2. 若AB屬于CLOSURE(I)，那么，對任何關于B的產(chǎn)生式B，項目B也屬于CLOSURE(I)； 3. 重復執(zhí)行上述兩步驟直至CLOSURE(I) 不再增大為止。,回顧：NFA確定化 設I是的狀態(tài)集的一個子集，定義I的-閉包-closure(I)為: i) 若sI，則s-closure(I)； ii) 若sI，則從s出發(fā)經(jīng)過任意條弧而能到達的任何狀態(tài)s都屬于-closure(I) -closure(I)=Is|從某個sI出發(fā)經(jīng)過任意條弧能到達s,2. 若狀態(tài)i為X .A ，A為非終結符， 則從狀態(tài)i畫一

48、條邊到所有狀態(tài)A.。,為了識別活前綴，我們定義一個狀態(tài)轉(zhuǎn)換函數(shù)GO是一個狀態(tài)轉(zhuǎn)換函數(shù)。I是一個項目集，X是一個文法符號。函數(shù)值GO(I，X)定義為： GO(I，X)CLOSURE(J) 其中 J任何形如AX的項目| A X屬于I。 直觀上說，若I是對某個活前綴 有效的項目集，那么，GO(I，X)便是對 X 有效的項目集。,回顧：設a是中的一個字符，定義 Ia= -closure(J) 其中，J為I中的某個狀態(tài)出發(fā)經(jīng)過一條a弧而到達的狀態(tài)集合。,文法G(S) SE EaA|bB AcA|d BcB|d I0=SE, EaA, EbB GO(I0, E)= closure(J)=closure(S

49、E) = SE = I1 GO(I0, a)= closure(J)=closure(EaA) = EaA, AcA, Ad )=I2 GO(I0, b)= closure(J)=closure (E b.B) =E b.B, B.cB, B.d= I3,構造文法G的拓廣文法G的LR(0)項目集規(guī)范族算法： PROCEDURE ITEMSETS(G)； BEGIN C:=CLOSURE(SS)； REPEAT FOR C中每個項目集I和G的每個符號X DO IF GO(I，X)非空且不屬于C THEN 把GO(I，X)放入C族中; UNTIL C不再增大 END 轉(zhuǎn)換函數(shù)GO把項目集連接成一個

50、DFA轉(zhuǎn)換圖.,0: SE EaA EbB,4: AcA AcA Ad,5: BcB BcB Bd,3: EbB BcB Bd,1: SE,2: EaA AcA Ad,11: Bd,8: AcA,10: Ad,9: BcB,6: EaA,7: EbB,文法G (S): SE EaA|bB AcA|d BcB|d,兩種構造識別活前綴的DFA的方法：,1.項目-NFA-DFA 2.Closure-GO-DFA,小結：,規(guī)范歸約過程中，保證分析棧中總是活前綴，就說明分析采取的移進/歸約動作是正確的 哪些字符串是活前綴?能不能構造一個DFA來識別活前綴? 兩種構造識別活前綴的DFA的方法： 1.項目-

51、NFA-DFA 2.Closure-GO-DFA,第五章 語法分析自下而上分析,自下而上分析的基本問題 算符優(yōu)選分析算法 LR分析法 LR(0)項目集規(guī)范族和LR(0)分析表的構造 SLR分析表的構造,LR(0)分析表的構造,假若一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況： 1) 既含移進項目又含歸約項目， 2) 含有多個歸約項目 則稱G是一個LR(0)文法。,0: SE EaA EbB,4: AcA AcA Ad,5: BcB BcB Bd,3: EbB BcB Bd,1: SE,2: EaA AcA Ad,11: Bd,8: AcA,10: Ad,9: B

52、cB,6: EaA,7: EbB,文法G (S): SE EaA|bB AcA|d BcB|d,構造LR(0)分析表的算法,令每個項目集Ik的下標k作為分析器的狀態(tài)，包含項目SS的集合Ik的下標k為分析器的初態(tài)。,在任何時候，分析棧中的活前綴X1X2 Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。也正是從識別活前綴的DFA的初態(tài)出發(fā)，讀出X1X2 Xm后到達的那個項目集(狀態(tài))。,LR(0)分析表的ACTION和GOTO子表構造方法： 1. 若項目Aa屬于Ik且GO(Ik, a)Ij，a為終結符，則置ACTIONk,a 為“sj”。 2. 若項目A屬于Ik，那么，對任何終結符a(或結束符#

53、)，置ACTIONk,a為 “rj”(假定產(chǎn)生式A是文法G的第j個產(chǎn)生式)。 3. 若項目SS屬于Ik，則置ACTIONk,#為 “acc”。 4. 若GO(Ik,A)Ij，A為非終結符，則置GOTOk,A=j。 5. 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報錯標志”。,文法G(S) SE EaA|bB AcA|d BcB|d,識別活前綴的DFA,LR(0)分析表為,例: 按上表對acccd進行分析 步驟狀態(tài)符號輸入串 10#acccd# 202#acccd# 3024#acccd# 40244#acccd#,文法G(S) SE EaA|bB AcA|d BcB|d,步驟狀態(tài)符號輸

54、入串 40244#acccd# 502444#acccd# 60244410#acccd# 7024448#acccA# 802448#accA#,文法G(S) SE EaA|bB AcA|d BcB|d,步驟狀態(tài)符號輸入串 802448#accA# 90248#acA# 10026#aA# 1101#E#,文法G(S) SE EaA|bB AcA|d BcB|d,SLR分析表的構造,LR(0)文法太簡單，沒有實用價值. 假定一個LR(0)規(guī)范族中含有如下的一個項目集(狀態(tài))IXb，A，B。FOLLOW(A)和FOLLOW(B)的交集為，且不包含b，那么，當狀態(tài)I面臨任何輸入符號a時，可以:

55、1. 若a=b，則移進； 2. 若aFOLLOW(A)，用產(chǎn)生式A進行歸約； 3. 若aFOLLOW(B)，用產(chǎn)生式B進行歸約； 4. 此外，報錯。,假定LR(0)規(guī)范族的一個項目集I=A1a11，A2a22，Amamm，B1，B2，Bn 如果集合a1，am，F(xiàn)OLLOW(B1)，F(xiàn)OLLOW(Bn)兩兩不相交(包括不得有兩個FOLLOW集合有#)，則： 1. 若a是某個ai，i=1,2,m，則移進； 2. 若aFOLLOW(Bi)，i=1,2,n，則用產(chǎn)生式Bi進行歸約； 3. 此外，報錯。 沖突性動作的這種解決辦法叫做SLR(1)解決辦法。,構造SLR(1)分析表方法: 首先把G拓廣為G，

56、對G構造LR(0)項目集規(guī)范族C和活前綴識別自動機的狀態(tài)轉(zhuǎn)換函數(shù)GO. 然后使用C和GO，按下面的算法構造SLR分析表： 令每個項目集Ik的下標k作為分析器的狀態(tài)，包含項目SS的集合Ik的下標k為分析器的初態(tài)。,SLR(1)分析表的ACTION和GOTO子表構造方法： 1. 若項目Aa屬于Ik且GO(Ik,a)=Ij，a為終結符，則置ACTIONk,a為 “sj”； 2. 若項目A屬于Ik，那么，對任何終結符a，aFOLLOW(A)，置ACTIONk,a為 “rj”；其中，假定A為文法G的第j個產(chǎn)生式； 3. 若項目SS屬于Ik，則置ACTIONk,#為“acc”; 4. 若GO(Ik,A)I

57、j，A為非終結符，則置GOTOk,A=j； 5. 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標志”。,LR(0)分析表的ACTION和GOTO子表構造方法： 1. 若項目Aa屬于Ik且GO(Ik, a)Ij，a為終結符，則置ACTIONk,a 為“sj”。 2. 若項目A屬于Ik，那么，對任何終結符a(或結束符#)，置ACTIONk,a為 “rj”(假定產(chǎn)生式A是文法G的第j個產(chǎn)生式)。 3. 若項目SS屬于Ik，則置ACTIONk,#為 “acc”。 4. 若GO(Ik,A)Ij，A為非終結符，則置GOTOk,A=j。 5. 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報錯

58、標志”。,按上述方法構造出的ACTION與GOTO表如果不含多重入口，則稱該文法為SLR(1)文法。 使用SLR表的分析器叫做一個SLR分析器。 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.,SLR(1)文法,例5.11 考察下面的拓廣文法： (0) SE (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,這個文法的LR(0)項目集規(guī)范族為：,I0: SE EE+T ET TT*F TT*F TF F (E) Fi,I1: SE EE+T,I2: ET TT*F,I3: TF,I4: F(E) EE+T ET TT*F TF F (E) Fi,I5 :Fi,I6: EE+T TT*F TF F(E) Fi,I7: TT*F F(E) Fi,I8: F(E) EE+T,I9: EE+T TT