大工20秋《编译原理基础》辅导资料十六

沙鸥老师

编译原理基础辅导资料十六主    题：第七章中间代码生成
学习时间：2021年1月11日--1月17日“不忘初心、牢记使命”主题理论学习：
我们党要始终成为时代先锋、民族脊梁，始终成为马克思主义执政党，自身必须始终过硬。全党要更加自觉地坚定党性原则，勇于直面问题，敢于刮骨疗毒，消除一切损害党的先进性和纯洁性的因素，清除一切侵蚀党的健康肌体的病毒，不断增强党的政治领导力、思想引领力、群众组织力、社会号召力，确保我们党永葆旺盛生命力和强大战斗力。
摘选自《决胜全面建成小康社会，夺取新时代中国特色社会主义伟大胜利》内    容：
我们这周主要学习第七章中间代码生成中间语言、声明语句的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
1.理解中间代码生成概念
2.理解各种语句如何翻译
重点和难点：
重点：
后缀表示
图形表示
三地址代码
静态单赋值形式
声明语句
作用域信息的保存
记录的域名
赋值语句
难点：
赋值语句
一、基本概念和术语
1、语法树
是一种图形化的中间表示，描绘了源程序在语义上的层次结构。
2、有向无环图
是一种图形化的中间表示，和语法树相比，它以更紧凑的方式给出同样的信息。  
二、中间代码生成
1、中间代码生成
中间代码
介乎源语言与目标代码之间，比源语言简单，比目标代码复杂。
区分编译器的前端与后端，方便提出针对新机器的编译器。
可以设计针对中间代码的优化器。


使用中间代码的优点
与机器无关，便于移植。
便于进行独立于机器的代码优化。
介绍几种常用的中间表示
后缀表示
图形表示
三地址代码
用语法制导定义和翻译方案的方法将源程序翻译成中间形式
2、后缀表示
E ( E opE | uopE | (E ) | id | num
表达式E 的后缀表示可以如下归纳定义：
        表达式E                后缀式E (
        id                         id
        num                num
        E1 opE2                E1( E2( op
        uopE                E (uop
         (E)                        E (
表达式E 的后缀表示可以如下递归定义
如果E 是变量或常数，那么E 的后缀表示就是E 本身。
如果E 是形式为E1 opE2的表达式，那么E 的后缀表示是E1( E2( op，其中E1(和E2(分别是E1和E2的后缀表示。
如果E 是形式为(E1)的表达式，那么E1的后缀表示也是E 的后缀表示。
后缀表示不需要括号
图形表示
构造赋值语句语法树的语法制导定义
修改构造结点的函数可生成有向无环图
产  生  式
语  义  规  则

S ( id :=E
S.nptr := mknode(‘assign’, mkleaf (id, id.entry), E.nptr)

E ( E1 +E2
E.nptr := mknode( ‘+’, E1.nptr, E2.nptr)

E ( E1 (E2
E.nptr := mknode( ‘(’, E1.nptr, E2.nptr)

E ( (E1
E.nptr := mkunode( ‘uminus’, E1.nptr)

E ( (E1)
E.nptr := E1.nptr

E ( id
E.nptr := mkleaf (id, id.entry)


三地址代码
一般形式：x := y op z
表达式x + y ( z 翻译成的三地址语句序列是
t1 := y ( z
t2 := x + t1 静态单赋值形式
一种便于某些代码优化的中间表示
和三地址代码的主要区别
所有赋值指令都是对不同名字的变量的赋值
        三地址代码                        静态单赋值形式
        p = a +b                        p1 = a +b
        q = p ( c                        q1 = p1 ( c
        p = q ( d                        p2 = q1 ( d
        p = e ( p                        p3 = e ( p2
        q = p + q                         q2 = p3 + q1
6、声明语句
为局部名字建立符号表条目
为它分配存储单元
符号表中包含名字的类型和分配给它的存储单元的相对地址等信息7、作用域信息的保存
所讨论语言的文法
        P ( D; S
        D ( D; D | id: T |
                   proc id ; D; S
8、记录的域名
T ( record D end
记录类型单独建符号表，作为类型表达式的
主要部分，域的相对地址从0开始。
T ( record  L D  end
                  {T.type = record (top(tblptr ) );       
                  T.width = top(offset );
                  pop(tblptr ); pop(offset ) }
L ( ({t = mkTable(nil );
                  push(t, tblprt ); push(0, offset ) } 本章练习题：
（一）填空题
1、常见的中间代码包括_____________、语法树、后缀表示。
答案：三地址代码
2、中间表示设计的选择随_____________不同而不同。
答案：编译器
（二）问答题
1、为赋值语句x=y+w-(z+y)*w
（1）构造语法树。
（2）（并根据语法树写出三地址代码。
答案：（1）语法树：


（2）x=y+w-(z+y)*w三地址代码：
t1=y+w;
t2=z+y;
t3=t2*w;
t4=t1-t3;
x=t5;
拓展资料开关和灯泡的对应关系
在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分哪个开关控制哪一盏灯？
答案：
设三个开关是1、2、3。打开开关1等半个小时，关上开关1并打开开关2。
进房后去摸灯泡，热的是开关1对应的灯泡；亮的是开关2对应的灯泡；不亮不热的是开关3对应的灯泡。
?分析：
首先想到的就是通过打开不同的开关，进去后看灯是否亮来找出对应关系。可能打开的开关数量只有0，1，2，3共四种情况，没有一种情况能解决这个问题。所以必须找到其它的信号。鉴于灯泡亮一段时间后会发热，我们可以使用灯的热度作为一个信号。这样我们就有了热且亮，热不亮，亮不热，不热不亮四种状态，足以用来区分三只灯泡了。
??这个题可以理解成一个编码问题，灯泡的状态作为编码空间，进屋的次数作为编码位数。
?如果只使用灯泡是否亮来判断，题目就相当于用一位二进制数来表示三种状态，是不可能的事情。加入了灯泡是否热后，就相当于用一位四进制数来表示三种状态，足够了。
此题的一些可能变化：?
1、在房里有四盏灯，房外有四个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分哪个开关控制哪一盏灯？
2、在房里有n盏灯，房外有n个开关，在房外看不见房内，且进门后只能观察灯的亮度的情况下，你需要进门多少次才能区分哪个开关控制哪一盏灯？
3、在房里有n盏灯，房外有n个开关，每个开关有三种状态（开，关，半开（亮度为开的一半））在房外看不见房内，且进门后只能观察等的亮度的情况下，你需要进门多少次才能区分哪个开关控制哪一盏灯？?????????????
其他题目：
现有共2007只灯均亮，每个灯都只有一个开关，第一次按2倍数的灯开关，第二次按3倍数的灯，第三次按5倍数的灯，最后亮灯有几只？
思路：这个题目跟集合的并集是有关系的，首先这么思考，一个灯的开关操作偶数次跟没有操作是一样的效果，操作一次跟操作奇数次是一样的效果。则2的倍数与3的倍数交集中减去2、3、5的倍数共同交集剩下的集合操作了偶数次，跟没有操作是一样的，所以这些灯还是亮着的，而2、3、5倍数的并集的补集中的这些灯一直没有操作，状态是没有变化的，一直都是亮着的。。
所以：2007中2的倍数有1003个
2007中3的倍数有669个
2007中5的倍数有401个
2007中6的倍数有334个
2007中10的倍数有200个
2007中15的倍数有133个
2007中30的倍数有66个

2、3、5倍数的并集的补集为2007-（1003+669+401-334-200-133+66）=535 这些灯一直没有操作，状态是没有变化的，一直都是亮着的。。
2的倍数与3的倍数交集中减去2、3、5的倍数共同交集剩下的集合操作了偶数次，跟没有操作是一样的，这些灯共有268盏。。
同理另外134盏和67盏灯都是操作了偶数次，跟没有操作是一样的，也是亮着的。
所以：最后的亮灯共有535+268+134+67=1004
验证程序如下：
#include <stdio.h>
#include <stdlib.h>
void main()
{
        int a[2008],i,sum=0;
        for(i=1;i<2008;i++)
                a[i]=1;
        for(i=1;i<2008;i++)
        {
                if(i%2==0)
                        a[i]=1-a[i];
        }
        for(i=1;i<2008;i++)
        {
                if(i%3==0)
                        a[i]=1-a[i];
        }
        for(i=1;i<2008;i++)
        {
                if(i%5==0)
                        a[i]=1-a[i];
        }
        for(i=1;i<2008;i++)
        {
                if(a[i]==1)      //统计亮灯的个数
                        sum++;
        }
        printf("%d\n",sum);
        system("pause");
}
扩展题：
有1到100号的灯，一开始全部点亮。每盏灯都有独立的开关，且开关只有“开”和“关”两种状态。
第一次把所有1的倍数灯的开关按一次，第二次把所有2的倍数灯的开关按一下，一直到第一百次把所有100的倍数灯的开关按一下。
问，此时还有多少灯亮着？
因为开始时全部亮着，只有开关按偶数次的才会亮着。
实际上是问1,2,3,...,100这100个每个数的约数的个数。除了平方数，1，4，9,16,...,100(共10个外），其它所有数的约数的个数都是偶数个。因而最后亮灯的有100-10=90个。
（所有的平方数，其约数的个数都是奇数个，比如4^2=16, 当约数是4时，无法找到另外一个不同的约数与之配对)。
?
---------------------
作者：hackbuteer1
来源：CSDN
原文：https://blog.csdn.net/Hackbuteer1/article/details/6732456
版权声明：本文为博主原创文章，转载请附上博文链接！本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986