乔姆斯基范式：上下文无关文法CFL，没有空串，只有以下两个产生式

A->BC

A->a

这就是乔姆斯基范式或者CNF（Chomsky Normal Form）。一般随便的CFL(上下文无关文法)都可转化为CNF。

下面先是大致了解：

CYK算法，填表：

CYK算法是判断句子合法性的方法，就是上述填表的算法，通过层层合并最后变成一个。这么看的话，CYK算法也是一个自底向上的分析过程吧。

Chart Parsing也是一种判断句子合法性的一种方法，基于图的句法分析技术，可以有效防止回溯，说白了，就是移进-规约分析，活前缀项集->活动弧，不活动弧就是规约完毕的。但是冲突怎么办呢？二义性？如果有二义性的，就把可能全部先存入队列中，它根据二义性进行分裂。子树就是一个Key，又或者说是一个完整的句柄。分层次的点，每一个句柄都拥有一个点，用来处理句柄中的句柄，或者说非终结符中的非终结符，等非终结符的终结符匹配成功了，本层非终结符的点就移到末尾了，而上一层非终结符的点只能移动一个，也就是本非终结符。

非活动弧是规约完毕的，是正确的，放到chart中，活动弧放到agent中

或者说白了，就是并行匹配，如果出现错误了，就删除之，什么叫出现错误呢？就是后面的符号跟文法预测的符号不一致，就没有办法进行下去了。注意这是自底向上，而eager是自顶向下。

现在也看懂了。

POS代表每个终结符可以代表的非终结符。

现在大概也明白了是怎么回事：

例如这么一个，每一个单词可以轻松确定一个非终结符

然后在弧上画更大的弧，设定更大的非终结符，直到最后生成唯一起始符，感觉跟第一个没有什么两样。不到最

后就是活动弧。

区别是CYK是用单词，chart法是用词与词之间的空隙。关键是它能有一定的推导能力，不仅仅只有一个选择。CYK算法要比Chart算法要容易理解一些，其优点是：简单易行，执行效率高；但是，必须对文法进行范式化处理，且无法区分歧义。

它们跟编译编程语言的方法的区别就是它们允许歧义。用动态规划的方法避开错误。

然后接下来就是nltk的表示了。之所以用这个方法，是因为普通自底向上的方法非常容易产生回溯，而解决的办法莫过于动态规划了。效果会更好吧。非活动边集就是已经规约成功的，活动边集就是未完全匹配的产生式，正在活动中的。

说白了，就是将分析过程中的中间状态全部保存下来，然后进行匹配，这样。

先说CYK再说chart。

句法分析的研究起始于20世纪50年代，可以粗略地分为基于规则的句法分析与基于统计的句法分析两个派别。纯粹基于规则的句法分析盛行于60年代到80年代，后逐渐被基于统计的句法分析所代替。现行的句法分析算法一般同时运用基于规则与基于统计的方法，来提升计算机句法分析的速度与正确率。

感觉这张图也是蛮重要的。这个说明了演化顺序，还是有收获的。

句法分析策略指的是句法分析的过程中按照何种方式进行分析，通常采用的策略有：

自顶向下的方法又称为基于预测的方法，也就是说，这种方法产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上出现了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。

自底向上的方法也叫基于规约的方法。就是说，这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层规约为可能的成份。如果整个待分析字符串被规约为开始字符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串规约为句子的方案，那么就需要回溯。

左角分析法是一种自顶向下和自底向上相结合的方法。

常见的上下文无关语法的句法分析算法有：

CYK算法全称为“Cocke-Younger-Kasami Algorithm”，三个人名的语法。

任何上下文无关文法，都可以转换为只包含二叉树的乔姆斯基标准型。下边是三个方法：

对于箭头右边终端结点与非终端结点同时出现的情况，例如 X → a B，可以用添加非终端结点的方式改写为 X → A B, A → a

对于箭头右边只有一个非终端结点的情况，例如 X → A, A → a，可以用删除非终端结点的方式改写为 X → a

对于箭头右边结点多于两个的情况，例如 X → A B C，可以用添加非终端结点的方式改写为 X → A Y，Y → B C

可以确定的是，CYK文法必然生成一个二叉树。二叉树的中间节点必然是非终结符，叶子节点必然是终结符。那么自下而上构建一棵树，还是蛮简单的。使用填表法的话，就必然要考虑它是一棵树，每一个中间格仅仅是由两个格组成的，而这两个格恰好能覆盖所有子节点这样。

而且你看这个表，两个格的确定也是非常好确定的，正好是互补的那种：

这里有一个问题，那么树形图怎么获取呢？

答案是，只要向下走，能走的，都对，因为不止一个树，这个是肯定的。普通遍历就可以，遍历分叉正好表明不止一个树。

那么，如何实现呢？

首先需要单词对照表，是一个map类型的，python不常用啊，例如"red": "ADJ", "介词"，不不，这个可以直接填入文法中就行。

然后文法部分，也是map类型的，只不过变量里要不是两个的，要不是一个的。

然后是一个输入语句，一个字符串足矣。

然后是这个表，这个表怎么造呢？结构是list，表明它能表示的是什么，当然不止一个，当然也有可能为空。

填完了之后开始由下向上遍历，每一个格子再循环一遍，填入list中，直到最后。

然后回归的时候，就从右上角开始，如果有一个成立分叉进行下去，是一个递归的过程。行。

线图分析法同样有3种策略来构建句法分析树，分别是：

与 CYK 算法相比，Earley 算法的优势在于，不要求语法规则一定要以乔姆斯基标准型（Chomsky Normal Form，CNF）的形式表示，而是可以凭借以任意形式的上下文无关文法表示的语法规则，对给定的句子进行分析。

Earley 算法是自上而下算法，一张图说明Earley算法：

它的链接在微信的深入浅出句法分析（第2期） | Earley 算法（上）