0

我正在尝试根据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]) 包含正确的值。

非常感谢帮助。

4

1 回答 1

1

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

我认为当您访问数组而不是在 and 的范围内时，您必须进行基于 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
于 2019-03-17T22:09:27.950 回答