-
Notifications
You must be signed in to change notification settings - Fork 1
/
cky.py
95 lines (75 loc) · 1.77 KB
/
cky.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#Implementation of CKY algorithm
def CKY(t):
#A CFG
grammar = """S -> NP VP
S -> VP
NP -> MODAL PRON | DET NP | NOUN VF | NOUN | DET NOUN | DET FILENAME
MODAL -> 'MD'
PRON -> 'PPSS' | 'PPO'
VP -> VERB NP
VP -> VERB VP
VP -> ADVERB VP
VP -> VERB FILENAME
VERB -> 'VB' | 'VBN'
NOUN -> 'NN' | 'NP'
VF -> VERB FILENAME
FILENAME -> 'FN'
ADVERB -> 'RB'
DET -> 'AT'"""
grammar_list = grammar.split('\n')
new_grammar = []
for item in grammar_list:
item = item.strip()
new_grammar.append(item)
#now save in a chart or a dictionary
rules = {}
for item in new_grammar:
arr = item.split('->')
lhs = arr[0].strip()
rhs = arr[1].strip()
if '|' in rhs:
rhs_chunks = rhs.split('|')
for rc in rhs_chunks:
rc = rc.strip()
rc = rc.strip("'")
rules[rc] = lhs
else:
rhs = rhs.strip("'")
rules[rhs] = lhs
table = {}
split = {}
tree = []
sentence = t
n = len(sentence)
table[(0,1)] = sentence[1]
for j in range(1,n):
table[(j-1,j)] = rules[sentence[j]]
for i in xrange(j-2,-1,-1):
for k in xrange(i+1,j):
if (i,k) in table and (k,j) in table:
if table[(i,k)]+' '+table[(k,j)] in rules:
if (i,j) in table:
table[(i,j)] = table[(i,j)]+rules[table[(i,k)]+" "+table[(k,j)]]
else:
table[(i,j)] = rules[table[(i,k)]+" "+table[(k,j)]]
split[(i,j)] = k
print(table)
if 'S' in table[(0,n-1)]:
print("Parsed")
#Retrieve the tree
tree_arr = ['']*(2**n)
k = 0
i = 0
j = n-1
root = 1
while (k < n-2):
k = split[(i,j)]
left = 2*root
right = left+1
tree_arr[root] = table[(i,j)]
tree_arr[left] = table[(i,k)]
tree_arr[right] = table[(k,j)]
i = k
root = i
print(tree_arr)
CKY(['','MD','PPSS','VB','AT','FN'])