1 / 10 第十章 代码优化
某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。
本章重点：局部优化 基本块的DAG表示
第一节 优化技术简介
为了说明问题，我们来看下面这个例子，源程序是：
P :=0
For I :=1 to 20 do
P :=P+A[I]*B[I];
经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。
1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4 :=T1。这种优化称为删除多余运算或称为删除公共子表达式。
2、代码外提 减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成
1编译原理仅用于教学
章符号表第10章符号表
◆符号表的作用
◆符号表的内容
◆符号表的组织
◆栈式符号表
学习目标
掌握
符号表的作用
符号表的内容
符号表的组织方法
栈式符号表10.1 概述
1．符号表的作用
符号表在整个编译期间的作用主要有两条：一是辅助
语义的(即上下文有关的)正确性检查；二是辅助代码生成。
2．符号表的生存期
符号表的建立可以开始于词法分析阶段(有些内容初始
建立)，也可以放到语法语义分析阶段，但符号表的使用，
有时会延续到目标代码的运行阶段(如运行时刻为了诊断的
需要，数组下标地址计算的需要等)。
10.2 符号表的内容
◆标识符的名字
◆与标识符有关的信息
不同的标识符在符号表中具有不同的信息：
ⅰ.数组——信息向量表(内情向量表)
ⅱ.记录——域紧接着相应的记录变量名字相继存放
ⅲ.过程或函数——参数的个数、类型、次序、是否允
许递归等①类型信息
包括种类(常量、变量、数组、标号、函数或过程等)与属
性(整型、实型、字符型、布尔型等)。10.2 符号表的内容
②地址码
ⅰ.简单变量/常量——在数据区中的绝对或相对地址
ⅱ.数组——在数据区中的首地址
ⅲ.过程或函数——过程或函数的分程序入口地址
③层次信息——标识符所属分程序(过程)的静态层次
④行号信息——标识符在源程序中的行号(说明行与引用行)
210.3 符号表的结构与组织
1．符号表的结构
线性符号表、树结构、散列表或桶等。
2．符号表的组织
符号表的条目一般由两部分组成，即名字栏与信息栏。
通常，条目用连续的存储字构成的记录来实现。为保持
符号表条目记录的统一，往往把与名字相关联的构造类型等
信息保存在符号表的某处(如数组的信息向量表等)，而把相
应的指针或序号放在记录内。3．符号表的操作
大量的查找、填表与删除等操作。10.3 符号表的结构与组织
10.4 栈式符号表——PASCAL符号表的设计
PASCAL按照最近嵌套作用域原则，一个名字的作用域
是那个包含了这个名字的说明的最小过程或函数。
第十章目标程序运行时的存储组织
课前索引
【课前考虑】
◇回忆一般的编译过程,能否寻到本章所讲内容在哪个过程？
◇什么缘故编译程序要考虑目标程序运行时存储区的治理和组织？
◇请回纳C语言和PASCAL语言的程序结构和数据类型的不同点
【学习目标】
全面了解目标程序运行时存储区的整体布局；每种存储区的组织方式和治理方法；并通过实例着重掌握，对准许过程嵌套定义的情况，栈式动态存储分配的组织方式和运行时进栈退栈的活动实现方法。
【学习指南】
在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。一般来讲，假设编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。我们那个地点所讲的运行时的存储区组织，是指目标程序运行时的数据空间的治理和组织。
【难重点】
◇目标程序运行时，存储区域的整体布局，以及各区域的作用。
◇各种不同类型的数据表示。
◇准许过程嵌套定义的情况，栈式动态分配的组织治理。
◇对过程的调用，进进和退出时，栈式动态分配的工作原理。
◇过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式。
◇过程参数传递的不同方式。
【知识结构】 从逻辑上瞧，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。一般来讲，假设编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象〔变量和常数〕所需的存储空间，作为保持中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输进/输出所需的缓冲区。目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址能够编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。
第一章 概述
1、 编译程序：是现代计算机的基本组成部分之一。是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。
2、 编译程序的五个阶段：（表格管理程序和错误处理程序涉及到编译程序的每个阶段）
（1）词法分析：词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词。
（2）语法分析：语法分析的任务根据语法规则（即语言的文法），分析并识别出各种语法单位（如表达式、说明、语句等）并进行语法检查，即检查各种语法单位在语法结构上的正确性。
（3）语义分析及中间代码生成：定义一种语言除要求定义语法外，还要求定义其语义，即对语言的各种语法单位赋予具体的意义。
（4）代码优化：代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效的，即省时间和空间的目标代码。
（5）目标代码生成：目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
3、 自动构造工具：LEX、YACC、GCC
第二章 文法和语言的基本知识
1、 字母表：是元素的非空有穷集合。
符号（字符）：字母表中的元素称为符号，或称为字符。
符号串（字）：符号的有穷序列称为符号串。
不包含任何符号的符号串，称为空符号串，用ε表示。
A的正闭包表示A上元素a,b构成的所有符号串的集合，集合A的闭包比正闭包多含一个空符号串ε。
2、 形式语言：序列的集合称为形式语言。每个形式语言都是某个字母按某种规则构成的所有符号串的集合，反之，任何一个字母表上符号串的集合均可定义为一个形式语言。
3、 规则：也称产生式，它是一个符号与另一个符号串的有序对（A,β），通常写作A→β或A：：=β。 一组规则规定了一个语言的语法结构。
4、 文法是规则的非空有穷集合，通常表示成四元组G=（VN,VT,P,S）。其中：
VN是规则中非终结符号的集合。
