跳转至

实验五：CYK 算法

背景

CYK 算法是一种基于动态规划的测试上下文无关语言的成员性的方法，它从语言 L 的 CNF 文法 G = (V, T, P, S) 出发，输入是 L 中的串 w = a1 a2 ... an。该算法在 O(n3) 的时间内构造出一个表明 w 是否属于 L 的表。CYK 算法自底向上处理输入字符串，通过填表记录每个子串能否推导出某个非终结符，最终根据表格顶部条目是否包含初始符号 S 来判断整个字符串是否属于该语言。

任务

你需要完成homework/CYK-algorithm/CYK.h中的TODO，根据传入的 CFG（保证为乔姆斯基范式）和该文法的句子，生成任意一个合法的语法分析树，使项目通过CI/CD且不会输出CYK algorithm assignment has not been completed.。

提示

  1. 首先自底向上填表，由于输入字符串保证是 CFG G 的句子，X1n 中必有 G 的初始符号，由此可自顶向下地生成语法分析树。

  2. 为了生成语法分析树，你需要维护每个 Xij 的来源，但因为最终只需要生成一棵语法分析树，不必记录 Xij 的每个来源。

思考题目

  1. 试证明：给定已知的 CNF 文法，设输入的字符串长度为 n，CYK 算法的时间复杂度为 O(n3)。

  2. 设 CNF 文法 G' 是由 CFG G 根据课上讲的方法构造而来，如何根据 w 对于 G' 的语法分析树生成 w 对于 G 的语法分析树？

作者：张英奇

评论