用CYK算法生成解析树

Question

我使用CYK算法(已经在Java中实现了)来查看是否根据特定的语法识别字符串。现在我需要为字符串生成一个解析树，这是一种从使用CYK算法时使用的矩阵生成树的方法吗？

Answer 1

当将CYK实现为仅仅是一个识别器时，图表中的框通常只是一组比特(或其他布尔值)，它们对应于可能在此时应用的结果。这并不能给您留下足够的信息来重构解析树。

如果您存储一组对象，则这些对象包括非终端，并跟踪组合的两个产品。完成后，检查最后一个框是否包含一个表示开始符号产生的对象。如果是这样的话，您可以按照指针返回来重构解析树。