【正文】 優(yōu)先關(guān)系矩陣 FIRSTVT( B )={b|B?b… 或 B?Cb…,b ∈ Vt, B∈ Vn} + + LASTVT( B )={a|B?…a 或 B?…aC,a ∈ Vt, B∈ Vn} + + ?求 “ = ” 檢查每一條規(guī)則，若有 A::=… ab… 或 A::=… aBb…, 則 a=b . . ?求“ ”、“ ”復(fù)雜一些，需定義兩個(gè)集合 . . 23 ?求“ ”、“ ”: . . 若文法有規(guī)則 A→...aB... ，對任何 b, b∈ FIRSTVT(B) 則有： a b . 若文法有規(guī)則 A→...Bb... ，對任何 a, a∈ LASTVT(B) 則有： a b . 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 求每個(gè)非終結(jié)符號(hào)的 FIRSTVT及 LASTVT FIRSTVT LASTVT E {+,*,(,i} {+.*,),i} T {*,(,i } {*,),i} F {(,i} {),i} 求 =關(guān)系： (=) 求 關(guān)系： +FIRSTVT(T),*FITSTVT(F),(FIRSTVT(E) 求 關(guān)系：LASTVT(E)+,LASTVT(T)*,LASTVT(E)) ) = ( i * + ) ( i * + b(右棧外 ) a(右棧內(nèi) ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 構(gòu)造優(yōu)先關(guān)系表： 26 構(gòu)造 FIRSTBT(A)的算法 1)若有規(guī)則 A→b… 或 A→Bb…( 存在 A?b… 或 A?Bb…) 則 b∈ FIRSTVT(A) + + 2)若有規(guī)則 A→B… 且 b∈ FIRSTVT(B), 則 b∈ FIRSTVT(A) 說明 :因?yàn)?B?b… 或 B?Cb…, 所以有 A?B… ?b… 或 A?B… ?Cb… + + + + 27 設(shè)一個(gè)棧 S和一個(gè)二維布爾數(shù)組 F F[A,b]=TRAE iff b∈ FIRSTVT(A) PROCEDBRE INSERT(A,b) IF NOT F[A,b] THEN BEGIN F[A,b]:=TRAE 把 (A,b)推進(jìn) S棧 /* b∈ FIRSTVT(A) */ END BEGIN {main} FOR 每個(gè)非終結(jié)符號(hào) A和終結(jié)符 b DO F[A,b]:=FALSE /*賦值符 */ FOR 每個(gè)形如 A::=b… 或 A::=Bb… 的規(guī)則 DO INSERT(A,b) 具體方法如下 : 28 WHILE S棧非空 DO BEIGN 把 S棧的頂項(xiàng)彈出 ,記為 (B,b)/* b∈ FIRSTVT(A)*/ FOR 每條形如 A::=B… 的規(guī)則 DO INSTER(A,b)。 /* b∈ FIRSTVT(A)*/ END OF WHILE END 上述算法的工作結(jié)果是得到一個(gè)二維的布爾數(shù)組 F,從 F 可以得到任何非終結(jié)符號(hào) A的 FIRSTVT FIRSTVT(A)={b|F[A,b]=TRAE} 29 構(gòu)造 LASTBT(A)的算法 A::=…a 或 A::==…aB, 則 a∈ LASTVT(A) A::=…B, 且 a∈ LASTVT(B)則 a∈ LASTVT(A) 設(shè)一個(gè)棧 ST,和一個(gè)布爾數(shù)組 B PROCEDARE INSERT(A,a) IF NOT B[A,a] THEN BEGIN B[A,a]::=TRAE。把 (A,a)推進(jìn) ST棧 。 END。 30 BEGIN FOR 每個(gè)非終結(jié)符號(hào) A和終結(jié)符號(hào) a DO B[A,a]:=FALSE。 FOR 每個(gè)形如 A::=…a 或 A::=…aB 的規(guī)則 DO INSERT (A,a)。 WHILE ST棧非空 DO BEGIN 把 ST棧的棧頂彈出 ,記為 (B,a)。 FOR 每條形如 A::=…B 的規(guī)則 DO INSERT(A,a)。 END OF WHILE。 END。 31 構(gòu)造優(yōu)先關(guān)系矩陣的算法 FOR 每條規(guī)則 A::=x1x2…x n DO FOR i:=1 TO n1 DO BEGIN IF xi和 xi+1均為終結(jié)符 ,THEN 置 xi=xi+1 IF i≤n2，且 xi和 xi+2都為終結(jié)符號(hào)但 xi+1為非終結(jié)符號(hào) THEN 置 xi=xi+2 IF xi為終結(jié)符號(hào) xi+1為非終結(jié)符號(hào) THEN FOR FIRSTVT(xi+1)中的每個(gè) b DO 置 xib IF xi為非終結(jié)符號(hào) xi+1為終結(jié)符號(hào) THEN FOR LASTVT(xi)中的每個(gè) a DO 置 axi+1 END . . . . 32 （ 3）算符優(yōu)先分析算法的實(shí)現(xiàn) . 先定義優(yōu)先級，在分析過程中通過比較相鄰運(yùn)算符之間的優(yōu)先級來確定句型的“句柄”并進(jìn)行歸約 . [定義 ] 素短語：文法 G的句型的素短語是一個(gè)短語，它至少包含有一個(gè)終結(jié)符號(hào)，并且除它自身以外不再包含其他素短語 . 最左素短語 ？ 33 文法的語法樹 : E T E + T + T T F * F i E 短語 :T+T*F+i, T+T*F T(最左 ), T*F, i 其中 T不包含終結(jié)符 ,T是句型 而 T+T*F+i和 T+T*F包含其他 素短語 . 只有 T*F和 i為素短語 ,其中 T*F為最左素短語 ,而該句型句柄為 T. 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 求句型 T+T*F+i 的素短語 34 于是算符優(yōu)先分析法：如何確定當(dāng)前句型的最左素短語？ 設(shè)有 OPG文法句型為 : N1a1N2a2…N nanNn+1 其中 Ni為非終結(jié)符 (可以為空 ), ai為終結(jié)符 定理 ：一個(gè) OPG句型的最左素短語是滿足下列條件的 最左子串： aj1Njaj…N iaiNi+1ai+1 其中 aj1aj aj=aj+1, aj+1= aj+2 ,…, a i2= ai1, ai1= ai ai ai+1 . . . . . . 35 根據(jù)該定理 ,要找句型的最左素短語就是要找滿足 上述條件的最左子串 . 注意 :出現(xiàn)在 aj左端和 a i右端的非終結(jié)符號(hào)一定屬于這個(gè)素短語 ,因?yàn)槲覀兊倪\(yùn)算是中綴形式給出的(OPG文法的特點(diǎn) )NaNaNaN ?NaWaN 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 分析文法的句型 T+T*F+i 36 可以看出 : 1. 每次 規(guī)約 最左子串 ,確實(shí)是當(dāng)前句型的 最左素短語(語法樹） 2. 規(guī)約的不都是真句柄（僅 i規(guī)約為 F是句柄，但它是最左短語 ) 3. 沒有完全按規(guī)則進(jìn)行規(guī)約 ,因?yàn)?素短語不一定是簡單短語 步驟 句型 關(guān)系 最左子串 規(guī)約符號(hào) 1 2 3 4 T+T*F+i T+T+i E+i E+F +*+i ++i +i + T*F T+T i E+F T E E F . . . . . . . . . . . . . . 37 算符優(yōu)先分析法的實(shí)現(xiàn)： 詳見講義，基本部分是找句型的最左子串（最左素短語） 并進(jìn)行規(guī)約。 分析程序 優(yōu)先關(guān)系矩陣 符號(hào)棧 輸入串 當(dāng)棧內(nèi)終結(jié)符的優(yōu)先級＜＝棧外的終結(jié)符的優(yōu)先級時(shí)，移進(jìn)；棧內(nèi)終結(jié)符的優(yōu)先級＞棧外的終結(jié)符的優(yōu)先級時(shí)，移進(jìn)。表明找到了素短語的尾，再往前找其頭，并進(jìn)行規(guī)約。 優(yōu)先函數(shù) 為了節(jié)約存儲(chǔ)空間和便于執(zhí)行比較運(yùn)算 ?，用兩個(gè)優(yōu)先函數(shù) f和 g，它們是從終結(jié)符號(hào)映射到整數(shù)的函數(shù)。對于終結(jié)符號(hào) a和 b選擇 f和 g,使之滿足： 1. 當(dāng) a=b時(shí) , f(a)= g(b)。 2 .當(dāng) a＜ b 時(shí) , f(a)＜ g(b)。 3. 當(dāng) a＞ b時(shí) , f(a)＞ g(b)。 于是 a和 b之間的優(yōu)先關(guān)系可以由比較 f(a)與g(b)的大小來決定。 算法 : 從優(yōu)先關(guān)系構(gòu)造優(yōu)先函數(shù) 方法： ∈ VT∪ {},建立兩個(gè)符號(hào) fa和 ga。 a = b, 從 fa至 gb畫一條??；也從 gb至 fa畫 一條弧 ， b ∈ VT，