Python实现SLR（1）语法分析器
实验课前一天晚上肝了个SLR语法分析器，当时还发朋友圈语法分析器和我晚上总得走一个，从第二天状态来看，应该是我们俩一起走了（笑
- 编写的时间比较仓促，所以代码有些地方实现不是很好，存在一些问题，以后有时间的话再来修补一下，比如在对两个项目规范族进行比较时效率比较低，first集和follow集中对连续多个非终结符推到ε的情况下可能会有bug，但在我的文法定义中特意绕开了ε，勉强能用。
- 为了方便代码阅读，加入了许多注释后的打印语句，将这些打印语句取消注释后运行，能够告诉你当前这段代码所做的事。
- 在编写过程中，尽量对模块进行封装，把逻辑和文法定义分开，做到文法可以方便地修改，但时间过于仓促可能还是有点小问题。当文法修改时，修改
getCol函数（该函数将终结符和非终结符映射到action和goto表中相应的列），initProduction函数（该函数定义了文法产生式（拓广文法），在本文中有28个产生式），source（输入单词序列），varset（非终结符集合），terminalset（终结符集合）
SLR（1）分析流程
- 输入文法
- 求first集
- 求follow集
- 构造LR（0）项目集DFA
- 构造Action和Goto
- 按照Action和Goto进行分析
1.主要数据结构定义和基础函数：
基础函数
-
isVariable函数判断是不是非终结符
-
isTerminal函数判断是不是终结
-
transf(production_set, var)函数 production_set为一个LR（0）项目，尝试通过var（终结符或非终结符）进行转移
-
isSameStatus（status1, status2）函数：判断status1和status2是不是两个相同的LR（0）项目
-
isInPointset(production_set, pointset):#用来检验production_set是不是已经存在的point ，如果存在就把point返回（生成DFA时用到）
数据结构
- 产生式采用类来存储，left和right分别为list，number‘为产生式编号
- GraphPoint存储DFA转移，transfer为有向边集合，集合中的一个元素由var（终结符或非终结符），和另一个GraphPoint组成
class Production:
def __init__(self, left, right, number):
self.left = left
self.right = right
self.number = number
class GraphPoint:
def __init__(self, begin_production, id):
self.status = begin_production
self.transfer = []
self.id = id
def add_transfer(self, var, graphPoint):
self.transfer.append([var, graphPoint])2.文法定义
1.分析目标代码：int lexicalanalysis(){ float a; int b; a=1.1; b=2; while(b<100){ b=b+1; a=a+3;}; if(a>5) {b=b-1;} else {b=b+1;}}
2.语法分析器输入为目标代码的词法分析器输出的单词序列
source = [[5, "int", " 关键字"], [1, "lexicalanalysis", " 标识符"], [13, "(", " 左括号"], [14, ")", " 右括号"], [20, "{", " 左大括号"],
[4, "float", " 关键字"], [1, "a", " 标识符"], [15, ";", " 分号"], [5, "int", " 关键字"], [1, "b", " 标识符"],
[15, ";", " 分号"], [1, "a", " 标识符"], [12, "=", " 赋值号"], [3, "1.1", " 浮点数"], [15, ";", " 分号"], [1, "b", " 标识符"],
[12, "=", " 赋值号"], [2, "2", " 整数"], [15, ";", " 分号"], [8, "while", " 关键字"], [13, "(", " 左括号"],
[1, "b", " 标识符"], [17, "<", " 小于号"], [2, "100", " 整数"], [14, ")", " 右括号"], [20, "{", " 左大括号"],
[1, "b", " 标识符"], [12, "=", " 赋值号"], [1, "b", " 标识符"], [9, "+", " 加 号"], [2, "1", " 整数"], [15, ";", " 分号"],
[1, "a", " 标识符"], [12, "=", " 赋值号"], [1, "a", " 标识符"], [9, "+", " 加号"], [2, "3", " 整数"], [15, ";", " 分号"],
[21, "}", " 右大括号"], [15, ";", " 分号"], [6, "if", " 关键字"], [13, "(", " 左括号"], [1, "a", " 标识符"],
[16, ">", " 大于号"], [2, "5", " 整数"], [14, ")", " 右括号"], [20, "{", " 左大括号"], [1, "b", " 标识符"],
[12, "=", " 赋值号"], [1, "b", " 标识符"], [10, "-", " 减号"], [2, "1", " 整数"], [15, ";", " 分号"], [21, "}", " 右大括号"],
[7, "else", " 关键字"], [20, "{", " 左大括号"], [1, "b", " 标识符"], [12, "=", " 赋值号"], [1, "b", " 标识符"],
[9, "+", " 加号"], [2, "1", " 整数"], [15, ";", " 分号"], [21, "}", " 右大括号"], [21, "}", " 右大括号"]]3.文法定义：拓广文法共有28个产生式，0号产生式为保证分析器只有一个接受状态，而拓广的产生式。
def initProduction():
production_list = []
production = Production(["A1"], ["A"], 0)
production_list.append(production)
production = Production(["A"], ["E", "I", "(", ")", "{", "D", "}"], 1)
production_list.append(production)
production = Production(["E"], ["int"], 2)
production_list.append(production)
production = Production(["E"], ["float"], 3)
production_list.append(production)
production = Production(["D"], ["D", ";", "B"], 4)
production_list.append(production)
production = Production(["B"], ["F"], 5)
production_list.append(production)
production = Production(["B"], ["G"], 6)
production_list.append(production)
production = Production(["B"], ["M"], 7)
production_list.append(production)
production = Production(["F"], ["E", "I"], 8)
production_list.append(production)
production = Production(["G"], ["I", "=", "P"], 9)
production_list.append(production)
production = Production(["P"], ["K"], 10)
production_list.append(production)
production = Production(["P"], ["K", "+", "P"], 11)
production_list.append(production)
production = Production(["P"], ["K", "-", "P"], 12)
production_list.append(production)
production = Production(["I"], ["id"], 13)
production_list.append(production)
production = Production(["K"], ["I"], 14)
production_list.append(production)
production = Production(["K"], ["number"], 15)
production_list.append(production)
production = Production(["K"], ["floating"], 16)
production_list.append(production)
production = Production(["M"], ["while", "(", "T", ")", "{", "D", ";", "}"], 18)
production_list.append(production)
production = Production(["N"], ["if", "(", "T", ")", "{", "D",";", "}", "else", "{", "D", ";","}"], 19)
production_list.append(production)
production = Production(["T"], ["K", "L", "K"], 20)
production_list.append(production)
production = Production(["L"], [">"], 21)
production_list.append(production)
production = Production(["L"], ["<"], 22)
production_list.append(production)
production = Production(["L"], [">="], 23)
production_list.append(production)
production = Production(["L"], ["<="], 24)
production_list.append(production)
production = Production(["L"], ["=="], 25)
production_list.append(production)
production = Production(["D"], ["B"], 26)
production_list.append(production)
production = Production(["B"], ["N"], 27)
production_list.append(production)
return production_list
3.求First集
根据此算法即可求解first集，第8，9步可以采用递归的方式进行求解。
def getFirst(production_list, varset, terminalset):
first_dic = {}
# 用来标记first集是否计算完毕，防止重复计算浪费时间
done = {}
for var in varset:
first_dic[var] = set()
done[var] = 0
# 所有终结符的first集是他自身
for var in terminalset:
first_dic[var] = {var}
done[var] = 1
# print("初始化后的done",done)
# print("初始化的first_dic",first_dic)
for var in varset:
if done[var] == 0:
# print("计算",var)
getFirstForVar(var, first_dic, varset, terminalset, done)
# print("计算完毕",var)
# print("此时的done", done)
# print("此时的first_dic", first_dic)
else:
pass
return first_dic
def getFirstForVar(var, first_dic, varset, terminalset, done):
# 已经推导过直接结束
if done[var] == 1:
# print("我已经推导过了吼")
return
# 对非终结符求first集合,先看右边第一个元素为终结符
for production in production_list:
if var in production.left:
if isTerminal(production.right[0], terminalset):
first_dic[var].add(production.right[0])
# 用null表示空字符
if production.right[0] == "null":
# print("出现右侧为空")
first_dic[var].add("null")
# 右边第一个元素为非终结符
for production in production_list:
if var in production.left:
if isVariable(production.right[0], varset):
if var == production.right[0]:
continue
if done[production.right[0]] == 0:
getFirstForVar(production.right[0], first_dic, varset, terminalset, done)
if "null" in first_dic[production.right[0]]:
first_dic[production.right[0]].remove("null")
first_dic[var] = first_dic[var] | first_dic[production.right[0]]
# print("将 ",production.right[0],"的集合 ",first_dic[production.right[0]],"并入",var,"的集合中",first_dic[var],"中","得到",)
if isVariable(production.right[0], varset) and len(production.right) > 1:
index = 1
count = 1
while isVariable(production.right[index], varset):
index = index + 1
count = count + 1
if index >= len(production.right):
break
i = 0
while i < count:
getFirstForVar(production.right[i], first_dic, varset, terminalset, done)
if "null" in first_dic[production.right[i]]:
getFirstForVar(production.right[i + 1], first_dic, varset, terminalset, done)
first_dic[var] = first_dic[var] | first_dic[production.right[i + 1]]
else:
break
i = i + 1
# 完成后置为1
done[var] = 1
4.求解follow集
通过使用非终结符的follow集，提高识别能力，是SLR（1）分析的核心思想。
只有当项目集包含 A→α· ，则action[i，x]= rj，x属于FOLLOW(A)，j为产生式 A→α的编号，通过这种方式可以解决一部分的移进和归约冲突。
ps：代码中有坑，如果文法中出现了刁钻ε，比如几个非终结符连续推为空，会产生bug，时间原因以及我的文法定义中并不存在ε就没有解决这个问题。
def getFollow(varset, terminalset, first_dic, production_list):
follow_dic = {}
done = {}
for var in varset:
follow_dic[var] = set()
done[var] = 0
follow_dic["A1"].add("#")
# for var in terminalset:
# follow_dic[var]=set()
# done[var] = 0
for var in follow_dic:
getFollowForVar(var, varset, terminalset, first_dic, production_list, follow_dic, done)
return follow_dic
def getFollowForVar(var, varset, terminalset, first_dic, production_list, follow_dic, done):
if done[var] == 1:
return
for production in production_list:
if var in production.right:
##index这里在某些极端情况下有bug，比如多次出现var，index只会返回最左侧的
if production.right.index(var) != len(production.right) - 1:
follow_dic[var] = first_dic[production.right[production.right.index(var) + 1]] | follow_dic[var]
# 没有考虑右边有非终结符但是为null的情况
if production.right[len(production.right) - 1] == var:
if var != production.left[0]:
# print(var, "吸纳", production.left[0])
getFollowForVar(production.left[0], varset, terminalset, first_dic, production_list, follow_dic,
done)
follow_dic[var] = follow_dic[var] | follow_dic[production.left[0]]
done[var] = 1
5.构建LR（0）项目集DFA
1.首先先定义一个CLOSURE函数，它将会对集合中的产生式状态进行不断地扩充，并最终形成一个项目集闭包
def CLOSURE(varset, terminalset, production_set, production_list):
算法：
2.构建DFA。函数定义
def generatingGraph(begin_production_set, varset, terminalset, production_list):
我们首先使用0号产生式来形成初始LR（0）项目集，产生初始节点（即开头数据结构中的类），并将它放到一个集合中，每次从集合中取一个节点，来用 每一个var属于（V | T）尝试进行转移，转移成功后将这条有向边存入该节点地transfer中，每次转移后的项目集判断是否是新项目集，如果是新项目集，则将新项目集放入集合中，当集合为空算法停止。
# 生成状态转移图
def generatingGraph(begin_production_set, varset, terminalset, production_list):
global id
CLOSURE(varset, terminalset, begin_production_set, production_list)
beginPoint = GraphPoint(begin_production_set, id)
id = id + 1
# print("从这个状态开始！")
# print(beginPoint.id)
# for onepro in beginPoint.status:
# print(onepro.number, " ", onepro.left, "->", onepro.right, " ")
pointset = [beginPoint]
set = varset | terminalset
stack = [beginPoint]
while len(stack) != 0:
currentPoint = stack.pop()
######
# print("该点被弹出,进行转移！")
# print(currentPoint.id)
# for onepro in currentPoint.status:
# print(onepro.number, " ", onepro.left, "->", onepro.right, " ")
#####
for var in set:
# print("尝试用",var,"进行转移")
result = transf(currentPoint.status, var)
if len(result) == 0:
# print(var,"转移失败！")
continue
else:
# print(var,"可转移！")
# print("将使用result进行转移！")
# for onepro in result:
# print(onepro.number, " ", onepro.left, "->", onepro.right, " ")
# 求出转移后的闭包
CLOSURE(varset, terminalset, result, production_list)
nextpoint = isInPointset(result, pointset)
if nextpoint is None:
# print(var,"转移为新状态：")
# 新节点压入寻找栈和点集合中，旧节点不能压入
nextpoint = GraphPoint(result, id)
id = id + 1
pointset.append(nextpoint)
stack.append(nextpoint)
# print(nextpoint.id)
# for onepro in nextpoint.status:
# print(onepro.number, " ", onepro.left, "->", onepro.right, " ")
currentPoint.add_transfer(var, nextpoint)
# print("生成一个新状态")
# for onepro in result:
# print(onepro.number," ",onepro.left,"->",onepro.right," ")
return pointset
# 形成闭包
def CLOSURE(varset, terminalset, production_set=[], production_list=[]):
sizebefore = len(production_list)
sizeafter = -1
# 用来测试是不是已经形成闭包，避免进入死循环
flag = 0
for production_in_set in production_set:
if production_in_set.right.index(".") != len(production_in_set.right) - 1:
if isVariable(production_in_set.right[production_in_set.right.index(".") + 1], varset):
flag = 1
if flag == 0:
return
while sizeafter != sizebefore:
for production_in_set in production_set:
# 点在最右侧就不可能转移
if (production_in_set.right.index(".") == len(production_in_set.right) - 1):
continue
i = production_in_set.right.index(".") + 1;
# print(i," length",len(production_in_set.right))
if isTerminal(production_in_set.right[i], terminalset):
continue;
templist = []
for x in production_list:
# print(i,len(production_in_set.right))
if x.left[0] == production_in_set.right[i]:
y = copy.deepcopy(x)
y.right.insert(0, ".")
flag = 0
for one in production_set:
rightflag = 0;
if len(one.right) != len(y.right):
rightflag = 1
else:
for j in range(0, len(y.right)):
if one.right[j] != y.right[j]:
rightflag = 1
if one.left[0] == y.left[0] and rightflag == 0:
flag = 1
if flag == 0:
templist.append(y)
sizebefore = len(production_set)
production_set.extend(templist)
sizeafter = len(production_set)
6.构造Action和Goto表
算法：
算法中的（1）（2）思想类似于计算机网络中的洪泛控制，将初始节点放入一个集合中，从集合中取一个节点，从一个节点走出它的所有有向边，并将这个节点标记为已经走过，将到达所有的之前没有走过的节点放入集合中，如此以往，直到集合为空。代码中的一些打印出错的语句为检测是否存在冲突的语句，由于编写时间限制原因，大多数的冲突可被测出，但少部分冲突仍然不可见（天坑）。
算法（3）（4）通过遍历项目集中的产生式状态即可判断。
#Cell为Action中的一个元素，do表示动作，which表示数字，如转移的状态或采用归约的产生式序号，done为是否已经走过，类似于洪泛控制的作用
class Cell:
def __init__(self):
self.do = -1
self.which = -1
self.done = 0
def initActionAndGoto(pointset, varset, terminalset, begin, follow_dic):
Action = [[Cell() for i in range(len(terminalset))] for j in range(len(pointset))]
Goto = [[-1 for i in range(len(varset))] for j in range(len(pointset))]
for point in pointset:
# 转移状态
for tran in point.transfer:
if isVariable(tran[0], varset):
if Goto[point.id][getCol(tran[0])] != -1:
print("出错404")
Goto[point.id][getCol(tran[0])] = tran[1].id
else:
if Action[point.id][getCol(tran[0])].done == 1:
print("出错403")
Action[point.id][getCol(tran[0])].done = 1
Action[point.id][getCol(tran[0])].do = "S"
Action[point.id][getCol(tran[0])].which = tran[1].id
for production in point.status:
if production.right.index(".") == len(production.right) - 1 and production.left[0] == begin:
if Action[point.id][getCol("#")].done == 1:
print("出错415")
Action[point.id][getCol("#")].do = "acc"
Action[point.id][getCol("#")].done = 1
if production.right.index(".") == len(production.right) - 1 and production.left[0] != begin:
# 在follow集中才可归约
for terminal in terminalset:
if terminal in follow_dic[production.left[0]]:
# 冲突检测
if Action[point.id][getCol(terminal)].done == 1:
for xx in point.status:
print(xx.number, " ", xx.left, "->", xx.right)
print("Action表", point.id, "行", getCol(terminal), "列冲突")
print("原本", Action[point.id][getCol(terminal)].do, Action[point.id][getCol(terminal)].which)
print("现在", "R", production.number)
print("出错416")
Action[point.id][getCol(terminal)].do = "R"
Action[point.id][getCol(terminal)].done = 1
# 采用该产生式归约
Action[point.id][getCol(terminal)].which = production.number
return Action, Goto
7.根据Action和Goto进行语法分析
算法思想：
开始时句型前缀栈和状态站分别压入#和0状态。
循环：
如果表中为si，则将缓冲区第一个元素压入句型前缀栈，并将 i（状态）压入状态栈
如果表中为ri ， 则采用第i个表达式进行归约，弹出的元素个数为i个表达式的右侧的元素个数，之后根据栈顶状态和归约得到的非终结符查看GOTO表，查找当前状态，并将当前状态和规约得到的非终结符分别入栈。
如果表中为error！，恭喜出错，去找bug吧（也有可能是你的输入不符合当前文法，文法冲突也会导致这种情况）。
如果表中为acc，恭喜成功。
# SLR分析开始
def SLR(Action, Goto, source, production_list):
source.append([0, "#", "结束符"])
statusstack = [0]
sentence_stack = ["#"]
print(source)
while 1:
print("*****************************************")
print("缓冲区剩余元素", source)
terminal = source.pop(0)
print("状态栈", statusstack)
print("句型栈", sentence_stack)
# 移进
if Action[statusstack[len(statusstack) - 1]][terminal[0]].do == "S":
print("动作： 移入操作，从缓冲区中读取",terminal[1],"元素进行移入，并根据Action压入",Action[statusstack[len(statusstack) - 1]][terminal[0]].which,"状态")
statusstack.append(Action[statusstack[len(statusstack) - 1]][terminal[0]].which)
sentence_stack.append(terminal[1])
elif Action[statusstack[len(statusstack) - 1]][terminal[0]].do == "R":
# 归约
# 记录归约产生式
r_production = 0
for production in production_list:
if production.number == Action[statusstack[len(statusstack) - 1]][terminal[0]].which:
r_production = production
for i in range(len(r_production.right)):
statusstack.pop()
sentence_stack.pop()
statusstack.append(Goto[statusstack[len(statusstack) - 1]][getCol(r_production.left[0])])
print("动作： 归约操作，根据Action表利用第",r_production.number,"个产生式归约")
sentence_stack.append(r_production.left[0])
source.insert(0, terminal)
elif Action[statusstack[len(statusstack) - 1]][terminal[0]].do == "acc":
print("！！！！！！！！！！语义分析完成！！！！！！！！！！！！！！")
break;
else:
print("error 462!");
8.运行与测试
source = [[5, "int", " 关键字"], [1, "lexicalanalysis", " 标识符"], [13, "(", " 左括号"], [14, ")", " 右括号"], [20, "{", " 左大括号"],
[4, "float", " 关键字"], [1, "a", " 标识符"], [15, ";", " 分号"], [5, "int", " 关键字"], [1, "b", " 标识符"],
[15, ";", " 分号"], [1, "a", " 标识符"], [12, "=", " 赋值号"], [3, "1.1", " 浮点数"], [15, ";", " 分号"], [1, "b", " 标识符"],
[12, "=", " 赋值号"], [2, "2", " 整数"], [15, ";", " 分号"], [8, "while", " 关键字"], [13, "(", " 左括号"],
[1, "b", " 标识符"], [17, "<", " 小于号"], [2, "100", " 整数"], [14, ")", " 右括号"], [20, "{", " 左大括号"],
[1, "b", " 标识符"], [12, "=", " 赋值号"], [1, "b", " 标识符"], [9, "+", " 加 号"], [2, "1", " 整数"], [15, ";", " 分号"],
[1, "a", " 标识符"], [12, "=", " 赋值号"], [1, "a", " 标识符"], [9, "+", " 加号"], [2, "3", " 整数"], [15, ";", " 分号"],
[21, "}", " 右大括号"], [15, ";", " 分号"], [6, "if", " 关键字"], [13, "(", " 左括号"], [1, "a", " 标识符"],
[16, ">", " 大于号"], [2, "5", " 整数"], [14, ")", " 右括号"], [20, "{", " 左大括号"], [1, "b", " 标识符"],
[12, "=", " 赋值号"], [1, "b", " 标识符"], [10, "-", " 减号"], [2, "1", " 整数"], [15, ";", " 分号"], [21, "}", " 右大括号"],
[7, "else", " 关键字"], [20, "{", " 左大括号"], [1, "b", " 标识符"], [12, "=", " 赋值号"], [1, "b", " 标识符"],
[9, "+", " 加号"], [2, "1", " 整数"], [15, ";", " 分号"], [21, "}", " 右大括号"], [21, "}", " 右大括号"]]
id = 0
varset = {"A1", "A", "E", "I", "D", "F", "G", "M", "P", "K", "T", "L", "B","N"}
terminalset = {"(", ")", "{", "}", ";", "int", "float", "number", "floating", "while", "if", "else", ">", "<", ">=",
"<=", "==", "=", "#", "+", "-", "id"}
production_list = initProduction()
first_dic = getFirst(production_list, varset, terminalset)
# for x in first_dic:
# print(x," : ",first_dic[x])
follow_dic = getFollow(varset, terminalset, first_dic, production_list)
# print("follow:")
# for x in follow_dic:
# print(x, ":", follow_dic[x])
production = Production(["A1"], [".", "A"], 0)
production_set = [production]
# for x in production_set:
# print(x.number," ",x.left,"->",x.right," ")
pointset = generatingGraph(production_set, varset, terminalset, production_list)
begin = "A1"
Action, Goto = initActionAndGoto(pointset, varset, terminalset, begin, follow_dic)
print("**********************GOTO***********************************")
for i in range(len(Goto)):
print(i, end=" ")
for j in range(len(Goto[i])):
print("%3d" % Goto[i][j], end=" ")
print("")
print("**********************Action***********************************")
for i in range(len(Action)):
print("%2d" % i, end=": ")
for j in range(len(Action[i])):
if (Action[i][j].done == 0):
print("error!", end=" ")
else:
print("%3s" % Action[i][j].do, "%2d" % Action[i][j].which, end=" ")
print("")
SLR(Action, Goto, source, production_list)
结果：
GOTO表（局部）：（60*14）
Action表（局部）：60*22
规约过程（局部）：共142次
开始：
结束：
完整代码编译原理结课会放在博客里
2020.11.12
