语法 表示了自然语言对话中的句法规则。但在形式语言理论中，语法定义为一组可以生成字符串的规则。由一个语法可以生成的所有字符串的集合，称为该语法的语言。
上下文无关语法：
假设我们有一个上下文无关语法 G = (V, X, R, S) 和一个字符串 w，其中：
- V 是变量或非终结符的有限集合，
- X 是终结符的有限集合，
- R 是规则的有限集合，
- S 是起始符号，是 V 中的一个独特元素，且
- 假设 V 和 X 是不相交的集合。
成员问题 的定义是：语法 G 生成一个语言 L(G)。给定的字符串是 L(G) 的成员吗？
乔姆斯基范式：
如果上下文无关语法 G 的每一条规则都符合以下形式，则称其处于乔姆斯基范式（CNF）中：
- A –> BC， [ 右侧最多包含两个非终结符 ]
- A –> a，或 [ 右侧包含一个终结符 ]
- S –> nullstring， [ 空字符串 ]
Cocke-Younger-Kasami (CYK) 算法
该算法用于通过动态规划方法来解决成员问题。该算法基于这样一个原则：问题 [i, j] 的解可以由子问题 [i, k] 的解和子问题 [k, j] 的解构造而成。该算法要求语法 G 必须处于乔姆斯基范式（CNF）。请注意，任何上下文无关语法都可以系统地转换为 CNF。施加这一限制是为了确保每个问题只能被划分为两个子问题，不会更多——以此来界定时间复杂度。
CYK 算法是如何工作的？
对于一个长度为 N 的字符串，我们构建一个大小为 N x N 的表 T。表 T 中的每个单元格 T[i, j] 是所有可以生成从位置 i 到 j 的子串的成分的集合。这个过程涉及用自底向上解析过程中遇到的子问题的解来填充表格。因此，单元格的填充顺序是从左到右、从下到上。
1
3
5
—
—
—
[1, 1]
[1, 3]
[1, 5]
[2, 3]
[2, 5]
[3, 3]
[3, 5]
[4, 5]
[5, 5]在 T[i, j] 中，行号 i 表示起始索引，列号 j 表示结束索引。
A \in T[i, j] \text{ 当且仅当 } B \in T[i, k], C \in T[k, j] \text{ 且 } A \rightarrow BC \text{ 是 G 的一条规则}
该算法会考虑字母的每一个可能的子序列，如果从 i 到 j 的字母序列可以由非终结符 K 生成，则将 K 添加到 T[i, j] 中。 对于长度为 2 及以上的子序列，它会考虑将子序列划分为两个部分的每一种可能方式，并检查语法中是否存在 A ? BC 形式的规则，其中 B 和 C 可以根据 T 中已有的条目分别生成这两个部分。只有当整个字符串被起始符号匹配时，即如果 S 是 T[1, n] 的成员，该句子才能由语法生成。
让我们考虑一个乔姆斯基范式中的示例语法：
*NP --> Det | Nom*
*Nom --> AP | Nom*
*AP --> Adv | A*
*Det --> a | an*
*Adv --> very | extremely*
*AP --> heavy | orange | tall*
*A --> heavy | orange | tall | muscular*
*Nom --> book | orange | man*
现在考虑短语“a very heavy orange book” (一本非常重的橙色的书)：
a(1) very(2) heavy (3) orange(4) book(5)
让我们根据上述规则，开始从左到右、从下到上填充表格：
1a
3heavy
5book
—
—
—
Det
–
NP
AP
Nom
A, AP
Nom
Nom
Nom表格的填充方式如下：
- T[1, 1] = {Det}，因为 Det –> a 是语法中的一条规则。
- T[2, 2] = {Adv}，因为 Adv –> very 是语法中的一条规则。
- T[1, 2] = {}，因为没有观察到匹配的规则。
- T[3, 3] = {A, AP}，因为 A –> very 和 AP –> very 是语法中的规则。（注：此处对应原文 A/AP 生成 heavy）
- T[2, 3] = {AP}，因为 AP –> Adv (T[2, 2]) A (T[3, 3]) 是语法中的一条规则。
- T[1, 3] = {}，因为没有观察到匹配的规则。
- T[4, 4] = {Nom, A, AP}，因为 Nom –> orange 以及…