-
Notifications
You must be signed in to change notification settings - Fork 2
/
cyk.py
30 lines (27 loc) · 1.03 KB
/
cyk.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
def dictionary_CNF(CNF):
new_dict = {}
for rules in CNF :
new_dict[str(rules[0])] = []
for rules in CNF:
productions = []
for i in range(1,len(rules)):
temp = rules[i]
productions.append(temp)
new_dict[str(rules[0])].append(productions)
return new_dict
def CYK(CNF, arrayInput):
N = len(arrayInput)
CNF = dictionary_CNF(CNF)
table = [[set([]) for j in range(N)] for i in range(N)]
for j in range(N):
for leftRule, rightRules in CNF.items():
for rule in rightRules:
if len(rule) == 1 and rule[0] == "'" +arrayInput[j] + "'":
table[j][j].add(leftRule)
for i in range(j, -1, -1):
for k in range(i, j):
for leftRule, rightRules in CNF.items():
for rule in rightRules:
if len(rule) == 2 and rule[0] in table[i][k] and rule[1] in table[k + 1][j]:
table[i][j].add(leftRule)
return len(table[0][N - 1]) != 0