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

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



# CNF from example pg. 142
w = 'cabab'
cnf = {
  'S' : ['AB','b'],
  'A' : ['CB', 'AA','a'],
  'B' : ['AS', 'b'],
  'C' : ['BS', 'c'],
  }

w = 'babbab'
cnf = {
  'S' : ['AB','b'],
  'A' : ['BC', 'a'],
  'B' : ['AS', 'CB', 'b'],
  'C' : ['SS', 'a'],
  }

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)]
cyk = dict();


for k in cnf.keys():
  for i in irange(1,n):
    for j in irange(1,n):
      cyk[(k,i,j)] = []


def print_r():
  print '''
\\begin{table}[htbp] 
\\center
\\begin{tabular}{|c||%s}
\\hline
''' % ('c|'*n)
  print 'i\\textbackslash j &',
  for i in irange(1,n):
    print "%-10s" % i,
    if i != n:
      print "&",
  print "\\\\ \\hline \\hline"
  

  for i in irange(1,n):
    print "%17i &" % i,
    for j in irange(1,n):
      if r[i][j] == [None]:
        item = "$\\emptyset$",
      else: 
        item = ''
        for k in r[i][j]:
           c =  from_cyk(k,i,j)
           if c:
             item += "%s: %s \\\\" % (k, c)
           else:
             item += "%s \\\\" % k
             
      print "\\begin{tabular}{l}",
      print "%-10s \\end{tabular}" % item,
      if j != n:
        print "&",
    print "\\\\ \\hline"
  print '''
\\end{tabular}
\\caption{$CYK(L(G),%s)$. Algoritme in \cite{JS2009}[pg.~142]}
\\end{table}
''' % w


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 to_cyk(A,i,j,B):
  cyk[(A,i,j)] += [B]

def from_cyk(A,i,j):
  r = cyk[(A,i,j)]
  if not r:
    return None 
  else:
    return ",".join(["(%s,%s,%s)" % (x[0],x[1],x[2]) for x in r])


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)
            to_cyk(y,i,j,(x[0],x[1],k))


print_r()
#pprint(cyk)