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