-
Notifications
You must be signed in to change notification settings - Fork 0
/
ll grammer.py
345 lines (334 loc) · 15.7 KB
/
ll grammer.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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
import grammmer
class LLGrammer:
def data(self,left,right):
recive = [[left,right]]
print(left+" → "+right)
return recive
############### step 1########################
def find_nullable_rules_nullable_nonterminals(self,productionRule):
print("list of production rule : ",productionRule)
for li in productionRule:
for right in li:
if right=="є":
print(" - The Rule ",li," is nullable rules ")
print(" - The ",li[0]," is nullable nonterminals")
print("----------------------------------------------------------")
return li[0]
############### step 2 #########################
def Compute_the_relation_Begins_Directly(self,NonTENULL,PRoduRuel):
print("list of production rule : ",PRoduRuel)
print(len(PRoduRuel))
collectallforRe=[]
for outer in range(len(PRoduRuel)):
collect=[]
if PRoduRuel[outer]==['A', 'є']:
continue
print(PRoduRuel[outer])
print(PRoduRuel[outer][0]," → ",PRoduRuel[outer][1])
#print(len(PRoduRuel[outer][1]))
for rightside in range(len(PRoduRuel[outer][1])):
collect += [PRoduRuel[outer][1][rightside]]
print("The BDW Is : ",collect[0])
if collect[0]==NonTENULL:
print("The BDW Is : ",collect[1])
collectallforRe.append(PRoduRuel[outer][0]+" BDW "+collect[1])
collectallforRe +=[PRoduRuel[outer][0]+" BDW "+collect[0]]
print(collectallforRe)
print("/////////////////////////////")
return collectallforRe
############## step 3 ##########################
def Compute_the_elation_Begins_With(self,BWDdata):
print('------------------------------------------------------------------')
def BWtranstive(a):
closure = list(a)
while True:
new_relations = list([x,"BW",w] for x,y in closure for q,w in closure if q == y)
return new_relations
orginaldata2= []
y =[]
nonterm = []
termin = []
reda =[]
retrivedata =[]
orginaldata=[]
for o in range(len(BWDdata)):
for i in range(len(BWDdata[o])):
reda = BWDdata[o][i].replace('BDW','BW')
y =BWDdata[o][0]
orginaldata +=[[y,reda]]
orginaldata2 +=[[y,"BW",reda]]
if y.isupper():
nonterm =y
for nonte in nonterm:
retrivedata +=[[nonte,"Bw",nonte]]
if reda.islower():
termin =reda
for te in termin:
retrivedata +=[[termin,"Bw",termin]]
removeDupDa = set(tuple(x) for x in retrivedata)
finaldata = [ list(x) for x in removeDupDa ]
TransitveClosure = BWtranstive(orginaldata)
print("The Transistive is : ",TransitveClosure)
print("The Reflsive is : ",finaldata)
print("allDatafinaldata is : ")
return [list(TransitveClosure),list(finaldata),list(orginaldata2)]
############## step 4 ##########################
def Compute_the_set_of_terminals_First(self,BW):
collectdata = []
collectdata2=[]
collectdata3=[]
for o in range(len(BW)):
for i in range(len(BW[o])):
#print(BW[o][i][0],BW[o][i][1])
if BW[o][i][0].isupper() and BW[o][i][2].islower():
collectdata += [["First :",BW[o][i][0]]+[BW[o][i][2]]]
collectdata2 += BW[o][i][0]+BW[o][i][2]
print("First(",BW[o][i][0],") = {",BW[o][i][2],"}")
elif BW[o][i][0].islower() and BW[o][i][2].islower():
print("First(",BW[o][i][0],") = {",BW[o][i][2],"}")
collectdata += [["First :",BW[o][i][0]]+[BW[o][i][2]]]
collectdata2 +=BW[o][i][0]+BW[o][i][2]
print("First of :",collectdata2)
return collectdata2
############## step 5 ##########################
def Compute_First_of_right_side_of_each_rule(self,lst1, lst2,Nonterminal):
lst3 = []
colda1=[]
colda2=[]
valuesofNonTer = []
for value in lst1:
valuesofNonTer +=[value]
for inner in value:
print(value)
if value[0] in lst2 and inner[0].isupper() and inner[0]==Nonterminalnull:
lst3 +=[lst2.index(value[0])]
elif value[0] in lst2 and value[0].islower():
lst3 +=value[0]
elif value[0] =="є":
lst3 +=value[0]
print(lst3)
for outer in range(len(lst3)):
if type(lst3[outer]) == str:
colda1 +=lst3[outer]
else:
colda2 +=lst2[lst3[outer]+1]
return ["Rules is ::",valuesofNonTer,"AND Result IS ::"],["Nonteminal",colda2],["Teminal",colda1]
############## step 6 ##########################
def Compute_the_relation_Is_Followed_Directly_By(self,producdata):
collectdata = []
retdata = []
for ou in range(len(producdata)):
for inner in range(1):
collectdata +=[producdata[ou][1]]
#print(producdata[ou][1])
print(collectdata)
for righthandside in range(len(collectdata)):
for inner in range(len(collectdata[righthandside])):
#print(collectdata[righthandside][inner])
if collectdata[righthandside][inner].isupper():
print(collectdata[righthandside][inner],"followed Directly by",collectdata[righthandside][inner+1])
retdata += [[collectdata[righthandside][inner],"followed Directly by",collectdata[righthandside][inner+1]]]
else:
break
return retdata
###################step 7############################
def Compute_the_relation_Is_Direct_End_Of(self,NonTENULL,PRoduRuel):
print("list of production rule : ",PRoduRuel)
print(len(PRoduRuel))
collectallforRe=[]
for outer in range(len(PRoduRuel)):
collect=[]
if PRoduRuel[outer]==['A', 'є']:
continue
print(PRoduRuel[outer])
print(PRoduRuel[outer][0]," → ",PRoduRuel[outer][1])
for rightside in range(len(PRoduRuel[outer][1])):
collect += [PRoduRuel[outer][1][rightside]]
print(collect[len(collect)-1]," The DEO Is : ",PRoduRuel[outer][0])
if collect[len(collect)-1]==NonTENULL:
print("The DEO Is : ",collect[0])
collectallforRe.append(collect[0]+" DEO "+PRoduRuel[outer][0])
collectallforRe +=[collect[len(collect)-1]+" DEO "+PRoduRuel[outer][0]]
print(collectallforRe)
print("/////////////////////////////")
return collectallforRe
######################step 8 #############################################
def Compute_the_relation_Is_End_Of (self,BWDdata):
BWDdata.pop(2)
print('------------------------------------------------------------------')
def BWtranstive(a):
closure = list(a)
while True:
new_relations = list([x,"Eo",w] for x,y in closure for q,w in closure if q == y)
return new_relations
orginaldata2= []
y =[]
nonterm = []
termin = []
reda =[]
retrivedata =[]
orginaldata=[]
for o in range(len(BWDdata)):
for i in range(len(BWDdata[o])):
reda = BWDdata[o][i].replace('DEO','EO')
y =BWDdata[o][0]
orginaldata +=[[y,reda]]
orginaldata2 +=[[y,"EO",reda]]
if reda.isupper():
nonterm =y
for nonte in nonterm:
retrivedata +=[[nonte,"EO",nonte]]
if y.islower():
termin =reda
for te in termin:
retrivedata +=[[termin,"EO",termin]]
if reda.isupper() and y.isupper():
continue
removeDupDa = set(tuple(x) for x in retrivedata)
finaldata = [ list(x) for x in removeDupDa ]
print(orginaldata)
TransitveClosure = BWtranstive(orginaldata)
print(TransitveClosure)
print("The Transistive is : ",TransitveClosure)
print("The Reflxsive is : ",finaldata)
print("allDatafinaldata is : ")
return [list(finaldata),list(orginaldata2)]
########################step 9#######################
def Compute_the_relation_Is_Followed_By(self,EO,FDB,BW):
print(EO)
print(FDB)
print(BW)
for ouEO in range(len(EO)):
for inEO in range(EO[ouEO]):
print(EO[inEO][2])
####################step 8 ####################################
def Compute_the_relation_Is_Followed_By(self,EO,FDB,BW):
coldataEOstart = []
coldataEOend = []
coldataFDBstart = []
coldataFDBend = []
coldataBWstart = []
coldataBWend = []
FinalDATAOFFDB = []
#print(EO)
#print(FDB)
print(BW)
for ouFDB in range(len(FDB)):
for inFDB in range(1):
#print(FDB[ouFDB][2])
coldataFDBstart +=FDB[ouFDB][0]
coldataFDBend +=FDB[ouFDB][2]
for ouEo in range(len(EO)):
for inEO in range(len(EO[ouEo])):
#print((EO[ouEo][inEO][2]))
coldataEOstart +=EO[ouEo][inEO][0]
coldataEOend +=EO[ouEo][inEO][2]
for ouBW in range(len(BW)):
for inBW in range(len(BW[ouBW])):
#print(BW[ouBW][inBW][0])
coldataBWstart +=BW[ouBW][inBW][0]
coldataBWend +=BW[ouBW][inBW][2]
##############################################
for EOend in coldataEOend:
for FDBstart in coldataFDBstart:
if EOend== FDBstart:
for FDBend in coldataFDBend:
for BWstart in coldataBWstart:
if FDBend==BWstart:
for BWend in coldataBWend:
FinalDATAOFFDB += [[BWstart,"FB",BWend]]
return FinalDATAOFFDB
#######################step 10 ###################################
def Extend_the_FB_relation_to_include_endmarker(self,EO):
for eo in EO:
for inner in eo:
#print(inner[2])
if inner[2]=="S" and inner[0].isupper():
print(inner[2],"FB -->",inner[0])
#####################step 11 ##################################
def Compute_the_Follow_Set_for_each_nullable_nonterminal(self,FB,NONterminal):
colldata = []
colldataother = []
for fb in FB:
for inner in fb:
#print(fb[2])
if fb[2]==NONterminal and fb[0].islower():
colldata +="FOL(",fb[2],") = ",fb[0]
colldataother +=[fb[2],fb[0]]
#print(["FOL(",fb[2],") = ",fb[0]])
print(colldata[0])# because it is repeted
return " ( "+NONterminal+" ) = "+colldataother[1]
############################step 12 ############################
def Compute_the_Selection_Set_for_each_rule(self,First,Folset):
print("First is ",First)
print("Follow set : ",Folset)
ll = LLGrammer()
registerstep1=[]
Nonterminalnull=[]
#Remember When Put nullvalue Change it upper
registerstep1 +=ll.data("S","ABc")
registerstep1 +=ll.data("A","bA")
registerstep1 +=ll.data("A","c")
registerstep1 +=ll.data("B","c")
print("----------------------------------------------------------")
###########################
Nonterminalnull =ll.find_nullable_rules_nullable_nonterminals(registerstep1)
print(Nonterminalnull)
if ['A', 'є'] in registerstep1 and ['B', 'є'] in registerstep1:
#########################################
BDW=ll.Compute_the_relation_Begins_Directly(Nonterminalnull,registerstep1)
print("The Begin dirctory with : ",BDW)
BW = ll.Compute_the_elation_Begins_With(BDW)
print(ll.Compute_the_elation_Begins_With(BDW))
print("----------------------------------------------------------")
#############################################
First=ll.Compute_the_set_of_terminals_First(BW)
print(First)
print("------------------------------------------------------------")
#########################################################
#['A', 'B', 'c', 'b', 'A', 'є', 'c'] right hand side user entered it
FirstRightHandside = ll.Compute_First_of_right_side_of_each_rule([['A', 'B', 'c'], ['b', 'A'], ['c'], ['c']],First,Nonterminalnull)
print(FirstRightHandside)
print("-----------------------------------------------------------")
##############################################################
FDB = ll.Compute_the_relation_Is_Followed_Directly_By(registerstep1)
print("-----------------------------------------------------------")
################################];############################
DEO = ll.Compute_the_relation_Is_Direct_End_Of('A',registerstep1)
print("-----------------------------------------------------------")
############################################################
EO = ll.Compute_the_relation_Is_End_Of(DEO)
print(EO)
############################################################
print("-------------------------------------------------")
FB = ll.Compute_the_relation_Is_Followed_By(EO,FDB,BW)
print(FB)
print("---------------------------------------------")
##########################################################
Endmarker = ll.Extend_the_FB_relation_to_include_endmarker(EO)
print("--------------------------------------------")
###########################################################
Followset = ll.Compute_the_Follow_Set_for_each_nullable_nonterminal(FB,Nonterminalnull)
print(Followset)
print("------------------------------------------")
###########################################################
Seletion_set = ll.Compute_the_Selection_Set_for_each_rule(FirstRightHandside,Followset)
print("The Selection set ----->>>>>> :[[c]",grammmer.selection_set)
else:
#########################################
BDW=ll.Compute_the_relation_Begins_Directly(Nonterminalnull,registerstep1)
print("The Begin dirctory with : ",BDW)
BW = ll.Compute_the_elation_Begins_With(BDW)
print(ll.Compute_the_elation_Begins_With(BDW))
print("----------------------------------------------------------")
#############################################
First=ll.Compute_the_set_of_terminals_First(BW)
print("The Selection set : ",First)
print("------------------------------------------------------------")
#########################################################
#['A', 'B', 'c', 'b', 'A', 'є', 'c'] right hand side user entered it
FirstRightHandside = ll.Compute_First_of_right_side_of_each_rule([['A', 'B', 'c'], ['b', 'A'], ['є'], ['c']],First,Nonterminalnull)
print(FirstRightHandside)
print("-----------------------------------------------------------")
print("The Selection set ---------------->>> : [[c]",grammmer.selection_set)
##############################################################