什么是抽象语法树和三地址表达（通俗理解版）

2.1 什么是抽象语法树和三地址表达（通俗理解版）

文献来源：《编译原理（第2版）》第二章

准备知识：术语

• 语法（Syntax）

规定了语言得表达形式。可以参考英语学习中的例子。英语句子的正常表达是按照主谓宾结构。例如

I love you.

当写成

I you love

就被认为是语法错误

• 语义（Semantics）

比如I love you是去爱，那么如果其行为为hate则为错。当然，计算机内部不会有爱与恨，但是有加减乘除等操作。如果是表达式是加法，而其行为是减法，则认为语义有错。

• 词法单元（Token）

词法分析器（一种对表达式进行分析的程序）处理多个字符组成的构造。比如词法分析器分析下列表达式

count + 1

假设词法分析器内部定义标识符为一个词法单元，那么count就是一个词法单元。

抽象语法树和语法树

语法树(syntax tree)是抽象语法树(abstract syntax tree)的简称。它表示了源程序的层次化语法结构。

假设C语言代码

do{
	i = i + 1;
}while(a[i]<v);

形成抽象语法树的过程如下。

1. 确定叶子节点。所有的变量，数字都为叶子。

i, 1, a, v

2. 确定父节点。所有运算所涉及的符号

赋值(=), +, do-while逻辑中的循环体，do-while逻辑中的循环条件(<)，索引[]

3. 用叶子节点与父节点构成树形结构。

比如i+1

    +
   / \
  i   1

然后将每一个子树进行组合形成整个表达式的抽象语法树

三地址代码

三地址码（Three Address Code）是一种最常用的中间语言，编译器可以通过它来改进代码转换效率。每个三地址码指令，都可以被分解为一个四元组（4-tuple）的形式：（运算符，操作数1，操作数2，结果）。由于每个陈述都包含了三个变量，即每条指令最多有三个操作数，所以它被称为三地址码。
https://blog.csdn.net/weixin_44966641/article/details/121718233

例如子树

可表达为

i = i + 1

整个抽象语法树的三地址表达为

《编译原理（第2版）》原文：这个中间代码的名字源于它的指令形式：x = y OP z ，其中OP是一个二目运算符，y和z是运算分量的地址，x是运算结果的存放地址。三地址指令最多只执行一个运算，通常是计算、比较或者分支跳转运算。

用途

编译器将源码解释成抽象语法树，抽象语法树很容易转为三地址表达式，而三地址表达式几乎跟汇编指令一样了。

例如：

i = i + 1

可变为x64汇编

add $1, %rax

这样就可以从源码变为目标代码让CPU执行。