编译原理——LR(1)分析方法的python实现

给定LR(1)分析表,输入以‘#’结尾的字符串,输出分析过程

输出的分析过程包括:步骤编号、状态栈、符号栈、剩余输入串、动作

代码实现:

# coding:UTF-8
class Stack(object): # 栈的实现
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def show(self):
        print(self.items, end='')


GOTO = dict(list()) # GOTO表
ACTION = dict(list()) # ACTION表
MAP = dict(list()) # 文法产生式
stat = Stack() # 状态栈
symbol = Stack() # 符号栈
left = Stack() # 剩余字符串


def init(original): # 给定分析表
    GOTO['E'] = (1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1)
    GOTO['T'] = (2, -1, -1, -1, 2, -1, 9, -1, -1, -1, -1, -1)
    GOTO['F'] = (3, -1, -1, -1, 3, -1, 3, 10, -1, -1, -1, -1)

    ACTION['i'] = ('s.5', '0', '0', '0', 's.5', '0', 's.5', 's.5', '0', '0', '0', '0')
    ACTION['+'] = ('0', 's.6', 'r.2', 'r.4', '0', 'r.6', '0', '0', 's.6', 'r.1', 'r.3', 'r.5')
    ACTION['*'] = ('0', '0', 's.7', 'r.4', '0', 'r.6', '0', '0', '0', 's.7', 'r.3', 'r.5')
    ACTION['('] = ('s.4', '0', '0', '0', 's.4', '0', 's.4', 's.4', '0', '0', '0', '0')
    ACTION[')'] = ('0', '0', 'r.2', 'r.4', '0', 'r.6', '0', '0', 's.11', 'r.1', 'r.3', 'r.5')
    ACTION['#'] = ('0', 'A', 'r.2', 'r.4', '0', 'r.6', '0', '0', '0', 'r.1', 'r.3', 'r.5')

    MAP[1] = ("E", "E+T")
    MAP[2] = ("E", "T")
    MAP[3] = ("T", "T*F")
    MAP[4] = ("T", "F")
    MAP[5] = ("F", "(E)")
    MAP[6] = ("F", "i")

    r_original = original[::-1] # 输入字符串逆序入栈成为剩余字符串
    for each in r_original:
        left.push(each)

    stat.push(0) # 开始状态入符号栈
    symbol.push('#') # 终结符入状态栈


def show_all(cnt, act): # 输出当前栈内信息
    print(cnt, '\t\t\t', end='')
    stat.show()
    print('\t\t\t\t  ', end='')
    symbol.show()
    print('\t\t\t\t', end='')
    left.show()
    print('\t\t\t\t', end='')
    print(act)


def run():
    print('步骤\t\t  ', '状态栈\t\t\t', '符号栈\t\t\t\t\t', '剩余输入串\t\t\t\t\t', '动作')
    cnt = 0
    show_all(cnt, '初始化')
    while True: # 开始分析过程
        stat_ = stat.peek()
        left_ = left.peek()

        act = ACTION[left_][stat_]

        if 's' in act: # 移进
            stat.push(int(act.split('.')[1]))
            symbol.push(left.pop())
        elif 'r' in act: # 规约
            tmp = int(act.split('.')[1])
            key = MAP[tmp][0]
            value = MAP[tmp][1]
            key_r = key[::-1]
            value_r = value[::-1]

            t_str = ""
            while t_str != value_r:
                # print("t_str= ", t_str," value= ", value_r)
                t_str += symbol.peek()
                symbol.pop()

            for each in key_r:
                symbol.push(each)

            stat.pop()
            stat.push(GOTO[symbol.peek()][stat.peek()])
        elif 'A' in act: # 接受
            print('ACCEPT')
            return
        else: # 出错
            print("Error")
            break

        while symbol.size() is not stat.size(): # 状态栈和符号栈平衡过程,也许应该放到规约过程中(未测试)
            stat.pop()

        cnt += 1

        show_all(cnt, act)


def main():
    string = input("字符串:")
    init(string)
    run()


if __name__ == "__main__":
    main()

输入:i*i+i#

输出: