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

在线作业答案

编译原理基础辅导资料十七主    题：第七章中间代码生成
学习时间：2021年1月18日--1月24日“不忘初心、牢记使命”主题理论学习：
忠诚是共产党人必须具备的优秀品格。“忠诚印寸心，浩然充两间”的坚毅，“砍头不要紧，只要主义真”的无畏，腹中满是草根而宁死不屈的气节，食指钉入竹签而永不叛党的坚贞，无数先烈用鲜血诠释了对党的忠诚。对党忠诚必须是纯粹的、无条件的，是政治标准、更是实践标准，鲜明体现在坚决贯彻党中央决策部署上。
摘选自《在第十九届中央纪律检查委员会第二次全体会议上的讲话》内    容：
我们这周主要学习第七章中间代码生成赋值语句、布尔表达式和控制语句的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
1.理解中间代码生成概念
2.理解各种语句如何翻译
重点和难点：
重点：
数组元素的地址计算
数组元素地址计算的翻译方案
类型转换
临时名字
布尔表达式
控制流语句
布尔表达式的控制流翻译
开关语句的翻译
过程调用的翻译
难点：
布尔表达式的控制流翻译符号表中的名字


产生一个新的临时变量的名字，把该名字存入符号表，并返回该条目的地址，输出三地址码，相当于printf。数组元素的地址计算
一维数组A的第i 个元素的地址计算
                base + ( i ( low ) ( w
变换成
                i ( w + (base ( low ( w)
减少了运行时的计算
二维数组
        A: array[1..2, 1..3] of T
列为主
   A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3]
行为主
        A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3]
A[1,1]  A[1,2]   A[1,3]
A[2,1]  A[2,2]   A[2,3]

多维数组下标变量A[i1, i2, ..., ik ]的地址表达式
( (… ( (i1 ( n2 + i2 ) ( n3 + i3 ) … ) ( nk + ik) ( w
+ base ( ( ( … ( (low1 ( n2 + low2) ( n3 + low3) … ) ( nk + lowk ) ( w三、赋值语句类型转换
1例 x = y + i ( j
        中间（x和y的类型是real，i和j的类型是integer）
代码
        t1 = i int( j
        t2 = inttoreal t1
        t3 = y real+ t2
        x = t3
E ( E1 + E2
E.place = newTemp();
if E1.type == integer && E2.type == integer then begin
        emit(E.place,‘=’,E1.place,‘int+’,E2.place);
        E.type = integer
end
else if E1.type == integer && E2.type == real then begin
        u = newTemp();
        emit (u, ‘=’, ‘inttoreal’, E1.place);
        emit (E.place, ‘=’, u, ‘real+’, E2.place);
        E.type = real
end
四、赋值语句临时名字的重新使用
大量临时变量的使用对优化有利
大量临时变量会增加符号表管理的负担
也会增加运行时临时数据占的空间
E ( E1 + E2的动作产生的代码的一般形式为
        计算E1到t1
        计算E2到t2
        t3 := t1 + t2                        ( (  ) ) ( ( ( ) ( ) ) ( ) )
临时变量的生存期像配对括号那样嵌套或并列


五、布尔表达式
布尔表达式有两个基本目的
计算逻辑值
在控制流语句中用作条件表达式
本节所用的布尔表达式文法
B ( B or B | B and B | not B | ( B )
                    | E relop E | true | false
布尔表达式的完全计算
值的表示数值化
其计算类似于算术表达式的计算
布尔表达式的“短路”计算
B1 or B2      定义成  if B1 then true else B2
B1 and B2  定义成    if B1 then B2 else false
用控制流来实现计算，即用程序中的位置来表示值，因为布尔表达式通常用来决定控制流走向
两种不同计算方式会导致程序的结果不一样六、控制流语句的翻译
S ( if B then S1
        | if B then S1 else S2
        | while B do S1
        | S1; S2 、


布尔表达式的控制流翻译
如果B 是a < b 的形式，
那么代码是：
if a < b goto B.true
goto B.false
   例  表达式
        a < b or c < d and e < f
的代码是：
                if a < b goto Ltrue
                goto L1
L1:        if c < d goto L2
                goto Lfalse
L2:        if e < f goto Ltrue
                goto Lfalse
开关语句的翻译
switch E
begin
case V1: S1
case V2: S2
. . .
case Vn - 1: Sn – 1
default: Sn
end
九、过程调用的翻译
S ( call id (Elist)
Elist ( Elist, E
Elist ( E本章练习题：
（一）选择题
1、中间代码生成时所依据的为___。
词法规则
语法规则
语义规则
等价变换规则
答案：C
（二）问答题
1、翻译算数表达式-a*(c+d)+(a+b)为三地址语句序列。
答案：
t1=-a
t2=c+d
t3=t1*t2
t4=a+b
t5=t3+t4拓展资料海量数据随机抽样问题（蓄水池问题）
随机抽样问题表示如下：
要求从N个元素中随机的抽取k个元素，其中N无法确定。
这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保持随机性，于是有了这个问题。所以搜索网站有时候会问这样的问题。
这里的核心问题就是“随机”，怎么才能是随机的抽取元素呢？我们设想，买彩票的时候，由于所有彩票的中奖概率都是一样的，所以我们才是“随机的”买彩票。那么要使抽取数据也随机，必须使每一个数据被抽样出来的概率都一样。
【解决】
解决方案就是蓄水库抽样（reservoid sampling）。主要思想就是保持一个集合（这个集合中的每个数字出现），作为蓄水池，依次遍历所有数据的时候以一定概率替换这个蓄水池中的数字。
其伪代码如下：
Init : a reservoir with the size： k
        for    i= k+1 to N
            M=random(1, i);
            if( M < k)
                 SWAP the Mth value and ith value
       end for
?解释一下：程序的开始就是把前k个元素都放到水库中，然后对之后的第i个元素，以k/i的概率替换掉这个水库中的某一个元素。
下面来具体证明一下：每个水库中的元素出现概率都是相等的。
【证明】
（1）初始情况。出现在水库中的k个元素的出现概率都是一致的，都是1。这个很显然。
（2）第一步。第一步就是指，处理第k+1个元素的情况。分两种情况：元素全部都没有被替换；其中某个元素被第k+1个元素替换掉。
我们先看情况2：第k+1个元素被选中的概率是k/(k+1)（根据公式k/i），所以这个新元素在水库中出现的概率就一定是k/(k+1)（不管它替换掉哪个元素，反正肯定它是以这个概率出现在水库中）。下面来看水库中剩余的元素出现的概率，也就是1-P(这个元素被替换掉的概率)。水库中任意一个元素被替换掉的概率是：(k/k+1)*(1/k)=1/(k+1)，意即首先要第k+1个元素被选中，然后自己在集合的k个元素中被选中。那它出现的概率就是1-1/(k+1)=k/(k+1)。可以看出来，旧元素和新元素出现的概率是相等的。
情况1：当元素全部都没有替换掉的时候，每个元素的出现概率肯定是一样的，这很显然。但具体是多少呢？就是1-P(第k+1个元素被选中)=1-k/(k+1)=1/(k+1)。
（3）归纳法：重复上面的过程，只要证明第i步到第i+1步，所有元素出现的概率是相等的即可。看到一个问题：怎样随机从N个元素中选择一个元素，你依次遍历每个元素，但不知道N多大。
将N个元素用[1、2、...、N]编号。如果在知道N的大小，我们可以从[1、N]中随机选择一个数作为选择对象。
但是现在不知道N的大小，要使每一个元素被取的概率相等（随机）。这个概念叫蓄水池抽样。Solution：以1/i的概率取第i个元素。
证明：数学归纳法。当i=1时：第1个元素以1/1=1的概率被取，符合条件。
设i=k时符合条件，即前k个元素都以1/k的概率被取。
则i=k+1时：对于第k+1个元素，被取概率为1/（k+1），符合条件。
对于前k个元素，每个元素被取的概率=被取并且没被第k+1个元素替换的概率=（1/k）*(1?1/（k+1）)=1/（k+1）符合条件。
综上所述：得证。将问题扩展：给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
这次与上面唯一的不同是：总共需要取k个元素。仿照即可得出解决方案。
Solution：以1的概率取前k个元素，从i=k+1开始，以k/i的概率取第i个元素，若被取，以均等的概率替换先前被取的k个元素。
证明：同样数学归纳法。当i=k+1时：第k+1个元素以k/k+1概率被取，前k个元素被取的概率=1 - 被第k+1个元素替换的概率=1?k/(k+1)*1/k=k/(k+1) 符合条件。
设i=p时符合条件，即前p个元素都以k/p的概率被取。
则i=p+1时：对第p+1个元素，被取概率为k/(p+1)符合条件。
对于前p个元素，每个元素被取的概率=被取并且没有被第p+1个元素替换的概率=
k/p*((1?k/(p+1))+k/(p+1)*(1?1/k))=k/p+1同样符合条件。
综上所述：得证。
---------------------
作者：hackbuteer1
来源：CSDN
原文：https://blog.csdn.net/Hackbuteer1/article/details/7971328
版权声明：本文为博主原创文章，转载请附上博文链接！本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986