如何在Ruby中实现CYK解析算法？

Question

我正在尝试根据pseudocode from Wikipedia用Ruby语言实现CYK算法。我的实现无法生成正确的解析表。在下面给出的方法中，grammar是我自己的语法类的成员。代码如下：

# checks whether a grammar accepts given string
# assumes input grammar to be in CNF

def self.parse(grammar, string)
    n = string.length
    r = grammar.nonterminals.size
    # create n x n x r matrix
    tbl = Array.new(n) { |_| Array.new(n) { |_| Array.new(r, false) } }
    (0...n).each { |s| 
        grammar.rules.each { |rule| 
            # check if rule is unit production: A -> b
            next unless rule.rhs.size == 1
            unit_terminal = rule.rhs[0]
            if unit_terminal.value == string[s]
                v = grammar.nonterminals.index(rule.lhs)
                tbl[0][s][v] = true
            end
        }
    }
    (1...n).each { |l| 
        (0...n - l + 1).each { |s| 
            (0..l - 1).each { |p| 
                # enumerate over A -> B C rules, where A, B and C are
                # indices in array of NTs
                grammar.rules.each { |rule| 
                    next unless rule.rhs.size == 2
                    a = grammar.nonterminals.index(rule.lhs)
                    b = grammar.nonterminals.index(rule.rhs[0])
                    c = grammar.nonterminals.index(rule.rhs[1])
                    if tbl[p][s][b] and tbl[l - p][s + p][c]
                        tbl[l][s][a] = true
                    end
                }
            }
        }
    }
    v = grammar.nonterminals.index(grammar.start_sym)
    return tbl[n - 1][0][v]
end

我用这个简单的例子对它进行了测试：

grammar:
A -> B C
B -> 'x'
C -> 'y'

string: 'xy'

解析表tbl如下：

[[[false, true, false], [false, false, true]],
[[false, false, false], [false, false, false]]]

问题肯定存在于算法的第二部分-长度大于1的子串。第一层(tbl[0])包含正确的值。

非常感谢您的帮助。

Answer 1

问题出在伪代码中从1开始的数组到代码中从0开始的数组的转换过程中。当您在循环的第一次运行中查看条件tbl[p][s][b] and tbl[l-p][s+p][c]中的第一个索引时，这一点就变得很明显。伪代码检查tbl[1] and tbl[1]，您的代码检查tbl[0] and tbl[1]。

我认为在访问数组时必须从0开始进行校正，而不是在l和p的范围内。否则，使用指数的计算是错误的。这应该是可行的：

 (2..n).each do |l|
    (0...n - l + 1).each do |s|
      (1..l - 1).each do |p|
        grammar.rules.each do |rule|
          next unless rule.rhs.size == 2
          a = grammar.nonterminals.index(rule.lhs)
          b = grammar.nonterminals.index(rule.rhs[0])
          c = grammar.nonterminals.index(rule.rhs[1])
          if tbl[p - 1][s][b] and tbl[l - p - 1][s + p][c]
            tbl[l - 1][s][a] = true
          end
        end
      end
    end
  end