LL1语法生成器-python
因为题主时间能力有限，没有格外写一个控制页面，只能完成最基础的语法生成。效果如下：
另外，可能是代码本身问题，有时会跑不出来，多跑几次就好了。如果有大佬知道原因也欢迎留下评论！
构建first集
# 获取first集
def getFirst():
while (1):
test = FIRST.copy()
for i in sentences:
temp0 = i.split("->")[0]
temp1 = i.split("->")[1]
if (temp0 in VT) or (temp1[0] in VT) or (temp1[0] == 'ε'):
if (temp0 in VT):
FIRST[temp0] = FIRST.get(temp0)
else:
FIRST[temp0] = FIRST.get(temp0) + temp1[0]
else: # 首字符为非终结符
flag = 1
for j in temp1:
FIRST[temp0] = FIRST.get(temp0) + str(FIRST[j]).replace('ε', '')
if 'ε' not in FIRST[j]: # 若不含空集则break
flag = 0
break
if flag == 1:
FIRST[temp0] = FIRST.get(temp0) + 'ε'
for i, j in FIRST.items():
temp = ""
for word in list(set(j)):
temp += word
FIRST[i] = temp
if test == FIRST:
break
print(FIRST)
构建follow集
def getFollow():
while (1):
test = FOLLOW.copy()
for i in sentences:
temp0 = i.split("->")[0]
temp1 = i.split("->")[1]
for p in temp1:
if p in VT or p == 'ε':
continue
local = temp1.find(p)
flag0 = 0 # 判断是否为终结符
flag1 = 0
for j in temp1[local + 1:]:
FOLLOW[p] = FOLLOW.get(p) + str(FIRST[j]).replace('ε', '')
if 'ε' not in FIRST[j] or j in VT:
if j in VT:
flag0 = 1
else:
flag1 = 1
break
if (flag1 == 0) and (flag0 == 0):
FOLLOW[p] = FOLLOW.get(p) + FOLLOW.get(temp0)
for i, j in FOLLOW.items():
temp = ""
for word in list(set(j)):
temp += word
FOLLOW[i] = temp
if test == FOLLOW:
break
print(FOLLOW)
构建分析表
# 像二维字典插入数据
def addDict(dict, a, b, val):
if a in dict:
dict[a].update({b: val})
else:
dict.update({a: {b: val}})
# 构建预测分析表
def creat_Select():
print(sentences)
for sentence in sentences:
a=sentence.split("->")[0]
str=sentence.split("->")[1]
temp=str[0]
for i in VT:
if i in FIRST[temp]:
addDict(SELECT, a, i, str)
if 'ε' in FIRST[temp]:
for j in FOLLOW[a]:
addDict(SELECT, a, j, 'ε')
print(SELECT)
以下为全部代码
import sys
VT = [] # 终结符
VN = [] #
sentences = [] # 语法
file = "text.txt"
Start = 'E'
FIRST = {} # first集
FOLLOW = {} # follow 集
SELECT = {"": {"": ""}} # 分析表
STACK = ["#"] # 输入栈
STACK_INPUT = [] # 剩余输入串
massage = []
def getGram():
with open(file, encoding='UTF-8') as f:
text = f.read().splitlines()
print(text)
for sentence in text:
Start = sentence[0]
if len(sentence.split('|')) < 2:
sentences.append(sentence)
else:
part_head = sentence.split('|')[0]
sentences.append(part_head)
for i in sentence.split('|')[1:]:
sentences.append(part_head[0] + "->" + i)
print(sentences)
# 获取VN
def getVN():
for i in sentences:
if i[0] not in VN:
VN.append(i[0])
VN.sort()
print(VN)
# 获取VT
def getVT():
for i in sentences:
for j in i:
if not j.isupper():
if not j in VT:
VT.append(j)
VT.remove('ε')
VT.sort()
print(VT)
def initail():
for str in sentences:
part_begin = str.split("->")[0]
part_end = str.split("->")[1]
FIRST[part_begin] = ""
FOLLOW[part_begin] = ""
for i in VT:
FIRST[i] = i
FOLLOW[i] = i
FIRST['ε'] = 'ε'
FOLLOW['ε'] = 'ε'
FOLLOW[Start] = '#'
# 获取first集
def getFirst():
while (1):
test = FIRST.copy()
for i in sentences:
temp0 = i.split("->")[0]
temp1 = i.split("->")[1]
if (temp0 in VT) or (temp1[0] in VT) or (temp1[0] == 'ε'):
if (temp0 in VT):
FIRST[temp0] = FIRST.get(temp0)
else:
FIRST[temp0] = FIRST.get(temp0) + temp1[0]
else: # 首字符为非终结符
flag = 1
for j in temp1:
FIRST[temp0] = FIRST.get(temp0) + str(FIRST[j]).replace('ε', '')
if 'ε' not in FIRST[j]: # 若不含空集则break
flag = 0
break
if flag == 1:
FIRST[temp0] = FIRST.get(temp0) + 'ε'
for i, j in FIRST.items():
temp = ""
for word in list(set(j)):
temp += word
FIRST[i] = temp
if test == FIRST:
break
print(FIRST)
# 获取follow集
def getFollow():
while (1):
test = FOLLOW.copy()
for i in sentences:
temp0 = i.split("->")[0]
temp1 = i.split("->")[1]
for p in temp1:
if p in VT or p == 'ε':
continue
local = temp1.find(p)
flag0 = 0 # 判断是否为终结符
flag1 = 0
for j in temp1[local + 1:]:
FOLLOW[p] = FOLLOW.get(p) + str(FIRST[j]).replace('ε', '')
if 'ε' not in FIRST[j] or j in VT:
if j in VT:
flag0 = 1
else:
flag1 = 1
break
if (flag1 == 0) and (flag0 == 0):
FOLLOW[p] = FOLLOW.get(p) + FOLLOW.get(temp0)
for i, j in FOLLOW.items():
temp = ""
for word in list(set(j)):
temp += word
FOLLOW[i] = temp
if test == FOLLOW:
break
print(FOLLOW)
# 像二维字典插入数据
def addDict(dict, a, b, val):
if a in dict:
dict[a].update({b: val})
else:
dict.update({a: {b: val}})
# 构建预测分析表
def creat_Select():
print(sentences)
for sentence in sentences:
a=sentence.split("->")[0]
str=sentence.split("->")[1]
temp=str[0]
for i in VT:
if i in FIRST[temp]:
addDict(SELECT, a, i, str)
if 'ε' in FIRST[temp]:
for j in FOLLOW[a]:
addDict(SELECT, a, j, 'ε')
print(SELECT)
def record(left1, key='', string=''):
msg = ""
for s in STACK:
msg += s
if key == '':
b = ''
c = 'GETNEXT'
else:
b = '{}->{}'.format(key, string)
c = 'POP,PUSH({})'.format(string)
massage.append([msg,left1, b, c])
def analyse():
STACK_INPUT = input(print("Please input: "))+"#"
STACK.append(Start)
index = 0
a = STACK_INPUT[index]
x = STACK.pop()
while not a == x == '#':
if x in VN:
fm = SELECT[x][a]
for c in reversed(fm):
if c != 'ε':
STACK.append(c)
record(STACK_INPUT[index:], x, fm)
else:
if a in VT:
index += 1
a = STACK_INPUT[index]
record(STACK_INPUT[index:])
x = STACK.pop()
print("步骤 分析栈 剩余输入串 所用产生式 动作")
count=1
for i in massage:
print('{:<5}'.format(count),'{:<8}'.format(i[0]),'{:>7}'.format(i[1]),'{:^13}'.format(i[2]),'{:<13}'.format(i[3]))
count+=1
if __name__ == '__main__':
getGram()
getVT()
getVN()
initail()
getFirst()
getFollow()
creat_Select()
analyse()