c - 验证解析器中的数据类型/结构

Question

我正在编写一个递归下降解析器，但我不确定如何验证所有内容。我什至不确定是否应该在解析器阶段执行此操作。我的意思是，我可以有一些语法，即:

int x = 5
int x = 5

这是有效的，那么解析器会检查 x 是否已经被定义了吗？如果是这样，我会使用 HashMap 吗？我需要存储什么样的信息，比如如何处理变量的范围，因为 x 可以在本地和全局范围的函数中定义:

int x = 5;
void main() {
    int x = 2;
}

最后，当我存储到 HashMap 时，如何区分类型？例如，我可以有一个名为 foo 的变量和一个也称为 foo 的结构。因此，当我将 foo 放入 HashMap 时，可能会导致一些错误。我想我可以给它加上前缀，就像将其存储为结构 struct_xyz 的 HashMap 键，其中 xyz 是结构的名称，以及变量 int_xyz 的 HashMap 键？ 谢谢:)

Answer 1

我假设无论您选择哪种方法，您的解析器都将构建某种抽象语法树。您现在有两个选择。或者，解析器可以用标识符节点填充树，这些标识符节点存储它们引用的变量或函数的名称。正如许多编译器教科书所提倡的那样，这将范围解析问题留给了稍后的处理。

另一种选择是让解析器立即在它构建的符号表中查找标识符，并将指向该符号的指针存储在抽象语法树节点中。如果您的语言不允许对尚未声明的名称进行隐式前向引用，则此方法往往效果很好。

我最近在我正在开发的编译器中实现了后一种方法，到目前为止我对结果非常满意。下面我将简要描述我的解决方案。

符号存储在如下结构中:

typedef struct symbol {
    char  *name;
    Type  *type;
    Scope *scope; // Points to the scope in which the symbol was defined.
} Symbol;

那么这个Scope是什么东西呢？我正在编译的语言是词法​​作用域的，每个函数定义、 block 等都会引入一个新的作用域。作用域形成一个堆栈，其中底部元素是全局作用域。结构如下:

typedef struct scope {
    struct scope *parent;
    Symbol *buckets;
    size_t  nbuckets;
} Scope;

buckets 和 nbuckets 字段是标识符(字符串)到 Symbol 指针的 HashMap 。通过跟踪parent指针，人们可以在搜索标识符时遍历作用域堆栈。

有了数据结构，就可以轻松编写一个根据词法作用域规则解析名称的解析器。

1. 遇到引入新作用域的语句或声明(例如函数声明或 block 语句)时，解析器会将新的作用域压入堆栈。新作用域的 parent 字段指向旧作用域。
2. 当解析器看到一个标识符时，它会尝试在当前范围内查找它。如果在当前作用域中查找失败，则会在 parent 作用域中继续递归查找，依此类推。如果找不到相应的 Symbol，则会引发错误。如果查找成功，解析器将创建一个带有指向该符号的指针的 AST 节点。
3. 最后，当遇到变量或函数声明时，它会被绑定(bind)在当前作用域中。

某些语言使用多个命名空间。例如，在 Erlang 中，函数和变量占用不同的命名空间，需要像 fun foo:bar/1 这样笨拙的语法来获取函数的值。通过保留多个 Scope 堆栈(每个命名空间一个)，可以在我上面概述的模型中轻松实现这一点。