我使用 CYK 算法(已经在 Java 中实现了它)来查看是否根据特定语法识别出一个字符串。现在我需要为字符串生成一个解析树，是一种从使用 CYK 算法时使用的矩阵生成树的方法吗？
最佳答案
当仅将 CYK 实现为识别器时，图表中的框通常只是一组位(或其他 bool 值)，对应于可能适用于该点的产生式。这不会给您留下足够的信息来重建解析树。
如果您改为存储一组对象，则这些对象包括非终结符并跟踪组合的两个产生式。完成后，检查您的最终框是否包含代表开始符号产品的对象。如果是，您可以按照指针返回来重建解析树。
关于parsing - 从 CYK 算法生成解析树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29563867/