在抽象语法树中实现goto

Question

背景：在寒假期间，我正在尝试用Python和PLY实现一种叫做Axe的编程语言（这个语言是为图形计算器设计的）。简单说一下，这种语言只允许使用全局变量，并且大量使用指针。

我想在这个语言中实现goto功能，但我不知道该怎么做。

我的一般方法是先用PLY把代码解析成抽象语法树（ast），然后在遍历这棵树的过程中执行代码。

比如，语句

If 3
    Disp 4
    Disp 6
End

...会变成...

['PROGRAM', 
  ['BLOCK', 
    ['IF', 
      ['CONDITION', 3], 
      ['BLOCK', 
        ['DISP', 4], 
        ['DISP', 6]
      ]
    ]
  ]
]

...然后我会递归地执行它（我加了缩进让它更易读）。

因为这棵抽象语法树是树形结构，我不太确定怎么在不同的节点之间跳转。我考虑过把这棵树转换成一个比较扁平的数组 ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]]，这样我就可以用数组的索引来跳转到代码的特定行，但这样做似乎缺少了一些优雅，感觉有点像退步（不过我可能错了）。

我看过这个链接，但没能理解它是怎么工作的。

任何帮助或提示都非常感谢。

Answer 1

你还可以把抽象语法树（AST）变成一个有向图，也就是控制流图。举个例子，如何把它做成一个可以被解释器遍历的networkx图，你可以在这个Python包promela里找到。需要注意的是，你得为这个目的写一些AST类。

Answer 2

我考虑过把树结构转换成一个比较扁平的数组……但这样做似乎缺少了一些优雅，感觉有点像退步（不过我可能错了）。

你错了。机器代码总是扁平的。像C这样的编程语言会被转换成机器代码，变得扁平。

计算器（和其他简单的机器）也是扁平的。

不过，把你的AXE语法树扁平化并不是完全必要的。

你只需要给树中的每个节点加上编程源代码的标签。

然后，一个“GOTO”指令就可以在树中查找那个标签，并从那个标签继续执行。

Answer 3

“递归执行”这个说法和goto不太搭。要让goto正常工作，你需要一个程序计数器（PC），也就是“程序计数器”，而且你程序里的每一条语句都得有一个独特的地址。当程序执行时，每条语句的地址会被赋值给这个程序计数器。当遇到goto时，goto后面指定的地址会被放入程序计数器，然后程序从这个地址继续执行。

用基于栈的递归方法几乎无法做到这一点。你有两个选择：

• 把你的抽象语法树（AST）扁平化成一个序列，这样你就可以给每条语句分配一个独特的地址。

• 给你的解释器添加一个“跳过”模式。当遇到goto时，抛出一个GotoException，这样就可以跳出所有的栈帧，回到根部。处理语句（跳过它们而不执行），直到到达目标地址。

我想你可以想象，这种实现goto的方式性能并不好，而且实现起来可能会很脆弱。