什么是DAG（只讲概念不讲算法）

发布时间：2023年12月21日

什么是DAG（只讲概念不讲算法）

前提知识

中间表达

编译器的目的是将源程序编程目标代码（汇编）放入计算机执行。
在这里插入图片描述
这里有一个问题，世界上有很多不同架构的CPU，比如x86，ARM等。不同架构的CPU有不同的汇编。于是上图带来的问题是直接从源程序翻译成不同架构CPU的目标代码工作量太大且容易出错。正确的做法是在源程序和目标代码中间加一层中间表示作为桥梁，将其衔接起来。

在这里插入图片描述

名词解释

DAG: Directed Acycle Graph

中文：无环有向图

通过名字就知道，该图不是闭合的，但是内部有方向。

重点：

  • DAG叶子节点对应原子运算分量。
原子运算：每次只进行一次操作

  • 在DAG中一个结点N表示一个公共子表达式，但N可能有多个父节点。比如

    a*(b-c)+(b-c)*d

    b-c作为一个表达式，其表达式树为

       _
  / \
 b   c

    但该子树有2个父节点

    *    *
 \  /
  -
 /  \
b    c

    整个表达式的变化过程为:

    1. 形成a*(b-c)和(b-c)*d的子树组合
       *   *
  / \ / \  
 a   -   d
    / \
   b   c
    1. 用+将二者合并
           +
      / \
     *    *
    / \  / \
   a   -    d
      / \
     b   c

举例说明

在这里插入图片描述

语法制导和编码

语法制导算法将源文件表达式转成DAG。具体实现参见《编译原理（第二版）》6.1，关于如何对DAG的节点进行编码参见6.2.

用途

用于产生三地址代码，三地址代码很容易转成对应平台的汇编指令

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