使用Python实现特定领域语言的符号表

Question

假设我有一个特定于域的语言的类型化表达式：

x+y<=z

其中x,y,z类型为int

我们应该使用python中的哪个内置数据结构来实现符号表？我只知道dictionary，所以符号表可以实现为

^{pr2}$

但也许还有其他更好的选择？在

Answer 1

符号表的基本概念是将标识符映射到有关标识符的信息（类型、用途…）

<>所以任何将名称（几乎总是字符串）与“类型值”关联的机制是很好的基础。所以，字典会有用的。（事实上，标识符键上的哈希表是实现这一点的经典方法）。在

但对于真正的符号表，你需要更多。您需要将每个这样的映射与有效的范围相关联。在许多经典的类似Algol的语言中，这样的作用域是由嵌套块引入的。在更复杂的语言（例如，C++）中，一个具有名称空间和其他复杂的范围结构，并且映射到范围的关系可能需要复杂的映射回到SouCE代码（或者AST节点或任何你使用的表示）。在

查找“符号表”中的需要有关如何确定当前范围（因此是当前标识符到类型映射）的规则，以及如果在该范围中找到标识符，该怎么办，以及在该范围中找不到标识符时该怎么办（通常，查看由语言规则定义的另一个范围）。允许重载的复杂语言可能需要一个作用域中的多个条目来表示重载的名称；突然间，一个简单的字典是不够的，您可能需要在映射中找到的每个标识符附加一个选项树，或者需要一个更复杂的标识符与签名数据映射到一个作用域项。在

在许多类似Algol的语言中，“在另一个作用域中查找”需要向上搜索块的“词法嵌套”，因此每个映射都必须与父作用域关联。复杂的语言，如C++，可能有多个继承规则，现在你必须能够确定哪个（“父”）范围可能有助于继承，以及搜索父母的顺序。由于复杂语言可能根据符号的上下文有许多不同的查找规则，因此每个标识符映射可能需要其特定的策略（过程附件），以说明如何进行本地查找（例如，处理找到的重载）以及如何处理失败的查找。在

因此，虽然字典对于一个只有一个作用域的简单语言来说已经足够了，但实际上，您需要更多的“结构”来存储复杂语言的符号表。在

如果你相信你的“简单”语言只会有小的实例，因此只需要一个单一的作用域，你会对你的用户最终所做的事情感到惊讶。（见过一千行SQL语句吗？）随着DSL实例变得越来越大，您需要更多的作用域规则来使其易于管理，并且您最终会遇到我上面描述的一些或所有复杂情况。做这件事要考虑长远。在

（请查看我的个人简历，寻找一个用于构建dsl的工具，它具有处理上述所有问题的符号表机制。但没有在Python中实现）。在