image.png

import queue

input_dict = {'a':0,'b':1,'#':2,'S':3,'B':4}


shift = 0
merge = 1
accepted = 2


class grammar():
    def __init__(self,left,right):
        self.left = left
        self.right = right
        self.merge_len = len(right)


grammar1 = grammar('S','BB')
grammar2 = grammar('B','aB')
grammar3 = grammar('B','b')


# 有可能是转移或者根据语法规约
class action():
    def __init__(self,move_or_merge,state_or_grammer=None):
        self.action = move_or_merge
        self.state_or_grammer = state_or_grammer


line0 = [action(shift,3),action(shift,4),None,action(shift,1),action(shift,2)]
line1 = [None,None,action(accepted),None,None]
line2 = [action(shift,3),action(shift,4),None,None,action(shift,5)]
line3 = [action(shift,3),action(shift,4),None,None,action(shift,6)]
line4 = [action(merge,2),action(merge,2),action(merge,2),None,None]
line5 = [action(merge,0),action(merge,0),action(merge,0),None,None]
line6 = [action(merge,1),action(merge,1),action(merge,1),None,None]


class state_table():
    def __init__(self):
        self.Table = [line0,line1,line2,line3,line4,line5,line6]

class grammer_table():
    def __init__(self):
        self.Table = [grammar1,grammar2,grammar3]

def LR_machine(input_str):
    my_state_table = state_table()
    my_grammer_table = grammer_table()
    stack = queue.LifoQueue()
    stack.put([0,'#'])
    current_state = 0
    str_ptr = 0

    while str_ptr < len(input_str):
        new_input = input_str[str_ptr]
        new_input_index = input_dict[new_input]
        new_action = my_state_table.Table[current_state][new_input_index]
        if new_action.action == shift:
            current_state = new_action.state_or_grammer
            print('stack input:')
            print([current_state,new_input])
            stack.put([current_state,new_input])
            str_ptr += 1
        elif new_action.action == merge:
            while new_action.action == merge:
                # print(new_action.state_or_grammer)
                grammar = my_grammer_table.Table[new_action.state_or_grammer]
                str = ''
                for i in range(grammar.merge_len):
                    # str += stack.get()[1]
                    temp = stack.get()
                    print('output:')
                    print(temp)
                    str = temp[1] + str

                if str == grammar.right:
                    new_input = grammar.left
                    new_input_index = input_dict[new_input]
                    # 新的输入是语法的左端，再取出新的状态
                    temp = stack.get()
                    current_state = temp[0]
                    stack.put(temp)
                    new_action = my_state_table.Table[current_state][new_input_index]
                else:
                    print('error:merge,input is not in grammer\'s right part!')
                    return -1

                new_action = my_state_table.Table[current_state][new_input_index]

            if new_action.action == shift:
                current_state = new_action.state_or_grammer
                print('stack input:1')
                print([current_state, new_input])
                stack.put([current_state, new_input])
            else:
                print('error:!!')
        elif new_action.action == accepted:
            current_state = accepted
            return 0
        else:
            print('error:can\'t find right new_action')
            return -1

    print('error:str run out and not get in accepted state!')
    return -1



def main():
    print(LR_machine('bab#'))


if __name__ == '__main__':
    main()