嵌套范围内查找的最佳数据结构

您正在实现的编程语言肯定会为名称解析定义精确的规则。我认为这不会导致深度优先搜索。名称解析规则,很常见,看起来像这样:

1. 搜索当前范围,经常只考虑源代码中当前位置声明的内容;
2. 当满足某些特定规则时,例如 using / import 或链接到某个其他作用域的任何其他构造,在该其他作用域中执行搜索(顺序地搜索所有此类作用域),并在其中递归:
   1. 搜索给定范围,
   2. 递归任何相关的嵌套范围;
3. 进入直接封闭范围;
4. 重复(1),其中“当前”范围是(3)中确定的范围。

换言之,您将逐步进入封闭范围树,并决定是否搜索任何“外来”引用范围。声明,如 使用 / 进口 导致作用域之间的引用,这反过来导致被视为作用域树的内容实际上是一个有向图。

关于查找表的构造,我将从一个简单的哈希表开始。 Prefix trees (tries) 也适用于这些场景。

最后但并非最不重要的一点是,我不会太在意查找性能,除非在编译数十行或数十万行代码时遇到真正的性能问题。