#!/usr/bin/python3 grammar = { ('Prn', 'I', None), ('Prn', 'she', None), ('Prn', 'her', None), ('N', 'duck', None), ('N', 'man', None), ('N', 'telescope', None), ('N', 'park', None), ('P', 'in', None), ('P', 'with', None), ('D', 'a', None), ('D', 'the', None), ('V', 'duck', None), ('V', 'saw', None), ('NP', 'D', 'N'), ('NP', 'NP', 'PP'), ('NP', 'Prn', 'N'), ('NP', 'I', None), ('NP', 'she', None), ('NP', 'her', None), ('PP', 'P', 'NP'), ('VP', 'V', 'S'), ('VP', 'VP', 'PP'), ('VP', 'V', 'NP'), ('VP', 'duck', None), ('VP', 'saw', None), ('S', 'NP', 'VP') } def print_table(table): n = len(table) for i in range(n): for j in range(1,n+1): if i < j: s = " ".join(table[i][j]) else: s = "" print("[{0: >15}]".format(s), end="") print() def get_pos(word): pos_tags = set() for l, r1, r2 in grammar: if r2 is None and word == r1: pos_tags.add(l) return pos_tags def cky(words, grammar): n = len(words) table = [[set() for j in range(n+1)] for i in range(0,n)] for j in range(1,n+1): table[j-1][j] = get_pos(words[j - 1]) for i in reversed(range(j)): for k in range(i+1, j): for l, r1, r2 in grammar: if (r1 in table[i][k] and r2 in table[k][j]): table[i][j].add(l) print_table(table) if __name__ == "__main__": cky(['I', 'saw'], grammar) print() cky(['I', 'saw', 'her', 'duck'], grammar) print() cky(['I', 'saw', 'her', 'duck', 'with', 'a', 'telescope'], grammar)