python实现编译原理LR(0),SLR(1)

本文章使用python实现LR(0)与SLR(1)的分析过程，使用graphviz画LR的dfa图，使用SLR（1）分析表进行词法分析

---

1.求first集合

```python
def getFirstForVar(production_list, var, first_dic, varset, terminalset, done):
    if done[var] == 1:
        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':
                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_list, 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]]

            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_list, 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 + 1
    done[var] = 1


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
    for var in varset:
        if done[var] == 0:
            getFirstForVar(production_list, var, first_dic, varset, terminalset, done)
        else:
            pass
    return first_dic

2.求follow集合

follow集合中的$符号表示文法语句结束

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:
            if production.right.index(var) != len(production.right) - 1:
                follow_dic[var] = first_dic[production.right[production.right.index(var) + 1]] | follow_dic[var]

            if production.right[len(production.right) - 1] == var:
                if 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 getFollow(varset, terminalset, first_dic, production_list):
    follow_dic = {}
    done = {}
    for var in varset:
        follow_dic[var] = set()
        done[var] = 0
    follow_dic[production_list[0].left[0]] = {'$'}

    for var in follow_dic:
        getFollowForVar(var, varset, terminalset, first_dic, production_list, follow_dic, done)
    return follow_dic

3.计算闭包

def CLOSURE(varset, terminalset, production_set, production_list):
    """
    计算闭包
    :param varset: 非终结符号集
    :param terminalset: 终结符号集
    :param production_set: 状态集合
    :param production_list: 文法规则
    :return: production_set 新的状态集合
    """
    lenbefore = len(production_list)
    lenafter = -1

    #     测试是否已经形成闭包(避免出现死循环)
    flag = 0
    for production_in_set in production_set:
        if production_in_set.right.index('.') != len(production_in_set.right) - 1:
            if production_in_set.right[production_in_set.right.index('.') + 1] in varset:
                flag = 1
    if flag == 0:
        return production_set

    # 当长度不再增大时停止循环
    while lenafter != lenbefore:
        for production_in_set in production_set:
            # 符号.位于最优侧，则无需再进行判断
            if production_in_set.right.index('.') == len(production_in_set.right) - 1:
                continue
            next = production_in_set.right.index('.') + 1
            # 如果符号.的下一符号是终结符号，则无需再进行判断
            if production_in_set.right[next] in terminalset:
                continue
            templist = []
            for x in production_list:
                if x.left == production_in_set.right[next]:
                    # 进行深拷贝
                    y = copy.deepcopy(production_in_set[next])
                    y.right.insert(0, '.')
                    # 判断是否存在原来的状态集合production_set中的标志，1：存在，0：不存在
                    flag = 1
                    for item in production_set:
                        # 判断右边是否相等的标志，1：存在，0：不存在
                        rightflag = 1
                        if len(y.right) != len(item.right):
                            # 右边长度不相同，必然不通
                            rightflag = 0
                        else:
                            # 右边长度相同则逐个符号比较
                            for j in range(len(item.right)):
                                if y.right[j] != item.right[j]:
                                    rightflag = 0
                        if y.left == item.left and rightflag == 1:
                            flag == 0
                    if flag == 0:
                        templist.append(y)
        lenbefore = len(production_set)
        if len(templist) != 0:
            production_set.append(templist)
        lenafter = len(production_set)

    return production_set

4.生成DFA图片

def generatingGraph(begin_production_set, varset, terminalset, production_list):
    """
    生成dfa图
    :param begin_production_set:
    :param varset:
    :param terminalset:
    :param production_list:
    :return:所有结点集
    """
    id = 0
    begin_production_set = CLOSURE(varset, terminalset, begin_production_set, production_list)

    beginPoint = GraphPoint(begin_production_set, id)
    id = id + 1

    pointset = [beginPoint]
    set = []
    for i in varset:
        set.append(i)
    for j in terminalset:
        set.append(j)
    stack = [beginPoint]

    while len(stack) != 0:
        tmp = stack.pop()
        for var in set:
            # 尝试使用var进行转移
            currentpoint = copy.deepcopy(tmp)
            result = transf(currentpoint.status, var)
            if len(result) == 0:
                # 转移失败
                continue
            else:
                # 转移成功
                result = CLOSURE(varset, terminalset, result, production_list)
                if (not isInPointSet(result, pointset)):
                    # 不存在
                    nextpoint = GraphPoint(result, id)
                    id = id + 1
                    pointset.append(nextpoint)
                    stack.append(nextpoint)
                    tmp.add_transfer(var, nextpoint.id)
    return pointset



def drawGraph(pointset):
    # 实例化一个Digraph对象(有向图)，name:生成的图片的图片名，format:生成的图片格式
    dot = Digraph(name="dfa", comment="the test", format="png")

    # 生成图片节点，name：这个节点对象的名称，label:节点名,color：画节点的线的颜色
    for item in pointset:
        label = ''
        for i in item.status:
            label = label + ''.join([str(j) for j in i.left])
            label = label + '->'
            label = label + ''.join([str(j) for j in i.right])
            label = label + '\n'
        label = label + str(item.id)
        dot.node(name=str(item.id), label=label, color='red')

    # 在节点之间画线，label：线上显示的文本,color:线的颜色
    for item in pointset:
        if len(item.transfer) != 0:
            i = 0
            while i < len(item.transfer):
                dot.edge(str(item.id), str(item.transfer[i + 1]), label=str(item.transfer[i]), color='blue')
                i = i + 2

    # 打印生成的源代码
    # print(dot.source)
    # 跟view一样的用法(render跟view选择一个即可)，一般用render生成图片，不使用view=True,view=True用在调试的时候
    dot.render(filename='MyPicture', directory="D:\Mytest", view=True)

5.求Action表与Goto表

def initActionAndGoto(pointset, varset, terminalset, begin, follow_dic):
    """
    构建action与goto表
    :param pointset:
    :param varset:非终结符号集
    :param terminalset:终结符号集
    :param begin:
    :param follow_dic:
    :return:Action, Goto
    """
    varset.append('$')
    terminalset.append('$')
    # 构建action和goto二维表
    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:
        j = 0
        while j < len(point.transfer):
            if isVariable(str(point.transfer[j]), varset):
                Goto[point.id][getCol(point.transfer[j], varset, terminalset)] = point.transfer[j + 1]
                j = j + 2
            else:
                # print('action初始化')
                # print('row', point.id, type(point.id))
                # print('col', getCol(point.transfer[j], varset, terminalset))
                Action[point.id][getCol(point.transfer[j], varset, terminalset)].done = 1
                Action[point.id][getCol(point.transfer[j], varset, terminalset)].do = 's'
                Action[point.id][getCol(point.transfer[j], varset, terminalset)].which = point.transfer[j + 1]
                j = j + 2
        for production in point.status:
            if production.right.index('.') == len(production.right) - 1 and production.left[0] == begin:
                Action[point.id][getCol('$', varset, terminalset)].do = 'acc'
                Action[point.id][getCol('$', varset, terminalset)].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]]:
                        # 冲突检测
                        # done=1说明前面已经操作过
                        if Action[point.id][getCol(terminal, varset, terminalset)].done == 1:
                            for xx in point.status:
                                print(xx.number, ' ', xx.left, '->', xx.right)
                        Action[point.id][getCol(terminal, varset, terminalset)].do = 'r'
                        Action[point.id][getCol(terminal, varset, terminalset)].done = 1
                        Action[point.id][getCol(terminal, varset, terminalset)].which = production.number
    return Action, Goto

6.求SLR分析过程

def SLR(Action, Goto, source, production_list, varset, terminalset):
    """
    使用SLR分析表(Action, Goto)进行词法分析
    :param Action:Action二维表
    :param Goto:Goto二维表
    :param source:源代码
    :param prudction_list:文法规则
    :return:
    """
    source.append('$')
    statusstack = [0]
    sentence_stack = ['$']
    while 1:
        print('******************************')
        print('缓冲区剩余元素', source)
        # 移除列表中的最后一个元素
        if len(source) == 0:
            break
        getchar = source[0]
        del source[0]

        print('状态栈', statusstack)
        print('句型栈', sentence_stack)

        if Action[statusstack[len(sentence_stack) - 1]][getCol(getchar, varset, terminalset)].do == 's':
            # 移进
            print("动作： 移入操作，从缓冲区中读取", getchar, "元素进行移入，并根据Action压入",
                  Action[statusstack[len(statusstack) - 1]][getCol(getchar, varset, terminalset)].which, "状态")
            statusstack.append(Action[statusstack[len(statusstack) - 1]][getCol(getchar, varset, terminalset)].which)
            sentence_stack.append(getchar)
        elif Action[statusstack[len(statusstack) - 1]][getCol(getchar, varset, terminalset)].do == 'r':
            # 归约
            r_production = []
            for production in production_list:
                if production.number == Action[statusstack[len(statusstack) - 1]][
                    getCol(getchar, varset, terminalset)].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], varset, terminalset)])
            print("动作： 归约操作，根据Action表利用第", r_production.number, "个产生式归约")
            sentence_stack.append(r_production.left[0])
            source.insert(0, getchar)
        elif Action[statusstack[len(statusstack) - 1]][getCol(getchar, varset, terminalset)].do == "acc":
            print("！！！！！！！！！！语义分析完成！！！！！！！！！！！！！！")
            break
        else:
            print('error!')