- 1【Android】MQTT的接入_org.eclipse.paho:org.eclipse.paho.client.mqttv3:1.
- 2C# Stable Diffusion using ONNX Runtime_stable diffusion 接口c#
- 3OFDM 802.11a的FPGA实现（十六）长训练序列：LTS（含Matlab和verilog代码)
- 4只会 Vue 的前端工程师是没有前途的
- 5安卓开发——Android Studio常见报错与解决方法_no toolchains found in the ndk toolchains folder f
- 6计算机网络 DNS与ARP_arp,dns,路由表三者在数据发送过程中分别起到了什么作用
- 7时序预测 | Python实现TCN时间卷积神经网络时间序列预测
- 8小程序-本地存储StorageSync的相关用法_setstoragesync
- 9nltk 词性标注详解_nltk词性标注的原理
- 10前端性能优化——图片优化_前端图片加载优化
动手实现编译器（十三）——左结合和右结合_右结合返回左值的
赞
踩
上一节中，我们实现了真正的全局变量，在这一节中，我们要重新考虑左值和右值的关系。所以，我们可能需要删除我们已经编写的代码并重新编写它以使其更通用，或者修复缺点。
我们现在实现的代码：
int x;
x = 12;
- 1
- 2
这实现得很好，但我知道我们最终必须支持在赋值语句的左侧使用数组元素，例如
a[0] = 13;
- 1
为此，我们必须重新讨论左值和右值。
左值是绑定到特定位置的值，而右值是不绑定的值。 左值是持久的，因为我们可以在未来的指令中检索它们的值。另一方面，右值是暂时的：一旦它们使用完毕，我们就可以丢弃它们。
正如我之前提到的，左值和右值来自赋值语句的两侧：左值在左边，右值在右边。
现在，编译器几乎将所有内容都视为右值。对于变量，它就是变量的位置值。我们对左值概念的唯一认可是将赋值左侧的标识符标记为A_LVIDENT。为此，我们要修改AST树节点类型，使其能区分左值和右值。
修改AST节点类型
// 抽象语法树结构体
struct ASTnode
{
int op; // 节点的操作类型
int type; // 表达式数据类型
int rvalue; // 节点为右值则为真
/*......其他属性......*/
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
rvalue字段只保存一位信息；稍后，如果我们需要存储其他布尔值，我们将能够将其用作位域。
为什么我让字段表示节点的右值而不是左值？毕竟，我们 AST 树中的大多数节点将保存右值而不是左值。
由于以后不能反转间接，因此解析器假定每个部分表达式都是左值。
考虑处理语句 b = a + 2 的解析器。 在解析了 b 标识符之后，我们还不能分辨这是一个左值还是一个右值。 直到我们点击 = 标记，我们才能得出它是一个左值的结论。
另外，SysY语言允许赋值为表达式，所以我们也可以写成 b = c = a + 2。 同样，当我们解析 a 标识符时，在解析下一个标记之前，我们无法判断它是左值还是右值。
因此，我选择将每个AST节点默认为左值。 一旦我们可以明确地判断一个节点是否是右值，我们就可以设置右值字段来指示这一点。
我在上面提到SysY语言允许将赋值作为表达式。 现在我们有了明确的左值/右值区别，我们可以将赋值的解析转换为语句，并将代码移动到表达式解析器中。 我们在后面会实现这个。
现在来看看我们对编译器代码做了什么修改来使这一切发生。与往常一样，我们首先从词法分析开始。
修改词法分析
这次我们没有添加新的单词或新的关键字。但是有一个影响词法分析代码的变化。= 现在是一个二元运算符，每边都有一个表达式，因此我们需要将它与其他二元运算符集成。
根据语言定义，= 操作符的优先级比 + 或 - 低得多。我们需要重新排列我们的运算符列表及其优先级。
// 单词类型
enum
{
T_EOF, T_EQU,
T_ADD, T_SUB, T_MUL, T_DIV, T_MOD, T_EQ, T_NE, T_LT, T_GT, T_LE, T_GE,
/*......其他单词类型......*/
};
// AST节点类型
enum
{
A_ASSIGN = 1, A_ADD, A_SUB, A_MUL, A_DIV, A_MOD, A_EQ, A_NE,
/*......其他AST节点类型......*/
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
这里把=的单词类型T_EQU提前到+的单词类型T_ADD之前，便于我们后面修改优先级列表。对应的，也要把A_ASSIGN提到A_ADD之前，否则会造成单词类型和AST节点类型不匹配。
修改优先级列表
// 每个AST节点的运算符优先级
int OpPrec[] = {0, 10, 20, 20, 30, 30, 30, 40, 40, 50, 50, 50, 50};
//依次为:T_EOF, T_EQU, T_ADD, T_SUB, T_MUL, T_DIV, T_MOD, T_EQ, T_NE, T_LT, T_GT, T_LE, T_GE
- 1
- 2
- 3
修改语法分析
现在我们必须删除将赋值作为语句的解析并将它们变成表达式。因此，我删除了
assignment_statement()。现在我们的左值概念和右值不同，我还删除了A_LVIDENTAST 节点类型。
目前，single_statement() 中的语句解析器假设接下来出现的是一个表达式，如果它不能识别第一个标记：
// 分析一条语句，并返回其AST树 struct ASTnode *single_statement() { int type; switch (Token.token) { case T_PRINT: return print_statement(); case T_KEYINT: type = parse_type(); ident(); var_declaration(type); return NULL; // 没有AST树生成 case T_IF: return if_statement(); case T_WHILE: return while_statement(); case T_RETURN: return return_statement(); default: { // 判断这是否是一个表达式,这会捕获赋值语句。 return binexpr(0); } } return NULL; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
这确实意味着“2+3;”现在将被视为合法的语句，我们稍后会解决这个问题。在 compound_statement() 中，我们还确保表达式后跟一个分号：
// 一些句子后面要识别";"
if (tree != NULL && (tree->op == A_ASSIGN || tree->op == A_RETURN || tree->op == A_FUNCTIONCALL || tree->op == A_PRINT))
semi();
- 1
- 2
- 3
在这里，我直接把赋值、IF语句、打印整数语句和函数调用三种语句统一在复合函数语句中识别";"，所以，我们要在这些语句中删除semi();。
虽然=被标记为一个二元表达式运算符并且我们已经设置了它的优先级，但我们仍需要担心的有两件事：
- 我们需要在生成左边左值的代码之前生成右边右值的汇编代码。我们过去常常在语句解析器中执行此操作，而现在我们必须在表达式解析器中执行此操作。
- 赋值表达式是右结合的：运算符与右侧表达式的绑定比左侧的绑定更紧密。
看一个例子来学习右结合性，考虑表达式2 + 3 + 4。 我们可以从左到右解析它并构建 AST 树：
+
/ \
+ 4
/ \
2 3
- 1
- 2
- 3
- 4
- 5
那么，对于表达式a= b= 3，如果我们执行上述操作，我们最终会得到树：
=
/ \
= 3
/ \
a b
- 1
- 2
- 3
- 4
- 5
很显然我们不想在将3分配给这个左子树之前执行 a= b。 相反，我们想要生成的是这棵树：
=
/ \
= a
/ \
3 b
- 1
- 2
- 3
- 4
- 5
我已将叶节点反转为汇编输出顺序。我们首先将3存储在 b 中。然后这个赋值的结果3被赋值给 a 。
修改Pratt分析器
我们正在使用 Pratt 解析器来正确解析我们的二元运算符的优先级。
如何添加右结合性到Pratt解析器：下一个运算符是优先级大于op的二元运算符，或优先级等于op的右结合运算符，则需要先计算下一个运算符
因此，对于右结合运算符，我们测试下一个运算符是否与我们要使用的运算符具有相同的优先级。这是对解析器逻辑的简单修改。
我增加了一个新函数来判断运算符是否是右结合，显然，在SysY语言中只有=运算符是右结合的。
// 如果标记是右结合的，则返回1，否则返回0
int rightassoc(int tokentype)
{
if (tokentype == T_EQU)
return 1;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
在 binexpr() 中，我们改变了while循环，并且我们还放入了特定于A_ASSIGN的代码来交换子树：
// 返回一个以二元操作符为根的树 struct ASTnode *binexpr(int pretokentype) { struct ASTnode *left, *right; struct ASTnode *ltemp, *rtemp; int ASTop, tokentype; // 获取左节点的整数，同时获取下一个单词 left = primary(); // 如果下一个单词是';'或者')'，则返回左节点 tokentype = Token.token; if (tokentype == T_SEM || tokentype == T_RPAREN) { left->rvalue = 1; return left; } // 当前单词的优先级高于前一个单词的优先级 while (op_precedence(tokentype) > pretokentype || (rightassoc(tokentype) && op_precedence(tokentype) == pretokentype)) { // 获取下一个单词 scan(&Token); // 根据优先级递归生成右子树 right = binexpr(OpPrec[tokentype]); // 确定要对子树执行的操作 ASTop = token_op(tokentype); if (ASTop == A_ASSIGN) { // 赋值操作,把右边的树变成右值 right->rvalue= 1; // 生成一个赋值AST树。但是，左右子树交换， // 这样右表达式的代码将在左表达式之前生成 ltemp = left; left = right; right = ltemp; } else { // 我们没有做赋值，所以两棵树都应该是右值 // 如果它们是左值树，则将它们转换为右值 left->rvalue = 1; right->rvalue = 1; } // 从单词类型得到到节点类型，然后合并左、右子树 left = mkastnode(token_op(tokentype), left, NULL, right, 0); // 更新当前单词的详细信息 tokentype = Token.token; // 如果遇到';'或者')'，则返回左节点 // 此时的左节点已经更新为合并后的树的根节点 if (tokentype == T_SEM || tokentype == T_RPAREN) { left->rvalue = 1; return left; } } left->rvalue = 1; return left; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
还要注意将赋值表达式的右侧显式标记为右值的代码。并且，对于非赋值，表达式的两边都被标记为右值。
在binexpr()中的最后几行代码，用于将树显式设置为右值。当我们处理一个叶子节点时，这些就会被执行。例如，b= a;中的a标识符需要标记为右值，但我们永远不会进入while循环体来执行此操作。
修改代码生成器
现在已经清楚地标识了左值和右值节点，我们可以将注意力转向如何将每个节点转换为汇编代码。有许多节点，如整数文字、加法等，它们显然是右值。code_generator() 中的代码只需要着重处理可能是左值的AST节点类型。
// 给定一个 AST、一个可选标签和父级的AST操作， // 递归生成汇编代码,返回带有树的最终值的寄存器id int code_generator(struct ASTnode *n, int label, int parentASTop) { int leftreg, rightreg; // 特定的AST节点处理 switch (n->op) { case A_IF: return code_IF_generator(n); case A_WHILE: return code_WHILE_generator(n); // 执行每个子语句，并在每个子语句执行之后释放寄存器 case A_GLUE: code_generator(n->left, NOLABEL, n->op); arm_freeall_registers(); code_generator(n->right, NOLABEL, n->op); arm_freeall_registers(); return NOREG; // 在生成主体代码之前生成函数的前言 case A_FUNCTION: arm_function_preamble(Tsym[n->v.id].name); code_generator(n->left, NOLABEL, n->op); arm_function_postamble(n->v.id); return NOREG; } // 一般AST节点处理 // 获取左右子树值 if (n->left) leftreg = code_generator(n->left, NOLABEL, n->op); if (n->right) rightreg = code_generator(n->right, NOLABEL, n->op); 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_EQ: case A_NE: case A_LT: case A_GT: case A_LE: case A_GE: // 如果父AST节点是A_IF或WHILE，则生成一个比较后跟一个跳转。 // 否则，比较寄存器并根据比较结果将寄存器设置为1或0 if(parentASTop == A_IF || parentASTop == A_WHILE) return arm_compare_and_jump(n->op, leftreg, rightreg, label); else return arm_compare_and_set(n->op, leftreg, rightreg); case A_INT: return (arm_load_int(n->v.intvalue)); case A_IDENT: // 如果标识符是右值，则加载它的值 if (n->rvalue) return arm_load_global(n->v.id); else return NOREG; case A_ASSIGN: // 判断分配的是不是标识符 if(n->right->op == A_IDENT) return arm_stor_global(leftreg, n->right->v.id); else { fprintf(stderr, "Can't A_ASSIGN in code_generator(), op:%d on line %d\n", n->op, Line); exit(1); } case A_PRINT: arm_print_reg(leftreg); arm_freeall_registers(); return NOREG; case A_RETURN: arm_return(leftreg, Functionid); return NOREG; case A_FUNCTIONCALL: return arm_call(leftreg, n->v.id); default: { fprintf(stderr, "Unknown AST operator %d\n", n->op); exit(1); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
测试结果
输入：
int a,b;
int main()
{
a = b = 3;
a = 4;
print a + b;
return a + b;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
输出（out.s）：
.text .global __aeabi_idiv .section .rodata .align 2 .LC0: .ascii "%d\012\000" .text .comm a,4,4 .text .comm b,4,4 .text .align 2 .globl main .type main, %function main: push {fp, lr} add fp, sp, #4 sub sp, sp, #8 str r0, [fp, #-8] mov r4, #3 ldr r3, .L2+4 ldr r5, [r3] ldr r3, .L2+4 str r4, [r3] ldr r3, .L2+0 ldr r6, [r3] ldr r3, .L2+0 str r4, [r3] mov r4, #4 ldr r3, .L2+0 ldr r5, [r3] ldr r3, .L2+0 str r4, [r3] ldr r3, .L2+0 ldr r4, [r3] ldr r3, .L2+4 ldr r5, [r3] add r4, r4, r5 mov r1, r4 ldr r0, .L3 bl printf ldr r3, .L2+0 ldr r4, [r3] ldr r3, .L2+4 ldr r5, [r3] add r4, r4, r5 mov r0, r4 b L1 L1: sub sp, fp, #4 pop {fp, pc} .align 2 .L3: .word .LC0 .L2: .word a .word b
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
输出（out）：
7
- 1
总结
在这一节中，我们主要重构了代码，探讨了左结合和右结合的实现方式，为我们后面实现数组建立了一点的基础。在下一节中，我们会处理注释，这是一个比较简单的问题。
