11

几年前，我开始为包含程序员定义的函数的小型领域特定语言编写解释器。

起初，我使用一个简单的符号表堆栈来实现变量范围。但现在我想转向正确的词法范围（可以选择闭包）。谁能解释词法作用域背后的数据结构和算法？

4

5 回答 5

10

要在解释器中获得正确的词法作用域和闭包，您需要做的就是遵循以下规则：

  • 在您的解释器中，变量总是在调用者传入的环境表中查找或保存为变量，而不是一些全局环境堆栈。您的 eval 操作的签名就像eval(expression, env) => value.
  • 当解释代码调用函数时，环境不会传递给该函数。您的函数应用程序操作的签名就像apply(function, arguments) => value.
  • 当一个解释函数被调用时，它的主体被评估的环境是定义函数的环境，与调用者没有任何关系。所以如果你有一个局部函数，那么它就是一个闭包，也就是一个包含字段的数据结构{function definition, env-at-definition-time}。

要扩展 Python-ish 语法中的最后一点：

x = 1
return lambda y: x + y

应该像执行一样执行

x = 1
return make_closure(<AST for "lambda y: x + y">, {"x": x})

其中第二个 dict 参数可能只是 current-env 而不是当时构建的数据结构。（另一方面，保留整个环境而不仅仅是封闭的变量可能意味着程序会出现令人惊讶的内存泄漏，因为闭包会保留不需要的东西。这值得在任何“实用”语言实现中修复，但不当您只是在尝试语言语义时。）

于 2010-03-05T02:47:56.747 回答
7

有许多不同的方法来实现词法作用域。以下是我的一些最爱：

  • 如果您不需要超快的性能，请使用纯函数式数据结构来实现符号表，并通过包含指向代码的指针和指向符号表的指针的对来表示嵌套函数。

  • 如果您需要本机代码速度，我最喜欢的技术在Simon Marlow 和 Simon Peyton Jones的Making a Fast Curry中有所描述。

  • 如果您需要本机代码速度，但柯里化函数并不那么重要，请考虑闭包传递样式。

于 2010-03-05T03:33:02.333 回答
2

例如阅读Lua 5.0 的实现。

于 2010-03-05T03:02:46.850 回答
1

没有单一的正确方法可以做到这一点。重要的是清楚地说明您希望提供的语义，然后数据结构和算法将随之而来。

于 2010-03-05T02:30:35.550 回答
1

Stroustrup 在第一个 C++ 编译器中实现了这一点，每个作用域只有一个符号表，以及一个沿着作用域向外直到找到定义的链接规则。这完全取决于您的精确语义。确保首先确定这些。

Knuth 在《计算机编程艺术》第 1 卷中给出了 Cobol 符号表的算法，通过链接确定范围。

于 2010-03-05T03:42:00.007 回答