parsing - 将 CKY 表转换为解析树

Question

我试图弄清楚如何将 CYK 表转换为解析树的机制。

我的 CFG 语法如下：

S -> EA
S -> TB
S -> NC
S -> 1
S -> 0
E -> EA
E -> TB
E -> NC
E -> 1
E -> 0
T -> TB
T -> NC
T -> 1
T -> 0
T -> x
F -> NC
F -> 1
F -> 0
A -> PT
B -> MF
N -> m
P -> p
M -> s
C -> 1
C -> 0

测试字符串是0pm1sm0p1

生成的表格是：

现在，假设我将表中的变量更改为规则，例如 fe S,E->S -> EA等E -> EA。

通过查看表格，我无法弄清楚如何构建解析树，因为我可以看到测试字符串中只有 2 个p，但是唯一的规则生成p是A -> PT我在表格3 A -> PT条目中看到的已经无法给出正确的解析树，因为会有太多p，E-> EA 规则也是如此，因为表中的规则太多了。我想自下而上地构建树，但是，我遇到了多个规则的问题。我错过了什么吗？我需要从表格中过滤掉一些规则吗？