《程序设计语言与编译》课程PPT教学课件（高职）第十六讲 优先关系表的构造

5优先关系表的构造 (1) FIRSTVT集 FIRSTVT(P)aPa.,或PQaa∈VnQ∈V} 若P→>a.或P→>Qa,则a∈ FIRSTVT(P 若P→>Q…,则 FIRSTVT(Q∈ FIRSTVT(P; 直至 FIRSTVT(P)不再增大

5. 优先关系表的构造 (1)FIRSTVT集 FIRSTVT(P)={a|Pa…,或PQa…,aVT ,Q VN} 若P→a…或P→Qa…, 则aFIRSTVT(P); 若P→Q…, 则FIRSTVT(Q)FIRSTVT(P); 直至FIRSTVT(P)不再增大。 + +

(2 ASTVt集 LASTVT(P)={aPa或P.aQa∈V1Q∈V} 若P>.a或P→>.aQ,则a∈ LASTVT(P), 若P→>.Q,则 LASTVT( QCLASTVT(P); 直至 LASTVT(P)不再增大

(2)LASTVT集 LASTVT(P)={a|P...a,或P…aQ,aVT ,Q VN} 若P→...a或P→…aQ, 则aLASTVT(P); 若P→...Q, 则LASTVT(Q)LASTVT(P); 直至LASTVT(P)不再增大。 + +

之例G(E)E→B+TT T→T*FF F→(E) FIRSTVT LASTVT E + T F

例 G(E) E→E+T│T T→T*F│F F→(E) │i E T F FIRSTVT LASTVT ( i + * ( i ) i + * ) i * ) i ( i *

(3)构造优先关系表的算法 FOR每条产生式PX1X2XnDO FOR i: =1 TO n-1 DO BEGIN IFX和X均为终结符 THEN X=X+1; IFi<=n-2且X和X2均为终结符但X∈ EVN THEN X-Xi+2 IFX∈VnX+1∈VN then Va∈ FIRSTVT(X1)≤a; FXEVN ∈VT THEN VaELASTVT(Xi a>Xi+ END

(3)构造优先关系表的算法 FOR 每条产生式P→X1X2…Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN Xi= Xi+1; IF i<=n-2 且 Xi和Xi+2均为终结符 但 XiVN THEN Xi=Xi+2; IF XiVT , Xi+1VN THEN aFIRSTVT(Xi+1) Xi<a; IF XiVN, Xi+1VT THEN aLASTVT(Xi ) a>Xi+1 END;

之例G(E)E→B+TT T→T*FF F→(E) FIRSTVT LASTVT E + T F 考察E→E+T中的E和+、+和T 考察T→T*F中的和*、*和F 考察F→(E)中的(和E、(和)、E和)

例 G(E) E→E+T│T T→T*F│F F→(E) │i E T F FIRSTVT LASTVT ( i + * ( i ) i + * ) i * ) i ( i * 考察E→E+T中的E和+ 、 +和T 考察T→T*F中的T和* 、 *和F 考察F→(E)中的(和E 、 (和) 、 E和)