Python 实现极简小编译器编译程序1+2+3到栈式计算机

最近开始学习编译原理的课程：https://www.bilibili.com/video/BV16h411X7JY/

任务一、编译1+2+3到栈式计算机

栈式计算机有俩条指令，push n和add, push n即遇到数字n把数字n推进栈底，

add即遇到+号把栈顶和次栈顶的数字推出，计算俩者的和，计算后将和再推进去。

首先是二叉树

#二叉树
class Node:
    def __init__(self,value=None,left=None,rigth=None):
        self.value=value
        self.left=left
        self.rigth=rigth

    def __repr__(self) -> str:
        return f"TreeNode({self.value},{self.left},{self.rigth})"

我们想要的结构如下：

    +
   / \
  +   3
 / \
1   2

#生成一颗语法树
def get_node_root(expression):
    num = ''
    root=Node()
    for char in expression:
        if char.isdigit():
            num += char
        else:
            if root.value==None:
                root.value=int(num)
                num=''
                parent=Node()
                parent.value="+"
                parent.left=root
                root=parent
            else:
                node =Node()
                node.value=int(num)
                num=''
                if root.left==None:
                    root.left=node
                elif root.rigth==None:
                    root.rigth=node
                    parent=Node()
                    parent.value="+"
                    parent.left=root
                    root=parent
                else:
                    parent=Node()
                    parent.value="+"
                    parent.left=root
                    parent.rigth=node
                    root=parent
    if num:
         node=Node()
         node.value=int(num)
         root.rigth=node
   #print(root)
    return root

这里主要是判断是否是int 类型的。然后设置左节点、和又节点、并且设置值。如果进入到else 中那么此刻就是+ 这里可能会存在一些问题。

例如1+2+3-6 这样的就会存在问题

然后就是一个遍历树的节点了。通常使用的是 树的后序遍历  postOrder 

#1+2+3到栈式计算机

# 栈式计算机有两指令  push n 和add push n 碰到数字就进行压栈
# add 遇到+ 就把栈顶的数字推出、计算两者的和、计算后在推入栈中

#二叉树
class Node:
    def __init__(self,value=None,left=None,rigth=None):
        self.value=value
        self.left=left
        self.rigth=rigth

    def __repr__(self) -> str:
        return f"TreeNode({self.value},{self.left},{self.rigth})"

#生成一颗语法树
def get_node_root(expression):
    num = ''
    root=Node()
    for char in expression:
        if char.isdigit():
            num += char
        else:
            if root.value==None:
                root.value=int(num)
                num=''
                parent=Node()
                parent.value="+"
                parent.left=root
                root=parent
            else:
                node =Node()
                node.value=int(num)
                num=''
                if root.left==None:
                    root.left=node
                elif root.rigth==None:
                    root.rigth=node
                    parent=Node()
                    parent.value="+"
                    parent.left=root
                    root=parent
                else:
                    parent=Node()
                    parent.value="+"
                    parent.left=root
                    parent.rigth=node
                    root=parent
    if num:
         node=Node()
         node.value=int(num)
         root.rigth=node
   #print(root)
    return root

#树的后续遍历  从左右中 
def GetRoot(root):
    instructions = []
    def traverse(node):
        if node is None:
            return
        traverse(node.left)
        if node.rigth is not None:
            # 访问右子节点
            traverse(node.rigth)
        
        if isinstance(node.value, int):
            instructions.append(f'push {node.value}')
        else:
            instructions.append('add')
    traverse(root)
    return instructions

#打印语法数
def print_tree(root, level=0, prefix="", is_left=True):
    if root is not None:
        # 打印当前节点的值
        print(' ' * (level * 10) + prefix + ' ' + str(root.value))
        # 递归打印左子树
        print_tree(root.left, level + 1, prefix + "", True)
        # 递归打印右子树
        if root.rigth is not None:
            print_tree(root.rigth, level + 1, prefix + "", False)


#执行push n  和add指令
def GetReult(instructions):
    stack = []
    for instruction in instructions:
        if instruction.startswith('push'):
            stack.append(int(instruction[5:]))  # 将数字推入栈
        elif instruction == 'add':
            if len(stack) < 2:
                #如果不足两个直接返回
                return stack[0]
            a = stack.pop()
            b = stack.pop()
            stack.append(a + b)  # 执行加法并将结果推回栈
    
    return stack[0] if stack else None

expression = "1+2+4"
root_infos = get_node_root(expression)
print("打印树")
print_tree(root_infos)
instructions=GetRoot(root_infos)
ret=GetReult(instructions)
print("执行结果",ret)

此刻的指令这样的。

push 1
push 2
add
push 4
add

任务二：增加一个代码优化的阶段