我正在阅读 CYK algorithm ,并且有一部分伪代码我无法理解。整个伪代码是:
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
有人会给出一些关于这些伪代码的提示吗?
最佳答案
伪代码
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
应按以下方式解释。假设 P[j, k, B] 为真。这意味着从位置 j 开始的 k 个字符组成的字符串可以派生自非终结符 RB。如果 P[j + k, i - k, C] 也为真,那么从位置 j + k 开始的 i - k 个字符组成的字符串可以从非终结符 RC。因此,由于 RA → RB RC 是一个产生式,因此从位置 j 开始的 i 个字符组成的字符串可以从 RA 派生。
我认为将伪代码解释为可能会有所帮助
For each production RA → RB RC:
if P[j,k,B] == true and P[j+k,i-k,C] == true, then set P[j,i,A] = true
希望这对您有所帮助!
关于java - 看不懂CYK算法伪代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16006194/