source: liacs/TPFL2010/assignment3/cyk.py@ 252

#!/usr/bin/env python
#
# Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm.
#


# Word to search for
w = 'cabab'

# CNF 
cnf = {
  'S' : ['AB','b'],
  'A' : ['CB', 'AA','a'],
  'B' : ['AS', 'b'],
  'C' : ['BS', 'c'],
  }

def irange(i,j):
  """ Return i till and including(!) j """
  return range(i,j+1)

n = len(w)
r = [[[]]*(n+1) for x in irange(0,n)]




def printr():
  print 'i\\textbackslash j &',
  for i in irange(1,n):
    print "%-10s &" % i,
  print "\\\\ \\hline \\hline"
  

  for i in irange(1,n):
    print "%17i &" % i,
    for j in irange(1,n):
      if r[i][j] == [None]:
        item = "@"
      else:
        item = ",".join(r[i][j]),
      print "%-10s &" % item,
    print "\\\\ \\hline"

def to_r(i,j,k):
  if k not in r[i][j]:
    if r[i][j] == [None]:
      r[i][j] = [k]
    else:
      r[i][j] = r[i][j] + [k]

def from_r(i,j):
  return r[i][j]

def letter(i):
  return w[i-1]


# Initial productions (leafs)
for i in irange(1,n):
  for k,v in cnf.iteritems():
    if letter(i) in v:
      to_r(i,i,k)

# Longer length Productions
for d in irange(1,n-1):
  for i in irange(1,n-d):
    j = i + d
    to_r(i,j,None)
    for k in irange(i,j-1):
      for y,z in cnf.iteritems():
        # Iterate over all YX rules
        for x in [w for w in z if len(w) == 2]:
          if x[0] in from_r(i,k) and x[1] in from_r(k+1,j):
            to_r(i,j,y)


printr()