blob: e02e34ad66f5dad827952c5bf9b14dfe0acd79c9 (
plain) (
blame)
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
|
###############################################
# module: cyk.py
# Elizabeth Hunt
# A02364151
###############################################
def format_table(derives: list[list[set]], max_row: int) -> str:
table = ""
n = len(derives)
for row in range(max_row):
curr_row = f"{row+1}: "
for col in range(n - row):
set_of_nonterminals = " ".join(derives[row][col])
curr_row += f"|{set_of_nonterminals}|"
table += curr_row + "\n"
return table
class CYK(object):
@staticmethod
def is_in_cfl(test_string, cnfg, table_display_flag=False):
n = len(test_string)
derives = [[set() for _ in range(n)] for _ in range(n)]
for i, terminal in enumerate(test_string):
derives[0][i] |= cnfg.fetch_lhs(terminal)
if table_display_flag:
print(format_table(derives, 1))
for length in range(2, n + 1):
for start in range(n - length + 1):
for split_idx in range(1, length):
for first in derives[split_idx - 1][start]:
for second in derives[length - split_idx - 1][
start + split_idx
]:
derives[length - 1][start] |= cnfg.fetch_lhs(first, second)
if table_display_flag:
print(format_table(derives, length))
return "S" in derives[n - 1][0]
|
