几年前,我开始为一个领域特定语言编写一个解释器,其中包括程序员定义的函数。
起初,我使用一组简单的符号表实现了变量范围。但现在我想转向适当的词法范围(可选择闭包)。任何人都可以解释词法范围背后的数据结构和算法吗?
要在解释器中获得正确的词法作用域和闭包,您需要做的就是遵循以下规则:
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,而不是当时构造的数据结构。 (另一方面,保留整个env而不仅仅是关闭的变量可能意味着程序具有令人惊讶的内存泄漏,因为闭包持有不需要的东西。这在任何“实际”语言实现中都是值得修复的,但不是当你只是试验语言语义时。)
有许多不同的方法来实现词法范围。以下是我的一些最爱:
没有一种正确的方法可以做到这一点。重要的是要清楚地说明您要提供的语义,然后将遵循数据结构和算法。
Stroustrup在第一个C ++编译器中实现了这一点,每个范围只有一个符号表,并且一个链接规则向外跟随范围,直到找到定义。这是如何工作的确切取决于您的精确语义。确保先将它们钉上。
Knight in the Computer of Computer Programming,Vol 1,给出了一个Cobol符号表的算法,通过链接完成作用域。