0

编程语言用来评估其 AST 的算法是什么？

也就是说，假设我们有 4 个基本函数/*+-。什么是可以正确评估任何 AST 的基本算法，例如：

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

我的疑问实际上是如果对节点的评估返回仍然需要评估的东西会发生什么。例如，在 Scheme 中，对 的评估((lambda (a) (+ a 2)) 3)将是(+ 3 2)。但这可以再次评估为 5。那么语言如何确定何时停止评估表单？

4

4 回答 4

2

您完全误解了 Scheme/Lisp 评估的工作原理。我将使用您提供的示例：

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

为了评估一个列表，我们评估每个元素。第一个预计会返回一个过程（我忽略了语法运算符的特殊情况），其余的可以返回任意值。我们将其余部分作为参数调用该过程。

在顶层，这是一个包含 3 个元素的列表：

  1. +
  2. (- (* 3 2) (+ (/ 5 2)))
  3. (* 2 4)

对这些中的每一个进行评估。第一个是一个变量，其值为一个过程（Scheme 的内置加法函数）。其他是列表，需要递归到评估算法中。我将跳过描述第二个，因为它的复杂性，并转到第三个：(* 2 4).

这是 3 个元素的列表：*、2 和 4。如上所述，* 是乘法函数。2 和 4 是文字，因此它们对自己进行评估。所以我们用参数 2 和 4 调用乘法函数，它返回 8。

复杂的第二个参数经历了相同的过程，只是多了几个层次的递归。它最终返回 4。因此我们使用参数 4 和 8 调用乘法函数，它返回 32。

您的第二个示例的处理方式类似。在顶部，您有一个包含两个元素的列表：

  1. (lambda (a) (+ a 2))
  2. 3

对这些中的每一个进行评估。Lambda 是一种特殊语法，它解析其内容并返回一个过程，该过程在参数变量绑定到参数的上下文中评估其主体，因此第一个返回的过程将其参数添加 2 并返回。3 是一个字面量，所以它只返回数字 3。然后我们使用参数 3 调用该过程，它将 2 添加到它并返回 5。

于 2012-10-09T01:43:06.907 回答
0

有许多不同的算法。

备选方案 1：您可以将 AST 编译为更线性的中间表示。您的代码可以编译为如下内容：

a <- 3 * 2
b <- 5 / 2
c <- a - b
d <- 2 * 4
e <- c + d
return e

这很容易评估，因为它只是一系列指令。大多数指令具有相同的格式：X <- Y OP Z，因此评估器将非常简单。

备选方案 2：您可以将备选方案 #1 编译为机器码或字节码。

li      r3, 3
muli    r3, 2
li      r4, 5
divi    r4, r5, 2
subf    r3, r3, r4
li      r4, 2
muli    r4, r4, 4
add     r3, r3, r4
blr

备选方案 3：您可以将备选方案 #1 编译为称为 SSA 的特殊形式，或“单一静态分配”，它类似于 #1，但每个分配的 LHS 是唯一的，并且特殊的“phi”节点用于组合来自不同的分支。然后可以将 SSA 编译为机器码或字节码。

备选方案 4：您可以通过递归下降来评估 AST。大多数关于 Scheme / Lisp 的书籍都详细介绍了这一点。

备选方案 5：您可以使用递归下降将代码转换为堆栈机器代码，然后对其进行评估。就像是：

push 3
push 2
mul
push 5
push 2
div
sub
push 2
push 4
mul
add
ret

Alternative ∞：还有很多其他的技术。关于这个主题的书很厚。

于 2012-10-09T00:53:09.497 回答
0

在您给出的情况下，执行将在 5 处停止，因为它是一个文字值并代表它自己。这并不难测试。您不妨问一个深入遍历列表的函数如何知道如何停止（实际上，您应该知道，因为在 Scheme 中这是同一件事）。

在 Scheme 中，任何复合表达式最终都应解析为 7 种原始数据类型之一或空列表，除非它陷入无限循环。如果您想提前知道表达式是否会解决，那么这是一个有趣的问题：http ://en.wikipedia.org/wiki/Halting_problem

于 2012-10-09T00:06:08.930 回答
0

我想你可能问错了问题，但我会尝试：

直到它得到一个可以使用的结果。在您的示例中，您询问的是解释器何时停止评估表达式......它 100% 依赖于语言，如果您要询问编译器，这将是一个完全不同的答案。对于您的方案示例，您需要阅读方案规范 ( R5RS )。

所以它是由解释器的作者定义的。如果单个文字（甚至变量）是我的语言中表达式的预期结果，那么它将停在那里。

于 2012-10-09T00:30:24.980 回答