精华内容
下载资源
问答
  • 编译原理dag
    千次阅读
    2019-11-26 16:21:42

    题目:

                                                                   DAG优化

                                                                        Time Limit: 1000 ms Memory Limit: 65536 KiB

    Problem Description

    大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。

    Input

    输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数

    之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * /

    例如:A=B+C

    Output

     通过构造DAG图,进行代码优化,只需要保留AB,删除无用变量,删除变量时,尽量保留最早出现的变量。

    PS:保证AB的值不同

    Sample Input

    3
    A=B+C
    B=B+B
    A=C+C

    Sample Output

    B=B+B
    A=C+C

     

     解题代码:

    #include <cstdio>
    #include <vector>
    using namespace std;
     
    int n;
    int cnt;
    struct node 
    {
        char id;
        int left = -1, right = -1;
        vector<char> var;
    }node[110];
    bool Find_var(int i, char c)
    {
        for (char j : node[i].var)
            if (j == c) return 1;
        return 0;
    }
    int Add_node(char c)
    {
        for (int i = cnt - 1; i >= 0; i--)
            if (node[i].id == c || Find_var(i, c))
                return i;
        node[cnt].id = c;
        return cnt++;
    }
    void Add_operator(char c, char op, int L, int R)
    {
        for (int i = cnt - 1; i >= 0; i--)
        {
            if (node[i].left == L && node[i].right == R && node[i].id == op)
            {
                node[i].var.push_back(c);
                return;
            }
        }
        node[cnt].id = op;
        node[cnt].var.push_back(c);
        node[cnt].left = L;
        node[cnt].right = R;
        cnt++;
    }
    char s[10];
    char ans[110][10];
    bool flag[110];
    void DFS(int x)
    {
        if (node[x].left != -1)
        {
            flag[x] = 1;
            DFS(node[x].left);
            DFS(node[x].right);
        }
    }
    int main()
    {
        cnt = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%s", s);
            int L = Add_node(s[2]);
            int R = Add_node(s[4]);
            Add_operator(s[0], s[3], L, R);
        }
        for (int i = 0; i < cnt; i++)
        {
            if (node[i].left != -1)
            {
                ans[i][0] = node[i].var[0];
                ans[i][1] = '=';
                struct node  LL = node[node[i].left], RR = node[node[i].right];
                ans[i][2] = LL.var.size() > 0 ? LL.var[0]:LL.id;
                ans[i][3] = node[i].id;
                ans[i][4] = RR.var.size() > 0 ? RR.var[0] : RR.id;

            }
        }
        for (int i = cnt - 1; i >= 0; i--)
        {
            if (ans[i][0] == 'A')
            {
                DFS(i);
                break;
            }
        }
        for (int i = cnt - 1; i >= 0; i--)
        {
            if (ans[i][0] == 'B')
            {
                DFS(i);
                break;
            }
        }
        for (int i = 0; i < cnt; i++)
            if (flag[i]) puts(ans[i]);
        return 0;
    }

     

    更多相关内容
  • 编译原理DAG的优化

    2013-03-14 15:52:21
    编译原理的课设,DAG的优化,内有源代码
  • N - DAG优化【编译原理

    千次阅读 2020-12-07 19:32:31
    N - DAG优化 Description 大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。 Input 输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数 之后n行为表达式,每个变量为一个字母...

    N - DAG优化

    Description

    大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。

    Input

    输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数

    之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * /

    例如:A=B+C

    Output

     通过构造DAG图,进行代码优化,只需要保留AB,删除无用变量,删除变量时,尽量保留最早出现的变量。

    PS:保证AB的值不同

    Sample

    Input 

    3
    A=B+C
    B=B+B
    A=C+C

    Output 

    B=B+B
    A=C+C
    #include <bits/stdc++.h>
    
    using namespace std;
    int cnt,n; // cnt 为当前结点的个数,n为输入的表达式个数
    char s[10]; //临时输入
    char ans[101][101]; // 最后输出的优化后的表达式
    bool flas[101]; //用于记录那些表达式最后可以输出
    
    struct st{
        char id; // 结点的值
        int left = -1; // left 和 right 都是存放的标号,即左/右子树所在的标号
        int right = -1;
        vector<char>var;
    }node[101];
    
    // i 是第i个结点,c是当前查找的符号
    bool find_var(int i, char c)
    {
        // 一个结点可能有多个标记
        int len = node[i].var.size();
        for(int k = 0; k < len; k ++)
        {
            if(node[i].var[k] == c)
            {
                // 找到
                return true;
            }
        }
        return false;
    }
    // 建立结点
    // add_node 返回的值时该结点的标号,也就是位置
    int add_node(char c)
    {
        // 遍历当前已经建立的结点
        for(int i = cnt - 1; i >= 0; i --)
        {
            // 如果该结点建立过,或者和其他结点在同一个上面
            // 这个时候已经变量就会得到合并
            if(node[i].id == c || find_var(i,c))
            {
                return i;
            }
        }
        // 没有找到该结点,则需要新建立
        node[cnt].id = c;
        return cnt ++;
    }
    
    //添加表达式
    void add_operator(char c, char op, int l, int r)
    {
        for(int i = cnt - 1; i >= 0; i --)
        {
            //如果该表达式已经存在,将该表达式左边的值放到结点的var中即可。
            if(op == node[i].id && node[i].left == l && node[i].right == r)
            {
                node[i].var.push_back(c);
                return ;
            }
        }
        // 如果没有,则需要把整个表达式都加进去
        // 形状是结点为操作符,左右结点为操作数,结果存到父节点的var中
        node[cnt].id = op;
        node[cnt].left = l;
        node[cnt].right = r;
        node[cnt].var.push_back(c);
        cnt ++;
    }
    // 保留变量标记
    void dfs(int i){
        // 如果保留的变量需要使用该表达式,则标记为1,保留下来
        if(node[i].left != -1)
        {
            flas[i] = 1;
            dfs(node[i].left);
            dfs(node[i].right);
        }
    }
    // ok函数
    char ok(int i)
    {
        int len = node[i].var.size();
        for(int k = 0; k < len; k++)
        {
            // 遍历i结点这个地方是不是有A||B,如果有的话,就说明这个值就没用了,用A||B就行
            if(node[i].var[k] == 'A' || node[i].var[k] == 'B')
            {
                return node[i].var[k];
            }
        }
        // 如果没有那就暂时保存这个值
        return node[i].var[0];
    }
    int main()
    {
        cnt = 0;
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            cin >> s;
            // 使用add_node建立结点
            int l = add_node(s[2]);
            int r = add_node(s[4]);
            // 将表达式构成树
            // 左右的l、r 使用的就是两个变量存在的标号
            add_operator(s[0],s[3],l,r);
        }
        for(int i = 0; i < cnt; i ++)
        {
            // 保留有左子树的,有左子树情况就是一个表达式的表示
            if(node[i].left != -1){
                // 搞定复写的另一种,比如c = d + d,a = d + d,b = e + c
                // 这时候确定存在ans[i][0]的是a,而不是c
                ans[i][0] = ok(i);
                ans[i][1] = '=';
                // node[i] 是由其左右结点运算得来的
                st ll = node[node[i].left];
                st rr = node[node[i].right];
                // 如果这个结点的左子树不是空的,那操作数就是ok(node[i].left)
                //就是判断c = d + d,a = d + d,b = e + c是否将c换成a
                // 如果是空的,那就是左子树本身的值,即ll.id
                ans[i][2] = ll.left != -1 ? ok(node[i].left) : ll.id;
                ans[i][3] = node[i].id;
                ans[i][4] = rr.left != -1 ? ok(node[i].right) : rr.id;
                ans[i][5] = '\0';
            }
        }
        // 保留所需要变量
        // 题目中要求保留A、B
        for(int i = cnt - 1; i >= 0; i --)
        {
            // 把A能用的表达式或者值进行标记
            if(ans[i][0] == 'A')
            {
                dfs(i);
                break;
            }
        }
         for(int i = cnt - 1; i >= 0; i --)
        {
            // 把B能用的表达式或者值进行标记
            if(ans[i][0] == 'B')
            {
                dfs(i);
                break;
            }
        }
        for(int i = 0; i < cnt; i ++)
        {
            if(flas[i])
            {
                puts(ans[i]);
            }
        }
        return 0;
    }
    

     

    展开全文
  • (8)(9) 画图 DAG优化 (1) T0 = 3.14 (2) T1 = 2 * T0 (3) T2 = R + r (4) A = T1 * T2 (5) B = A (6) T3 = 2 * T0 (7) T4 = R + r (8) T5 = T3 * T4 (9) T6 = R - r (10) B = T5 * T6 (1) T0 = 3.14 (2) T1 = 6.28 ...

    优化原因

    • 逐条语句进行的代码生成策略经常产生含有大量冗余指令和次最优解结构的目标代码。
    • 代码优化就是被优化程序进行一种语义保持的变换

     

    优化位置

    • 中间代码优化(与机器无关)
    • 目标代码优化(与机器有关)

     

    优化分类

    • 局部优化
    • 循环优化
    • 全局优化

     

    优化技术

    • 删除公共子表达式t1 = 4 * it2 = 4 * i的右侧是公共的,优化为t1 = 4 * it2 = t1
    • 复写传播t1 = f[t2]t3 = t2t4 = f[t3]优化为t1 = f[t2]t3 = t2t4 = f[t2]
    • 删除无用表达式:把上面的t3 = t2删掉(事实上,复写传播的目的正是使某些变量的复制变为无用)
    • 强度削弱t1 = 4 * i,i的值每次循环减1,优化为t1 = t1 - 4,将强度较高乘法运算优化为强度较低的加法运算
    • 删除归纳变量:若存在线性关系t1 = 4 * it2 = 4 * j,则i > j优化为t1 > t2

     
     

    流图构造

    ——— 根据中间代码构造流图需要三步:

    1. 入口语句程序的第一句 + 转移语句的目标句 + 转移语句的下一句
    2. 根据入口语句划分基本块
    3. 画图

    ——— 例题练手 >_<:

    (1) read x
    (2) read y
    (3) r = x mod y
    (4) if r = 0 goto (8)
    (5) x = y
    (6) y = r
    (7) goto (3)
    (8) write y
    (9) end
    
    1. 找入口语句:(1) (3) (5) (8)
    2. 划分基本块:(1)(2); (3)(4); (5)(6)(7); (8)(9)
    3. 画图
      在这里插入图片描述

     
     
     

    DAG优化

    (1) T0 = 3.14
    (2) T1 = 2 * T0
    (3) T2 = R + r
    (4) A = T1 * T2
    (5) B = A
    (6) T3 = 2 * T0
    (7) T4 = R + r
    (8) T5 = T3 * T4
    (9) T6 = R - r
    (10) B = T5 * T6
    

    在这里插入图片描述

    (1) T0 = 3.14
    (2) T1 = 6.28
    (3) T3 = 6.28
    (4) T2 = R + r
    (5) T4 = T2
    (6) A = 6.28 * T2
    (7) T5 = A
    (8) T6 = R - r
    (9) B = A * T6
    

     
     
     
     

     
     
     
     

     
     
     
     

    E N D END END

    展开全文
  • 如下图:

    如下图:在这里插入图片描述
    第一次重构,T1 =6.28并没有因为复写传播而去掉,
    下一次优化,就会被去掉,T1直接用6.28表示
    T2 =R+r
    A = 6.28 * T2
    T6 =R - r
    B = A * T6

    Ps:完成复写传播的消除,就会产生无用代码,伴随着删除无用代码的操作

    展开全文
  • 大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。 Input 输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - *...
  • 大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。 Input 输入第一行为一个整数n(n &lt; 100),表示该组输入的表达式的个数 之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + ...
  • N - DAG优化(编译原理练习) Input 输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数 之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * / 例如:A=B+C Output 通过构造...
  • 编译原理》画 DAG 图与求优化后的 4 元式代码- 例题解析
  • 编译原理》画 DAG 图与求优化后的 4 元式代码 - 例题解析DAG 图 (Directed Acyylic Graph) 无环路有向图(一)基本块基本块是指程序中一顺序执行的语句序列, 其中只有一个入口语句 (第一个语句) 和一个出口语句(最后...
  • 编译原理笔记及例题

    千次阅读 2022-04-02 22:45:39
    编译原理笔记及例题
  • 有问题联系我 整合、完善已完成的编译程序各阶段相关内容,并能可视化演示。 (2)深入研究编译相关算法,从下列...利用DAG进行基本块的优化 (3)完成编译后端相关程序。可以选择实现解释器,也可以选择生成汇编代码。
  • 输入任意给定的基本块,构造与之等价的DAG图,并以图形方式输出。 基本要求 输入的形式和输入值的范围 以四元式的形式输入任意给定的基本块,即一个字符串,最左边和右边是两个括号(),四个符号之间用三个逗号...
  • 并行编译的两大工作是程序代码划分和调度。对于调度问题,目前已有大量的解决方案,但是针对代码划分提取并行性的研究工作却非常少。该文提出了通过合并结点来划分DAG图的新的划分算法。实例分析证明,该算法是一种...
  • 编译原理习题及其答案,大家将就着看吧。各个地方不一样
  • 9.2 递归子程序的原理 89 9.3 单元测试 95 十、语法分析—自下而上分析_1 96 10.1 自下而上分析方法的基本思想 96 10.2 分析树与规范规约 99 10.3 符号栈的使用 103 10.4 单元测试 105 十一、语法分析—自下而上分析...
  • 编译原理 课程设计 DAG 报告+源码(C++版,C语言版两份)
  • 编译原理课程设计

    2018-04-15 17:28:59
    C语言实现的一个小型编译器,实现了LR、LL(1)语法分析和DAG四元式优化
  • 山东大学计算机编译原理期末考试试卷完整展示,并且涵盖大部分易出现的题目,包括所有可能出现的题目类型,答案可以与同学对,很有可能会考到
  • 整理的部分知识点
  • 编译原理期末复习知识点,一些类型题目给出了所涉及到的基本知识,然后对每类题目中的第一道例题进行了做法进行了讲解
  • 山东大学2017编译原理试题默写。题目精确,适合复习。仅供学习交流使用!
  • 编制程序,完成局部优化过程中的基本块划分。给定一段代码,判定程序的入口语句,划分基本块,删除无用产生式和冗余节点。
  • 3)典型控制语句的翻译方法 六、目标代码生成 1)基本块划分 2)寄存器选择——寄存器的待用信息与活跃信息的确定 七、中间代码的优化 (1) 基于DAG图的优化方法 一、概念 1)字母表、字符串、字符串和运算 字母表用 ...
  • 编译原理:代码优化

    千次阅读 2021-10-07 21:54:55
    局部优化技术大部分都是将基本块转为有向无环图(DAG). 每个语句s都对应一个内部结点N 结点N的标号是s中的运算符;同时还有一个定值变量表被关联到N ,表示s是在此基本块内最晚对表中变量进行定值的语句 N的子结点是...
  • 华东交通大学编译原理试题库,第一卷
  • 这是山东大学2017年编译原理的考试题,虽然是回忆版,但是每个题目都写的十分清楚,总的来说与往年相比题型没啥变化,也很简单
  • 编译时可以确定的常量表达式的值计算出来并且用值替换常量表达式,例如常量表达式2*3.14可以被替换为6.28. 还有一类优化利用基本块的 DAG实现。DAG的构造过程可以帮助我们应用如交换律和结合律这样的变换。例如,...
  • 文章目录目标代码生成一、目标代码生成概述1.1 任务1.2 输入1.3 输出二、抽象计算机模型三、代码生成3.1 代码生成原则3.2 待用信息和活跃信息...概念3.4 代码生成算法3.4.1 算法描述3.4.2 算法举例四、DAG的目标代码...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,680
精华内容 1,072
关键字:

编译原理dag

友情链接: VBcan.zip