【文章內容簡介】 個數(shù)組元素 F[A， a]賦初值，并對數(shù)組元素 F[A， a]初值為真的符號對 (A． a)都放入棧中，然后對棧做如下運算。 ? 當棧不空時，就將棧頂項彈出，并記為 (B， a)， 再用規(guī)則 2， 若F[A， a]為假，則使其變?yōu)檎?，且?(A， a)推進棧，如此重復直到棧折空為止。 ? 程序描述 ? 示例 程序描述 ? 將置為真的操作： PROCEDURE INSERT(A． a)。 IF NOT F[A， a] THEN BEGIN F[A． a]：＝ TRUN PUSH(A． a) 0NT0 STRACK END ?主程序： BEGIN(MAIN) FOR 每一個非終結符 A和終結符 a， DO F[A， a]：＝ FALSE； FOR 每個形如 A?a或 A?Ba… 的產生式 DO INSERT(A， a) WHILE STACK非空 DO BEGIN 把 STACK的頂項記為 (B， a)托出去 FOR 每個形如 A? B… 的產生式 Do INSERT(A ， a) END END 算法計算示例 文法 G[E]： (0) E’→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→P?F|P (6) P→(E) (7) P→i 首次掃描 STRACK的初值： (6) (P,i) (5) (P,( ) (4) (F,?) (3) (T,*) (2) (E,+) (1)( E’,) 棧頂（ 6）的改變： F?P ( F,i) T?F (T,i) E?T (E,i) 由于無右部以 E開始的產生式，所以 (E,i)彈出后無進棧項，此時當前的棧頂為(P,( ) 。 棧頂（ 5）的改變： F?P ( F,( ) T?F (T,( ) E?T (E,( ) (E,（ )彈出后無進棧項，此時當前的棧頂為 (F, ? )。 棧頂（ 4）的改變： T?F (T, ? ) E?T (E, ? ) (E, ? )彈出后無進棧項，此時當前的棧頂為 (T, * )。棧頂（ 3）的改變： E?T (E, * ) 以下逐次彈出棧頂元素后，都再無進棧項，直至?？?。 + * ↑ i ( ) E’ 1 E 1 1 1 1 1 T 1 1 1 F 1 1 1 P 1 1 FIRSTVT(E’)={} FIRSTVT(E)={+,*,?,(,i} FIRSTVT(T)={*,?,(,i} FIRSTVT(F)={?,(,i} FIRSTVT(P)={(,i} 關系圖計算算符優(yōu)先關系 ? 關系圖的構造方法 ? 圖中的結點為非終結符的 FIRSTVT(A)和終結符 。 ? 對每一個形如 A?a… 或 A?Ba… 的產生式，則構造由 FIRSTVT(A)結點到終結符結點 (a)用箭弧連接的圖形； ? 對每一個形如 A?B… 的產生式，則對應圖中由FIRSTVT(A)結點到 FIRSTVT(B)結點用箭弧連接； ? 對每一非終結符的 FIRSTVT(A) 經箭弧有路徑能到達的終結符結點 (a) ，則有 a? FIRSTVT(A)。 ? 示例 關系圖計算示例 FIRSTVT(E’) FIRSTVT(E) FIRSTVT(T) FIRSTVT(F) FIRSTVT(P) + * ? ( ) 文法 G[E]： (0) E’→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→P?F|P (6) P→(E) (7) P→i 由關系圖法計算算符優(yōu)先關系 ? 文法符號的關系定義 ? 優(yōu)先關系與符號關系之間的聯(lián)系 ? 算符關系構造規(guī)則 ? ?的關系構造規(guī)則 ? ?的關系構造規(guī)則 ? 示例 ? 文法符號之間的關系 ? 文法終結符之間的 ?關系圖 ? 文法終結符之間的 ?關系圖 文法符號的關系定義（ ） ? 設 G=(VN， VT， P， S)是一個上下文無關文法，則： ? A FIRST B 當且僅當存在形如 A?B?的產生式； ? A LAST B 當且僅當存在形如 A??B的產生式； ? B FIRSTTERM b 當且僅當存在形如 B?b?或 B?Cb?的產生式； ? B LASTTERM a 當且僅當存在形如 B??a或 B??aC的產生式； ? X FOLLOWEDBY Y 當且僅當存在形如 A??XY?的產生式，中必須是一個為終結符，另一個為非終結符； ? A FIRST* B 當且僅當存在形如 A?B或存在 A?X1?，X1?X2?， ?， Xn1?Xn?， Xn?B?的產生式序列 ； ? A LAST* B當且僅當存在形如 B?A或存在 A??X1，X1??X2， ?， Xn1??Xn， Xn??B的產生式序列。 優(yōu)先關系與符號關系之間的聯(lián)系 ? a?b?a FOLLOWEDBY B B FIRST* P P FIRSTTERM b ? a?b?存在形如 A? ?aB?的產生式 ,其中 B?+b?或 B?+Cb? ? 而 B?+b?可寫成 B?*P? ?b? ? B?+Cb?可寫成 B?*P? ?Cb? ? 所以 B?+b?或 B?+Cb? ?B FIRST* P P FIRSTTERM b ? a?b ?(B LAST* P P LASTTERM a)T B FOLLOWEDBY b ? a?b?存在形如 A? ?Bb?的產生式 ,其中 B?+a?或 B?+aC? ? 而 B?+ ? a可寫成 B?* ? P ? ?a ? B?+ ? aC可寫成 B?* ? P ? ?aC ? 所以 B?+ ? a或 B?+ ? aC ?B LAST* P P LASTTERM a ? 的關系構造規(guī)則 ? 凡有終結符在前非終結符在后相鄰關系的，則由終結符結點到非終結符結點畫一箭弧。 ? 對有 FIRSTTERM關系的非終結符和終結符對，則從非終結符結點到終結符點畫一箭弧。 ? 對非終結符對之間存在 FIRST關系的，從左邊的非終結符結點到右邊的非終結符結點畫一箭弧。 ? 對每個終結符結點 a凡有路徑能到達另一終結符結點 b的，則有 a?b關系存在。 ?的關系構造規(guī)則 ? 對非終結符和終結符相鄰關系的，由非終結符結點到終結符結點畫一箭弧。 ? 對有 LASTTERM關系的，由終結符結點到非終結符結點畫一箭弧。 ? 對 LAST關系的非終結符對，由后面的非終結符結點到前面的非終結符結點畫一箭弧。 ? 對每個終結符結點 a凡有路徑能到達另一終結符結點 b的，則有 a?b的關系成立。 文法符號之間的關系 E LAST T T LAST F F LAST F F LAST P FIRST關系有 E FIRST E