从CYK算法生成解析树

Question

6

我使用 CYK 算法（已在 Java 中实现）来确定一个字符串是否符合特定语法。现在我需要为该字符串生成解析树，是否有一种方法可以通过我在使用 CYK 算法时使用的矩阵生成该树？

- Lucy

我假设你的矩阵由0和1或'true'和'false'组成。你可以创建解析树节点并适当地存储它们，而不是存储这些布尔值。 - user2030052

矩阵包含非终端符号（来自语法），因此现在我只需要生成解析树。 - Lucy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adrian McCarthy · Accepted Answer

实现CYK算法作为识别器时，图表中的框通常只是一组比特（或其他布尔值），对应于可能在该点应用的产生式。这并不足以让您重构解析树。

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