动手实现编译器（六）——实现全局变量_判定变量是否为全局变量在编译器哪一步-程序员宅基地

技术标签：编译器

我们在上一节中实现了对语句的编译，在这一节中，我们希望向语句中加入全局变量。实现类似以下语句：

int a;
int b;
int c;
int d;
int e;
int f;
int g;
a = 2;
b = 3;
c = 4;
d = 5;
e = 6;
f = 7;
g = 8;
print a + b * c / d % e - f + g;

这需要变量有以下功能：

声明变量
使用变量获取存储值
给变量赋值

全局变量符号表

为了实现变量，我们必须要有一张符号表，来存放变量。在本节中，只建立全局变量符号表。

#define SYMBOL_NUM   1024	// 符号表长度
// 符号表结构体
struct symtable
{
    
    char *name;			        // 符号名
};
struct symbol_table Tsym[SYMBOL_NUM];	// 全局符号表

此外，我们还要添加三个操作全局变量符号表的函数。

int Globals = 0;		// 全局符号表下一个空闲位置

// 检查符号s是否在全局符号表中。
// 返回其插槽位置或-1
int find_global(char *s)
{
    
    int i;
    for (i = 0; i < Globals; i++)
    {
    
        if (*s == *Tsym[i].name && !strcmp(s, Tsym[i].name))
        return i;
    }
    return -1;
}

// 获取新的全局符号槽的位置
int new_global()
{
    
    int p;
    if ((p = Globals++) >= SYMBOL_NUM)
    {
    
        fprintf(stderr, "Too many global symbols on line %d\n", Line);
        exit(1);
    }
    return p;
}

// 将全局变量添加到符号表，并返回符号表中的位置
int add_global(char *name)
{
    
    int y;
    // 如果已经在符号表中，则返回现有位置
    if ((y = find_global(name)) != -1)
        return (y);
    // 获得一个新的位置，并填入信息和返回位置
    y = new_global();
    Tsym[y].name = strdup(name);
    return y;
}

修改词法分析器

为了实现新加的语法功能，我们需要一些新单词类型：

‘int’，称为 T_KEYINT
‘=’，称为 T_EQU
标识符名称，称为 T_IDENT

将‘int’加入match_keyword()函数：

        case 'i':
            if(!strcmp(s, "int"))
                return (T_KEYINT);
            break;

将"="加入scan()函数：

        case '=':   t->token = T_EQU;   break;

对于标识符，我们已经在scan_ident() 将单词存储到Text变量中了，如果变量不是关键字，那它就是标识符，返回T_IDENT。将scan()函数中的语句段

	                    printf("Unrecognised symbol %s on line %d\n", Text, Line);
	                    exit(1);

修改为

	                    t->token = T_IDENT;
                        break;

修改语句分析器

新增变量语法后，语句分析器也要进行相应的修改：

// 分析语句
void statements()
{
    
    while (1)
    {
    
        switch (Token.token)
        {
    
            case T_PRINT:   print_statement();      break;
            case T_KEYINT:  var_declaration();      break;
            case T_IDENT:   assignment_statement(); break;
            case T_EOF:     return;
            default:    fprintf(stderr, "Syntax error, token:%s on line %d\n", Token.token, Line); 
                        exit(1);
        }
    }
}

同时把原来在statement()函数中的分析打印语句的语句块函数化，生成一个新的函数。

// 分析打印语句
void print_statement()
{
    
    struct ASTnode *tree;
    int reg;
    // 匹配第一个"print"单词
    match(T_PRINT, "print");
    // 分析表达式并生成汇编代码
    tree = binexpr(0);
    reg = code_generator(tree, -1);
    arm_print_reg(reg);
    arm_freeall_registers();
    // 匹配接下来的";"
    semi();
}

声明变量

为词法分析器，添加一个声明变量的函数

// 检查当前单词是否为标识符，并获取下一个单词
void ident()
{
    
    match(T_IDENT, "identifier");
}

// decl.c

// 分析变量声明
void var_declaration()
{
    
    // 检查当前单词是否为“int”，后跟一个标识符和一个分号
    match(T_KEYINT, "int");
    ident();
    add_global(Text);
    arm_global_sym(Text);
    semi();
}

赋值功能

我们考虑下面这个式子

a = b + c;

我们计算这个式子的流程是先计算b + c，再将和赋给a。所以，在建立AST树的时候，我们要生成一个A_ASSIGN的新类型节点，表示是赋值操作，它的左孩子是表达式（a + b），右孩子是一个A_LVIDENT的新类型的节点。A_LVIDENT节点表示，该节点是左值标识符，左值是绑定到特定位置的值，在这里它是内存中保存变量值的地址。
这样做时，我们将先计算左子树的表达式值，然后赋给右子树中保存的地址得到的标识符。好处是右值不依赖于特定的位置，表达式结果可能在任意寄存器中。
修改AST节点类型为

// AST节点类型
enum
{
    
    A_ADD, A_SUB, A_MUL, A_DIV, A_MOD, A_INT, A_IDENT, A_ASSIGN, A_LVIDENT
};

现在我们需要在 A_INTLIT AST 节点中存储整数文字值，或者在 A_IDENT AST 节点中存储符号的详细信息，所以在 AST 结构中添加了一个并集以执行此操作，修改AST结构体为

// 抽象语法树结构体
struct ASTnode
{
    
    int op;				        // 节点的操作类型
    struct ASTnode *left;
    struct ASTnode *right;
    union {
    
        int intvalue;		    // 对于立即数，储存数值
        int id;			        // 对于标识符，储存符号表位置
    } v;
};

增加分析赋值语句的函数

// 分析赋值语句
void assignment_statement()
{
    
    struct ASTnode *left, *right, *tree;
    int id;
    // 检查标识符
    ident();
    // 检查它是否已定义，然后为它创建一个叶节点
    if ((id = find_global(Text)) == -1)
    {
    
        fprintf(stderr, "Undeclared variable on line %d\n", Line); 
        exit(1);
    }
    right = mkastleaf(A_LVIDENT, id);
    // 匹配等号
    match(T_EQU, "=");
    // 分析接下来的表达式
    left = binexpr(0);
    
    // 生成赋值AST树
    tree = mkastnode(A_ASSIGN, left, right, 0);
    // 生成汇编代码
    code_generator(tree, -1);
    arm_freeall_registers();
    // 匹配";"
    semi();
}

修改代码生成函数

我们首先执行左侧的AST子级，然后获取一个保存左侧子树值的寄存器号，现在我们将此寄存器号传递给右侧子树，我们需要对A_LVIDENT节点执行此操作，以便于让后面的函数知道哪个寄存器保存赋值表达式的右值结果。
代码如下：

// 给定AST，生成汇编代码，返回值为结果所在寄存器号
int code_generator(struct ASTnode *n, int reg)
{
    
    int leftreg, rightreg;
    if (n->left)    leftreg = code_generator(n->left, -1);
    if (n->right)   rightreg = code_generator(n->right, leftreg);
    switch (n->op)
    {
    
        case A_ADD:    return (arm_add(leftreg,rightreg));
        case A_SUB:    return (arm_sub(leftreg,rightreg));
        case A_MUL:    return (arm_mul(leftreg,rightreg));
        case A_DIV:    return (arm_div(leftreg,rightreg));
        case A_MOD:    return (arm_mod(leftreg,rightreg));
        case A_INT:    return (arm_load_int(n->v.intvalue));
        case A_IDENT:  return (arm_load_global(n->v.id));
        case A_LVIDENT:return (arm_stor_global(reg, n->v.id));
        case A_ASSIGN: return rightreg;
        default:    fprintf(stderr, "Unknown AST operator %d\n", n->op);
                    exit(1);
    }
}

注：这里将arm_load()修改成其他arm_load函数一样的arm_load_XXX()形式。
这里解释一下这段代码的意思，考虑以下 AST 树：

           A_ASSIGN
          /        \
       A_INT   A_LVIDENT
        (3)        (5)

我们调用leftreg = code_generator(n->left, -1); 以执行 A_INT操作，这将执行 case A_INT: return (arm_load_int(n->v.intvalue)); 即加载值为3的寄存器并返回寄存器ID。
然后我们调用 rightreg = code_generator(n->right, leftreg); 以执行A_LVIDENT操作，这将把 return (arm_load_global(Tsym[n->v.id].name)); 返回的寄存器存储到名称为Tsym[5]的变量中。
然后我们回到A_ASSIGN操作，右值仍在寄存器中，因此让它保留在那里并返回它。

表达式加载变量

我们对primary()函数进行修改，使其同时加载变量的值：

// 解析一个整数单词并返回表示它的AST节点
struct ASTnode *primary()
{
    
    struct ASTnode *n;
    int id;
    switch (Token.token)
    {
    
        // 对于整数单词，为其生成一个AST叶子节点
        case T_INT:  
            n = mkastleaf(A_INT, Token.intvalue);
            break;
        // 对于标识符，检查存在并为其生成一个AST叶子节点
        case T_IDENT:
            id = find_global(Text);
            if (id == -1)
            {
    
                fprintf(stderr, "Unknown variable %s on line %d\n", Text, Line);
                exit(1);
            }
            n = mkastleaf(A_IDENT, id);
            break;
        default:
            fprintf(stderr, "syntax error, token %s on line %d\n", Token.token, Line);
            exit(1);
    }
    // 扫描下一个单词,并返回左节点
    scan(&Token);
    return n;
}

生成汇编代码

上面已经说了，我将旧arm_load()函数的名称更改为arm_load_int()，现在我们有一个函数可以从全局变量加载值：

// 确定变量与.L2标签的偏移量
void set_var_offset(int id)
{
    
    fprintf(Outfile, "\tldr\tr3, .L2+%d\n", id * 4);
}

// 将变量中的值加载到寄存器中，并返回寄存器编号
int arm_load_global(int id)
{
    
    // 获得一个新的寄存器
    int r = arm_alloc_register();
    // 获得变量偏移地址
    set_var_offset(id);
    fprintf(Outfile, "\tldr\tr%d, [r3]\n", r);
    return r;
}

同样我们需要一个函数来将寄存器值保存到变量中：

// 将寄存器的值装载入变量
int arm_stor_global(int r, int id)
{
    
    // 获得变量偏移地址
    set_var_offset(id);
    fprintf(Outfile, "\tstr\tr%d, [r3]\n", r);
    return r;
}

我们还需要一个函数来创建新的全局整数变量：

// 生成全局变量符号表
void arm_global_sym(char *name)
{
    
    fprintf(Outfile, "\t.text\n\t.comm\t%s,4,4\n", name);
}

对应的，我们也要修改汇编尾代码函数，时期能输出全局变量表。

// 汇编尾代码
void arm_postamble()
{
    
    fputs(
        "\tmov     r3, #0\n"
        "\tmov     r0, r3\n"
        "\tpop     {fp, pc}\n"
        ".L3:\n"
        "\t.word   .LC0\n"
        "\t.size   main, .-main\n",
    Outfile);
    fprintf(Outfile, ".L2:\n");
    for (int i = 0; i < Globals; i++)
    {
    
        fprintf(Outfile, "\t.word %s\n", Tsym[i].name);
    }
}

测试结果

输入：

int a;
int b;
int c;
int d;
int e;
int f;
int g;
int h;
int i;
a = 1;
b = 4;
c = 13;
d = 11;
e = 2;
f = 0;
g = 20;
h = 1024;
i = 10;
a = a + b;
c = c - d;
e = e * f;
g = g / g;
h = h % i;
print a;
print c;
print e;
print g;
print h;
g = a + c + e + g + h;
print g;

输出（out.s）:

	.text
	.global __aeabi_idiv
	.section	.rodata
	.align  2
.LC0:
	.ascii  "%d\012\000"
	.text
	.align  2
	.global main
	.type   main, %function
main:
	push    {
    fp, lr}
	add     fp, sp, #4
	.text
	.comm	a,4,4
	.text
	.comm	b,4,4
	.text
	.comm	c,4,4
	.text
	.comm	d,4,4
	.text
	.comm	e,4,4
	.text
	.comm	f,4,4
	.text
	.comm	g,4,4
	.text
	.comm	h,4,4
	.text
	.comm	i,4,4
	mov	r4, #1
	ldr	r3, .L2+0
	str	r4, [r3]
	mov	r4, #4
	ldr	r3, .L2+4
	str	r4, [r3]
	mov	r4, #13
	ldr	r3, .L2+8
	str	r4, [r3]
	mov	r4, #11
	ldr	r3, .L2+12
	str	r4, [r3]
	mov	r4, #2
	ldr	r3, .L2+16
	str	r4, [r3]
	mov	r4, #0
	ldr	r3, .L2+20
	str	r4, [r3]
	mov	r4, #20
	ldr	r3, .L2+24
	str	r4, [r3]
	mov	r4, #1024
	ldr	r3, .L2+28
	str	r4, [r3]
	mov	r4, #10
	ldr	r3, .L2+32
	str	r4, [r3]
	ldr	r3, .L2+0
	ldr	r4, [r3]
	ldr	r3, .L2+4
	ldr	r5, [r3]
	add	r4, r4, r5
	ldr	r3, .L2+0
	str	r4, [r3]
	ldr	r3, .L2+8
	ldr	r4, [r3]
	ldr	r3, .L2+12
	ldr	r5, [r3]
	sub	r4, r4, r5
	ldr	r3, .L2+8
	str	r4, [r3]
	ldr	r3, .L2+16
	ldr	r4, [r3]
	ldr	r3, .L2+20
	ldr	r5, [r3]
	mul	r4, r4, r5
	ldr	r3, .L2+16
	str	r4, [r3]
	ldr	r3, .L2+24
	ldr	r4, [r3]
	ldr	r3, .L2+24
	ldr	r5, [r3]
	mov	r0, r4
	mov	r1, r5
	bl	__aeabi_idiv
	mov	r4, r0
	ldr	r3, .L2+24
	str	r4, [r3]
	ldr	r3, .L2+28
	ldr	r4, [r3]
	ldr	r3, .L2+32
	ldr	r5, [r3]
	mov	r6, r4
	mov	r0, r6
	mov	r1, r5
	bl	__aeabi_idiv
	mov	r6, r0
	mul	r6, r6, r5
	sub	r4, r4, r6
	ldr	r3, .L2+28
	str	r4, [r3]
	ldr	r3, .L2+0
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	ldr	r3, .L2+8
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	ldr	r3, .L2+16
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	ldr	r3, .L2+24
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	ldr	r3, .L2+28
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	ldr	r3, .L2+0
	ldr	r4, [r3]
	ldr	r3, .L2+8
	ldr	r5, [r3]
	add	r4, r4, r5
	ldr	r3, .L2+16
	ldr	r5, [r3]
	add	r4, r4, r5
	ldr	r3, .L2+24
	ldr	r5, [r3]
	add	r4, r4, r5
	ldr	r3, .L2+28
	ldr	r5, [r3]
	add	r4, r4, r5
	ldr	r3, .L2+24
	str	r4, [r3]
	ldr	r3, .L2+24
	ldr	r4, [r3]
	mov     r1, r4
	ldr     r0, .L3
	bl      printf
	mov     r3, #0
	mov     r0, r3
	pop     {
    fp, pc}
.L3:
	.word   .LC0
	.size   main, .-main
.L2:
	.word a
	.word b
	.word c
	.word d
	.word e
	.word f
	.word g
	.word h
	.word i

输出（out）：

总结

我们写出了符号表管理，我们处理了两种新的语句类型，我们添加了一些新单词类型的和一些新的AST节点类型，我们添加了一些代码以生成正确的汇编代码。在下一节中，我们将仿照本节的方法，添加六个比较运算符。

本文链接：https://blog.csdn.net/qq_34851605/article/details/117921750

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Unity性能优化篇(四) GPU Instancing_u3d gpu instancing-程序员宅基地

文章浏览阅读572次，点赞3次，收藏4次。一般来说，当场景中有大量重复的网格实例时，可以尝试启用GPU Instancing。例如场景中有大量树木、草地、石块等，这些实例具有相同的网格和材质，只是位置、颜色等属性稍有差异，那么启用GPU Instancing或许能够显著提高性能。启用GPU Instancing，我们可以选中一个材质，然后在Inspector窗口勾选Enable GPU Instancing。使用GPU Instancing往往能减少CPU和GPU的开销，提升游戏性能，但同时也会占用一定的内存。3、网格的顶点布局和着色器必须相同。_u3d gpu instancing

selenium+python+unittest:一个类中只执行一次setUpClass和tearDownClass里面的内容（可解决重复打开浏览器和关闭浏览器，或重复登录等问题）...-程序员宅基地

文章浏览阅读516次。unittest框架是python自带的，所以直接import unittest即可，定义测试类时，父类是unittest.TestCase.可实现执行测试前置条件、测试后置条件，对比预期结果和实际结果，检查程序的状态，生成测试报告。且断言的话unittest框架很方便。在这主要记录下setUp()和tearDown()这两个的问题，每次执行一个测试用例（test开头的方法）..._unitest怎么避免每次打开一遍网页

计算机网络A卷浙江农林大学,2018年浙江农林大学842信息技术基础考研大纲-程序员宅基地

文章浏览阅读793次。2018年浙江农林大学842信息技术基础考研大纲1浙江农林大学硕士研究生入学考试信息技术基础(农业工程与信息技术)考试大纲一、考试性质浙江农林大学硕士研究生入学《信息技术基础》考试是为招收农业信息化专业而设置的具有选拔功能的水平考试。它的主要目的是测试考生对计算机基础知识及信息技术应用的掌握程度及应用相关知识解决问题的能力。二、考试的基本要求要求考生对计算机技术、多媒体技术和网络技术为核心的信..._信息技术基础842

阿里云大模型数据存储解决方案，为 AI 创新提供推动力_阿里云能够为大模型ai创新提供三方面能力-程序员宅基地

文章浏览阅读1k次，点赞22次，收藏17次。随着国内首批大模型产品获批名单问世，百“模”大战悄然开启。在这场百“模”大战中，每一款大模型产品的诞生，都离不开数据的支撑。如何有效存储、管理和处理海量多模态数据集，并提升模型训练、推理的效率，保障 AI 业务平台运行的稳定，仍是亟待解决的难题。_阿里云能够为大模型ai创新提供三方面能力

静态方法在多线程下的调用_多线程static方法中new stringbuilder-程序员宅基地

文章浏览阅读2.1k次。 class Program { static void Main(string[] args) { Thread t1 = new Thread(new ParameterizedThreadStart(Work)); t1.Start(0); Thread.Sleep(1000); Thread t2 = new Thread(_多线程static方法中new stringbuilder

不属于python标准库的是_python标准库和扩展库-程序员宅基地

文章浏览阅读1k次。Tkinter————Python默认的图形界面接口。Tkinter是一个和Tk接口的模块，Tkinter库提供了对Tk API的接口，它属于Tcl/Tk的GUI工具组。Tcl/Tk是由John Ousterhout发展的书写和图形设备。Tcl(工具命令语言)是个宏语言，用于简化shell下复杂程序的开发，Tk工具包是和Tcl一起开发的，目的是为了简化用户接口的设计过程。Tk工具包由许多不同的小部..._不属于python的标准库

随便推点

将yolov5的detect.py改写成可以供其他程序调用的方式，并实现低时延（＜0.5s）直播推理_yolov5 dataset = loadstreams-程序员宅基地

文章浏览阅读1.5w次，点赞50次，收藏322次。将yolov5的推理代码改成可供其它程序调用的方式，并实现低时延（<0.5s）直播推理yolov5的代码具有高度的模块化，对于初学者十分友好，但是如果咱们要做二次开发，想直接调用其中一些函数，恐怕还是得费一番功夫。参考https://www.pythonheidong.com/blog/article/851830/44a42d351037d307d02d/和https://blog.csdn.net/ld_long/article/details/113920521（不知道为什么失效了）实现_yolov5 dataset = loadstreams

JavaScript之Proxy详解_js中proxy-程序员宅基地

文章浏览阅读445次，点赞8次，收藏10次。是JavaScript中的一个强大而灵活的特性，它允许你创建一个代理对象，可以拦截并改变对象的底层操作。是ES6引入的一个新对象，用于创建一个对象的代理，可以拦截并重定义基本的操作。提供了丰富的拦截操作，使得我们能够对对象的行为进行灵活的定制。可以实现对象属性的懒加载，只在访问时才进行实际的计算或获取。能够实现更清晰和易读的代码，避免了传统的一些hack手段。的特性和应用场景，有助于更好地利用它提供的强大功能。是ES6引入的特性，不支持ES6的环境无法使用。可以实现数据绑定，监听对象属性的变化。_js中proxy