-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathCFGtoCNF.py
148 lines (131 loc) · 5.47 KB
/
CFGtoCNF.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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
'''
ada 4 step cara ngetranslate CFG to CNF
1. ilangin eplison
2. ilangin non terminal -> non terminal (cuman satu biji di sisi kanan)
3. ilangin variabel yg gabakal tercapai
4. bikin jadi 2 non terminal atau satu terminal di sisi kanan
ini gk ngecover no 1 sama no 3.
no 1 gk dicapai karena blom kebayang gimana caranya hehe
no 3 gk dilakuin karena in reality, ini juga gk pernah kebikin :v. kita bikin variabel ya variabel yang at some point bisa dicapai
'''
'''
- untuk memudahkan, di cfg.txt, kalo ada nonterminal 2 biji di jejerin, kasi spasi dulu. harusnya gk ngerusak, dan memudahkan pengerjaan translate ke CFG. nti waktu udah jadi CFG, mau ditempel juga gamasalah
- jangan tulis enter dibagian akhir dari CFG
- SPECIAL SHIT. ini bakal ngaruh di CYK layer pertama
angka
string
variabel
'''
from os import pipe
CNFVarCounter = 1
# mengembalikan true jika X adalah terminal
# terjadi ketika seluruh kata ditulis dengan huruf kapital
def isNotTerminal(X):
for i in X:
if i not in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
return False
return True
# remove burden lol
def removeBurden(burdenDict,CFGdict,outputString):
while burdenDict:
arrBurdenKey = []
for eachBurdenKey in burdenDict:
arrBurdenKey.append(eachBurdenKey)
# print(arrBurdenKey)
for eachKey in arrBurdenKey:
outputString += eachKey + " -> "
# print("burdenDict[eachBurdenKey]")
# print(burdenDict[eachBurdenKey])
outputString, burdenDict = addToOuputCNF(burdenDict[eachKey],CFGdict,outputString,burdenDict)
del burdenDict[eachKey]
outputString = outputString[0:-2] + ";"
outputString += "\n"
return outputString
# digunakan untuk menambahkan arr ke dalam output string. bisa melihat catatan dict. arr itu list of non terminal or terminal yang ada di sisi kanan CFG.
def addToOuputCNF(arr,dict, outputString,burden):
global CNFVarCounter # artinya 'hey im using the global variable'
# kasus satu. hanya ada satu item, dan item tersebut non terminal aka variabel.
# print('arr = ', arr)
# print(len(arr))
if len(arr) == 1 and isNotTerminal(arr[0]):
# print("kasus satu")
for eachShit in dict[arr[0]]:
# print("heres each shit", eachShit)
outputString,burden = addToOuputCNF(eachShit,dict, outputString,burden)
# kasus dua. hanya ada satu item, dan item tersebut terminal.
elif len(arr) == 1 and not(isNotTerminal(arr[0])):
# print("kasus dua")
outputString += arr[0]
outputString += " | "
# kasus tiga. ada dua item, dan kedunya non terminal
elif len(arr) == 2 and isNotTerminal(arr[0]) and isNotTerminal(arr[1]):
# print(type(outputString))
# print("kasus ketiga")
outputString += arr[0]
outputString += arr[1]
outputString += " | "
# kasus empat. artinya perlu membuat rule baru. barulah burden dipake
else:
# print("kasus empat")
if isNotTerminal(arr[0]):
outputString += arr[0]
outputString += 'CNF'+ str(CNFVarCounter) + " | "
burden['CNF' + str(CNFVarCounter)] = arr[1:]
CNFVarCounter += 1
else:
burden['CNF' + str(CNFVarCounter)] = [arr[0]]
outputString += 'CNF' + str(CNFVarCounter)
CNFVarCounter += 1
if not(len(arr) == 2 and isNotTerminal(arr[1])):
outputString += 'CNF'+ str(CNFVarCounter) + " | "
burden['CNF' + str(CNFVarCounter)] = arr[1:]
CNFVarCounter += 1
else:
outputString += arr[1] + " | "
return outputString,burden
# sebuah prosedur yang melakukan translasi CFG dari file cfg.txt menjadi CNF lalu meletakkannya di file cnf.txt.
# tidak menerima input dan output
def CFGtoCNF(filename):
f = open(filename, "r")
stringCFG = f.read()
listCFG = stringCFG.split("\n")
outputCNF = ""
# buat catetan CFG yang tersedia sebagai dictionary. LeftSide sebagai key, right side sebagai value, dalam bentuk aray (of array hehe)
dictCFG = {}
for element in listCFG:
leftSide= element.split("->")[0]
# print(leftSide)
rightSide = element.split("->")[1]
# print(rightSide)
leftSide = leftSide.lstrip().rstrip()
# outputCNF += leftSide + " -> "
# print(outputCNF)
listRightSide = rightSide.split(";")[0].split("|")
dictCFG[leftSide] = []
for eachRightSide in listRightSide:
eachRightSide = eachRightSide.lstrip().rstrip()
listEachRightSide = eachRightSide.split()
dictCFG[leftSide].append(listEachRightSide)
# print(dictCFG)
# leftSide = 'VALUE'
for leftSide in dictCFG:
# print(leftSide)
outputCNF += leftSide + " -> "
# print("======================================")
burden = {}
for eachRightSide in dictCFG[leftSide]:
# print(eachRightSide)
# burden adalah rule2 baru yang harus di implement
outputCNF,burden = addToOuputCNF(eachRightSide,dictCFG,outputCNF,burden)
# print("burden")
# print(burden)
outputCNF = outputCNF[0:-2] + ";"
outputCNF += "\n"
outputCNF = removeBurden(burden,dictCFG,outputCNF)
# print("====== hasil ======")
# return outputCNF
# print(burden)
# print(outputCNF)
outputCNF = outputCNF[0:-1]
fcyk = open("cnf.txt", "w")
fcyk.write(outputCNF)