优先关系表
优先关系表
●从算符优先文法G构造优先关系表的算法。 ●通过检查G的每个产生式的每个候选式,可找出所 有满足a回b的终结符对。 ●确定满足关系<和>的所有终结符对: 首先需要对G的每个非终结符P构造两个集合 FIRSTVT(P)和 LASTVT(P): FR77(P)={P→a…,或P→Qa…,a∈V而Q∈V} L4ST7(P)={a|P→…a或P→…Q,a∈V而Q∈V}
从算符优先文法G构造优先关系表的算法。 通过检查G的每个产生式的每个候选式，可找出所 有满足a b的终结符对。 确定满足关系< .和.>的所有终结符对： ⚫ 首先需要对G的每个非终结符P构造两个集合 FIRSTVT(P)和LASTVT(P)： FIRSTVT P a P a P Qa a V Q V T N ( ) = { | , , } + + 或 而 ( ) { | , , } VT Q VN LASTVT P = a P a P aQ a + + 或 而
口有了这两个集合之后,就可以通过检查每 个产生式的候选式确定满足关系<和的所 有终结符对。 假定有个产生式的一个候选形为 naP,。 那么,对任何b∈ FIRSTVT(P),有a<b 假定有个产生式的一个候选形为 Pb 那么,对任何a∈ LASTVT(P),有a>b
❑有了这两个集合之后，就可以通过检查每 个产生式的候选式确定满足关系< .和.>的所 有终结符对。 ➢假定有个产生式的一个候选形为 …aP… 那么，对任何bFIRSTVT(P)，有 a < . b。 ➢假定有个产生式的一个候选形为 …Pb… 那么，对任何aLASTVT(P)，有 a .> b
●首先讨论构造集合 FIRSTVT(P)的算法。按 其定义,可用下面两条规则来构造集合 FIRSTVT(P) 1若有产生式Pa.或P→Qa.,则 a∈ FIRSTVT(P); 2若a∈ FIRSTVT(Q),且有产生式P→Q,则 a∈ FIRSTVT(P)
首先讨论构造集合FIRSTVT(P)的算法。按 其定义，可用下面两条规则来构造集合 FIRSTVT(P)： 1. 若有产生式P→a…或P→Qa…，则 aFIRSTVT(P)； 2. 若aFIRSTVT(Q)，且有产生式P→Q…，则 aFIRSTVT(P)
构造 FIRSTVT(P的算法: 引入一个布尔数组FP,a,使得F[P,a为真 的条件是,当且仅当a∈ FIRSTVT(P)。开始时, 按上述的规则1)对每个数组元素F[P,a赋初 值 引入一个栈 STACK,把所有初值为真的数组元 素FP,a]的符号对P,a全都压入 STACK中
构造FIRSTVT(P)的算法： ⚫ 引入一个布尔数组F[P，a]，使得F[P，a]为真 的条件是，当且仅当aFIRSTVT(P)。开始时， 按上述的规则(1)对每个数组元素F[P，a]赋初 值。 ⚫ 引入一个栈STACK，把所有初值为真的数组元 素F[P，a]的符号对(P，a)全都压入STACK中