使用矩阵计算优先关系≤ 步骤1:构造优先关系矩阵B ·步骤2:构造关系HEAD的矩阵B1EAD 步骤3:使用 Warshall算法计算BmAD+ 步骤4:计算BB1EAD+
使用矩阵计算优先关系 • 步骤1：构造优先关系矩阵B • 步骤2：构造关系HEAD的矩阵BHEAD • 步骤3：使用Warshall算法计算BHEAD+ • 步骤4：计算 B BHEAD+
使用矩阵计算优先关系≥ 步骤1:计算TAL的布尔矩阵B1u 步骤2:计算BτAm+,并将该矩阵转置得到 (Bu+)T。 步骤3:构造优先关系矩阵B 步骤4:构造HEAD的矩阵B1EAD 步骤5:计算BAD+的矩阵,并由此得到 I+HEAD的矩阵B1+HEAD+。 步骤6:计算(BTm+)BB I+HEAD 需要在得到的矩阵中,把非终结符号对应列中 的1去掉。(因为≥的右边时终结符号)
使用矩阵计算优先关系 • 步骤1：计算TAIL的布尔矩阵BTAIL • 步骤2：计算BTAIL+，并将该矩阵转置得到 (BTAIL+) T 。 • 步骤3：构造优先关系矩阵B • 步骤4：构造HEAD的矩阵BHEAD。 • 步骤5：计算BHEAD+的矩阵，并由此得到 I+HEAD+的矩阵BI+HEAD+。 • 步骤6：计算(BTAIL+ ) TB BI+HEAD+。 • 需要在得到的矩阵中，把非终结符号对应列中 的1去掉。(因为的右边时终结符号）
计算优先关系的例子P136 文法:S:=WaW:=Wb W 将文法中的符号按照S,W,a,b排列。 0100 0110 0110 0110 HEAD 0000 BHEAD+=0000 0000 0000 0010 0100 0011 0110 0000 (BrAn+)1=000 0000 0000
计算优先关系的例子P136 • 文法：S::=Wa W::=Wb W::=a • 将文法中的符号按照S，W，a，b排列。 BHEAD = 0100 0110 0000 0000 BHEAD+= 0110 0110 0000 0000 BTAIL = 0010 0011 0000 0000 (BTAIL+)T= 0100 0110 0000 0000
计算优先关系的例子(续) 0000 1110 B 001 B 0110 0000 I+HEAD 0010 0000 0001 0000 B B 0000 <一D≡ DHEAD 0000 0000 0000 B≥=Bwu+)B.BHEt=001 0011
计算优先关系的例子(续) B = 0000 0011 0000 0000 B I+HEAD+= 1110 0110 0010 0001 B =B BHEAD+= 0000 0000 0000 0000 B =(BTAIL+ ) TB BI+HEAD+= 0000 0000 0011 0011
优先关系的冲突 当优先矩阵中出现值不唯一的元素时, 文法不适合使用优先识别技术来识别句 型
优先关系的冲突 • 当优先矩阵中出现值不唯一的元素时， 文法不适合使用优先识别技术来识别句 型