CKY.rb

class CkySolver
  def initialize(&init_proc)
    @init_proc = init_proc
  end

  def solve(n, &callback)
    a = Array.new(n * n)
    n.times {|i| a[i*n + i] = @init_proc.call(i) }

    (n - 1).times do |d|
      (n - d - 1).times do |i|
        j = i + d + 1
        (i..(j - 1)).each do |k|
          a[i*n + j] = callback.call(a, i, j, k)
        end
      end
    end

    a
  end
end

data = [
 {w: "I", p: [:N, :NP]},
 {w: "saw", p: [:V, :VP]},
 {w: "a", p: [:DET]},
 {w: "girl", p: [:N, :NP]},
 {w: "with", p: [:PREP]},
 {w: "a", p: [:DET]},
 {w: "telescope", p: [:N, :NP]},
]

chomsky_form =
[
  [:S, [:NP, :VP]],
  [:NP, [:DET, :N]],
  [:NP, [:NP, :PP]],
  [:VP, [:V, :NP]],
  [:VP, [:VP, :PP]],
  [:PP, [:PREP, :NP]],
]

solver = CkySolver.new {|i| data[i].merge(i: i) }

n = data.length
result = solver.solve(data.length) do |a, i, j, k|
  bc = [a[i*n + k]&.fetch(:p), a[(k+1)*n + j]&.fetch(:p)]
  _a = chomsky_form.find {|k, v| bc[0]&.include?(v[0]) && bc[1]&.include?(v[1]) }&.first

  if a[i*n + j]
    a[i*n + j][:p] << _a if _a
    a[i*n + j]
  else
    _a && { p: [_a] }
  end
end

result.each_slice(n) do |row|
  pp row
end

自然言語処理 (放送大学教材)のP.90のCKY法をrubyで解いてみた。
どこから来たのかという情報を残していないので、これだけだと構文木を作るところまではできない。

参考： 放送大学テキスト「自然言語処理（著：黒橋教授）」読書会 Vol.3 - connpass