上下文无关文法的CYK算法解释
CKY的意思是Cocke-Kasami-Younger。它是最早的识别和解析算法之一。CKY的标准版本只能识别由乔姆斯基范式(CNF)中的上下文无关文法定义的语言。
也可以扩展CKY算法来处理一些不在CNF中（难以理解）的语法。
基于“动态编程”方法-
从子解决方案组合构建解决方案
它直接使用语法。
算法
Begin
for ( i = 1 to n do )
Vi1 { A | A → a is a production where i th symbol of x is a }
for ( j = 2 to n do )
for ( i = 1 to n - j + 1 do )
Begin
Vij = ϕ
For k = 1 to j - 1 do
Vij = Vij ∪ { A | A → BC is a production where B is in Vik and C is in V(i + k)(j - k) }
End
End示例
CYK算法用于查找给定的上下文无关文法是否生成给定的字符串。
给定的上下文无关文法(CFG)-
S --> AB | BC A --> BA | a B --> CC | b C --> AB | a
需要检查的字符串是w=ababa
字符串长度|w|=5
C→a
C→a
C→a
CεAB
A→BA
CεAB
A→BA
C→Ab
S出现在最后一个单元格中，因此该字符串有效。
解释
第一个字母a可以通过变量A或C找到。对于b，变量B可以找到终端b。因此，B将坐在第一排的第二个字段中。
对于row2我们需要制作一对两个终端，它将减少1cell。与第2行一样，第1行的字段将成为一对，就像我们将有ab,ba,ab,ba一样。
因此，在此需要找到将找到ab的变量，并且该变量将放置在字段row2,column1中。对于a，我们有A、C会找到它。对于b，我们有B。因此，对于ab，它将像AB、CB一样按顺序生成一对。
现在我们需要检查这两个产生式AB,CB在给定的语法中是否存在。AB可以通过S和C找到。
所以，S,C生产将被放置在那里。
同样，对于ba，b需要B，a需要A，C。因此，生产将是BA，BC。而BA,BC可以通过产生式S,A找到。所以，这将被放置在row2,column2。然后再次row2column3是abso，与row2column1相同。而row2column4将与row2Column2相同。
类似地，接下来的行需要找到终端aba,bab,aba并且按照顺序，可以找到它的变量将是B代表aba，S,C代表bab，B代表aba。
现在第4行的四个终端将作为abab,baba连接在一起。它的产量将是B。在最后一个学期ababa将所有五个都放在一起，它的产量将是S、C、A。
如果最后一个的S是起始状态，则接受给定的字符串。因此，对于给定的字符串，成员资格为真。
此外，您还需要看到，如果将三个终端连接在一起，则可以将其生成为(aba)或(aba)。类似地，对于四个终端，一个(abab)或(abab)或(abab)。同样，对于五(ababa)或(ababa)或(ababa)....