python ply 语法分析器 python 语法解析器 |
您所在的位置：网站首页 › python语法解析器 › python ply 语法分析器 python 语法解析器 |
python ply 语法分析器 python 语法解析器
|
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(b5) {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, "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"], ["="], 23) production_list.append(production) production = Production(["L"], ["", 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, Goto7.根据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, "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", ">", "=", "",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 --------------------------------------------------------------------------------------------------------------------------------------------- 2020.12.27 完整代码： import copy class Production: def __init__(self, left, right, number): self.left = left self.right = right self.number = number def isTerminal(value, terminalset): if value in terminalset: return 1 return 0 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 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 def isVariable(value, varset): if value in varset: return 1 return 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"], ["="], 23) production_list.append(production) production = Production(["L"], ["", 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) class Cell: def __init__(self): self.do = -1 self.which = -1 self.done = 0 def getCol(var): col_dic = {} col_dic["#"] = 0 col_dic["id"] = 1 col_dic["number"] = 2 col_dic["floating"] = 3 col_dic["float"] = 4 col_dic["int"] = 5 col_dic["if"] = 6 col_dic["else"] = 7 col_dic["while"] = 8 col_dic["+"] = 9 col_dic["-"] = 10 col_dic["=="] = 11 col_dic["="] = 12 col_dic["("] = 13 col_dic[")"] = 14 col_dic[";"] = 15 col_dic[">"] = 16 col_dic["="] = 18 col_dic["", "=", "",x.right," ") pointset = generatingGraph(production_set, varset, terminalset, production_list) # print(len(pointset)) 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)
|
【本文地址】
今日新闻 |
推荐新闻 |