定理52证明(2) 如果存在规范句型.SSi.且S是某个句柄的最后符号: 考虑语法树中,同时包含有S和Si的最小子树。设 其根结点为U。而U的子结点从左到右为u 短语u的形状必然为VW.,且V=>*S而 W=>*Si。这是因为如果有某个u中的符号 X→>..SSi.,那么以X为根的子树才是最小的包含 S和Si的子树。 显然,根据定义Sj≥Si
定理5.2证明(2) • 如果存在规范句型…SjSi…且Sj是某个句柄的最后符号： – 考虑语法树中，同时包含有Sj和Si的最小子树。设 其根结点为U。而U的子结点从左到右为u。 – 短语u的形状必然为…VW…，且V=>*…Sj而 W=>*Si。这是因为如果有某个u中的符号 X=>…SjSi…，那么以X为根的子树才是最小的包含 Sj和Si的子树。 – 显然，根据定义Sj Si
优先关系的构造 ·根据优先关系的构造性的定义(定义5.1),我们立刻可以 得到构造算法 的构造:直接对每个规则右部处理,没有右部X1X2Xn, 都有X≡X10 ·≥的构造:由定义,S≥Si可以得到 存在规则U:=SjV.,也就是Sj≡V。 ⅤHEAD+Si。 HEAD关系可以通过检查每个规则得到。 由此可以得到≥就是(=)(HEAD+)。因此≥可以通过计算 关系≡和HEAD的传递闭包
优先关系的构造 • 根据优先关系的构造性的定义（定义5.1），我们立刻可以 得到构造算法。 • 的构造：直接对每个规则右部处理，没有右部X1X2…Xn， 都有Xi Xi+1。 • 的构造：由定义，Sj Si可以得到 – 存在规则U::=… SjV…，也就是Sj V。 – V HEAD+ Si。 – HEAD关系可以通过检查每个规则得到。 – 由此可以得到就是()(HEAD+)。因此可以通过计算 关系 和HEAD的传递闭包
优先关系的构造(续) ≤关系的构造:由定义,Sj≤S表示 存在规则U∷=.ⅤW. V≡W V TAIL+Si SJ(TAlL+)'V WHEAD SI 一将上面三个规则综合起来,可以得到≤关系就是 (A+)=BEAD米 从上面的算法可以看到:≡,TAL,HEAD可 以直接检查每个规则得到。因此,我们只需要 有对关系的联接,闭包运算就可以得到上面的 三个优先关系
优先关系的构造（续） • 关系的构造：由定义，Sj Si表示: – 存在规则U::=…VW… V W – V TAIL+ Sj Sj (TAIL+ ) T V – W HEAD* Si – 将上面三个规则综合起来，可以得到关系就是 (TAIL+ ) T HEAD* • 从上面的算法可以看到： ， TAIL， HEAD可 以直接检查每个规则得到。因此，我们只需要 有对关系的联接，闭包运算就可以得到上面的 三个优先关系
关系的boo矩阵表示和运算 关系可以使用boo矩阵来表示。对某个关 系R,SRS在矩阵中用B:=TURE来表示 对于两个关系R1,R2对应的矩阵B1,B2, B1和B2的乘积矩阵对应的关系就是R1和 R2联接运算结果
关系的bool矩阵表示和运算 • 关系可以使用bool矩阵来表示。对某个关 系R，SjRSi在矩阵中用 Bij =TURE来表示。 • 对于两个关系R1，R2对应的矩阵B1，B2， B1和B2的乘积矩阵对应的关系就是R1和 R2联接运算结果
关系闭包和 Marshal算法 Marshal算法是利用矩阵计算关系传递闭包的方法。计 算B的传递闭包的算法伪代码如下 a=B r(1=1,i<=ni,i++) for g=l; j<=n;j++) f(Ai]=1) for(k-l; k<=n; k++) ALj, k=AL, k]+AL, k
关系闭包和Warshall算法 • Warshall算法是利用矩阵计算关系传递闭包的方法。计 算B的传递闭包的算法伪代码如下： A = B; for (i = 1; i<=n; i++) for (j=1; j<=n; j++) { if (A[j,i]==1) for(k=1; k<=n; k++) A[j,k] = A[j,k]+A[i,k] }