在抽象语法树中实现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]
      ]
    ]
  ]
]

我希望能够递归执行以下代码（为了易读性，我添加了缩进）。

由于ast是一棵树，我不确定如何在不同的节点之间跳转。我考虑将树转换为类似数组的形式['IF'，['CONDITION'，3]，['DISP'，4]，['DISP'，6]]，这样我就可以使用类数组的索引来定位到代码中的特定行，但这似乎缺少某种优雅感，几乎感觉像是一步退步（虽然我可能错了）。

我查看了这里，但无法理解它的工作原理。

如果您能提供任何帮助或提示，将不胜感激。

- Michael0x2a

---

“Jump”？你认为“Jump”是什么意思？为什么要在节点之间“跳跃”？请提供一个具体的例子，说明何时需要“跳跃”到任意节点。在基于树的语言中，很难找到合理的需要使用跳跃的情况。 - S.Lott

我选择实现的语言中有goto语句。我想要匹配规范，这就是为什么我需要goto的原因。我选择基于树结构实现，因为当时看起来是个明智的选择。我猜那是一个错误：还有哪些其他形式的语言呢？ - Michael0x2a

AXE真的需要一个GOTO吗？听起来很奇怪。语言有无限多种“形式”：过程化、函数式等等。在过程化语言中，Python和Java（还有其他语言）都没有GOTO。这是一件相当罕见的事情。 - S.Lott

AST在编译方面表现良好，但在评估方面则不是。除了“goto”之外，还有其他问题-循环。你想如何实现循环而不使用某种程序计数器？ - werewindle

这是一种低级语言。此外，我之前使用“while”循环实现了循环。 - Michael0x2a

Answer 1

“递归执行”与“goto”不太匹配。为了让“goto”正常工作，您需要一台个人电脑、一个“程序计数器”，并且程序中的每个语句必须具有不同的地址。执行时，每个语句的地址都被分配给计数器。当遇到“goto”时，跳转目标地址（它的参数）被放入计数器，并从那里恢复执行。

这在基于堆栈的递归方法中几乎是不可能实现的。您有两个选择：

1. 将AST展开为序列，以便可以为每个语句分配一个唯一的地址。 2. 向解释器添加“跳过”模式。当遇到“goto”时，抛出一个“GotoException”，它会跳出所有堆栈帧并返回到根。处理语句（跳过而不执行）直到达到目标地址。

我想你可以想象出这种“goto”的实现性能不佳，而且可能很难实现。

- Aaron Digulla

---

好的，谢谢你的建议！我想我会选择将树结构扁平化。 - Michael0x2a

Answer 2

我考虑过将树形结构转换为类似于数组的平面结构......但这似乎缺乏某种优雅感，几乎感觉像是一个倒退的步骤(虽然我可能错了)。

你错了。机器代码总是平面的。像C这样的语言会被展开以创建机器代码。

计算器(如其他简单机器)也是平面的。

然而，将AXE语法树展开并不完全是必要的。

您只需要将编程源标签应用于树中的每个节点。

然后，“GOTO”只需搜索该标签在树中的位置并在该标签处恢复执行即可。

- S.Lott

---

啊，关于机器码的观点很好。我想我之前是错的 :) - Michael0x2a

因为机器码是平的，现在我们不经常使用它进行编程。我们更喜欢结构化语言，并使用工具将优美、结构化的语言压缩成机器执行的平面世界。 - S.Lott

Answer 3

你也可以将 AST 压缩为有向图（控制流图）。如何通过 networkx 图生成可被解释器遍历的示例，可以在 Python 包 promela 中找到 。请注意，您需要编写一些 AST 类来实现此目的。

- 0 _