LR0语法分析实现(完整版)[编译原理实验]

目录

一、实验要求:

二、实现效果:(基于python实现)

三、源代码 :

 四、测试文法(保存于1.txt)

 五、参考代码

 六、源代码下载


一、实验要求:

  1. 给定LR(0)文法,计算LR(0)项目集规范族。
  2. 构造其自动机(转换函数形式)。
  3. 判断文法是否为LR(0)的。
  4. 根据自动机构造其语法分析表。
  5. 模拟LR语法分析过程。

二、实现效果:(基于python实现

 

 


三、源代码 :

grams = []  # 存储产生式
dot_grams = []  # 存储带.的产生式
VN = []  # 非终结符集
VT = []  # 终结符集
V = []  # 终结符和非终结符集
items = []  # 存储LR0项目集规范族
fx = []  # 存放自动机转换函数
table = []  # 存放LR(0)分析表
analyse_fx = []  # 存放输出串分析过程中所使用的产生式


def get_grams():
    with open("1.txt", "r") as f:
        for line in f:
            line = line.replace('n', "")
            grams.append(line)
        f.close()


def print_grams():
    print("输入文法:")
    for gram in grams:
        print(gram)


# 划分终结符和非终结符
def get_v():
    for s in grams:
        x, y = s.split("->")
        # print(x,y)  x:'S' y:'aAcBE'
        if x not in VN:
            VN.append(x)

        for v in y:
            if v.isupper():
                if v not in VN:
                    VN.append(v)
            else:
                if v not in VT:
                    VT.append(v)
    # 终结符加上$
    VT.append("$")
    # 求终结符和非终结符集
    V.extend(VN)
    V.extend(VT)
    # for vn in VN:
    #     V.append(vn)
    # for vt in VT:
    #     V.append(vt)


# 为所有产生式加点
def dot_gram():
    # 增广文法
    str0 = "S'->." + grams[0][0]
    dot_grams.append(str0)
    str1 = "S'->" + grams[0][0] + "."
    dot_grams.append(str1)

    for gram in grams:
        # ind = gram.find("->")
        for i in range(len(gram) - 2):
            tmp = gram[:3 + i] + "." + gram[3 + i:]
            dot_grams.append(tmp)


# 返回非终结符产生的A->.aBb形式
def get_VN_gram(v):
    res = []
    for gram in dot_grams:
        index = gram.find("->")  # 返回'-'的下标
        if gram[0] == v and gram[index + 2] == ".":
            res.append(gram)
    return res


# CLOSURE函数
def Closure(I):
    closure = I
    for it in I:
        if it not in closure:
            closure.append(it)
        x, y = it.split(".")
        if y == "":  # .后面为终结符无操作,跳转到下一次循环
            continue
        v = y[0]
        if v in VN:  # .后面为非终结符,加入B->.γ
            res = get_VN_gram(v)
            for re in res:
                if re not in closure:
                    closure.append(re)
    return closure


# Go函数
def Go(I, v):
    # 生成并返回下一个item
    tmp = []
    for it in I:
        x, y = it.split(".")
        if y != "":
            if y[0] == v:
                new_it = x + y[0] + "." + y[1:]
                tmp.append(new_it)

    if len(tmp) != 0:
        new_item = Closure(tmp)
        return new_item


def is_inItems(new_item):
    # 判断item是否已经存在, 存在返回位置,不存在返回-1
    if new_item is None:
        return -1

    new_set = set(new_item)
    num = 0
    for item in items:
        old_set = set(item)
        if old_set == new_set:
            return num
        num = num + 1

    return -1


# 添加DFA的转换函数
def myAppend(xx, v, xy):
    t = []
    t.append(xx)
    t.append(v)
    t.append(xy)
    fx.append(t)


# 构建item的集合
def get_items():
    # 初始化,生成I0
    item = []
    item.append(dot_grams[0])
    it = Closure(item)
    num = 0
    # print("I0 is :" + str(item))
    items.append(it)
    num = num + 1
    # print("n自动机转换函数形式:")
    for item in items:
        for v in V:
            new_item = Go(item, v)
            # 判断状态不为空
            if new_item is not None:
                if is_inItems(new_item) == -1:  # 不存在于状态集items中
                    items.append(new_item)
                    x = is_inItems(item)
                    y = is_inItems(new_item)
                    # print("f(I{0},{1})=I{2}".format(x, v, y))
                    myAppend(x, v, y)
                    num = num + 1
                else:  # 存在于状态集items中
                    x = is_inItems(item)
                    y = is_inItems(new_item)
                    # print("f(I{0},{1})=I{2}".format(x, v, y))
                    myAppend(x, v, y)


# 输出LR(0)项目集规范族
def print_items():
    print("nLR(0)项目集规范族:")
    for i in range(len(items)):
        print("closure-I{0}: {1}".format(i, items[i]))


# 输出DFA的转换函数形式
def print_fx():
    print("n自动机转换函数形式:")
    for f in fx:
        print("f(I{0}, {1})=I{2}".format(f[0], f[1], f[2]))


# 判断文法是否为LR(0)
def judge_isLR0():
    for item in items:
        # 对于项目集中的每一个项目
        shiftNum = 0
        protocolNum = 0
        for it in item:
            # dot_index = it.find(".")
            # if dot_index + 1 >= len(it):  # .在最后,item中找到一个规约项
            #     shiftNum = shiftNum + 1
            # elif it[dot_index + 1] in VT:  # .后面为终结符,item中找到一个移进项
            #     protocolNum = protocolNum + 1
            x, y = it.split(".")
            if y == "":
                protocolNum = protocolNum + 1
            elif y[0] in VT:
                shiftNum = shiftNum + 1
        if protocolNum > 1 or (protocolNum >= 1 and shiftNum >= 1):
            print("n该文法不是LR(0)的")
            return -1
    print("n该文法是LR(0)的")
    return 1


def is_ingrams(new_gram):
    # 判断noDot_item是否已经存在, 存在返回位置,不存在返回-1
    if new_gram is None:
        return -1
    for i in range(len(grams)):
        if new_gram == grams[i]:
            return i
    return -1


# 创建LR(0)分析表
def creat_table():
    tmp = []
    tmp1 = []
    index_tmp1 = 0
    for item in items:
        t = []
        for it in item:
            x, y = it.split(".")
            if y == "":
                if it == dot_grams[1]:
                    t.append("-1")
                else:
                    t.append("0")
                    new_gram = x + y
                    tmp1.append(is_ingrams(new_gram))

            else:
                t.append(y[0])
        tmp.append(t)
    # print(tmp)
    for index_temp in range(len(tmp)):
        t = []
        for v in VT:
            # S'->E. 接受项目
            if "-1" in tmp[index_temp]:
                if v == "$":
                    t.append("acc")
                else:
                    t.append("")
            # .在最后,规约项目
            elif "0" in tmp[index_temp]:
                for vt in VT:
                    t.append("R" + str(tmp1[index_tmp1]+1))
                index_tmp1 = index_tmp1 + 1
                break
            # .后面为终结符 移进项目
            elif v in tmp[index_temp]:
                for f in fx:
                    if f[0] == index_temp and f[1] == v:
                        t.append("S" + str(f[2]))
                        break
            else:
                t.append("")
        # .后面为非终结符 待约项目
        for v in VN:
            if v in tmp[index_temp]:
                for f in fx:
                    if f[0] == index_temp and f[1] == v:
                        t.append(str(f[2]))
                        break
            else:
                t.append("")
        table.append(t)


# 打印LR(0)分析表
def print_table():
    print("n该文法的LR(0)分析表:")
    print('ttAction', end='t')
    print('ttGOTO')
    print('----------------------------------------')
    print("", end="t")
    for v in VT:
        print(v, end="t")
    for v in VN:
        print(v, end="t")
    print("n")
    for i in range(len(items)):
        print(i, end="t")
        for j in range(len(V)):
            print(table[i][j], end="t")
        print("n")


# 按格式输出字符串分析信息
def print_analyseinfo(status_stack, output_stack, input_stack, string):
    s = "".join(status_stack)
    o = "".join(output_stack)
    reverse_input_stack = input_stack[::-1]
    i = "".join(reverse_input_stack)
    print('%-20s' % s, end='')
    print('%-20s' % o, end='')
    print('%20s' % i, end='')
    if string == "":
        print('%20s' % 'wrong')
    else:
        print('%20s' % string)


# LR(0)分析过程
def analyse():
    status_stack = ['0']
    input_stack = ['$']
    output_stack = ['$']
    v = []
    v.extend(VT)
    v.extend(VN)
    string = input("请输入要分析的字符串:")
    print("对输入串{0}的分析过程:".format(string))
    for s in string[::-1]:  # 逆序
        if s in VT:
            input_stack.append(s)
        else:
            print("字符串含有其它终结符,不是该文法的句子!")
            return
    print('%-20s' % 'Status', end='')
    print('%-20s' % 'Symbol', end='')
    print('%20s' % 'Input', end='')
    print('%20s' % 'Action/Goto')
    for i in range(80):
        print("-", end="")
    print()
    while True:
        s1 = status_stack[-1]   # 状态栈栈顶元素
        s2 = input_stack[-1]  # 输入栈栈顶元素
        index1 = int(s1)    # 第几个项目集
        index2 = v.index(s2)   # s2在V中的位置
        string = table[index1][index2]  # 获得对应的table表中的信息
        print_analyseinfo(status_stack, output_stack, input_stack, string)  # 输出当前各个栈的状况
        if string == "":
            print("输入串不是该文法的句子!")
            break
        elif string[0] == "S":  # Action[s,a]
            status_stack.append(string[1])
            input_stack.pop()
            output_stack.append(s2)
        elif string[0] == "R":
            x, y = grams[int(string[1])-1].split("->")
            status_stack = status_stack[:-len(y)]   # 出栈
            output_stack = output_stack[:-len(y)]   # 出栈
            input_stack.append(x)   # 进栈
            analyse_fx.append(grams[int(string[1])-1])  # 保存使用的产生式
        elif string == "acc":
            print("输入串是该文法的句子!")
            print("使用的产生式依次为:")
            for af in analyse_fx:
                print(af)
            break
        else:   # Goto[t,A]
            status_stack.append(string)
            input_stack.pop()
            output_stack.append(s2)


if __name__ == '__main__':
    get_grams()
    print_grams()
    get_v()
    dot_gram()
    get_items()
    print_items()
    print_fx()
    if judge_isLR0() == 1:
        creat_table()
        print_table()
        analyse()

 四、测试文法(保存于1.txt

 


 五、参考代码

LR(0)语法分析器的实现代码(python) - 简书


 六、源代码下载

含有多个测试用例,和更多的注释?

 编译原理实验,LR0语法分析完整版-其它文档类资源-CSDN下载

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>