-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLL(1)_anylize
230 lines (219 loc) · 11.8 KB
/
LL(1)_anylize
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
import wx
import wx.xrc
FIRST = {}
FOLLOW = {}
GRAMMER = dict() #dict()构造字典，非终结符将存在键中，推导式存在值中
VT = set() #终结符集
TABLE = dict() #分析表
STACK = list() #分析栈
class haha(wx.Frame):
def __init__(self, parent):
wx.Frame.__init__(self, parent, id=wx.ID_ANY, title="实验二", pos=wx.DefaultPosition, size=wx.Size(660, 527),
style=wx.CAPTION | wx.CLOSE_BOX | wx.MINIMIZE_BOX | wx.SYSTEM_MENU | wx.TAB_TRAVERSAL, name=u"Main")
self.m_staticText3 = wx.StaticText(self, wx.ID_ANY, u"请选择文法文件的位置", wx.DefaultPosition, wx.DefaultSize, 0)
self.m_ListCtrl1 = wx.ListCtrl(self, -1, style=wx.LC_REPORT, size=wx.Size(630, 510))
self.m_ListCtrl1.InsertColumn(0, "分析栈")
self.m_ListCtrl1.InsertColumn(1, "剩余输入串")
self.m_ListCtrl1.InsertColumn(2, "所用产生式")
self.m_ListCtrl1.InsertColumn(3, "动作")
self.getVT()
self.getfirst()
self.getfollow()
self.gettable()
self.LLanylize()
def getgrammer(self): #读入文法，将文法存入grammer字典
file_grammer = open("ceshi.txt") #打开文件
for line in file_grammer.readlines(): #readlines()会读入文件的所有行
GRAMMER[line[0]]=list() #为所有非终结符构造列表
file_grammer = open("ceshi.txt")
for line in file_grammer.readlines(): #当文法有'|'时，从'|'进行切片，用replace(),将\n替换为""空字符
infer = line[3:].replace("\n", "").split("|")
for a in infer: #若出现切边，则需一个一个取出放入每个Vn的列表中，否则会出现列表嵌套列表
GRAMMER[line[0]].append(a) #对字典进行对应的键值对加入推导式
print("GRAMMER: ", GRAMMER, "\n")
def getVT(self):
self.getgrammer()
VT.add("#")
for a in GRAMMER.values(): #得到键值对的值，即获得各个推导式的右部
for b in a: #分别处理各个值
for c in b: #对各个值提取单个字符
if not(c.isupper()) and (c != 'ε'): #若不是大写字母且不是空子，即为终结符集
VT.add(c)
print("VT: ", VT, "\n")
def getfirst(self):
qs=0
for a in GRAMMER: #步骤1，若X->a... 则将a加入FIRST(X),若X->ε,则将ε加入FIRST(X)
FIRST[a] = list() #list()用于创建一个列表，或者将元组转为列表
infer = GRAMMER[a] #得到推导式
for b in infer:
if not (b[0].isupper()):
FIRST[a].append(b[0])
for i in range(1,5): #步骤2，若X->Y...，则将FIRST(Y)加入FIRST(X)
for x in FIRST:
qs = qs + len(FIRST[x])
qw = qs
for a in GRAMMER:
for b in GRAMMER[a]:
count = 0
tem = 0
if (b[0].isupper()) and 'ε' not in FIRST[b[0]]:
for c in FIRST[b[0]]:
FIRST[a].append(c)
while(b[count].isupper()) and (count < len(b)-1): #步骤三，连续几个非终结符都含有空字
count = count + 1
if ("ε" in FIRST[b[count-1]]):
tem = tem +1
if(tem == count):
FIRST[a].append("ε")
for x in FIRST:
qs = qs + len(FIRST[x])
if(qs == qw):
break
for a in FIRST: #去重
FIRST[a] = list(set(FIRST[a]))
print("FIRST: ", FIRST, "\n")
def getfollow(self):
qs=0
for q in GRAMMER:
FOLLOW[q] = list() #FOLLOW字典里分别构造列表
for q in GRAMMER:
FOLLOW[q].append("#")
break
for i in range(1, 5):
for x in FOLLOW:
qs = qs + len(FOLLOW[x])
qw = qs
for a in GRAMMER:
tem = GRAMMER[a]
for b in tem:
count = 0 #count用于指向当前字符和右边相邻字符
for c in b:
count = count + 1
length = len(b) #步骤一，若A->aBb,则把FIRST(b)^ε放入FOLLOW(B)中
if (c.isupper()) and (count <= length - 1): #防止越界
if not (b[count].isupper()):
FOLLOW[c].append(b[count]) #b为终结符，将其加入FOLLOW(B)
if (b[count].isupper()):
for z in FIRST[b[count]]:
FOLLOW[c].append(z) #b为非终结符，将FIRST(b)^ε放入FOLLOW(B)
FOLLOW[c].remove("ε")
if (count <= length - 1): #情况二，A->aB，A->aBb，ε在FIRST(b),则把FOLLOW(A)放入FOLLOW(B)
if (b[count].isupper()) and (length == 2):
for z in FOLLOW[a]:
FOLLOW[b[count]].append(z)
if (count + 1 <= length - 1):
if (b[count].isupper()):
if (b[count].isupper()) and (b[count + 1].isupper()) and ("ε" in FIRST[b[count + 1]]):
for z in FOLLOW[a]:
FOLLOW[b[count]].append(z)
for x in FOLLOW:
qs = qs + len(FOLLOW[x])
if (qs == qw):
break
for a in FIRST: #去重
FOLLOW[a] = list(set(FOLLOW[a]))
print("FOLLOW: ", FOLLOW, "\n")
def gettable(self):
for key in GRAMMER: #对于每一个产生式A->..B.. 若a在FIRST(..B..)中，则将A->..B..放入G[A,a]中
for produce in GRAMMER[key]:
first_str = produce[0]
if not(first_str.isupper()): #FIRST(..B..)的FIRST集等于首字符的FIRST集
if (first_str != "ε"):
TABLE[(key, first_str)] = produce
if (first_str.isupper()):
for subset in FIRST[first_str]:
if (subset != "ε"):
TABLE[(key, subset)] = produce
for key in GRAMMER: #步骤2
for produce in GRAMMER[key]:
first_str = produce[0]
if (first_str == "ε"):
for subset in FOLLOW[key]:
TABLE[(key, subset)] = produce
if (first_str != "ε") and not(first_str.isupper):
if "ε" in FIRST[first_str]:
for subset in FOLLOW[key]:
TABLE[(key, subset)] = produce
i=0
for a in TABLE:
print("TABLE: ",a ,TABLE[a],end='')
i=i+1
if i == 5:
print("\n")
i=0
def LLanylize(self):
mes = input()
message = list()
for a in mes:
message.append(a)
#message = ['i','+','i','*','i','#']
STACK.append("#")
for key in TABLE:
STACK.append(key[0])
break
length = len(message)
print("分析栈\t"+"剩余输入串\t"+"所用产生式\t"+"动作")
index = self.m_ListCtrl1.InsertItem(self.m_ListCtrl1.GetItemCount(), str(1))
self.m_ListCtrl1.SetItem(index, 0, "".join(STACK)) # 分析栈
self.m_ListCtrl1.SetItem(index, 1, "".join(message)) # 剩余输入串
self.m_ListCtrl1.SetItem(index, 2, "") # 所用产生式
self.m_ListCtrl1.SetItem(index, 3, "初始化") # 动作
self.m_ListCtrl1.SetColumnWidth(0, 120)
self.m_ListCtrl1.SetColumnWidth(1, 120)
self.m_ListCtrl1.SetColumnWidth(2, 120)
self.m_ListCtrl1.SetColumnWidth(3, 175)
while STACK and message:
for key in TABLE:
if not STACK and not message:
break
if (key[1] == message[0]): #分析表不为空白时处理
tem = list(TABLE[(key[0], message[0])]) #tem临时存储产生式右部
tem1 = list(reversed(tem)) #复制列表副本
STACK.pop() #弹出分析栈最后一个字符
while tem:
STACK.append(tem.pop()) #将使用的产生式倒序入栈
if (STACK[-1] != "ε"):
print(STACK, message, key[0], "->", TABLE[key], "pop", "push(", tem1, ")")
x3 = [key[0], "->", TABLE[key]]
x4 = ["pop", " push(", "".join(tem1), ")"]
index = self.m_ListCtrl1.InsertItem(self.m_ListCtrl1.GetItemCount(), str(1))
self.m_ListCtrl1.SetItem(index, 0, "".join(STACK)) # 分析栈
self.m_ListCtrl1.SetItem(index, 1, "".join(message)) # 剩余输入串
self.m_ListCtrl1.SetItem(index, 2, "".join(x3)) # 所用产生式
self.m_ListCtrl1.SetItem(index, 3, "".join(x4)) # 动作
self.m_ListCtrl1.SetColumnWidth(0, 120)
self.m_ListCtrl1.SetColumnWidth(1, 120)
self.m_ListCtrl1.SetColumnWidth(2, 120)
self.m_ListCtrl1.SetColumnWidth(3, 175)
if (STACK[-1] == "ε"):
STACK.pop() #只是出现空字时直接将其弹出
print(STACK, message, key[0], "->", TABLE[key], "pop")
index = self.m_ListCtrl1.InsertItem(self.m_ListCtrl1.GetItemCount(), str(1))
x3 = [key[0], "->", TABLE[key]]
x4 = ["pop"]
self.m_ListCtrl1.SetItem(index, 0, "".join(STACK)) # 分析栈
self.m_ListCtrl1.SetItem(index, 1, "".join(message)) # 剩余输入串
self.m_ListCtrl1.SetItem(index, 2, "".join(x3)) # 所用产生式
self.m_ListCtrl1.SetItem(index, 3, "".join(x4)) # 动作
self.m_ListCtrl1.SetColumnWidth(0, 120)
self.m_ListCtrl1.SetColumnWidth(1, 120)
self.m_ListCtrl1.SetColumnWidth(2, 120)
self.m_ListCtrl1.SetColumnWidth(3, 175)
if (STACK[-1] == message[0]):
STACK.pop() #分析栈
message.pop(0) #分析串出队第一个
print(STACK, message, key[0], "->", TABLE[key])
index = self.m_ListCtrl1.InsertItem(self.m_ListCtrl1.GetItemCount(), str(1))
self.m_ListCtrl1.SetItem(index, 0, "".join(STACK)) # 分析栈
self.m_ListCtrl1.SetItem(index, 1, "".join(message)) # 剩余输入串
self.m_ListCtrl1.SetItem(index, 2, "") # 所用产生式
self.m_ListCtrl1.SetItem(index, 3, "getnext(I)") # 动作
self.m_ListCtrl1.SetColumnWidth(0, 120)
self.m_ListCtrl1.SetColumnWidth(1, 120)
self.m_ListCtrl1.SetColumnWidth(2, 120)
self.m_ListCtrl1.SetColumnWidth(3, 175)
if __name__ == '__main__':
app = wx.App(False)
b = haha(None)
b.Show(True)
app.MainLoop()