无法理解CYK算法伪代码

问题描述：

我读的是CYK algorithm，有一部分伪代码我看不懂。整个伪代码：无法理解CYK算法伪代码

let the input be a string S consisting of n characters: a1 ... an. 
let the grammar contain r nonterminal symbols R1 ... Rr. 
This grammar contains the subset Rs which is the set of start symbols. 
let P[n,n,r] be an array of booleans. Initialize all elements of P to false. 
for each i = 1 to n 
    for each unit production Rj -> ai 
    set P[i,1,j] = true 
for each i = 2 to n -- Length of span 
    for each j = 1 to n-i+1 -- Start of span 
    for each k = 1 to i-1 -- Partition of span 
     for each production RA -> RB RC 
     if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true 
if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then 
    S is member of language 
else 
    S is not member of language

这些零件，我很困惑：

for each production RA -> RB RC 
     if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true

会有人给这些伪一些提示？

@ syb0rg：我故意留下缩进，以便更容易从大块代码中找到更小的代码片段。 – nhahtdh

@nhahtdh固定（格式化习惯，抱歉）。 – syb0rg

@ syb0rg：较小代码片段的缩进有点偏离（您可以从原始代码复制并粘贴）。 – nhahtdh

答

的伪码

对于每个生产ř_甲 → - [R _乙 - [R _Ç：

如果P [J，K，B]和P [J + K，IK ，C]然后设置P [j，i，A] = true

应该按照以下方式解释。假设P [j，k，B]为真的情况。这意味着从位置j开始的由k个字符组成的字符串可以从非终结符R _B派生。如果P [j + k，i-k，C]也是这种情况，那么由从位置j + k开始的i-k个字符形成的字符串可以从非终结符R _C导出。因此，由于R _甲 → - [R _乙 - [R _Ç是一个生产，它是从开始位置j第i个字符构成的字符串可以选自R _甲导出的情况。

我认为这可能有助于解释该伪代码作为

对于每个生产ř_甲 → - [R _乙 - [R _Ç：

如果P [J，K，B] == true和P [j + k，ik，C] == true，那么设置P [j，i，A] = true

希望这有助于！

您能澄清一下A B和C的索引是什么吗？ – user2280838

@ user2280838-该算法对所有非终端R_1，R_2，...，R_n进行编号。这里，A，B和C发生的是生产R_A - > R_B R_C中非终端的指数。例如，如果生产是S→T U和S有索引1，T有索引2，U有索引3，那么我们有A = 1，B = 2和C = 3。这有帮助吗？ – templatetypedef

它确实有帮助，但如果A B和C作为非终端在语法中定义了多次，该怎么办？分配一个ID值的索引排序是否有助于区分其他非终结点？ – user2280838

无法理解CYK算法伪代码

相关推荐