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

Question

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

# 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'

解析 table 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

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

How to implement CYK parsing algorithm in Ruby?

ruby

parsing

dynamic-programming

context-free-grammar

cyk