diff options
| author | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
|---|---|---|
| committer | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
| commit | 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 (patch) | |
| tree | ed97e39ec77c5231ffd2c394493e68d00ddac5a4 /Homework/cs5000/hw05/PyCYK/cnfg.py | |
| download | misc-undergrad-main.tar.gz misc-undergrad-main.zip | |
Diffstat (limited to 'Homework/cs5000/hw05/PyCYK/cnfg.py')
| -rw-r--r-- | Homework/cs5000/hw05/PyCYK/cnfg.py | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/Homework/cs5000/hw05/PyCYK/cnfg.py b/Homework/cs5000/hw05/PyCYK/cnfg.py new file mode 100644 index 0000000..bb1ed17 --- /dev/null +++ b/Homework/cs5000/hw05/PyCYK/cnfg.py @@ -0,0 +1,82 @@ +###############################################
+# module: cnfg.py
+# description: Chomsky Normal Form Grammar
+# bugs to vladimir kulyukin in canvas
+###############################################
+
+class CNFG:
+
+ def __init__(self, startSymbol = "S", productions = dict()):
+ self._productions = productions
+ self._startSymbol = startSymbol
+
+ def __str__(self):
+ productions = list()
+ for lhs in self._productions:
+ for rhs in self._productions[lhs]:
+ productions.append(lhs + " -> " + str(rhs))
+ return "\n".join(productions)
+
+ def add_production(self, lhs, rhs1, rhs2 = None):
+ if lhs in self._productions:
+ rhs = self._productions.get(lhs)
+ rhs.append(CNFProductionRHS(rhs1, rhs2))
+ else:
+ rhs = list()
+ rhs.append(CNFProductionRHS(rhs1, rhs2))
+ self._productions[lhs] = rhs
+
+ def fetch_lhs(self, rhs1, rhs2 = None):
+ lhs_list = set()
+ for lhs in self._productions:
+ for prod_rhs in self._productions[lhs]:
+ if rhs2 is None:
+ if prod_rhs.is_rhs1() and prod_rhs.is_rhs1_equal(rhs1):
+ lhs_list.add(lhs)
+ else:
+ if prod_rhs.is_rhs2() and prod_rhs.is_rhs2_equal(rhs1, rhs2):
+ lhs_list.add(lhs)
+
+ return lhs_list
+
+ def clear_productions(self):
+ self._productions.clear()
+
+ def get_start_symbol(self):
+ return self._startSymbol
+
+ def display(self):
+ print(str(self))
+
+
+class CNFProductionRHS:
+ def __init__(self, rhs1, rhs2 = None):
+ if rhs2 is None:
+ self._rhs_list = list(rhs1)
+ else:
+ self._rhs_list = list([rhs1, rhs2])
+
+ def __str__(self):
+ return "".join(self._rhs_list)
+
+ def is_rhs1(self):
+ return len(self._rhs_list) == 1
+
+ def is_rhs2(self):
+ return len(self._rhs_list) == 2
+
+ def is_rhs1_equal(self, rhs):
+ return self._rhs_list[0] == rhs
+
+ def is_rhs2_equal(self, rhs1, rhs2):
+ return self._rhs_list[0] == rhs1 and self._rhs_list[1] == rhs2
+
+ def get_productions(self):
+ if self.is_rhs1():
+ return self._rhs_list[0]
+ elif self.is_rhs2():
+ return self._rhs_list[0], self._rhs_list[1]
+ else:
+ return None
+
+
|