在解析器中验证数据 types/structs

Question

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

int x = 5
int x = 5

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

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

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

Answer 1

最好的方法是使用 class，您可以在其中定义像 HashMap 这样的结构，这样您就可以控制变量的类型和/或是否存在。这个 class 应该有静态方法来与解析器中编写的语法规则交互。

Answer 2

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

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

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

符号存储在如下所示的结构中：

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

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

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

buckets 和 nbuckets 字段是标识符（字符串）到 Symbol 指针的哈希映射。通过遵循 parent 指针，可以在搜索标识符的同时遍历作用域堆栈。

有了适当的数据结构，就可以轻松编写根据词法范围规则解析名称的解析器。

遇到引入新范围的语句或声明（例如函数声明或块语句）时，解析器会将新的 Scope 压入堆栈。新范围的 parent 字段指向旧范围。
当解析器看到一个标识符时，它会尝试在当前范围内查找它。如果在当前范围内查找失败，它将在 parent 范围内递归继续，等等。如果找不到相应的 Symbol，则会引发错误。如果查找成功，解析器将创建一个带有指向该符号的指针的 AST 节点。
最后，当遇到变量或函数声明时，将其绑定在当前范围内。

有些语言使用多个命名空间。例如，在 Erlang 中，函数和变量占据不同的命名空间，需要像 fun foo:bar/1 这样笨拙的语法来获取函数的值。这很容易在我上面概述的模型中实现，方法是保留几个 Scope 堆栈 - 每个命名空间一个。

Answer 3

如果我们将"scope"或"context"定义为从变量名到类型的映射（可能还有一些更多的信息，例如范围深度），那么它的自然实现要么是hashmap，要么是某种搜索树。到达任何变量定义后，编译器应将具有相应类型的名称插入到该数据结构中。当遇到某种 'end scope' 运算符时，我们必须已经有足够的信息来 'backtrack' 将此映射更改为之前的状态。

对于 hashmap 实现，对于每个变量定义，我们可以存储此名称的先前映射，并在到达 'end of scope' 运算符时恢复此映射。我们应该保留一堆更改堆栈（每个当前打开的范围一个堆栈），并在每个范围的末尾回溯最顶层的更改堆栈。

这种方法的一个缺点是我们必须一次性完成编译，或者将每个标识符的映射存储在程序中的某个地方，因为我们不能检查任何范围超过一次，或者检查顺序不是出现在源文件（或 AST）中。

对于基于树的实现，这可以通过所谓的 persistent trees 轻松实现。我们只是维护一堆树，每个范围一个，在我们 'open' 一些范围时推送，并在范围结束时弹出。

'depth of scope' 足以选择在新变量名与映射中已有变量名冲突的情况下要做什么。只需检查 old depth < new depth 并在成功时覆盖，或在失败时报告错误。

要区分函数名和变量名，您可以对这些对象使用单独（但相似或相同）的映射。如果某些上下文只允许函数或只允许变量名，那么您已经知道去哪里查找。如果在某些上下文中两者都被允许，则在两个结构中执行查找，如果名称同时对应于函数和变量，则报告"ambiguity error"。

在解析器中验证数据 types/structs

Verifying data types/structs in a parser

c

parsing

compiler-construction

scope

compiler-theory