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