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

2023-12-20 18:04:03

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
  1. 确定父节点。所有运算所涉及的符号
赋值(=), +, do-while逻辑中的循环体,do-while逻辑中的循环条件(<),索引[]
  1. 用叶子节点与父节点构成树形结构。

比如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是一个二目运算符,yz是运算分量的地址,x是运算结果的存放地址。三地址指令最多只执行一个运算,通常是计算、比较或者分支跳转运算。

用途

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

例如:

i = i + 1

可变为x64汇编

add $1, %rax

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

文章来源:https://blog.csdn.net/JimFire/article/details/135112010
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。