我正在编写一个递归下降解析器,我不确定如何验证所有内容。我什至不确定我是否应该在解析器阶段执行此操作。我的意思是,我可以有一些语法,即:
int x = 5
int x = 5
这将是有效的,那么解析器会检查 x 是否已经定义吗?如果是这样,我会使用哈希图吗?以及我需要存储什么样的信息,比如我如何处理变量的作用域,因为 x 可以在局部和全局作用域的函数中定义:
int x = 5;
void main() {
int x = 2;
}
最后,当我存储到哈希图时,如何区分类型?例如,我可以有一个名为 foo
的变量和一个也称为 foo
的结构。因此,当我foo
放入哈希图中时,可能会导致一些错误。我想我可以在它前面加上前缀,例如将其存储为结构struct_xyz
的哈希映射键,其中 xyz 是结构的名称,以及变量int_xyz
?感谢:)
我将假设无论您选择哪种方法,您的解析器都将构造某种抽象语法树。您现在有两个选择。或者,解析器可以使用标识符节点填充树,这些节点存储它们所引用的变量或函数的名称。这让范围解析问题留待以后解决,正如许多编译器教科书所倡导的那样。
另一种选择是让解析器立即在它构建的符号表中查找标识符,并将指向符号的指针存储在抽象语法树节点中。如果您的语言不允许隐式前向引用尚未声明的名称,则此方法往往效果很好。
我最近在我正在开发的编译器中实现了后一种方法,到目前为止,我对结果非常满意。我将在下面简要描述我的解决方案。
符号存储在如下所示的结构中:
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
堆栈 - 每个命名空间一个堆栈。
如果我们将"范围"或"上下文"定义为从变量名称到类型的映射(可能还有一些更多信息,例如范围深度),那么它的自然实现要么是哈希映射,要么是某种搜索树。到达任何变量定义后,编译器应将具有相应类型的名称插入到此数据结构中。当遇到某种"结束范围"运算符时,我们必须已经有足够的信息来"回溯"此映射中的更改到其先前状态。
对于哈希映射实现,对于每个变量定义,我们可以存储此名称的先前映射,并在到达"范围结束"运算符时恢复此映射。我们应该保留此更改的堆栈堆栈(每个当前打开的范围一个堆栈),并在每个范围的末尾回溯最顶层的更改堆栈。
这种方法的一个缺点是,我们必须一次完成编译,或者将每个标识符的映射存储在程序中的某个地方,因为我们不能多次检查任何范围,或者按照源文件(或 AST)中出现的顺序以外的顺序。
对于基于树的实现,这可以通过所谓的持久树轻松实现。我们只是维护一堆树,每个范围一个,在我们"打开"某个范围时推动,并在范围结束时弹出。
"范围深度"足以选择在新变量名称与映射中已有的变量名称冲突的情况下要做什么。只需检查old depth < new depth
并在成功时覆盖,或在失败时报告错误。
要区分函数和变量名称,您可以对这些对象使用单独的(但相似或相同)映射。如果某些上下文只允许函数或仅允许变量名称,那么您已经知道在哪里查找。如果在某些上下文中允许两者,请在两个结构中执行查找,如果名称同时对应于函数和变量,则报告"歧义错误"。
最好的方法是使用一个类,您可以在其中定义像 HashMap 这样的结构,它允许您对变量的类型和/或存在进行控制。此类应具有与解析器中编写的语法规则交互的静态方法。