parsing - 从 CYK 算法生成解析树

Question

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

Answer 1

当仅将 CYK 实现为识别器时，图表中的框通常只是一组位（或其他布尔值），它们对应于可能在该点应用的产生式。这不会给您留下足够的信息来重建解析树。

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