《程序设计语言与编译》课程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; IFiXi+ END

(3)构造优先关系表的算法 FOR 每条产生式P→X1X2…Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN Xi= Xi+1; IF iXi+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和)

算符优先关系表 $

+ + * * i i ( ( ) ) $ $ > > > > > > > > > > > > = = 算符优先关系表

LR分析法 1.LR(K)分析法 自底向上的LR分析法是指从左向右扫描 输入串,每次分析由分析栈中符号及向前 搜索K个输入符号以确定作为产生式右部 的短语(句柄)是否已在分析栈的栈顶形成, 从而决定应采取的动作。这种分析方法称 为LR(K)分析法。一般只考虑K的情况

二. LR分析法 1. LR(K) 分析法 自底向上的LR分析法是指从左向右扫描 输入串,每次分析由分析栈中符号及向前 搜索K个输入符号,以确定作为产生式右部 的短语(句柄)是否已在分析栈的栈顶形成, 从而决定应采取的动作。这种分析方法称 为LR(K)分析法。一般只考虑K1的情况

其组成为分析栈控制程序分析表输入串 输入串a1 a1 分析栈 驱动程序 输出 action goto 分析表

其组成为:分析栈,控制程序,分析表,输入串 输入串 分析栈 驱动程序 输出 action goto 分析表 s0 . . . sm-1 sm a1 ... ai ... $

2.分析栈 存放状态初始时置初始状态s栈里的 每一状态概括了从分析开始到某一时刻 已进行的分析工作

2. 分析栈 存放状态;初始时,置初始状态s0 ;栈里的 每一状态概括了从分析开始到某一时刻 已进行的分析工作

3.分析表 由 action[s,a]和 gotos, x]两个子表组成。 (1) action s, a定义了在状态s下,当前输入符号为 a时应采取的分析动作:移进归约接受,出错。 (2)goto表是一个状态及非终结符的二维矩阵, gotolS, X定义了在状态s下,面对文法符号x时的 状态转换

3. 分析表 由action[s,a]和goto[s,x]两个子表组成。 (1)action[s,a]定义了在状态s下, 当前输入符号为 a时应采取的分析动作: 移进, 归约,接受, 出错。 (2)goto表是一个状态及非终结符的二维矩阵, goto[s,x]定义了在状态s下, 面对文法符号x时的 状态转换