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

openhelp100

编译原理基础辅导资料十八主    题：第八章代码生成
学习时间：2021年1月25日--1月31日“不忘初心、牢记使命”主题理论学习：
“一带一路”是促进共同发展、实现共同繁荣的合作共赢之路，是增进理解信任、加强全方位交流的和平友谊之路。中国政府倡议，秉持和平合作、开放包容、互学互鉴、互利共赢的理念，全方位推进务实合作，打造政治互信、经济融合、文化包容的利益共同体、命运共同体和责任共同体。
摘选自《推动共建丝绸之路经济带和21世纪海上丝绸之路的愿景与行动》内    容：
我们这周主要学习第八章代码生成的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
1理解代码生成器设计中的问题
2理解代价的概念
重点和难点：
重点：
代码生成器的设计中的问题
目标机器
基本块和流图
一个简单的代码生成器
难点：
简单代码生成器
一、基本概念和术语
1、基本块
连续的语句序列，控制流从它的开始进入，并从它的末尾离开
2、流图
     三地址语句序列的一种图形表示称为流图。
二、代码生成
1、代码生成

2、目标程序
绝对机器语言程序
目标程序将装入到内存的固定地方
粗略地说，相当于现在的可执行目标模块
可重定位目标模块
代码中含重定位信息，以适应重定位要求
绝对机器语言程序
可重定位目标模块
代码中含重定位信息，以适应重定位要求
允许程序模块分别编译
调用其它先前编译好的程序模块
汇编语言程序
免去编译器重复汇编器的工作
从教学角度，增加可读性
指令的选择
   目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素
   指令的速度和机器特点是另一些重要的因素
寄存器分配
运算对象处于寄存器和处于内存相比，指令要短一些，执行也快一些。
寄存器分配
选择驻留在寄存器中的一组变量
寄存器指派
挑选变量要驻留的具体寄存器
3、目标机器
目标机器的指令系统
选择可作为几种微机代表的寄存器机器
四个字节组成一个字，有n个通用寄存器R0,R1, …,Rn-1
二地址指令： op    源，目的
                MOV        {源传到目的}
                ADD        {源加到目的}
                SUB        {目的减去源}
4、基本块的优化
术语
三地址语句x = y + z引用y和z并且对x定值
一个名字的值在基本块的某一点以后还要引用的话，则说这个名字（变量）在该点是活跃的
基本块的等价
两个基本块的出口点有同样的活跃变量集合
对其中每个变量，定义其值的两个表达式相等
有很多等价变换可用于基本块
局部变换
全局变换
5、一个简单的代码生成器
基本考虑：
依次考虑基本块的每个语句，为其产生代码
假定三地址语句的每种算符都有对应的目标机器算符
假定计算结果留在寄存器中尽可能长的时间，除非：
该寄存器要用于其它计算，或者
到基本块结束
为此，在生成代码过程中需要记录一些信息。
6、寄存器描述和地址描述
在代码生成过程中，需要跟踪寄存器的内容和名字的地址
寄寄存器描述记住每个寄存器当前存的是什么在任何一点，每个寄存器保存若干个(包括零个)名字的值
名字（变量）的地址描述记住运行时每个名字的当前值可以在哪个场所找到
        这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合
名字的地址信息存于符号表，另建寄存器描述表
这两个描述在代码生成过程中是变化的
7、代码生成算法
对每个三地址语句x = y op z
调用函数getreg决定放y op z计算结果的场所L
查看y的地址描述，确定y值当前的一个场所y(。如果y的值还不在L中，产生指令MOV y(，L
产生指令op z(，L，其中z(是z的当前场所之一
如果y和/或z的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，那么修改寄存器描述
函数getreg 返回保存x = y op z的x值的场所L
如果名字y在R中，这个R不含其它名字的值,并且在执行x = y op z后y不再有下次引用，那么返回这个R作为L
否则，如果有的话，返回一个空闲寄存器
否则，如果x在块中有下次引用，或者op是必须用寄存器的算符，那么找一个已被占用的寄存器R(可能产生MOV R，M指令，并修改 M的描述 )
否则，如果x在基本块中不再引用，或者找不到适当的被占用寄存器，选择x的内存单元作为L
8、条件语句
实现条件转移有两种方式
根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正
用条件码来表示计算的结果或装入寄存器的值是负、零还是正本章练习题：
（一）填空题
1、______________是连续的语句序列，控制流从它的开始进入，并从它的末尾离开。
答案：基本块
2、三地址语句序列的一种图形表示称为______________。
答案：流图
（二）简答题
1、简述代码生成器设计上通常遇到的问题。
答案：
存储管理
指令选择
寄存器的分配和指派
计算次序选择等拓展资料
《编程之美》--字符串移位包含的问题
对于这道题的前两种思想书中已经给了比较详细的解答，下面只是对于前两种思想的小总结和对第三种思想的阐述。
第一种思想：
真正的移位，比较容易想，实现起来也没什么困难。
第二种思想：
移位过程中找到的规律，不论是左移还是右移，如果字符串S2包含在S1S1中，那就说明S2可以由S1移位得到。
这里补充一个C++ 标准库中String类的一个小用法，c_str()函数（并不推荐使用它来复制字符串，推荐使用strncpy和strcpy）：
这个函数返回一个指向字符串的const字符指针，是只读的，是一个临时变量与字符串的生存周期相同，不用考虑指针空间的释放。
第三种思想：
模拟的移位，并不需要真正移位，对字符串的下标取模运算的话即使下标超出了字符串长度经过取模实际比较的还是字符串中的字符。虽然用文字描述起来有些难懂，但是这个思想还是很好理解的！这种思想不需要像第二种思想那样分配新的空间。
代码如下：
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main()
{
    char src[]="password";
    char des[]="swordpas";
    int srcLen=strlen(src),desLen=strlen(des);
    int i=0,j=0;
    for(j=0;j<srcLen;j++){
        if(des[0]==src[j%srcLen]){
            //printf("%d\n",j);
            int k=j;
            for(i=1;i<desLen;i++){
                if(des[i]!=src[++k%srcLen]){
                    break;
                }
            }
            if(i==desLen)
                return 1;
        }
    }
    if(j==srcLen)
        return -1;
}---------------------
作者：桃厉害
来源：CSDN
原文：https://blog.csdn.net/u012421436/article/details/48834389
版权声明：本文为博主原创文章，转载请附上博文链接！本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986