无法理解CYK算法的伪代码。

Question

我在阅读 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

请有人给一些关于这些伪代码的提示吗？

- user2280838

---

@syb0rg：我故意保留缩进，这样更容易从大块代码中找到较小的代码片段。 - nhahtdh

@nhahtdh 已修复（排版习惯问题，抱歉）。 - syb0rg

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

Answer 1

伪代码应该这样解释。假设 P[j，k，B] 为真。这意味着从 j 位置开始的 k 个字符组成的字符串可以由非终端符 R_B 推导出来。如果 P[j+k，i-k，C] 也是真的，则从 j + k 开始的 i - k 个字符组成的字符串可以由非终端符 R_C 推导出来。因此，由于 R_A → R_B R_C 是一个产生式，因此可以得出从 j 开始的 i 个字符组成的字符串可以由 R_A 推导出来。

我认为将伪代码解释为：

对于每个产生式 R_A → R_B R_C，如果 P[j,k,B] == true 且 P[j+k,i-k,C] == true，则将 P[j,i,A] 设置为 true。

希望能有所帮助！

- templatetypedef

---

请问您能澄清一下索引 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

@user2280838- 伪代码的工作原理是为每个非终端符号分配一个唯一的ID。如果您将多个产生式与同一非终端符号相关联，那么您不会“重新定义”相同的非终端符号；每次都是相同的非终端符号。这意味着即使您有像S -> UT和S -> XY这样的东西，S在两种情况下都是相同的（并且具有相同的索引）。 - templatetypedef