cyk.py

import pprint

pp = pprint.pprint

def cartesian(a,b):
	return set([u+v for u in a for v in b])

def findrules(g, s):
	return set(k for k in g if any(s in x for x in g[k]))

def union(sets):
	res = set()
	for x in sets:
		res = res.union(x)
	return res

def dumptable(table, latex=False):
	res = []

	n = max(max(u,v) for u,v in table) + 1

	for row in xrange(n):
		nrow = [
			','.join(str(nonterm) for nonterm in table.get((row, col), []))
			for col in xrange(n)
		]
		
		if latex:
			res.append(
				' & '.join(("$%s$" % cell).ljust(10) for cell in nrow)
			)
		else:
			res.append(
				' '.join((cell or '-').ljust(6) for cell in nrow)
			)
			
	return res

def maketable(grammar, word):
	n = len(word)
	res = {}
	
	for i in xrange(len(word)):
		res[i,i] = findrules(grammar, word[i])
	
	for d in xrange(2, n+1):
		for i in xrange(n-d+1):
			j = i-1+d
			
			pairs = [((i,i+a-1), (i+a,j)) for a in xrange(1, d)]
			combined = [cartesian(res[u], res[v]) for u,v in pairs]
			res[i,j] = union(findrules(grammar, w) for words in combined for w in words)

	return res


g1 = {
	'S': ["AB", "BC"],
	'A': ["BA", 'a'],
	'B': ['CC', 'b'],
	'C': ['AB', 'a'],
}

w1 = 'baaba'
w2 = 'aabbab'


print '\n'.join("%s \\\\" % x for x in dumptable(maketable(g1, w1), latex=True)), "\n"
print '\n'.join("%s \\\\" % x for x in dumptable(maketable(g1, w2), latex=True)), "\n"