用AI写编译器的第5天

Dentry

不想写介绍

语义分析理论基础

历史

语义分析的历史可以追溯到20世纪50年代。早期的编译器主要关注语法分析和代码生成，而忽略了语义分析这个阶段。直到20世纪60年代，出现了第一个使用语义分析的编译器 Algol 60 编译器。Algol 60 是一种高级编程语言，它是第一种具有块结构、递归函数和动态数组等特性的编程语言之一。Algol 60 编译器在语法分析的基础上，引入了类型检查和错误检测等语义功能，成为第一个完整实现语义分析的编译器之一。

定义

语义分析主要工作就是在语法树转化为中间代码之前检查语法树是否符合语义规则。在这个阶段，编译器将主要执行语法检查、类型检查、错误检测等操作，以确保生成的代码的正确性。

类型检查 ：语义分析阶段会检查所有变量、表达式和函数的数据类型是否匹配。如果存在不匹配的情况，编译器会报告错误。
作用域检查 ：编译器会检查变量和函数的作用域是否正确。例如，局部变量只能在函数内部使用，全局变量可以在整个程序中使用等等。
函数调用检查 ：编译器会检查函数调用是否正确。例如，检查参数数量是否正确、参数类型是否匹配等等。
错误报告： 在编译程序时，语义分析器将检查程序中是否存在语义错误，例如使用未定义的变量或函数，或者将不兼容的类型进行运算。如果发现了错误，语义分析器将向用户发出警告或错误信息，并指出错误的位置。

符号表

语义分析的核心数据结构是符号表。符号表是一个用来保存程序中所有已声明的变量、函数、常量等符号以及它们的属性信息的数据结构。

符号表示例：

   ╭───────────────────────────╮
   │         Global符号表       │
   ├─────────────┬─────────────┤
   │   变量名     │    类型      │
   ├─────────────┼─────────────┤
   │    var1     │     int     │
   ├─────────────┼─────────────┤
   │    var2     │    float    │
   ├─────────────┼─────────────┤
   │    main     │   function  │
   ╰─────────────┴─────────────╯
int var1; float var2; 
int main(){...}
Main->parent = Global
   ╭───────────────────────────╮
   │         Main符号表         |
   ├─────────────┬─────────────┤
   │   变量名     │    类型      │
   ├─────────────┼─────────────┤
   │    var3     │     int     │
   ├─────────────┼─────────────┤
   │    var4     │    float    │
   ├─────────────┼─────────────┤
   │    add      │   function  │
   ├─────────────┼─────────────┤
   |     ...     |    ...      |
   ╰─────────────┴─────────────╯
main() {int var3;float var4;
 var3 = add(var1, var2);...}

回想以下，程序就是一堆符号，表达式，语句构成的字符串。其中，符号通常包含标签地址，变量和函数。我们通过查询符号表来检查分析符号语义是否正确，比如重复声明，未声明的变量或者函数等等。通常一个正经的程序有成千上万个符号，符号表的查询功能被调用得很频繁。所以我们需要高效的查询功能，通过符号的名字可以快速返回符号的信息。我们将采用哈希表来实现以下的查询接口：

symbot_t *symbol_table_lookup(symbol_table_t *symtab, char *name);

哈希链表

哈希链表是一种内存数据存储。哈希表是一种基于键（Key）和值（Value）的数据结构，其中键用于访问值。当我们将一个值插入到哈希表中时，将使用哈希函数对键进行哈希，从而得到一个索引值。然后，将该值存储在与该索引值对应的桶（Bucket）中。如果多个值被哈希到同一个桶中，那么它们将被存储在一个链表或其他数据结构中。当我们需要查找一个值时，将使用哈希函数对键进行哈希，从而得到它所在的桶。然后，我们将遍历该桶中的链表或其他数据结构，直到找到所需的值。

以下是一个哈希链表的简单示例：

哈希表大小: 5 bucket
idx = hash(var) % 5
0 -> var2 -> var3
1 -> var1 -> fun1
2 -> var6 -> var6
3 -> var5
4 -> var4 -> fun2

在这个示例中，我们有一个5个bucket桶的哈希表，其中每个桶都是一个链表。假设我们要查找 var4 ，那么我们将使用哈希函数对键进行哈希，从而得到它在哈希表中的索引值。在这个示例中， var4 的哈希值为 4，因此它将存储在索引为 4 的桶中。然后，我们将遍历该桶中的链表，直到找到 var4 。在这个示例中， var4 是该链表的第一个元素，因此我们将直接找到它。如果 var4 不在链表中，那么我们将遍历整个链表，直到找到它或者遇到空链表为止。

哈希链表的查询时间复杂度是 O(1)，也就是一个常量，这也是几乎所有的编译器都选择哈希表来实现符号表的原因。

作用域

作用域是限定变量，函数名的使用范围的。不出意外，第一个引入作用域概念的编程语言也还是 ALGOL 60。我们的语法树中没有作用域的描述，所以作用域不是语法的概念，而是一种语义上的概念。所以，语义分析阶段不仅是检查语义，还要实现作用域这个编程语言的元素。而通常作用域是通过符号表来实现的，比如每个文件都分配一个文件全局的符号表，文件中的每个函数都有自己的局部符号表，每个代码块也有自己的符号表。

作用域示例：

int a = 1;
int add(int x, int y)
    int a = 3;
  return x + y + a;
int main()
    return a + add(1 + 2);
main函数将返回7(1+1+2+3)，在add函数的作用域a（局部变量）是3，在main函数的作用域，a（全局变量）是1。

人脑会语义分析吗

当然会，人脑进行语义分析时，主要依赖于对世界观，语境和文化知识的理解。人们能够根据上下文和语言知识来推测或者说修正得到句子或短语的真正的含义，即便是有很多语法或者有歧义的句子，复杂度远超程序语言。相比之下，编译器就是弱智，必须严格遵守编程语言的规范，对语法、类型等方面进行检查，并能够正确地处理各种异常情况，如未定义变量或函数、类型不匹配等。此外，编译器还需要实现作用域等编程语言的元素，以确保程序执行的正确性。

NLP的语义分析

自然语言处理和编译器的语义分析阶段都是涉及到语义理解的过程。它们的相同点在于都需要将源代码或自然语言文本转化为一种语义表示，以便后续的处理和分析。而它们的不同点在于，编译器的语义分析是针对编程语言的，主要涉及到类型检查、作用域检查、语法检查、函数调用检查等问题；而自然语言处理的语义分析则涉及到自然语言的语义理解，包括词义消歧、语义角色标注、语义关系分析等等。此外，自然语言处理的语义分析还需要考虑到语言的灵活性和多样性，因此需要使用一些机器学习和深度学习等技术来提高效果。

代码实现

遍历语法树

有了语法树，我们如何进行语义分析呢？其实很简单，就是通过深度优先的方式遍历语法树的所有结点，然后对每一个节点进行相应的处理，所谓的处理就是生成符号表，变量检查等。在这里，比起深度优先这种抽象的术语，我有个更加贴切接地气的描述，就是按照程序的执行顺序来处理的。

int x, y; 1 创建一个全局符号表global，并添加x, y
int main(int x, int y) 2 添加main符号到global, 创建main的符号表，并添加x和y到main
    { int x = 1;} 3 创建一个local的符号表，添加x到local
    int z；4 添加z到符号表main
    z = x + y; 5 依次查询z, x, y，检查是否在符号表中
    return z; 6 查询z是否在符号表中
}

以上这个简单程序，我们遍历AST对节点的操作，就是按照代码的顺序从1到6执行操作的。

实现作用域

C语言的作用域是嵌套式的，支持全局，函数，块的作用域，同一个变量名可以同时存在多个作用域，但同一个作用域不能有相同名字的变量。

实现嵌套，也就是遇见代码块”{ }”就需要动态的生成一个对应的符号表。
支持回溯，也就是当前的符号表没有查询到，一直向上回溯到全局符号表。

现在有了树形结构的AST，支持这两个功能很简单。对于嵌套，把生成的符号表和对应的树节点通过指针链接起来就行了。对于回溯，只需要在符号表的结构体中添加一个parent指针，然后在lookup函数中向上查询就行了。

typedef struct symbol_table {
#define TABLE_SIZE 1024
    struct hlist_head table[TABLE_SIZE];
    struct symbol_table *parent; //支持回溯
    char *name;
} symbol_table_t;
// Lookup symbol in symbol table backwards
static symbol_t *symbol_table_lookup(symbol_table_t *t, char *name,
                                     int upward)
    int idx = symbol_table_hash(name);
    struct hlist_head *head = t->table + idx;
    struct hlist_node *node;
    tc_debug(0, "lookup %s in %s\n", name, t->name);
    hlist_for_each(node, head) {
        symbol_t *s = hlist_entry(node, symbol_t, list);
        if (!strcmp(s->name, name))
            return s;