说在前面：
25 年的编译有很多创新题，和往年题完全不一样，因此强烈建议复习的时候不要只看往年题

0

1 记忆

#cloze

1. 语法树可以有 ，短语不能有 ，FIRSTVT 和 LASTVT 不能有

2. LR 分析过程每次归约的是句柄，算符优先分析过程每次归约的是最左素短语

3. 向输入文法插入动作符号后得到的文法是翻译文法，这个文法推导所产生的终结符号串称为活动序列，其由输入序列和动作序列组成。翻译文法中的符号，包括非终结符、终结符和动作符号，都是又穷集合中的符号，都没有值的概念

4. 与机器相关的代码优化技术，一旦目标机器产生改变，相应的优化方法也要做出调整。

5. 自顶向下语法分析的主要处理方法：递归下降子程序法和 LL 分析法

6. 自底向上语法分析的主要处理方法：算符优先分析法和 LR 分析法

7. 编译过程的七个逻辑组成部分、五个阶段

   1. 词法分析
   2. 语法分析
   3. 语义分析、中间代码生成
   4. 代码优化
   5. 生成目标程序
   6. 符号表管理
   7. 错误处理

8. 生成中间代码的目的是便于做代码优化和编译程序的移植

9. 编译过程本质上是一种翻译过程，将用高级程序语言书写的源程序加工为与其等价的目标程序

10. 对源程序（包括源程序的中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为遍，完成编译工作最少需要对源程序做 1 次扫描

11. 变量类型和名字是综合属性（从词法分析器/自底向上来是综合属性，自顶向下来是继承属性）

12. 常见程序设计语言的文法在乔姆斯基分类中属于上下文无关文法（2 型文法）

13. 活动记录中 Display 区存放的是外层模块活动记录的基地址

14. 文法 ，其中 代表文法中的终结符集合

15. 分程序索引表的作用：对源程序中个分程序的符号表进行统一管理与快速索引

16. 动态存储分配：

    1. 在目标程序运行阶段由目标程序实现对存储空间的组织管理，和为源程序中的变量分配存储
    2. 编译阶段要生成进行动态分配的目标指令。

17. 静态存储分配：

    1. 在编译阶段由编译程序实现对存储空间的组织管理,和为源程序中的变量分配存储
    2. 在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变

18. √语言和文法的关系是一对多

19. √规范句型的活前缀不一定唯一（求出句柄之后前面那堆都是活前缀）

20. √词法分析程序可以编成一个子程序（nextsym），由语法分析程序调用（如 parseStatement）

21. ×根据程序在运行时发现的错误，就能够找出错误在源程序中的确切位置

22. √对于源程序中的声明语句，编译程序通常不产生可执行代码

23. √LL(1)分析方法是非递归预测语法分析方法

1.0 代码优化

1. 局部优化：一个基本块内
   1. 代数变换
      • 常数合并：编译时完成常量表达式的计算
        a = 5+6+x -> a = 11+x
      • 整数类型与实型的转换
        设 x 为实型，x = 3+1 ，可变换成 x=4.0
      • 下标变量引用时，其地址计算的一部分工作可在编译时预先做好（运行时只需计算“可变部分”即可）。
      • 运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度(时、空开销)。
        如 x ** 2 -> x*x
   2. 复写传播：如 x := y 这样的赋值语句称为复写语句。由于 x 和 y 值相同，所以当满足一定条件时，在该赋值语句下面出现的 x 可用 y 来代替。
      如
      x = y
u = 2*x
v = x+1
   3. 常量传播：若上例中不是 x := y 而是 x := 3。则复写传播变成了常量传播。即
      x = 3
u = 2*x
v = x+1
   4. 删除冗余代码：冗余代码就是毫无实际意义的代码，又称死代码 (dead code)或无用代码(useless code)。
      如 x = x+0
FLAG = TRUE;
if FLAG THEN...
   5. 窥孔优化:关注在目标指令的一个较短的序列上.通过删除其中的冗余代码，或者用更高效简洁的新代码来替代其中的部分代码，达到提升目标代码质量的目的。并不局限在同一个基本块中。
2. 循环优化：循环语句内
   1. 循环不变式的代码外提
      不变表达式：不随循环控制变量改变而改变的表达式或子表达式。
      从而减少计算次数——也称为频度削弱
      
   2. 循环展开是一种将循环体内代码依序拓展成顺序执行指令的优化方法
      将构成循环体的代码(不包括控制循环的测试和转移部分)，重新产生许多次而不仅仅是一次。以空间换时间。
      
   3. 归纳变量的优化和条件判断的替换
      归纳变量: 在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为归纳变量(induction variable)。
      
      
   4. 把多重嵌套的循环变成单层循环。
   5. 把 n 个相同形式的循环合成一个循环等。
   6. in_line 展开
      可节省许多处理过程（函数）调用所花费的开销，省去了函数调用时参数压栈，保存返回地址等指令。
      仅仅限于简单的函数。
      
3. 全局优化：一个函数内，跨越多个基本块。
   1. 到达定义分析（全局数据流分析）
   2. 活跃变量分析
   3. 定义使用链、网
   4. 冲突图
4. 跨函数优化：整个程序
   跨函数别名分析，逃逸分析等

1.1 文法们

0 型

• 其中
• 短语结构文法。直接操作任意短语的整体结构
• 0 型语言：L0，可以用图灵机(Turing)接受。

1 型

• ：其中
• 上下文敏感或上下文有关。仅能在特定上下文下重写短语
• 1 型语言：L1，可以由一种线性界限自动机接受。

2 型！

• 其中
• 上下文无关文法。仅重写单个非终结符短语
• 注意：2 型文法与 BNF 表示相等价。
• 2 型语言：L2，可以由下推自动机接受。

3 型！

• 左线性：或其中
• 右线性：或其中
• 正则文法。仅支持线性的短语结构变换
• 3 型语言：L3，又称正则语言、正则集合，可以由有穷自动机接受。

0 型文法可以产生 L0、L1、L2、L3，
2 型文法只能产生 L2、L3，不能产生 L0、L1，语法分析、语义分析中用的比较多
3 型文法只能产生 L3，词法分析中用的比较多

1. LL(1)文法：一定无二义性
   构造出的 LL(1) 分析器不存在多重入口
   对于每个非终结符 A 的 任意 2 条规则 ，下列条件成立：
   2. 若 , 则
2. LR(0)文法：一定无二义性
   构造出的 LR(0) 分析器不存在多重入口
3. SLR(1)文法：一定无二义性
   构造出的 SLR(1) 分析器不存在多重入口
5. 算符文法：不一定无二义性
   无相邻的两个非终结符
6. 算符优先文法：不一定无二义性
   无相邻的两个非终结符且构造出的优先关系表无冲突

• 证明所有二义性文法都不是 LL(1)文法
  二义性文法对文法所定义的某些句子存在着 2 个最左推导，即在推导的某些步上存在多重定义，有 2 条规则可用，所以分析表是多重定义的

1.2 证明 xxx

1. 词法分析
   1. 证明是 DFA
      状态转移函数是单值函数
   2. 证明最小化的 DFA 是否等价：状态数不同一定不等价，状态数相同不一定等价。最小化 DFA 是唯一的
2. 语法分析
   1. 文法为了实现不采取超前扫描的前提下实现不带回溯的自顶向下分析，文法需要满足两个条件：
      1. 文法是非左递归的；
      2. 任一非终结符，其规则右部有多个选择时，各选择所推出的 FIRST 集两两不相交。
   2. 自顶向下分析不能处理左递归文法，但能处理其他递归文法
      • 左递归：因为在递归下降分析中，左递归文法会导致无限函数调用，会无限扩展同一个非终结符
      • 其他递归：其他递归在递归调用之前会先消耗输入符号，能保证递归的终止

1.3 错误分类

• 语法错误
  程序结构不符合语法（包括词法）规则的错误。
  A[x, y := 3,1416+T(T+H)
• 语义错误：课内将运行时错误也划分在语义错误范畴内
  程序不符合语义规则或超越具体计算机系统的限制。
  超越系统限制：（计算机系统和编译系统）
  1. 数据溢出错误，常数太大，计算结果溢出。（计算机系统限制）
  2. 符号表、静态存储分配数据区溢出。 （计算机系统限制）
  3. 动态存储分配数据区溢出。 （计算机系统限制）
  4. 标识符要先声明再引用。 （编译系统限制）
  5. 过程调用时，实参和形参个数必须相等，依次具有相同的类型。（编译系统限制）

1.4 句子、句型、语言、短语、简单短语、句柄、素短语、最左素短语

1. 句型：x 是句型，iff 且 。对于某个文法，该文法接受的一个句子必定是该文法的句型
2. 句子：x 是句子，iff 且
3. 语言：

• 短语
• 简单短语
• 句柄 = 最左简单短语
• 素短语：一定是短语，但不一定是简单短语
• 最左素短语

1.5 地址空间

• 代码区：存放目标代码
• 静态数据区
  • 全局变量
  • 静态变量
  • 部分常量，例如字符串
• 动态内存区 Heap
  • 程序员管理：C、C++
  • 自动管理（内存垃圾收集器）：Java、Ada
• 程序运行栈
  • 活动记录
  • 函数调用的上下文现场
    • 由调用方保存的一些临时寄存器
    • 被调用方保存的一些全局寄存器

2 杂题

2.1 RC 相关计算

2.2 逆波兰表示

• (：压栈

• )：弹出，直到弹出了(

• 栈顶符号>读入符号：弹出

• 否则压栈

• tips：优先级相同时，左结合符号（+-*/），栈内比栈外优先级高

2.3 BNF 范式表示

21-22 6 T一5

• BNF 的元符号： <, >, ::=, |
• 扩充的 BNF 的元符号： <, >, ::=, |, {, }, [, ], (, )

2.4 正则表达式

• 正则表达式中的运算符
  • | —— 或（选择） a|b 表示 a 或者 b 只会出现一个
  • • ——连接
  • * 或 { }——重复 a*表示 a 出现 0-n 次
  • （） ——括号 (ab)表示 ab 作为整体一起出现

3 NFA DFA

3.1 求：根据正则式求右线性/左线性文法

画不出来就先画 NFA 再转右线性文法
21-22 21 T4.1(2)

• 对于做线性文法来说：状态图终态为开始符号，如果开始状态为接受边，需改造（加个 S'）。最后写文法的时候要去掉开始状态。
  

---

正则式 => 正则文法
右线性算法：

1. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
2. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→xB 和 B→y，其中 B 为新的非终结符，。同样，对于 A→x*y => A→xA A→y ; A→x|y => A→x A→y
   左线性算法：
3. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
4. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→By 和 B→x，其中 B 为新的非终结符，。同样，对于 A→xy* => A→Ay A→x ; A→x|y => A→x A→y
   例子

   转成右线性（通常情况下）
   
   

3.2 求：根据正则式求 NFA

3.3 求：NFA 确定化——求 DFA

I I_a I_b I_c

3.4 求：DFA 最小化

经过分析，6、9 可以合并，所以去掉 6 保留 9，一共 10 个状态

3.5 求：根据 DFA 求语言

3.6 判断：最小化 DFA 是否等价

• 状态数不同一定不等价，状态数相同不一定等价
• 最小化 DFA 是唯一的

3.7 证明：是 DFA

状态转移函数是单值函数

4 LL(1)

4.1 求：FIRST FOLLOW

4.2 判断：此文法是否适合自顶向下的方法分析

适合

1. 非左递归
   // 2. 对于一个非终结符的多个产生式来说，FIRST 集不相交

4.3 判断：此文法是否是 LL(1) 文法

• 自顶向下分析 ≠ LL(1)
• LL(1)：分析表不含多重定义入口
  对于 G 的每个非终结符 A 的任意两条规则 A::=α|β,下列条件成立：
  1. Ф
  2. 若 , 则 Ф

4.4 求：LL(1) 分析表

对于文法中任意一条规则 ，设 a 为任一终结符或#

1. 若 ，则将 放入 。
   表示 A 在栈顶，输入符号是 a，应选择 去匹配
2. 若 或 ，而且 ，则 即 放入
   表示 A 已匹配输入串成功，其后继符号终结符 a 由 A 后面的语法成分去匹配
3. 把所有无定义的 都标上 error

4.5 求：句子 xxx 的识别过程

步骤 符号栈 读入符号 剩余符号串 使用规则

1. 把 # 和文法识别符号 E 推进栈，并读入输入串的第一个符号 a，重复下述过程直到正常结束或出错。
2. 根据栈顶符号 X 和当前输入符号 a，执行如下操作：
   1. 若 ，分析成功，停止。E 匹配输入串成功。
   2. 若 ，把 X 退出栈，再读入下一个符号。
   3. 若 ，转出错处理。
   4. 若 ，查分析表 。
      1. ，则将 弹出栈，将 逆序入栈。注： 在栈顶 （最左推导）
      2. 转出错处理
      3. 。a 为 X 的后继符号，则将 X 弹出栈（不读下一符号）继续分析。

5 SLR(1)

5.1 求：SLR(1) 分析表

2. 画图
3. 求 FIRST, FOLLOW
4. 画 SLR 分析表

5.2 判断：该文法是否是 SLR(1)文法

是。

• 无移进归约冲突、归约归约冲突
  或
• SLR(1) 分析表无冲突项

5.3 求：分析输入串 xxx

步骤 状态栈 符号 输入串 动作

5.4 求：有效项目集

1. 求 xx 活前缀的有效项目集：直接求
2. 求 xx 句型的有效项目集
   1. 求出所有活前缀
   2. 求出所有活前缀的有效项目集

6 算符文法/算符优先文法

6.1 判断：文法是否是算符文法

是，不存在 ，即没有相邻的非终结符

6.2 判断：文法是否是算符优先文法

是，任意两个终结符只有一种优先关系

6.3 求：每个非终结符的 FIRSTVT 和 LASTVT

6.4 求：算符优先关系矩阵

• 注意，有：
  ，所以

6.5 求：句子 xxx 的分析过程

• 当栈顶项（或次栈顶项）终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进。
• 步骤 符号栈 输入串 优先关系 动作
  

7 符号表&运行时栈

7.1 求：符号表

1. 符号的顺序是编译顺序

2. 类型不要写 array，要写 char 或者 integer

3. 种类是 func var，类型是 void int

4. 栈式符号表？有序符号表？

5. 栈式符号表

   1. 函数/过程过完之后只保留函数名
   2. 函数名在本层，从参数开始才到下一层

6. 符号表的层数 ≠ 运行栈的 abp

7. 为一个 int 分配地址时，如果分配的是 104，则它占的位置是 104-108

7.2 求：运行时栈

1. 栈的顺序是运行时的调用顺序

2. 最外层的不用写 abp ret addr prev abp:abp1

3. c 语言/java 语言：

   1. 有数组模板，写在数组前面
   2. 有嵌套：如下所示。 {} 内只有 prev abp

int main(){
	int a=0;
	{// 嵌套
		int b=0;
	}
}

2. Fortran 语言
   1. 有数组模版，写在数组前面
   2. 没有嵌套

8 代码优化

8.1 求：划分基本块、构建流图

8.2 求：DAG 图、启发式算法给出优化后的中间代码序列

1. 局部变量都保留（abcd）
2. 临时变量可以不保留（t1 t2 t3）

8.3 求：活跃变量分析

1. in 集合，初始化为空集。
2. 的后继基本块， ，
   进来的时候活跃的 = 先使用后定义的 + （出去时还需要活跃的 - 在块内定义的）
   例子

   

8.4 求：到达定义分析

1. 所有out 集合初始化为空集。
2. 的前驱基本块，
   B 末尾得到的数据流信息等于 B 本身产生的数据流信息，加上进入 B 时的数据流信息减去 B 注销的数据流信息后的数据流信息。
   例子

   1. 算 gen 和 kill

gen：本基本块内定义的变量（如果本基本块内重复定义了某一个变量，则只有最后一次算作 gen）
      如： d1:x=a, d2:y=b, d3:x=c，gen[B]={d2, d3}
kill：所有定义了本基本块中的 gen 中的变量的语句
   2. 算 in 和 out
      

8.5 求：冲突图

1. 冲突的定义
   in 集合内的变量互相冲突，out 集合内的变量互相冲突，没有其他冲突
2. 需要分析什么变量
   • 只有跨越基本块活跃的变量才能分配到全局寄存器
     跨越基本块：在 in 集合或 out 集合里的变量；但不包括只在 in 集合且其所在前序基本块只有 ，不包括只在 out 集合且其后继基本块只有
   • 全局变量不参与全局寄存器的分配（需要写出来这句话）

8.6 求：图着色

1 概论

p15 1 2 3 4 5

编译的起源

• 低级语言：机器语言（机器指令）、汇编语言
• 高级语言：面向用户的语言、面向问题的语言……

源程序 目标程序 翻译程序 汇编程序 编译程序 解释程序

• 源程序：汇编语言/高级语言编写的程序
• 目标程序：用目标语言表示的程序，目标语言可以是源语言和机器语言之间的中间语言，可以是机器语言，也可以是机器的汇编语言
• 翻译程序：把源程序转换为目标程序的程序（源程序经过翻译程序后变成了目标程序）
  
  • 源程序是汇编语言-翻译程序是汇编程序
  • 源程序是高级语言-翻译程序是编译程序
• 解释程序：对源程序进行解释执行的程序

编译型、解释型、编译解释型

• 编译执行 c/c++：源代码通过「编译器」一次性翻译成目标平台的机器语言（或汇编语言），生成可独立运行的二进制可执行文件；运行时直接执行该二进制文件，无需再依赖源代码或编译器。
  运行极快，跨平台性差
  
• 解释执行 python：无需提前编译，源代码通过「解释器」逐行 / 逐段解析为机器指令并立即执行，不生成独立的二进制文件；每次运行都需重新解析源代码。
  运行较慢，跨平台性好
  
• 编译-解释执行 java：先将源代码编译为「中间语言」（跨平台、比源码易执行）；运行时由「解释程序」解释执行字节码（或即时编译为机器码）。
  运行中等，跨平台性
  

编译过程：将高级语言程序翻译为等价的目标程序的过程

• 五个基本阶段
  • 词法分析：分析和识别单词（token）。源程序是由字符序列构成的，词法分析扫描源程序 (字符串)，根据语言的词法规则分析并识别单词，并以某种编码形式输出。
  • 语法分析：根据语法规则，分析并识别出各种语法成分，如表达式、各种说明、各种语句、过程、函数、程序等，并进行语法正确性检查，出错应输出出错信息
  • 语义分析、生成中间代码：对识别出的各种语法成分进行语义分析（变量在前面定义了吗、左右两边类型一不一样……），并产生相应的中间代码（翻译的实质：语义的等价性）
    • 常用中间代码：四元式（三地址指令）、三元式、逆波兰表示
  • 代码优化：为了得到高质量的目标程序
  • 生成目标程序：根据具体机器进行。做这部分工作时（要注意充分利用累加器），也可以进行优化处理。在翻译成目标程序的过程中，要切记保持语义的等价性。

编译程序的7 个逻辑部分

• 符号表管理——建表查表
  在整个编译过程中始终都要贯穿着建表（填表）和查表的工作。即要及时地把源程序中的信息和编译过程中所产生的信息（标志符、常量等）登记在表格中，而在随后的编译过程中同时又要不断地查找这些表格中的信息。
• 错误处理
  能诊察出错误，并向用户报告错误性质和位置，以便用户修改源程序。出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。

遍(Pass)

• 遍：对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。
• 遍与基本阶段
  • 上一遍的结果是下一遍的输入，最后一遍生成目标程序。
  • 可能扫一遍就能干完五个阶段的活，也可能要扫好几遍才能干完五个基本阶段的工作
• 一遍扫描编译程序：一遍扫描即可完成整个编译工作
  

• 一遍好还是多遍好？
  希望优化好：扫多遍好
  希望程序运行快：扫一遍好

前端 后端 前后处理器

• 前端：通常将与源程序有关的编译部分称为前端。
  • 词法分析、语法分析、语义分析、中间代码生成、代码优化 -------分析部分
  • 特点：与源语言有关
• 后端：与目标机有关的部分称为后端。
  • 目标程序生成（与目标机有关的优化）-------综合部分
  • 特点：与目标机器有关
    

• 编译程序的前后处理器（要让代码真正能跑起来，编译前后还有些要做的事）
  

2 文法和语言的概念及表示

• 符号串及其运算
  比较、长度、连接、乘积、幂、闭包
• 文法和语言
  文法定义、0 型、1 型、2 型、3 型、4 型
  句型、句子、语言
• 推导和规约
  最左规约 = 最右推导 = 规范推导
• 句型的短语、简单短语、句柄、素短语
  

P29 第 3 题；
P38 第 1、2、4、5、6、7 题；
P46-48 第 1、5、6、8、9 题；
P53 第 2 题

2.0 题型

1 !!!构造文法

• 构造文法的通用方法
  
  例题

  

  

2 证明 xxx 属于语言/推导 xxx

3 !!!列出短语、简单短语、句柄、素短语、最左素短语

4 画语法树

5 !!!证明是二义性文法

2.1 符号串及其运算

2.1.1 字母表和符号串

• 字母表：符号的非空有限集 例：
• 符号：字母表中的元素 例：
• 符号串：符号的有穷序列 例：

2.1.2 符号串和符号串集合的运算

• 符号串相等、长度、联接（一般 xy≠yx，而`εx＝xε```）
• 符号串集合的乘积运算：令 A、B 为符号串集合，定义
  A＝{a,b}, B={c,d}, AB={ac，ad，bc，bd}
{ε}A = A{ε} = A, {} A = A {} = {}
• 符号串集合的幂运算：有符号串集合 A，定义 , , , , ……, ＝
• 符号串集合的闭包运算：设 A 是符号串集合，定义 ＝ 称为集合 A 的正闭包。＝ 称为集合 A 的闭包。
  例：A={x,y}
  
  ＝

2.2 文法和语言

2.2.1 文法非形式定义

• 文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”），不涉及语义。

2.2.2 文法和语言的形式定义

• 形式语言：用文法和自动机所描述的没有语义的语言。
• 文法定义：四元组：G= ( Vn，Vt，P，Z )
• 语言定义：

1 文法的形式定义

1. 文法
   • ：非终结符集（所有产生式左边的符号）
   • ：终结符号集合（只出现在产生式右边的符号）
     称为文法的字汇表
   • ：产生式或规则的集合
     语法规则 ::= ->：通过建立一组规则，来描述句子的语法结构。
   • ：开始符号（识别符号）

2 推导的形式定义

1. 直接推导
   文法 ：＝，＝其中。
   若，则 。
   若＝＝，有，则。
   
2. 间接推导
   文法，
   则
   
3. 文法或则 。
4. 规范推导（最右推导）：有 , 则此推导为规范的，记为 。

3 语言的形式定义

1. 文法
   1. 句型：x 是句型，iff 且
   2. 句子：x 是句子，iff 且
   3. 语言：

形式语言理论可以证明以下两点

• 已知文法，求语言，通过推导，得到的东西唯一；
• 已知语言，构造文法，无形式化方法，更多是凭经验，得到的东西不唯一

2. 等价文法：G 和 G’是两个不同的文法，若 L(G) = L(G’) ，则 G 和 G’为等价文法。

4 递归文法

1. 递归规则：规则右部有与左部相同的符号
   • 对于 ， 一般递归
   • 若 ，即 ，左递归
   • 若 ，即 ，右递归
2. 递归文法：文法 G，存在 U ∈Vn
   • if ，则 G 为递归文法(自嵌入递归)；
   • if ，则 G 为左递归文法；
   • if ，则 G 为右递归文法。
3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析
4. 递归文法的优点：可用有穷条规则，定义无穷语言

2.2.3 文法和语言分类

0 型

• 其中
• 短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。
• 0 型语言：L0，这种语言可以用图灵机(Turing)接受。

1 型

• ：其中
• 上下文敏感或上下文有关。也即只有在 x、y 这样的上下文中才能把 U 改写为 u。
• 1 型语言：L1，这种语言可以由一种线性界限自动机接受。

2 型！

• 其中
• 上下文无关文法。也即把 U 改写为 u 时，不必考虑上下文。

• 翻译文法、属性翻译文法是上下文无关文法

• 1 型文法的规则中 x，y 均为 ε 时即为 2 型文法
• 注意：2 型文法与 BNF 表示相等价。
• 2 型语言：L2 这种语言可以由下推自动机接受。

3 型！

• 左线性：或其中
• 右线性：或其中
• 3 型文法称为正则文法。它是对 2 型文法进行进一步限制
• 3 型语言：L3，又称正则语言、正则集合，这种语言可以由有穷自动机接受。

根据上述讨论，
0 型文法可以产生 L0、L1、L2、L3，
2 型文法只能产生 L2、L3，不能产生 L0、L1
3 型文法只能产生 L3，词法分析中用的比较多

2.3 推导、规约、语法树、二义性

2.3.1 推导与语法树

1. 语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。
   • 叶结点：终结符或非终结符
2. 子树与短语：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。
3. 树与推导：推导<==>语法树
4. 规范规约（最左规约）：对句型中最左简单短语（句柄）进行的规约称为规范规约（最左规约）。
5. 规范句型：通过规范推导或规范规约所得到的句型称为规范句型。
   

2.3.2 文法的二义性

1 二义性文法

1. 某句子存在两棵不同的语法树，否则是无二义性文法。
   
   
2. 某句子存在两个不同的规范推导，否则是无二义性的。
3. 某规范句型的句柄不唯一，否则是无二义性的。
   对于句型 来说
   

2 如何让文法无二义性

若文法是二义性的，则在编译时就会产生不确定性。
遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。

1. 法 1：提出一些限制条件，称为无二义性的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的
   
   
2. 法 2：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。
   

3 有关文法的实用限制

1. 有害规则：若文法中有如 U::=U 的规则，则这就是有害规则，它会引起二义性。
   
2. 多余规则
   1. 在推导文法的所有句子中，始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。
   2. 在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。
      
3. 若某文法中无有害规则或多余规则，则称该文法是压缩过的。

   例
   
   

2.4 句型的短语、简单短语和句柄

8. 给定文法 ，为该文法的句型,
   • 若 , 且 , 则 u 是句型 w 相对于 U 的短语；
   • 若 , 且 , 则 u 是句型 w 相对于 U 的简单短语。
   • 任一句型的最左简单短语称为该句型的句柄。
   • 素短语：包含终结符且不包含素短语。
   • 最左素短语：最左边的素短语。
     其中 ，，

• 任何句型本身一定是相对于识别符号 Z 的短语。
• 短语、简单短语是相对于句型而言。一个句型可能有多个短语、简单短语，但句柄只能有一个。
  

2.5 文法的其它表示法

1. 扩充的 BNF 表示(Backus Normal Form)
   • BNF 的元符号： <, >, ::=, |
   • 扩充的 BNF 的元符号： <, >, ::=, |, {, }, [, ], (, )
     () 表示把符号组合起来
     {} 表示重复 0-n 次
     [] 表示出现 0-1 次
2. 语法图
   

3 词法分析

P73：1、2、3
P254: 第 1、2、4、5 题

3.0 题型

0 !!!左线性文法和右线性文法

正则式 => 正则文法
右线性算法：

1. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
2. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→xB 和 B→y，其中 B 为新的非终结符，。同样，对于 A→x*y => A→xA A→y ; A→x|y => A→x A→y
   左线性算法：
3. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
4. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→By 和 B→x，其中 B 为新的非终结符，。同样，对于 A→xy* => A→Ay A→x ; A→x|y => A→x A→y
   例子

   转成右线性（通常情况下）
   
   

状态图（有穷自动机）" dir="auto">1 正则文法 -> 状态图（有穷自动机）

正则文法" dir="auto">2 状态图（有穷自动机） -> 正则文法

有穷自动机（NFA DFA 最小化 DFA）" dir="auto">3 正则表达式 -> 有穷自动机（NFA DFA 最小化 DFA）

p254 T2,4,5

3.1 词法分析程序的功能及实现方案

• 词法分析程序的功能

  • 词法分析：根据词法规则识别及组合单词，进行词法检查。
  • 对数字常数完成数字字符串到数值的转换。
  • 删去空格字符和注解。

• 实现方案：2 种

  1. 词法分析单独作为一遍
     • 优点: 结构清晰、各遍功能单一
     • 缺点：效率低
       
  2. 词法分析程序作为单独的子程序：常用
     • 优点: 效率高
       

3.2 单词的种类及词法分析程序的输出形式

• 单词的种类
  1. 保留字：begin、end、for、do、if、else…
  2. 标识符：
  3. 常数：无符号数、布尔常数、字符串常数等
  4. 分界符：+、-、 * 、/、 == 、:=
• 词法分析程序的输出形式——单词的内部形式
• 2 种常用的单词内部形式：
  1. 按单词种类分类：begin 和 end 是一类
     
  2. 保留字和分界符采用一符一类 常用：begin 和 end 是两类
     

3.3 !!!正则文法和状态图

!!!根据文法画状态图

!!!利用状态图判断是否是句子

利用状态图可按如下步骤分析和识别字符串 x：

1. 置初始状态为当前状态，从 x 的最左字符开始，重复步骤 2，直到 x 右端为止。
2. 扫描 x 的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；
   • 如果找不到标有该字符的弧，那么 x 不是句子，过程到此结束；
   • 如果扫描的是 x 的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态 Z，则 x 是句子。

• 是自底向上归约
• 怎样确定句柄：每一步归约的都是当前句型的句柄
  
  1 是句柄

3.4 词法分析程序的设计与实现——状态图

词法规则 => 状态图 => 词法分析程序

3.4.1 文法及其状态图

• 语言的单词符号

  • 标识符
  • 保留字（标识符的子集）
  • 无符号整数
  • 单分界符 +、*、：、，（、）
  • 双分界符 :=

• 文法：下面例子是正则文法

  1. <标识符>::= 字母 | <标识符>字母 | <标识符>数字
  2. <无符号整数>::=数字 | <无符号整数>数字
  3. <单字符分界符>::= : | + | * | , | ( | )
  4. <双字符分界符>::= <冒号>=
  5. <冒号>::= :
  6. <注释头符号>::= <斜竖>*
  7. <斜竖>::= /

• 状态图
  
  

3.4.2 状态图的实现——构造词法分析程序

1. 单词及内部表示：保留字和分界符采用一符一类

2. 词法分析程序需要引用的公共（全局）变量和过程（没有返回值的函数）

3. 词法分析程序算法

3.5 !!!词法分析程序的自动生成——有穷自动机

3.5.1 正则表达式和正则集合的递归定义

正则集合：正则表达式所表示的语言称为正则集合

有字母表 ，定义在 上的正则表达式和正则集合递归定义如下:

1. 和 (空串)都是 上的正则表达式，它们所表示的正则集合分别为: 和 ;
2. 任何 , 是 上的正则表达式，它所表示的正则集合为: ;
3. 假定 和 都是 上的正则表达式，它们所表示的正则集合分别记为 和 ，那么 ， (连接)和 (重复) 也都是 上的正则表达式，它们所表示的正则集合分别为 、 和 ;
4. 任何 上的正则表达式和正则集合均由 1、2 和 3 产生

• 正则表达式中的运算符：
  | —— 或（选择） • ——连接 * 或 { }——重复 （） ——括号
• 运算符的优先级：
  先* , 后 • , 最后 |， • 在正则表达式中可以省略。
• 正则表达式相等 这两个正则表达式表示的语言相等。

正则表达式的性质

正则表达式与 3 型文法等价

3.5.2 确定有穷自动机机（DFA）

• 一个确定的有穷自动机（DFA） 是一个五元式: ，
  其中:
  1. — 有穷状态集
  2. — 输入字母表
  3. — 映射函数(也称状态转换函数)
     
     （s'叫做 s 的后继状态）
  4. — 初始状态
  5. — 终止状态集
• 所谓确定的状态机，其确定性表现在状态转移函数是单值函数
• 若存在一条从初始状态到某一终止状态的路径，且这条路径上所有弧的标记符连接成符号串 ,则称 为 DFA M(接受)识别
  

3.5.3 非确定的有穷自动机（NFA）

• 若 是一个多值函数，且输入可允许为 ，则有穷自动机是不确定的。即在某个状态下，对于某个输入字符存在多个后继状态。
• 正则表达式与 3 型文法等价：用 3 型文法所定义的语言都可以用正则表达式描述。
• 用正则表达式描述单词是为了指导生成词法分析程序。
• 有一个正则表达式则对应一个正则集合。
• 若 V 是正则集合，iff V = L ( M )，该 V 的正则表达式与 DFA M 等价。
• NFA 的形式定义为：（ 非单值函数，且有 弧，初始状态集合）
  一个非确定的有穷自动机 NFA 是一个五元式:
  NFA
  • — 有穷状态集
  • — 输入符号加上，即自动机的每个结点所射出的弧可以是中的一个字符或是。
  • — 初态集
  • — 终态集
  • — 转换函数
    ( ： 的幂集 — 的子集构成的集合）
    如：

( ： 的幂集 — 的子集构成的集合）定义回顾补充：
幂集（Power Set）：原集合中所有的子集（包括全集和空集）构成的集族。
例如： 集合
Ø

3.5.4 !!!NFA 的确定化

为什么需要 NFA 的确定化^fafed2

已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。也就是说，我们能够从：NFA M’构造成一个 DFA M，使得 L(M) = L(M’)
为了使得 NFA 确定化，我们首先给出两个定义：

定义 1：集合 I 的 ε-闭包

ε- closure(I)为：I 内的点+从 I 走 s 能到的点

定义 2 : 令 I 是 NFA M’的状态集的一个子集，a∈Σ

定义: 为 从 I 走 a 到的点本身，以及那些点走 ε 能到的点

根据定义 1、2，可以将上述的 M’确定化（即可构造出状态的转换矩阵）

1. 求初始状态的 ε 闭包
2. 求该闭包的 Ia, Ib, Ic，出现新状态就把它当做 I 来继续求 Ia, Ib, Ic

• 原初始状态 1 的 ε-closure 为 DFA M 的初态
• 包含原终止状态 4 的状态子集为 DFA M 的终态。
• 初态只有一个，终态（可接受状态）可以有很多个

3.5.5 !!!DFA 的极小化

• 对于任一个 DFA，存在一个唯一的状态最少的等价的 DFA
• 一个有穷自动机是化简的 <=> 它没有多余状态并且它的状态中没有两个是互相等价的。
• 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。

1 多余状态

多余状态：从该自动机的开始状态出发,任何输入串也不能到达那个状态。

2 等价状态

状态 s 和 t 的等价条件是：

1. 一致性条件：状态 s 和 t 必须同时为可接受状态（终态）或不接受状态（非终态）。
2. 蔓延性条件：对于所有输入符号，状态 s 和 t 必须转换到等价的状态里。

• 对于所有输入符号 c，Ic (s) = Ic (t)，即状态 s、t 对于 c 具有相同的后继，则称 s，t 是等价的。

• 若有穷自动机的状态 s 和 t 不等价，则称这两个状态是可区别的

• 判断等价状态——“分割法”：把一个 DFA（不含多余状态）的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的。

3.5.6 正则表达式与 DFA 的等价性

• 定理：在Σ上的一个字集 是正则集合，当且仅当存在一个 DFA M，使得 V = L( M )。
• 由于正则集合与正则表达式相对应，所以该定理表明了正则表达式与 DFA 的等价性。
  

3.5.7 转换

正则文法" dir="auto">1 有穷自动机 => 正则文法

1. 对转换函数 f (A, t) = B，可写成一个产生式:A→tB
2. 对可接受状态 Z，增加一个产生式：Z→ε
3. 有穷自动机的初态对应于文法的开始符号，有穷自动机的字母表为文法的终结符号集。
   例子

   

有穷自动机" dir="auto">2 正则文法 => 有穷自动机

（是右线性文法，从左往右画，推导；之前学的是左线性文法，从右往左画，归约）

1. 字母表与 G 的终结符号相同。
2. 为 G 中的每个非终结符生成 M 的一个状态，G 的开始符号 S 是开始状态 S。
3. 增加一个新状态 Z，作为 NFA 的终态。
4. 对 G 中的形如 A→tB，其中 t 为终结符或ε, A 和 B 为非终结符的产生式，构造 M 的一个转换函数 f (A, t) = B。
5. 对 G 中的形如 A→t 的产生式，构造 M 的一个转换函数 f (A, t) = Z。

3 !!!正则式 => 有穷自动机

算法：

正则式 R" dir="auto">4 有穷自动机 => 正则式 R

算法：

1. 在 M 上加两个结点 x, y。从 x 用ε弧连接到 M 的所有初态结点，从 M 的所有终态结点用ε弧连接到 y，形成与 M 等价的 M’。M’只有一个初态 x 和一个终态 y。
2. 逐步消去 M’中的所有结点，直至剩下 x 和 y 为止。在消除结点的过程中，逐步用正则式来标记箭弧。其消结规则如下：
   
   例子

   
   

正则式" dir="auto">5 正则文法 => 正则式

利用以下转换规则，直至只剩下一个开始符号定义的产生式，并且产生式的右部不含非终结符。

1. A→xB, B→y A=xy
2. A→xA | y A=x*y
3. A→x, A→y A=x|y
   例子

   

正则文法" dir="auto">6 正则式 => 正则文法

右线性算法：

1. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
2. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→xB 和 B→y，其中 B 为新的非终结符，。同样，对于 A→x*y => A→xA A→y ; A→x|y => A→x A→y
   左线性算法：
3. 对任何正则式 r，选择一个非终结符 S 作为识别符号，并产生产生式 S→r
4. 若 x, y 是正则式，对形为 A→xy 的产生式，重写为 A→By 和 B→x，其中 B 为新的非终结符，。同样，对于 A→xy* => A→Ay A→x ; A→x|y => A→x A→y
   例子

   转成右线性（通常情况下）
   
   

3.6 词法分析程序的自动生成器—LEX（LEXICAL）

3.6.1 LEX 源程序

一个 LEX 源程序主要由三个部分组成：

1. 规则定义式
2. 识别规则
3. 用户子程序
   各部分之间用%%隔开。

1 规则定义式

2 识别规则

3 例子

3.6.2 LEX 的实现

• LEX 的功能是根据 LEX 源程序构造一个词法分析程序，该词法分析器实质上是一个有穷自动机。
• LEX 生成的词法分析程序由两部分组成：状态转换矩阵(DFA)、控制执行程序
• ∴LEX 的功能是根据 LEX 源程序生成状态转换矩阵和控制程序

LEX 的处理过程

1. 扫描每条识别规则 Pi 构造一相应的非确定有穷自动机 Mi
2. 将各条规则的有穷自动机 Mi 合并成一个新的 NFA M
3. 确定化
4. 生成该 DFA 的状态转换矩阵和控制执行程序

LEX 二义性问题的两条原则

1. 最长匹配原则
   在识别单词过程中，有一字符串 根据最长匹配原则，应识别为这是一个符合 Pk 规则单词，而不是 Pj 和 Pi 规则的单词。
2. 最优匹配原则
   如有一字符串，有两条规则可以同时匹配时，那么用规则序列中位于前面的规则相匹配，所以排列在前面的规则优先权最高。
   例：字符串 BEGIN
   根据原则，应该识别为关键字 begin，所以在写 LEX 源程序时应注意规则的排列顺序。另要注意的是，优先匹配原则是在符合最长匹配的前提下执行的。

说明：

1. 以上是 LEX 的构造原理，虽然是原理性，但据此就不难将 LEX 构造出来。
2. 所构造出来的 LEX 是一个通用的工具，用它可以生成各种语言的词法分析程序，只需要根据不同的语言书写不同的 LEX 源文件就可以了。
3. LEX 不但能自动生成词法分析器，而且也可以产生多种模式识别器及文本编辑程序等。

4 语法分析

p84:1
p91:1-3 【注意：第 3 题第 3 个产生式应为 B::=aB|a，而不是 B::=aA|a】

p264 页 1, 2, 6（“试证明之”不需要证明）

P282 1，2 （规范句型活前缀）
P288 1 （有效项目集）
P297 1，2 （LR(0)文法）
P297 5，6，9（SLR(1)文法）

1. 自顶向下
   1. LL 分析法
      1. First集合、Follow集合、分析表的构造
      2. 执行程序的运行
      3. LL(1)文法的充要条件
2. 自底向上

0 题型

1 自顶向下：消除左递归

2 自顶向下：设计自顶向下的语法分析程序

3 自顶向下：LL(1)文法

• 构造 LL(1) 分析表需要先消除左递归!!!
• FOLLOW 不包含
• 注意 FOLLOW 的

4 自底向上：LR(0)

• 扩充文法，使分析表只有一个接受状态

5 自底向上：SLR(1)

• 扩充文法，使分析表只有一个接受状态
• 如果产生式中有T := ε，那么其对应的只有一个项目T := .，在构建分析器的时候需要在 中填写对应的 操作

6 自底向上：算符优先分析法

1. 优先关系的计算
   将产生式中的非终结符看作“括号” ，即具有更高优先级
   • 相邻非终结符、 “括号”两侧非终结符优先级相同
   • “括号”外左侧终结符“ ⋖ ”括号”内 FIRSTVT
   • “括号”内 LASTVT ⋗ “括号”外右侧终结符
   • 栈内和栈外的 # 优先级最低
2. 分析过程
   • 栈内跳过栈顶的 Vn（若存在），看第一个 Vt
   • 栈内 Vt 优先级小于或等于栈外 Vt 时移入
   • 栈内 Vt 优先级大于栈外 Vt 时，规约最左素短语

2 自顶向下分析法

• 基本思想：若则否则。从根节点开始，一步一步往下推，看能不能推出来
• 主要问题
  • 左递归问题
    文法里面如果有 U := Ua，会推不出来，需要改写文法去掉左递归
  • 回溯问题
    文法里面如果有 U := Ua|b，当沿着一条路发现推不下去之后需要回溯回来重新走另一条路，效率低
• 主要方法
  • 递归子程序法
  • LL 分析法

2.1 自顶向下分析的一般过程

给定符号串 S，若预测它是某一语法成分，那么可根据该语法成分的文法，设法为 S 构造一棵语法树。

• 若成功，则 S 最终被识别为某一语法成分。即 其中 为某语言成分的文法。
• 若不成功，则 。
  例

  

1. 分析过程是带有预测的。即要根据输入符号串中下一个单词，来预测之后的内容属于什么语法成分，然后用相应语法成分的文法建立语法树。
2. 分析过程是一种试探过程，是尽一切办法（选用不同规则）设法建立语法树的过程。由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。
3. 最左推导可以编出程序来实现，但在实际上价值不大，效率低，代价高。

2.2 自顶向下分析存在的问题及解决方法

2.2.1 左递归文法

有如下文法：令 U 是文法的任一非终结符，文法中有规则
∷ (直接) 或者 (间接)

方法 1-消除直接左递归：使用扩充的 BNF 表示来改写文法

1. 若∷
   则可改写为：∷
   其中再若：
   则 ∷
   • 总把 安置成最后的选择！
     若有规则：∷
     则可以改写为：∷
     注意：不应写成 ∷
2. 若有文法规则：∷
   其特点是：具有一个直接左递归的右部并位于最后，这表明该语法类 U 是由 x 或 y…或 z 打头，其后跟随零个或多个 v 组成
   可以改写为 ∷
   例子

   (1) ∷∷
   (2) ∷∷

方法 2-消除直接左递归：将左递归规则改为右递归规则

3. 若：∷
   则可改写为：∷
   ∷

方法 3-消除所有左递归

1. 把 G 的非终结符整理成某种顺序 ，使得
   
   
   

for i:=1 to n do
	begin
	for j :=1 to i-1 do
		把每个形如Ai∷= Aj r的规则替换成
		Ai ∷= (δ1 |δ2 |……|δk ) r
		其中Aj∷=δ1 |δ2 |……|δk是当前Aj 的全部规则
		消除Ai 规则中的直接左递归
	end

3. 化简由 2 得到的文法，即去掉那些多余的规则。

2.2.2 回溯问题

定义：设文法 G（不具左递归性），，
（ 表示能 能推出来的首个字符）
为避免回溯，对文法的要求是:

需要他们能推出来的首个字符不能相交（即不能 ）
也即所有非终结符的产生式 FIRST 集互不相交

方法 1：改写文法——反复提取左因子

对具有多个右部的规则反复提取左因子

方法 2：超前扫描

当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即向前侦察各输入符号串的第二个、第三个符号来确定要选择的目标
这种方法是通过向前多看几个符号来确定所选择的目标，从本质上来讲也有回溯的味道，因此比第一种方法费时，但是读的仅仅是向前侦察情况，不作任何语义处理工作。

2.2.3 总结

为了在不采取超前扫描的前提下实现不带回溯的自顶向下分析，文法需要满足两个条件：

1. 文法是非左递归的；
2. 对文法的任一非终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。
   在上述条件下，就可以根据文法构造有效的、不带回溯的自顶向下分析器。

2.3 递归子程序法（递归下降分析法）

具体做法：对语法的每一个非终结符都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。
虽然没有左递归，但是还可能有其他递归，因此叫“递归子程序法”

说明：

• 非终结符号的分析子程序功能，是用规则右部符号串去匹配输入串。
• 要注意子程序之间的接口。在程序编制时，进入某个非终结符的分析程序前，其所要分析的语法成分的第一个符号已读入 sym 中了。
• 递归子程序法对应的是最左推导过程！

2.4 用递归子程序法构造语法分析程序的例子

2.5 LL 分析法

• LL(1)文法
  • 无左递归、无二义
  • 若 则
• LL－自左向右扫描、自左向右地分析和匹配输入串。
  ∴分析过程表现为最左推导的性质。

2.5.1 LL 分析程序构造及分析过程

• 此过程有三部分组成
  • 分析表
  • 执行程序 (总控程序）
  • 符号栈 （分析栈）
    

1 分析表：二维矩阵 M

2 符号栈（四种情况）

1. 开始状态
   
2. 工作状态
   
3. 出错状态
   
4. 结束状态
   

3 执行程序

执行程序主要实现如下操作:

1. 把 # 和文法识别符号 E 推进栈，并读入输入串的第一个符号 a，重复下述过程直到正常结束或出错。
2. 根据栈顶符号 X 和当前输入符号 a，执行如下操作：
   1. 若 ，分析成功，停止。E 匹配输入串成功。
   2. 若 ，把 X 退出栈，再读入下一个符号。
   3. 若 ，转出错处理。
   4. 若 ，查分析表 。
      1. ，则将 弹出栈，将 逆序入栈。注： 在栈顶 （最左推导）
      2. 转出错处理
      3. 。a 为 X 的后继符号，则将 X 弹出栈（不读下一符号）继续分析。

2.5.2 !!!分析表的构造

设有文法 :

1. FIRST 集：若则，该集合称为 的头符号集合
2. FOLLOW 集：为识别符号；特殊地：若则

1 构造 FIRST 集的算法

设 ，求

1. 求出组成 的每一个符号 的 FIRST 集合
   1. 若 ，则
   2. 若 且 ，则
   3. 若 且 ，则按如下顺序计算
      • 若 ，则将 加入
      • 若 ，则将 加入
      • 若 ，则将 加入
      • ...
      • 若 ，则将 加入
      • 若 ，则将 加入
      • 注意：要顺序从上往下做，一旦不满足条件，过程就要中断进行
2. 得到 ，即可求出

2 构造 FOLLOW 集的算法

求 FOLLOW(B)
设 ，连续使用以下规则直至 集合不在扩大

1. 若 B 为识别符号，则把"#"加入 中
2. 若 ，则把 加入
3. 若 或 且 则把 加入
   注意：FOLLOW 集合中不能有 !!!

3 构造分析表的算法

对于文法中任意一条规则 ，设 a 为任一终结符或#

1. 若 ，则将 放入 。
   表示 A 在栈顶，输入符号是 a，应选择 去匹配
2. 若 或 ，而且 ，则 即 放入
   表示 A 已匹配输入串成功，其后继符号终结符 a 由 A 后面的语法成分去匹配
3. 把所有无定义的 都标上 error

2.5.3 !!!LL(1)文法

• 一个文法 G 的分析表 M 不含多重定义入口（即分析表中无两条以上规则），当且仅当它是一个 LL(1)文法。
• 文法 G 是 LL(1)文法的充分必要条件是：对于 G 的每个非终结符 A 的任意两条规则 A::=α|β,下列条件成立：
  1. Ф
  2. 若 , 则 Ф
• 如果 G 是左递归或二义的，那么 M 至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表 M。
  • 左递归： 左递归由 ，则有 ，故有
  • 二义文法：对文法所定义的某些句子存在着两（多）个最左推导，即在推导的某些步上存在多重定义，有两（多）条规则可用，所以分析表是多重定义的
• 有些文法可以从非 LL(1) 文法改写为 LL(1) 文法
• 但并不是所有的非 LL(1) 文法都能改写为 LL(1) 文法（如部分二义文法无法改写成 LL(1) 文法）

2.5.4 LL 分析的错误恢复

• 当符号栈顶的终结符和下一个输入符号不匹配，或栈顶是非终结符 A，输入符号 a，而 M[A, a]为空白（即 error）时，则分析发现错误。
• 错误恢复的基本思想是：跳过一些输入符号，直到期望的同步符号之一出现为止。
• 同步符号（可重新开始继续分析的输入符号）集合通常可按以下方法确定：
  1. FOLLOW(A) 的所有符号。如果我们跳读一些输入符号直到出现 FOLLOW(A)的符号，之后把 A 从栈中弹出，继续往下分析即可。
  2. 作为语句开头的关键字。（只用 FOLLOW(A) 作为非终结符 A 的同步符号集是不够的，容易造成跳读过多，如输入串中缺少语句结束符分号时）
  3. FIRST(A) 的所有符号。
  4. 推导ε的产生式可以作为缺省的情况（如果非终结符 A 可以产生空串）。这样做可以推迟某些错误检查，但不会漏过错误。
  5. 如果终结符在栈顶而不能匹配，则可弹出该终结符并发出一条信息后继续分析。这好比把所有其他符号均作为该符号的同步集合元素。

3 自底向上分析法

• 基本思想：若则否则。从输入符号串开始，通过反复查找当前句型的句柄（最左简单短语），并利用有关规则进行规约。若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子；否则有语法错误
• 主要问题
  • 句柄的识别问题
  • 若两个以上规则的右部都有相同的符号串且构成句柄，选哪个候选式
• 主要方法
  • 算符优先分析法
  • LR 分析法
• 分析过程(重复以下步骤)
  1. 找出当前句型的句柄 x （或句柄的变形）；
  2. 找出以 x 为右部的规则 X::= x ；
  3. 把 x 规约为 X，产生语法树的一枝。

3.1 自底向上分析的一般过程 （移进-归约分析）

要点：设置符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约

分析过程：

1. 把输入符号串按顺序一个一个地移进符号栈（一次移一个）；
2. 检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约——将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号；
3. 分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。

这一方法简单明了，不断地进行移进规约。关键是确定当前句型的句柄。
说明：

1. 例子的分析过程是一步步地规约当前句型的句柄。该句子的唯一语法树为：
   
   注意两点：
   ① 栈内符号串 + 未处理输入符号串 = 当前句型
   ② 句柄都在栈顶
2. 未真正解决句柄的识别问题
   上述分析过程中识别句柄的过程，主要看栈顶符号串是否形成规则的右部。
   这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。
   因为不能认为：对句型 xuy 而言，若有 U∷= u，即 U => u 就断定 u 是简单短语，u 就是句柄，而是要同时满足 。

3.2 LR 分析法

3.2.1 什么是 LR 分析

1. LR 分析：从左到右扫描(L)自底向上进行规约(R)(是规范规约，也即最右推导）
2. LR 分析器有三部分：状态栈、分析表、控制程序
   • 状态栈：放置分析器状态和文法符号。
   • 分析表：由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同的构造方法。
   • 控制程序：执行分析表所规定的动作，对栈进行操作。
     
3. 分析表的种类
   1. SLR 分析表（简单 LR 分析表）
      构造简单，最易实现，大多数上下文无关文法都可以构造出 SLR 分析表，所以具有较高的实用价值。使用 SLR 分析表进行语法分析的分析器叫SLR 分析器。
   2. LR 分析表（规范 LR 分析表）
      适用文法类最大，所有上下文无关文法都能构造出 LR 分析表，但其分析表体积太大，实用价值不大。
   3. LALR 分析表（超前 LR 分析表）
      这种表适用的文法类及其实现上的难易程度在 SLR 和 LR 之间，在实用上具有吸引力。使用 LALR 分析表进行语法分析的分析器叫 LALR 分析器。
      例：UNIX——YACC
      
4. 说明
   1. 三种分析表对应三类文法
   2. 一个 SLR 文法必定是 LALR 文法和 LR 文法
   3. 仅讨论 SLR 分析表的构造方法

3.2.2 LR 分析器

1 逻辑结构

(1) 状态栈

状态栈里有

1. 状态:
   • 其中 为初始状态， 为栈顶状态。
   • 栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息
2. 符号串：其中
   符号串是从开始状态（）到当前状态（）所识别出的规范句型的活前缀
   • 规范句型：通过规范归约得到的句型
   • 规范句型前缀：将输入串的剩余部分与当前已识别的符号串连结起来就构成了规范句型，如 为规范句型
     当前已识别的符号串是某个规范句型的前缀，且能与输入串剩余部分拼接成规范句型
   • 活前缀：若分析过程能保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀
     

(2) 分析表

1. 状态转移表 (GOTO 表)
   
   
   
2. 分析动作表（ACTION 表）
   
   分析动作：
   1. 移进 (shift)
      
      动作：将 a 推进栈，并设置新的栈顶状态为 。
      ，并将指针指向下一个输入符号。
   2. 规约 (reduce)
      (d 是文法规则编号，且假设有 (d) )
      动作：将符号串 (假定长度为 n ) 连同状态从栈内弹出，再把 推进栈，再压入新的栈顶状态为 ()
   3. 接受(accept)
      
   4. 出错 (error)
      

(3) 控制程序

1. 根据栈顶状态和现行输入符号，查分析动作表(ACTION 表)，执行由分析表所规定的操作；
2. 并根据GOTO 表设置新的栈顶状态（即实现状态转移）。

2 !!!LR 分析过程（不用改写去掉左递归）

合并 ACTION 和 GOTO 表，其中 r 的下标表示未来用第几条归约，s 的下标表示移近后要跳到哪个状态

由分析过程可以看到：

1. 每次规约总是规约当前句型的句柄，是规范规约！（而算符优先是规约最左素短语）
2. 分析的每一步栈内符号串均是规范句型的活前缀，且与输入串的剩余部分构成规范句型。

3 !!!构造 LR 分析表

构造 LR 分析表的方法是：

1. 根据文法构造识别规范句型活前缀的有穷自动机 DFA。
2. 由 DFA 构造 LR 分析表。

(1) 构造 DFA

什么是 DFA：DFA 是一个五元式

• ：有穷状态集
  在此具体情况下， 项目集规范族。
  项目集规范族：其元素是由项目所构成的集合。
• ：文法字汇表
• ：初始状态
• ：终态集合
  除 以外，其余全部是终态。
• GOTO：状态转移函数
  
  为项目集合
  
  表示当前状态 面临文法符号 时，应将状态转移到 。

构造 DFA 的方法：

1. 确定 S 集合，即 LR(0) 项目集规范族，同时确定 S0
2. 确定状态转移函数 GOTO

构造 LR(0) 的方法：
0. 一些概念
- LR(0)是 DFA 的状态集，其中每个状态又都是项目的集合。
- 项目：文法 G 的每个产生式（规则）的右部添加一个圆点就构成一个项目。
项目的直观意义：指明在分析过程中的某一时刻的已经规约部分（点之前）和等待规约（点之后）部分。

1. 将文法扩充
   • 目的：使构造出来的分析表只有一个接受状态，这是为了实现上的方便。
   • 方法：修改文法，使识别符号（开始符号）的规则只有一条。
     
2. 根据文法列出所有的项目
3. 将有关项目组合成集合，即 DFA 中的状态；所有状态构成了 项目集规范族。
   例子：LR(0)的构造&DFA 的构造

   
   
   

项目集闭包 closure 的求法：

状态转移函数 GOTO 的求法：

LR (0) 项目集规范族的构造算法:

关于自动机的说明：

1. 从 I0 到每一状态（除 I0 以外）的每条路径都识别和接受一个规范句型的活前缀。
   
2. 要求状态中每个项目对该状态能识别的活前缀都有效。
   
   

LR 文法

• 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为 LR 文法。
• 并非所有的上下文无关文法都是 LR 文法。但对于多数程序语言来说，一般都可用 LR 文法描述

(2) 构造 LR 分析表

• GOTO 表可由 DFA 直接求出
• ACTION 表由项目集规范族求出
  根据圆点所在的位置和圆点后是终结符还是非终结符，把项目集规范族中的项目分为以下四种：
  

LR（0）文法

• 假若一个文法 G 的拓广文法 G'的活前缀识别自动机中的每个状态(项目集)不存在下述情况：
  1. 既含移进项目又含归约项目
  2. 含有多个归约项目
     则称 G 是一个 LR(0)文法。
• 若：
  1. 移进和归约项目同时存在。移进-归约冲突
  2. 归约和归约项目同时存在。归约-归约冲突
• LR(0)分析器的特点是不需要向前查看任何输入符号就能归约。即当栈顶形成句柄，不管下一个输入符号是什么，都可以立即进行归约而不会发生错误。
• LR(0)文法过于简单。即使是定义算术表达式这样的简单文法也不是 LR(0)文法，所以没有实用价值！
  e.g. 移进归约冲突
  
  
  解决 LR（0）的冲突——SLR（1）文法
  

求 SLR 文法 ACTION 表的一般方法

• 假定一个 LR(0)规范族中含有如下的一个项目集（状态）
  ＝，，
  FOLLOW(A)和 FOLLOW(B)的交集为空，且不包含 b，那么，当状态 I 面临任何输入符号 a 时:
  1. 若 a = b，则移进；
  2. 若 ，用产生式 进行归约；
  3. 若 ，用产生式 进行归约；
  4. 此外，报错。
• 一般地，假定 LR(0)规范族的一个项目集
  ，，，，，，，
  如果集合 两两不相交（包括不得有两个 FOLLOW 集合有 # ），则：
  1. 若输入 a 是某个 ，i = 1, 2,…, m，则移进；
  2. 若 ，则用产生式 进行归约；
  3. 此外，报错。
• 说明：
  • 按上述方法构造出的 ACTION 与 GOTO 表如果不含多重入口，则称该文法为SLR(1)文法。
  • 使用 SLR 表的分析器叫做 SLR 分析器。
  • 每个 SLR(1)文法都是无二义的。但也存在许多无二义文法不是 SLR(1)的。

• SLR 文法中，如果项目集 含项目 。而下一输入符号 ，则状态 i 面临 a 时，可选用“”进行归约（但是有前提的）。
• 但在有些情况下（非 SLR 文法），当状态 i 显现于栈顶时，栈里的活前缀未必允许把 归约为 A，因为可能根本就不存在一个形如“”的规范句型。因此，在这种情况下用“”归约不一定合适。

3.3 算符优先分析

1. 这是一种经典的自底向上分析法，简单直观，并被广泛使用。开始主要是对表达式的分析，现在已不限于此，可以用于一大类上下文无关文法。
2. 称为算符优先分析是因为这种方法是仿效算术式的四则运算而建立起来的。做算术式的四则运算时，为了保证计算结果和过程的唯一性，规定了一个统一的四则运算法则，确定运算符之间的优先关系。
   运算法则:
   1. 乘除的优先级大于加减；
   2. 同优先级的运算符左大于右；
   3. 括号内的优先级大于括号外。
      于是： 4 + 8 – 6 / 2 * 3 运算过程和结果唯一。
3. 算符优先分析的特点:
   仿效四则运算过程，预先规定相邻终结符之间的优先关系，然后利用这种优先关系来确定句型的“句柄”，并进行规约（归约的实际上是最左素短语，不一定是句柄）。
4. 分析器结构:
   

3.3.1 分析过程

• 分析过程是从符号串开始，根据相邻终结符之间的优先关系确定句型的“句柄”并进行规约，直到识别符号 E。

• 出错情况：

  1. 相邻终结符之间无优先关系。
  2. 对双目运算符进行规约时，符号栈中无足够项。
  3. 非正常结束状态。

• 重要说明

  1. 上述分析过程不一定是严格的最左规约（即不一定是规范规约）。也就是每次规约不一定是当前句型的句柄，而是句柄的变形，但也是短语。
  2. 实际应用中，文法终结符间优先关系一般不用矩阵表示，而是采用两个优先函数来表示：f — 栈内优先函数，g — 栈外优先函数
     若 a < b 则令 f ( a ) < g ( b )
     a = b f ( a ) = g ( b )
     a > b f ( a ) > g ( b )
     特点：
     1. 优先函数值不唯一。
     2. 优点：
        • 节省内存空间。若文法有 n 个终结符，则关系矩阵为 ，而优先函数为 2n。
        • 易于比较：算法上容易实现。数与数比，不必查矩阵。
     3. 缺点：可能掩盖错误。例如对 ii+i*+i()，使用优先函数就会将其误认为是合法的句子。
  3. 可以设立两个栈来代替一个栈
     运算对象栈 (OPND)、运算符栈 (OPTR)
     好处是：便于比较，只需将输入符号与运算符栈的栈顶符号相比较。
  4. 使用算符优先分析方法可以分析二义性文法所产生的语言
     二义性文法若按规范分析，其句柄不唯一。

3.3.2 算符优先分析法的进一步讨论

1 算符优先文法(OPG)

• 算符文法（OG） 的定义
  若文法中无形如 U∷= …VW…的规则，这里 V, W∈Vn
  则称 G 为 OG 文法，也就是算符文法。
  算符文法不允许两个非终结符相邻！
• 优先关系的定义
  若 G 是一个 OG 文法，a, b∈Vt , U, V, W∈Vn 分别有以下三种情况:
  1. a=b iff 文法中有形如 U∷=…ab…或 U∷=…aVb…的规则。(a 和 b 同时被归约)
  2. a<b iff 文法中有形如 U∷=…aW…的规则，其中 或 。（想要归约 a 需要先归约 b）
  3. a>b iff 文法中有形如 U∷=…Wb…的规则，其中 或 。（想要归约 b 需要先归约 a）

• 算符优先文法（OPG—Operator Precedence Grammar）的定义
  设有一 OG 文法，如果在任意两个终结符之间，至多只有上述关系中的一种，则称该文法为算符优先文法(OPG)。
• 对于 OG 算法的几点说明：
  1. 运算是以中缀形式出现的。
  2. 可以证明，若文法为 OG 文法，则不会出现两个非终结符相邻的句型。
  3. 算法语言中的表达式以及大部分语言成分的文法均是 OG 文法。

2 构造优先关系矩阵

• 求“ = ” 检查每一条规则，若有 U::=…ab…或 U::=…aVb…, 则 a=b。
• 求“ < ”、“ > ”复杂一些，需定义两个集合
  • 若文法有规则 W∷= ... a U... ，对任何 b, b∈FIRSTVT( U )。则有：a < b
    或
  • 若文法有规则 W∷=...U b... ，对任何 a, a∈LASTVT( U )。则有：a > b
    或

(1) 构造 FIRSTVT(U)的算法

1. 若有规则 U∷= b…或 U∷= V b… 则 b∈FIRSTVT(U)（FIRSTVT 的定义中一步推导）
2. 若有规则 U∷= V…且 b∈FIRSTVT(V), 则 b∈FIRSTVT(U)（FIRSTVT 的定义中多步推导）
   说明：因为 或 ，所以有 或

上述算法的工作结果是得到一个二维的布尔数组 F，从 F 可以得到任何非终结符号 U 的 FIRSTVT：

(2) 构造 LASTVT(U) 的算法

1. 若有规则 U::=…a 或 U::=…aV，则 a∈LASTVT(U)
2. 若有规则 U::=…V，且 a∈LASTVT(V) 则 a∈LASTVT(U)
   
   

（3） 构造优先关系矩阵

3 算符优先分析算法的设计

• 先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的“句柄”并进行归约。
• 素短语：文法 G 的句型的素短语是一个短语，它至少包含有一个终结符号，并且除它自身以外不再含任何更小的素短语。

对于算符优先分析法：如何确定当前句型的最左素短语？

• 设有 OPG 文法句型为: # N1 a1 N2 a2 …Nn an Nn+1 #
  其中 Ni 为非终结符(可以为空)，ai 为终结符。
• 定理：一个 OPG 句型的最左素短语是满足下列条件的最左子串：
  
  其中
• 根据该定理，要找句型的最左素短语就是要找满足上述条件的最左子串。
• 注意：出现在 aj 左端和 ai 右端的非终结符号一定属于这个素短语，因为我们的运算是中缀形式给出的（OPG 文法的特点）

算符优先分析法的实现
基本部分是找句型的最左子串（最左素短语）并进行规约。

• 当栈内终结符的优先级＜或＝栈外终结符的优先级时，移进；
• 当栈内终结符的优先级＞栈外终结符的优先级时，表明找到了素短语的尾，再往前找其头，并进行规约。

4 算符优先分析算法的局限性

• 由于算符优先分析并未对文法非终结符定义优先关系，所以就无法发现有单个非终结符组成的“可规约串”。
• 忽略非终结符在规约过程中的作用，存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。
  例如：有文法 E::=F+F F::=i
  “ i ”明显不是一个合法的句子。但按照下推自动机
  

5 符号表管理技术

P115: 第 3、5 题

0 题型

1 画有序符号表

2 画栈式符号表

1 概述

• 符号表：在编译过程中，编译程序用来记录源程序中各种名字的特性信息，所以也称为名字特性表。

• 填表：分析到说明或定义语句时，应将说明或定义的名字以及与之有关的信息填入符号表中。
  例：Procedure P( )

• 查表：

  1. 填表前查表，检查在程序的同一作用域内名字是否重复定义；
  2. 检查名字的种类是否与说明一致；
  3. 对于强类型语言，要检查表达式中各变量的类型是否一致；
  4. 生成目标指令时，要取得所需要的地址。

2 符号表的组织与内容

2.1 符号表的结构与内容

• 符号表基本结构如下
  
• “名字”域：存放名字。一般为标识符的符号串，也可为指向标识符字符串的指针。
• “特性”域：可包括多个子域，分别表示标识符的有关信息。如：
  名字（标识符）的种类：简单变量、函数、过程、数组、标号、参数等
  类型：如整型、浮点型、字符型、指针等
  性质：变量形参、值形参等
  值：常量名所代表的数值
  地址：变量所分配单元的首址或地址位移
  大小：所占的字节数
  作用域的嵌套层次

  ---

  对于数组：维数、上下界值、计算下标量地址所用的信息（数组信息向量）以及数组元素类型等。
  对于记录（结构体、联合）：域的个数，每个域名、地址位移、类型等。
  对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等。
  对于指针：所指对象类型等。

2.2 符号表的组织方式

1. 统一符号表——不论什么名字都填入统一格式的符号表中
   符号表表项应按信息量最大的名字设计。填表、查表比较方便，结构简单，但是浪费大量空间。
2. 对于不同种类的名字分别建立各种符号表
   节省空间，但是填表和查表不方便。
   ① 符号名表（用来登记源程序中的常量名、变量名、数组名和过程名等，并记录其属性、引用等）
   ② 常数表（分类型登记各种常量值）
   ③ 标号表（登记标号的定义与应用）
   ④ 分程序入口表（登记过程的层号、分程序符号表的入口等）
   ⑤ 中间代码表
3. 折中办法——大部分共同信息组成统一格式的符号表。特殊信息另设附表，两者用指针连接。
   

3 非分程序结构语言的符号表组织

3.1 非分程序的结构语言

• 非分程序的结构语言：每个可独立进行编译的程序单元是一个不包含有子模块的单一模块，如 FORTRAN 语言
  ————不允许嵌套
• FORTRAN 程序构造
  主程序和子程序中可定义 common 语句：
  FORTRAN 程序中各程序单位之间的数据交换可以通过虚实结合来实现，也可以通过建立公用区的方式来完成。
  公用区有两种，一种是无名公用区，任何一个程序中只可能有一个无名公用区；
  一种是有名公用区，一个程序中可以根据需要由程序员开辟任意多个有名公用区。
  无名和有名公用区都通过 COMMON 语句来进行建立。
  

3.2 标识符的作用域及基本处理办法

1. 作用域
   全局：子程序名、函数名和公共区名。
   局部：程序单元中定义的变量。
2. 符号表的组织
   
3. 基本处理办法
   1. 子程序、函数名和公共区变量填入全局符号表。
   2. 在子程序(函数)声明部分读到标识符时，构造局部符号表。
      
   3. 在语句部分读到标识符，查表。
      
4. 程序单元结束：释放该程序单元的局部符号表。
5. 程序执行完成：释放全部符号表。

3.3 符号表的组织方式

1. 无序符号表——按扫描顺序建表，查表要逐项查找。
   查表操作的平均长度为 。
2. 有序符号表：符号表按变量名进行字典式排序。
   线性查表:
   折半查表:
3. 散列符号表（Hash 表）：
   符号表地址 = Hash（标识符）
   解决冲突

4 分程序结构语言的符号表组织

4.1 分程序的结构语言

模块内可嵌入子模块。

4.2 标识符的作用域和基本处理方法

4.2.1 作用域

作用域：标识符局部于所定义的模块（最小模块）

1. 模块中所定义标识符的作用域是定义该标识符的子程序。
   
2. 过程或函数说明中定义的标识符（包括形参）其作用域为本过程体。
   
3. 循环语句中定义的标识符，其作用域为该循环语句。
   不能从循环体外转到循环体内。循环语句应看作一层！
   

4.2.2 基本处理办法

• 基本处理办法：
  建查符号表均要遵循标识符作用域规定进行。
  建表：不能重复，不能遗漏。
  查表：按标识符作用域查找。
  

• 处理方法
  假设标识符是先声明后引用（标号例外，要特殊处理）。

  1. 在程序声明部分读到标识符时（声明性出现）建表
     
  2. 在语句中读到标识符（引用性出现），查表
     
  3. 标准标识符的处理
     主要是语言定义的一些标准过程和函数的名字。它们是标识符的子集。如 sin con abs….（注意它们不是语言的保留字）
     • 特点
       1. 用户不必声明就可全程使用。
       2. 设计编译程序时，标准名字及其数目已知。
     • 处理方法
       1. 单独建表：使用不便，费时。
       2. 预先将标准标识符填入名字表中。因为它们是全程量，所以应填入最外层。

4.3 符号表的组织方式

每个分程序一个分程序符号表，然后有一个分程序索引表

1. 分层组织符号表的登记项
   各分程序符号表登记项按照语法识别顺序连续排列在一起，不为其内层分程序的符号表登记项所割裂。
2. 用“分程序表”索引各分程序符号表的信息
   分程序表中的各登记项是自左至右扫描源程序的过程中，按分程序出现的顺序依次填入的，且对每一个分程序填写一个登记项。
   分程序表登记项序号隐含地表征各分程序的编号
3. 分程序表结构
   
   OUTERN——指明该分程序的直接外层分程序的编号
   ECOUNT——记录该分程序符号表登记项的个数
   POINTER——指向该分程序符号表的起始位置
   
   
4. 分程序符号表构造方法：
   1. 本例中，分程序符号表的形成顺序为 2、4、3、1，这个次序是闭分程序的次序(分程序中 END 出现的次序)。
   2. 为使各分程序的符号表连续地邻接在一起，并在扫描具有嵌套分程序结构的源程序时，总是按先进后出的顺序来扫描其中各个分程序，可设一个临时工作栈。
   3. 每当进入一层分程序时，就在栈顶预造该分程序的符号表，而当遇到该层分程序的结束符(END)时，此时该分程序的全部登记项已位于栈顶，再将该分程序的全部登记项移至正式符号表中。

6 运行时的存储组织及管理

P133: 第 2 题

6.0 题型

画运行栈（活动记录）

注意事项：

• 函数的返回值：与函数同名的变量
• 数组模板：一般写在局部变量之前
• 箭头指在 AR 的开始
• 最外层函数的外层 abp 可省略
  

6.1 概述

1. 运行时的存储组织及管理：目标程序运行时所需要存储空间的组织与管理以及源程序中变量存储空间的分配。
2. 静态存储分配：在编译阶段由编译程序实现对存储空间的管理,和为源程序中的变量分配存储的方法。
   条件:如果在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变，那么就可以采用静态存储分配方法。
3. 动态存储分配：在目标程序运行阶段由目标程序实现对存储空间的组织与管理，和为源程序中的变量分配存储的方法。
   特点
   • 在目标程序运行时进行分配。
   • 编译时要生成进行动态分配的目标指令。

• 静态内存分配
  • 能在编译期确定具体地址，e.g. 全局变量
• 动态内存分配（和我们平常所说的，在堆上的动态内存分配不一样。）
  • 不能在编译期确定具体地址，e.g. 局部变量
  • 编译器生成能够进行动态内存管理的目标代码，例如，我们在 MIPS 中维护栈帧的相关汇编指令。
  • 动态内存分配由目标代码自身完成

6.2 静态存储分配

6.2.1 分配策略

由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址。

• 开辟一数据区。（首地址在加载时确定）
• 按编译顺序给每个模块分配存储。
• 在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型确定。
• 目标地址填入变量的符号表中。

这种分配策略要求语言不允许指针或动态分配，不允许递归调用过程。典型的例子是 Fortran77。

6.2.2 模块（FORTRAN 子程序）的完整数据区

编译程序除了要给源程序（模块）中的各种变量分配数据区以外，对子程序来说还要在数据区中保留返回地址，对形式参数也要分配存储以存放相应的实参的信息。另外在编译时还要分配临时变量空间（如存放表达式计算的中间结果等）。

6.3 动态存储分配

• 动态存储分配：由于编译时还不能具体确定某些数据空间的大小，故对它们分配存储空间必须在程序运行时进行。这时，编译程序生成有关存储分配的目标代码，实际上的分配要在目标程序运行时进行。这种分配方式称为动态存储分配。

• 对于分程序结构，而且允许递归调用的语言，常使用栈式动态存储分配

• 分配策略
  整个数据区为一个堆栈

  1. 当进入一个过程时，在栈顶为其分配一个数据区。
  2. 当退出一个过程时，撤消该过程的数据区。

6.3.1 !!!活动记录

一个典型的活动记录可以分为三部分：

1. 局部数据区：存放模块中定义的各个局部变量。
2. 参数区： 存放隐式参数和显式参数。
   
   1. 形参数据区：每一形参都要分配数据空间，形参单元中存放实参值或者实参地址。
   2. prev abp：存放调用模块记录基地址。函数执行完时，释放其数据区，数据区指针指向调用前的位置。
   3. ret addr：返回地址，即调用语句的下一条执行指令地址。
   4. ret value：函数返回值（无值则空）。
3. display 区：各外层模块活动记录的基地址。
   对于例 1 中所举的程序段，模块 4 可以引用模块 1 和模块 3 中所定义的变量，故在模块 4 的 display 区，应包括 AR 1 和 AR 3 的基地址。
   

变量二元地址（BL、ON）

• BL：变量声明所在的层次。可以用它找到该层数据区开始地址。（注意为嵌套层次，并列过程具有相同层次）
• ON：相当于显示参数区开始位置的位移（相对地址）。
  

6.3.2 建造 display 区的规则

i 层模块调用 j 层模块

1. 若 j=i+1，j 层 display 区 = i 层 display 区 + i 层
   
2. 若 j≤i 即调用外层模块或同层模块
   

6.3.3 运行时的地址计算

在 LEV 层模块中引用 BL 层模块定义的变量，该如何计算变量的地址？

• BL = LEV
  addr := abp + (BL - 1) + nip + ON
  • abp 当前活动记录基指针值
  • BL 变量声明所在的层次。可以用它找到该层数据区开始地址。（注意为嵌套层次，并列过程具有相同层次）
  • BL-1 display 区大小
  • nip 隐式参数区大小
  • ON 相当于显示参数区开始位置的位移（相对地址）
    
• BL < LEV
  addr := display[BL] + (BL - 1) + nip + ON
  • display[BL] 当前活动记录 display 区中第 BL 个元素
• else
  write(“地址错误，不合法的模块层次”)

7 源程序的中间形式

P144: 第 1 ,2, 4 题

7.0 题型

1 转换波兰表达式

2 转换三元式、间接三元式、四元式

3 构造语法树

7.1 !!!波兰表示（后缀遍历）

算术表达式： F 3.1416 R ( H + R )
转换成波兰表示： F 3.1416 R H R +

• 优势
  • 在不使用括号的情况下可以无二义地说明算术表达式。
  • 波兰表示法更容易转换成机器的汇编语言或机器语言。
    操作数出现在紧靠操作符的左边，而操作符在波兰表示中的顺序即为进行计算的顺序。
  • 波兰表示不仅能用来作为算术表达式的中间代码形式，而且也能作为其它语言结构的中间代码形式。

7.1.1 !!!转换算法

当读到操作数时，就立即输出该操作数；当遇到操作符时，则要与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外，则输出该栈顶操作符；反之，则栈外操作符入栈。
对于赋值语句，则需规定赋值符号的优先级低于其它操作符，所以：
赋值语句的波兰表示 A := F 3.1416 R ( H + R )
A F 3.1416 R H R + :=

7.1.2 !!!if 语句的波兰表示

7.1.3 !!!前缀、中缀、后缀表达式

1. 中缀表达式
   中缀表达式是我们日常最常用的表达式形式，其核心特征是运算符位于两个操作数中间，同时需要依靠括号和运算符优先级来确定运算顺序。
   • 示例：
     • 简单表达式：a + b、3 × 4
     • 复杂表达式：a + (b × c - d) ÷ e
2. 前缀表达式
   前缀表达式又称波兰表达式，核心特征是运算符位于操作数的前面，无需括号和优先级规则即可确定运算顺序。
   • 示例：
     • 对应中缀 a + b：+ a b
     • 对应中缀 a + (b × c)：+ a × b c
3. 后缀表达式
   后缀表达式又称逆波兰表达式，是前缀表达式的逆序形式，核心特征是运算符位于操作数的后面，同样无需括号和优先级，且因适配栈结构而被广泛用于计算机领域。
   • 示例：
     • 对应中缀 a + b：a b +
     • 对应中缀 a + (b × c)：a b c × +

表达式类型	运算符位置	运算顺序依赖	解析难度（计算机）	典型应用场景
中缀表达式	操作数中间	括号 + 优先级	高（需处理优先级和括号匹配）	日常数学书写、人类阅读
前缀表达式	操作数前面	运算符位置	中（需从右往左遍历）	理论数学推导、部分表达式解析器
后缀表达式	操作数后面	运算符位置	低（适配栈结构，从左往右遍历）	计算机表达式求值、JVM 字节码、计算器底层逻辑

7.2 !!!N-元表示

7.2.1 !!!三元式

• n 元式的每条指令由 n 个域所组成，通常第一个域表示操作符，其余为操作数。
• 常用的 n 元表示是： 三元式 四元式
  三元式：操作符、左操作数、右操作数
  
  

7.2.2 !!!三元式 pro——间接三元式

• 使用三元式也不便于代码优化，例如当优化需要删除一些三元式，或对某些三元式的位置要进行变更时，由于三元式的结果（表示为编号）可以是某个三元式的操作数，导致操作数要随着三元式位置的变化而作相应的修改，很费事！

  例子

  例如进行下面代码优化时，会产生一系列的编号变化，可能影响到后续三元式的计算
  

• 间接三元式：三元式的执行次序用（操作）另一张表表示，这样在优化时（三元式位置的变更实际是执行顺序的变化），三元式可以不变，而仅仅改变其执行顺序表。
  

7.2.3 !!!四元式

• 四元式表示:操作符 操作数 1 操作数 2 结果
• 结果：通常是编译时分配的临时变量，可由编译程序分配一个寄存器或主存单元。
  例子

  
  优化：T1*T2 再存到 T1 里面，T3（T1）-E 再存到 T2 里面

7.3 !!!抽象机代码(Pcode)

既然是“抽象机”，就是表示它并不是实际的物理目标机器而通常是虚拟的一台“堆栈计算机”。该堆栈式计算机主要由若干寄存器、一个保存程序指令的储存器和一个堆栈式数据及操作存储组成。
寄存器有：

1. PC —— 程序计数器。
2. NP —— New 指针，指向“堆”的顶部。“堆”用来存放由 NEW 生成的动态数据。new 数据的时候在 NP 的地方划内存
3. SP —— 运行栈指针，存放所有可按源程序的数据声明直接寻址的数据。指向当前栈顶
4. BP —— 基地址指针，即指向当前活动记录的起始位置指针。
5. 其他（如 MP—栈标志指针，EP—极限栈指针等）
   

• 运行 Pcode 的抽象机没有专门的运算器或累加器，所有的运算（操作）都在运行栈的栈顶进行，如要进行 d := ( a + b ) * c 的运算，生成 Pcode 序列为：
  
• 编译程序生成 Pcode 指令程序后，我们可以用一个解释执行程序（interpreter）来解释执行 Pcode ，当然也可以把 Pcode 再变成某一机器的目标代码。显然，生成抽象机 Pcode 的编译程序是很容易移植的。

7.4 其他形式的中间代码

7.4.1 语法树

操作数出现在叶节点上，操作符出现在中间结点。

7.4.2 图表示

DAG 图（Directed Acyclic Graphs 有向无环图）––语法树的一种归约表达方式

1. 图的叶节点由变量名或常量所标记。对于那些在基本块内先引用再赋值的变量，可以采用变量名加下标 0 的方式命名其初值。
2. 图的中间节点由中间代码的操作符所标记，代表着基本块中一条或多条中间代码。
3. 基本块中变量的最终计算结果，都对应着图中的一个节点；具有初值的变量，其初值和最终值可以分别对应不同的节点。

7.4.3 三地址码

• 三地址码（英语：Three address code，经常被缩写为 TAC 或 3AC）

• 中间语言，编译器使用它来改进代码转换效率。

• 每个三地址码指令都可以被分解为一个四元组：（运算符，操作数 1，操作数 2，结果）。

• 因为每个陈述都包含了三个变量，所以它被称为三地址码。

• 适合目标代码生成和优化的一种表达形式

• 三地址码是语法树或者 DAG 图的线性表示

• 树的中间结点由临时变量表示

7.4.4 一种特殊的四元式表达方式 ：SSA

• Single Static Assignment form (SSA form) 静态单一赋值
  形式的 IR 主要特征是每个变量只赋值一次。
• SSA 的优点
  1. 可以简化很多优化的过程；
  2. 可以获得更好的优化结果。

8 错误处理

1 概述

1.1 错误处理是编译器的必备功能之一

• 正确的源程序：通过编译，生成目标代码。
• 错误的源程序：通过编译，发现并指出错误。
  对于错误的源程序不能一发现就停止，而是要能检查出错误的性质和出错位置，并使编译能继续下去，同时尽可能多而准确地发现错误和指出各种错误。

1.2 编译器的错误处理能力

1. 诊察错误的能力。
2. 报错及时准确（出错位置，错误性质）。
3. 一次编译尽量找出所有错误。
4. 改正错误的能力。
5. 遏制重复错误信息的能力。重复的错误报一次就好

2 错误的分类

• 语法错误
  程序结构不符合语法（包括词法）规则的错误。
  A[x, y := 3,1416+T(T+H)
• 语义错误：课内将运行时错误也划分在语义错误范畴内
  程序不符合语义规则或超越具体计算机系统的限制。
  超越系统限制：（计算机系统和编译系统）
  1. 数据溢出错误，常数太大，计算结果溢出。（计算机系统限制）
  2. 符号表、静态存储分配数据区溢出。 （计算机系统限制）
  3. 动态存储分配数据区溢出。 （计算机系统限制）
  4. 标识符要先声明再引用。 （编译系统限制）
  5. 过程调用时，实参和形参个数必须相等，依次具有相同的类型。（编译系统限制）

3 错误的诊断和报告

3.1 错误诊察

1. 违反语法和语义规则以及超过编译系统限制的错误：由编译程序在语法和语义分析过程中诊察出来。（语义分析要借助符号表）
2. 下标越界、计算结果溢出以及动态存储数据区溢出等(计算机系统限制)：在目标程序运行时才能检测，因此由目标程序诊察。
   • 对此，编译程序要生成相应的目标程序代码进行检查并处理。
   • 一般处理办法:
     当目标程序运行检测到这类错误时，就调用异常处理，打印错误信息和运行现场（寄存器和存储器中的值）等，然后停止程序运行。

3.2 错误报告

1. 出错位置：即源程序中出现错误的位置。
   实现：设立行号计数器 line-no，单词序号计数器 char-no
   一旦诊察出错误，当前的计数器内容就是出错位置。
2. 出错性质：
   可直接显示文字信息
   可给出错误编码
3. 报告错误（两种方式）
   1. 分析以后再报告（显示或者打印）
      编译程序可设一个保存错误信息的数据区（可用记录型数组)，将语法语义分析所诊断到的错误送数据区保存，待源程序分析完以后，统一显示或打印错误信息。
      
   2. 边分析边报告
      在分析一行源程序时若发现有错，可以立即输出该行源程序，并在其下输出错误信息。
      

4 错误处理技术

发现错误后，在报告错误的同时还要对错误进行处理，以方便编译能继续进行下去。目前有两种处理办法

4.1 错误改正

指编译诊察出错误以后，根据文法进行错误改正。

但不是总能做到，如：A := B – C * D + E )

• 是多一个右括号还是少一个左括号？
• 如果是少了左括号，应该少在何处？

4.2 错误局部化处理

指当编译程序发现错误后，尽可能把错误的影响限制在一个局部的范围，避免错误扩散和影响程序其它部分的分析。

1. 一般原则
   当诊断到错误以后，就暂停对后面符号的分析，跳过错误所在的语法成分（一旦跳过就认为该语法成分是正确的）然后继续往下分析。
   • 词法分析：发现不合法字符，显示错误，并跳过该标识符（单词）继续往下分析。
   • 语法语义分析：跳过所在的语法成分（短语或语句），一般是跳到语句右界符，然后从新语句继续往下分析。
2. 错误局部化处理的实现
   CX：全局变量，存放错误信息。
   • 用递归下降分析时，如果发现错误，便将有关错误信息（字符串或者编号）送 CX，然后转出错误处理程序；
   • 出错程序先打印或显示出错位置以及出错信息，然后跳出一段源程序，直到跳到语句的右界符（如 end、; ），或正在分析的语法成分的合法后继符号为止，然后再往下分析。

3. 提高错误局部化程度的方法
   设 S1: 合法后继符号集 （某语法成分的后继符号）
   S2: 停止符号（跳读必须停止的符号集）
   

4.3 遏制重复的错误信息

• 语义错误主要来源于标识符未声明和类型不一致等，这些错误往往会多次出现。
  该标识符的每一次引用都会出现“标识符未声明”错误。
  • 处理办法:
    建立一张错误名字表，每当发现出错名字后，先查表，若有，则不再打印错误信息；否则登入该表，并打印错误信息。
• 溢出错误：编译程序所需的工作区或源程序所需的数据区域溢出
  需要使编译正常运行，同时遏制重复的错误信息
  • 处理办法:
    对各数据区分别设置一个标志单元，初始为 0，当发生溢出时，则查看单元内容，若为 0，表示刚发生溢出，打印错误信息，置 1；若为 1，不再重复打印。

9 语法制导翻译

P166 第 1（只做前缀式），2，3，4，5 题

本章介绍了语法制导翻译概念和技术，是在抽象层次上讲的。

• 翻译文法：在输入文法中插入语义动作符号（完成翻译任务的语义子程序）
• 属性翻译文法：文法符号（包括动作符号）可带有属性，并定义相应的属性求值规则，就成为属性翻译文法。比翻译文法能较细地描述翻译过程。（属性有综合属性和继承属性之分）

0 题型

1 构造翻译文法

2 解释翻译文法

3 根据活动序列和输入文法写翻译文法

4 列出翻译文法定义的语法制导翻译的所有对偶

1 翻译文法(TG)和语法制导翻译

• 翻译的任务：把中缀表达式转化为逆波兰表示。

• 方法：在上述文法中插入相应的动作符号。如何加动作符号为经验决定

  例子

  
  

• 输入文法：未插入动作符号时的文法。
  由输入文法可以通过推导产生输入序列。

• 翻译文法：插入动作符号的文法。是上下文无关文法，终结符号集由输入符号和动作符号组成。
  由翻译文法可以通过推导产生活动序列（输入序列&动作序列）

  Example

  
  

• 活动序列：由翻译文法推导出的符号串，由终结符和动作符号组成。

  • 从活动序列中，抽去动作符号则得输入序列（i+i)*i
  • 从活动序列中，抽去输入序列，则得动作序列。执行动作序列，则完成翻译任务：
    @i @i @+ @i @* => ii+i*

• 符号串翻译文法：输入文法中的动作符号对应的语义子程序 是 输出动作符号标记@后的字符串 的文法。
  符号串翻译文法是这样一种文法：它里面的动作符号会绑定一个语义子程序，这个子程序的唯一工作，就是把动作符号里@标记后面的字符串提取出来并输出。

• 语法制导翻译：按翻译文法进行的翻译
  给定一个输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作过程。

• 语法制导翻译的实现方法：
  在文法的适当位置插入语义动作符号。当按文法分析到动作符号时就调用相应的语义子程序，完成翻译任务。
  翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。
  

2 属性翻译文法 (ATG)

• 在翻译文法的基础上，我们可以进一步定义属性文法。
• 翻译文法中的符号，包括终结符、非终结符和动作符号均可带有属性，这样能更好地描述和实现编译过程。
• 属性可以分为两种：综合属性、继承属性

2.1 综合属性

• 综合属性用 表示
  表示自底向上，自右向左计算
  表示属性变量或属性值

2.2 继承属性

• 对于上述文法的说明语句：integer A, B1

• 该文法的翻译任务：将声明的变量填入符号表（语义）

• 完成该工作的动作符号：@set_table
  

• 填表时需要的信息：类型、名字、以及位置（可以用全程变量的指针）如何得到？

• 终结符（输入符号）的类型和名字在词法分析时得到，可设两个综合属性
  t 中是类型值
  n 是变量名
  填表动作符号也可带有属性：
  可从其前面的符号得到，称为继承属性，继承前面符号的值。
  变量表 同上

• 属性翻译文法
  

  例子

  
  

• 总结：输入文法 => （字符串）翻译文法 => 属性翻译文法

2.3 属性翻译文法的自顶向下翻译

2.3.1 L-属性翻译文法（L-ATG）

• L-属性翻译文法
  这是属性翻译文法中较简单的一种。其输入文法要求是 LL(1)文法，可用自顶向下分析方法构造分析器。在分析过程中可进行属性求值。
  • LL(1)文法
    • 无左递归
    • A::=α|β，FIRST(α) ∩ FIRST(β) = Ф
    • 若β => ε, 则 FIRST(α) ∩ FOLLOW(A) = Ф
  • 特点：某个符号的继承属性只依赖于该符号左边的信息！
• L-属性翻译文法是带有下列说明的翻译文法：

  1. 文法中的终结符，非终结符及动作符号都带有属性，且每个属性都有一个值域。

  2. 非终结符及动作符号的属性可分为继承属性和综合属性。（终结符只能有综合属性）

  3. 开始符号的继承属性具有指定的初始值。

  4. 输入符号（终结符号） 的每个综合属性具有指定的初始值。

  5. 属性值的求值规则如下：
     继承属性——体现自顶向下，自左向右的求值特性。

     1. 产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值。
        t 可以取 x 的值
     2. 产生式右部符号（非终结符、动作符号） 的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算
        a 可以用 t 和 b 算

     综合属性——体现自底向上，自右向左的求值特性。

     1. 产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值。
     2. 产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某些右部符号的（任意）属性进行计算。
     3. 动作符号的综合属性用该符号的继承属性或某些右部符号的（任意）属性进行计算。
        适合在自顶向下分析过程中求值

• 一般来说，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个求值规则。
• 属性求值规则中只能使用相应产生式中的文法符号的属性（这有助于在产生式范围内“封装”属性的依赖性）。
• 但出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性求值规则进行计算。它们由其它产生式的属性规则计算。

2.3.2 简单赋值形式的 L-属性翻译文法(SL-ATG)

• 一般情况 x := f(y, z) x 的属性值是 y 和 z 的属性值的函数
• SL-ATG: x := 某符号的属性值或常量
  例 x := y x, y, z := 17 —— 称为复写规则
• 为了实现上的方便，常希望文法符号的属性求值规则为上述简单形式的。为此，我们对现有的 L-ATG 的定义做一点改变，从而形成一个称为简单赋值形式的 SL-ATG。
• 一个 L-ATG 被定义为简单赋值形式的(SL-ATG)，当且仅当满足如下条件:
  1. 产生式右部符号的继承属性是一个常量，它等于左部符号的继承属性值，或等于出现在所给符号左部某个符号的综合属性值。
  2. 产生式左部非终结符号的综合属性是一个常量，它等于其自身的继承属性值或等于右部某个符号的综合属性值。
• 目的：一个简单赋值形式的 L-ATG 除动作符号外，其余符号的属性求值规则右部是属性或是常量（——简单化）。

给定一个 L-ATG ，如何找一个等价的简单赋值形式的 L-ATG?

3 自顶向下语法制导翻译

先介绍翻译文法的自顶向下翻译，然后介绍属性翻译文法的自顶向下翻译。

3.1 翻译文法的自顶向下翻译——递归下降翻译器

按翻译要求，在文法中插入语法动作符号，在分析过程中调用相应的语义处理程序，完成翻译任务。

3.2 属性翻译文法的自顶向下翻译的实现——递归下降翻译器

我们把处理翻译文法的递归下降翻译器进行适当扩展，便可得到处理属性（翻译）文法的递归下降翻译器。

• 方法：对于每个非终结符号都编写一个翻译子程序（过程）。根据该非终结符号具有的属性数目，设置相应的参数。
  • 继承属性：声明为赋值形参
  • 综合属性：声明为变量形参
    
• 过程调用语句的实参：
  • 继承属性: 继承属性值（传实参值）
  • 综合属性: 属性变量名（传地址，返回时有值）
• 关于属性名的约定：
  1. 具有相同值的属性取相同的属性名。（这样可省去不少属性求值规则）
     
  2. 产生式左部的同名非终结符使用相同的属性名。（递归下降分析法规定每个非终结符只编写一个子程序!）
     具有简单赋值形式的属性变量名取相同的属性名，可删去属性求值规则。
     
     

如何构造属性文法的递归下降翻译器

例 1

下面通过一个例子，详细介绍如何构造属性文法的递归下降翻译器。（该文法应是具有 L-属性的符号串翻译文法）

1. 对简单赋值形式的属性变量取相同的属性名，其求值规则可以删去。
   开始符号的继承属性 R = 7。
   
2. 设计递归下降程序
   1. 全局变量的过程声明
      
   2. 主程序
      
   3. 其它代码
      
      
      
      

例 2

构造将算术表达式翻译成四元组的属性翻译文法，并写出递归下降分析程序。由该属性翻译文法来描述翻译过程。

1. 翻译文法设计
   
2. 属性翻译文法的设计
   在翻译文法的基础上可设计其属性翻译文法，以便语义分析过程中生成完整的四元式，完成翻译。
   • 输入符号（操作数） 有一综合属性，它是该符号在数据区的地址。
   • 每个非终结符有一个综合属性，该属性是由它产生的代表该子表达式在数据区中的地址（中间结果）。
   • 动作符号有三个继承属性，它们分别是左右操作数和运算结果在数据区的地址
     
     
     

10 语义分析和代码生成

例子没看

假定:

• 源语言：通用的过程语言（函数式语言，如 C,Pascal,FORTRAN）
• 生成代码：栈式抽象机的（伪）汇编程序
• 翻译方法：自顶向下的属性翻译
• 语法成分翻译子程序参数设置：
  • 继承属性为值形参
  • 综合属性为变量形参
• 语法成分翻译动作子程序参数设置：（如动作 ）
  • 继承属性为值形参
  • 综合属性不设形参，而作为动作子程序的返回值
    （由 RETURN 语句返回）

1 语义分析的概念

1. 语义分析是上下文有关分析（如标识符的作用域，使用变量时要检查是否声明过）
   
   • 但上下文有关文法构造困难且不好使 => 使用上下文无关文法+符号表
   • 把与语义相关的上下文有关信息填入符号表中，并通过查符号表中的这些信息来分析程序的语义是否正确。
2. 类型的一致性检查
3. 语义处理：
   1. 声明语句：其语义是声明变量的类型等，并不要求做其他的操作。
      语义分析程序的工作是填符号表，登录名字的特征信息，分配存储。
   2. 执行语句：语义是要做某种操作。
      语义处理的任务：按某种操作的目标结构生成中间代码或目标代码。

2 栈式抽象机及其汇编指令

• 栈式抽象机
  • 三个存储器
    • 数据存储器 （存放 AR 的运行栈）
    • 操作存储器 （操作数栈）
    • 指令存储器
  • 一个指令寄存器
  • 多个地址寄存器组成。
    
    
    

3 声明的处理

• 语义的表示：
  给出语言结构的属性翻译文法来说明其语义及语义动作，并把这些语义动作插入属性翻译文法产生式中的适当位置。

• 编译程序的任务：

  • 编译程序处理声明语句要完成的主要任务为：
    填表工作（填表前先得查表，检查是否重名）。
    1. 分离出每一个被声明的实体，并把它们的名字填入符号表中
    2. 把被声明实体的有关特性信息尽可能多地填入符号表中
  • 对于已声明的实体，在处理对该实体的引用时要做的事情：
    查表工作
    1. 检查对所声明的实体引用（种类、类型等）是否正确
    2. 根据实体的特征信息，例如类型、所分配的目标代码地址（可能为数据区单元地址，或目标程序入口地址）生成相应的目标代码

• 声明有常量声明，变量（包括简单变量，数组变量和记录变量等）和过程（函数）声明等，这里主要讨论常量声明和简单变量、数组声明的处理。

• 声明的两种方式：

  1. 类型说明符放在变量的前面。如 C 语言： int a; 在填表时已知类型和 a 的值（名字），直接填入符号表。
  2. 类型说明符放在变量的后面。如：Pascal，PL/1，Ada 等，需要反填。
     如 PL/1 声明语句：DECLARE( X, Y(N), YTOTAL) FLOAT;

3.1 常量类型声明处理

常量标识符通常被看作是全局名。

3.2 简单变量声明处理

• 对于变长字符串（或其它大小可变的数据实体），往往需要采用动态申请存储空间的办法把可变长实体存储在堆中。
• 我们可通过指向存放该实体数据区的指针来引用该实体，有时还应得到该实体存储空间的大小信息，并一起填入符号表内。
• 即可变长实体存储在堆中，而其指针存放在符号表中。

3.3 数组变量声明的处理

• 对于静态数组，即数组的大小在编译时是已知的，编译程序在处理数组声明时，可建立一个数组模板（又称为数组信息向量），以便以后的程序中引用该数组元素时，可按照该模板提供的信息，计算数组元素(下标变量）的存储地址。

• 对于动态数组，其大小只有在运行时才能最后确定。我们在编译时仅为该模板分配一个空间，而模板本身的内容将在运行时才能填入。

• 大部分程序设计语言，数组元素是按行（优先）存放在存储器中的（FORTRAN 例外！它按列（优先）存放数组元素）
  如声明数组 array B(N, -2:1) char ;
  

1 n 维数组的地址计算公式

1* 计算公式改进——提取出来不变的部分（RC）

2 数组信息向量表（模板）

功能：

1. 用于计算下标变量地址
2. 检查下标是否越界
   
   例子

   

3 数组声明的 ATG 文法

4 表达式的处理

• 分析表达式的主要目的是生成计算该表达式值的代码。通常的做法是把表达式中的操作数装载（LOAD）到操作数栈（或运行栈）栈顶单元或某个寄存器中，然后执行表达式所指定的操作，而操作的结果保留在栈顶或寄存器中。
• 注：操作数栈即操作栈，它可以和前述的运行栈（动态存储分配）合而为一，也可单独设栈。
  本章中所指的操作数栈实际应与动态运行（存储分配）栈分开。

例：整形表达式

• 上面所述的表达式处理实际上忽略了出现在表达式中各操作数类型的不同，且变量也仅限于简单变量。
• 下面假定表达式中允许整型和实型混合运算，并允许在表达式中出现下标变量（数组元素）。因此应该增加有关类型一致性检查和类型转换的语义动作，也要相应产生计算下标变量地址和取下标变量值的有关指令。

例：整型+实型+数组表达式

例：逻辑表达式

5 赋值语句的处理

6 控制语句的处理

6.1 if 语句

6.2 for 循环

7 过程调用和返回

• 过程：无返回值
• 函数：有/无返回值
  （此处的过程调用和返回既包括过程也包括函数）

7.1 参数传递的基本形式

7.1.1 传值（call by value）——值调用

• 实现：
  调用段（过程语句的目标程序段）：计算实参值 => 操作数栈栈顶
  被调用段（过程说明的目标程序段）：从栈顶取得值 => 形参单元
• 过程体中对形参的处理：对形参的访问等于对相应实参的访问
• 特点:数据传递是单向的
• 如 C 语言，Ada 语言的 in 参数,Pascal 的值参数。

7.1.2 传地址（call by reference）——引用调用

• 实现：
  调用段：计算实参地址 => 操作数栈栈顶
  被调用段：从栈顶取得地址 => 形参单元
• 过程体中对形参的处理：通过对形参的间接访问来访问相应的实参
• 特点:结果随时送回调用段
• 如：FORTRAN,Pascal 的变量形参。

7.1.3 传名（call by name）

• 又称“名字调用”。即把实参名字传给形参。这样在过程体中引用形参时，都相当于对当时实参变量的引用。
• 当实参变量为下标变量时，传名和传地址调用的效果可能会完全不同。
• 传名参数传递方式，实现比较复杂，其目标程序运行效率较低, 现已很少采用。
• 如：ALGOL 的换名形参。

7.2 过程调用处理

1 调用

与调用有关的动作如下 ：

1. 检查该过程名是否已定义（过程名和函数名不能用错），实参和形参在类型、顺序、个数上是否一致。(查符号表）
2. 加载实参（值或地址）（放到操作数栈顶）
3. 加载返回地址（放到操作数栈顶）
4. 转入过程体入口地址

2 声明

• 过程调用时，实参加载指令是把实参变量内容（或地址）送入操作数栈顶，过程声明处理时，应先生成把操作数栈顶的实参送运行栈 AR 中形参单元的指令。
• 将操作数栈顶单元内容存入运行栈（动态存储分配的数据区）当前活动记录的形式参数单元。
• 可认为此时运行栈和操作数栈不是一个栈（分两个栈处理）

3 过程调用的 ATG 文法

4 过程声明的 ATG 文法

7.3 返回语句和过程体结束的处理

其语义动作有：

1. 若为函数过程，应将操作数栈（或运行栈）顶的函数结果值送入（存回）函数值结果单元
2. 生成无条件转移返回地址的指令（JMP RA)
3. 产生删除运行栈中被调用过程活动记录的指令（只要根据 DL—活动链，把 abp 退回去即可）

11 代码优化

P356: 第 1、2、3、4、5、6 题

0

1 切分基本块&画流图

2 构建 DAG 图&导出优化后的中间代码

3 到达定义分析

4 活跃变量分析

5 定义-使用链

到达定义的具体应用

6 冲突图

活跃变量分析的具体应用，同时活跃 = 不能分配同一个寄存器 = 冲突

法 1

1. 跨基本块冲突：
   1. 求跨基本块活跃的变量：v 跨基本块活跃当且仅当 ，
   2. 求互相冲突的变量：x 和 y 冲突当且仅当 ，且
2. 基本块内冲突：
   对每个基本块，检查只出现在 in 或 out 中的变量，检查二者间是否冲突

法 2

根据网判断，如果两个变量的网有交点，就冲突

1 概述

• 代码优化（code optimization)
  • 目的：生成高质量的目标程序，提高目标代码运行效率
  • 原则：进行优化必须严格遵循“不能改变原有程序语义”原则。
• 只要做些简单的处理，便能得到明显的优化效果。若要进一步提高优化效果，就要逐步付出更大的代价。
  

优化的分类

• 从优化的层次，与机器是否有关，分为：
  • 独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进行的优化。
    如：数据流分析，常量传播，公共子表达式删除，死代码删除，循环交换，代码内联等等
  • 与机器有关的优化：充分利用系统资源（指令系统，寄存器资源）。
• 从优化涉及的范围，又分为：
  • 局部优化：一个基本块内
    局部公共子表达式删除
  • 循环优化：循环语句内
  • 全局优化：一个函数内，跨越多个基本块。
    全局数据流分析
  • 跨函数优化：整个程序
    跨函数别名分析，逃逸分析等

2 基本块和流图

2.1 基本块

• 程序的执行（控制流）只能从基本块的第一条语句进入。
• 程序的执行只能从基本块的最后一条语句离开。

2.2 算法：划分基本块

• 输入：四元式序列
• 输出：基本块列表。每个四元式仅出现在一个基本块中
• 方法：
  1. 首先确定入口语句（每个基本块的第一条语句）的集合。
     • 规则 1：第一条语句（1）
     • 规则 2：能由条件/无条件跳转语句转移到的第一条语句（3）
     • 规则 3：跳转语句之后的第一条语句（13）
  2. 每个入口语句直到下一个入口语句，或者程序结束，它们之间的所有语句都属于同一个基本块。

2.3 流图

• 流图的结点是基本块
• 如果在某个执行序列中，B2 的执行紧跟在 B1 之后，则从 B1 到 B2 有一条有向边
• 我们称 B1 为 B2 的前驱，B2 为 B1 的后继
  • 从 B1 的最后一条语句有条件或者无条件转移到 B2 的第一条语句；
  • 按照程序的执行次序，B2 紧跟在 B1 之后，并且 B1 没有无条件转移到其他基本块。

3 基本块内优化

3.1 利用代数性质（代数变换）

• 编译时完成常量表达式的计算（常数合并），整数类型与实型的转换。
  
• 下标变量引用时，其地址计算的一部分工作可在编译时预先做好（运行时只需计算“可变部分”即可）。
• 运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度(时、空开销)。
  

3.2 复写（copy）传播

• 如 x := y 这样的赋值语句称为复写语句。由于 x 和 y 值相同，所以当满足一定条件时，在该赋值语句下面出现的 x 可用 y 来代替。
  
• 若上例中不是 x := y 而是 x := 3。则复写传播变成了常量传播。即
  

3.3 删除冗余代码

• 冗余代码就是毫无实际意义的代码，又称死代码 (dead code)或无用代码(useless code)。
  

3.4 !!!算法：消除公共子表达式

通过 DAG 图（有向无环图）消除公共子表达式

• Directed Acyclic Graph
• 用来表示基本块内各中间代码之间的关系
  

DAG 图定义

• 图的叶结点由变量名或常量所标记。（对于那些在基本块内先引用再赋值的变量，可以采用变量名加下标 0的方式命名其初值）。
• 图的中间结点由中间代码的操作符所标记，代表着基本块中一条或多条中间代码。
• 基本块中变量的最终计算结果都对应着图中的一个结点；具有初值的变量，其初值和最终值可以分别对应不同的结点。
  

!!!算法：DAG 图的生成算法

• 输入：基本块内的中间代码序列
• 输出：完成局部公共子表达式删除后的 DAG 图
• 方法：
  1. 首先建立结点表，该表记录了变量名和常量值，以及它们当前所对应的 DAG 图中结点的序号。该表初始状态为空。
  2. 从第一条中间代码开始，按照以下规则建立 DAG 图。
  3. 对于形如 z = x op y 的中间代码，其中 z 为记录计算结果的变量名，x 为左操作数，y 为右操作数，op 为操作符：首先在结点表中寻找 x，如果找到，记录下 x 当前所对应的结点号 i；如果未找到，在 DAG 图中新建一个叶结点，假设其结点号仍为 i，标记为 x（如 x 为变量名，该标记更改为 x0）；在结点表中增加新的一项(x, i)，表明二者之间的对应关系。右操作数 y 与 x 同理，假设其对应结点号为 j。
  4. 在 DAG 图中寻找中间结点，其标记为 op，且其左操作数结点号为 i，右操作数结点号为 j。如果找到，记录下其结点号 k；如果未找到，在 DAG 图中新建一个中间结点，假设其结点号仍为 k，并将结点 i 和 j 分别与 k 相连，作为其左子结点和右子结点。
  5. 在结点表中寻找 z，如果找到，将 z 所对应的结点号更改为 k；如果未找到，在结点表中新建一项(z, k)，表明二者之间的对应关系。
  6. 对输入的中间代码序列依次重复上述步骤 3～5。
     
     

数组、指针及函数调用的 DAG 图

• 当中间代码序列中出现了数组成员、指针或函数调用时，算法 14.2 需要作出一定的调整，否则将得出不正确的优化结果。
• 数组：保守处理，把修改 a[i] 看做修改了 a
  
• 指针：保守处理
  
• 函数调用：在缺乏跨函数数据流分析的支持下，需要保守地假设函数调用改变了所有它可能改变的数据。

从 DAG 图重新导出中间代码

生成的中间代码顺序会影响最后代码的运行效率

!!!算法：从 DAG 导出中间代码的启发式算法

• 输入：DAG 图
• 输出：中间代码序列
• 方法：
  1. 初始化一个放置 DAG 图中间结点的队列。
  2. 如果 DAG 图中还有中间结点未进入队列，则执行步骤 3，否则执行步骤 5
  3. 选取一个尚未进入队列，但其所有父结点均已进入队列的中间结点 n，将其加入队列；或选取没有父结点的中间结点，将其加入队列
  4. 如果 n 的最左子结点符合步骤 3 的条件，将其加入队列；并沿着当前结点的最左边，循环访问其最左子结点，最左子结点的最左子结点等，将符合步骤 3 条件的中间结点依次加入队列；如果出现不符合步骤 3 条件的最左子结点，执行步骤 2
  5. 将中间结点队列逆序输出，便得到中间结点的计算顺序，将其整理成中间代码序列
     
     

3.5 窥孔优化

• 窥孔优化关注在目标指令的一个较短的序列上，通常称其为“窥孔”
• 通过删除其中的冗余代码，或者用更高效简洁的新代码来替代其中的部分代码，达到提升目标代码质量的目的
• 必须出现在同一个基本块中的情况：
  mov EAX, [ESP+08H]
mov [ESP+08H], EAX
• 但是窥孔优化并不局限在同一个基本块中。以上方法，如利用代数性质等都可以用。
  jmp B2
B2: …

4 全局优化

4.1 到达定义分析

• 用于获取数据在程序执行路径中如何流动的有关信息。
  例如：
  • 某个变量在某个特定的执行点（语句前后）是否还“存活”
  • 某个变量的值，是在什么地方定义的
  • 某个变量在某一执行点上被定义的值，可能在哪些其他执行点被使用
• 是全局优化的基础
• 数据流分析是为了了解程序的状态

1 程序的状态

• 程序的执行过程：程序状态的变换过程
  • 程序状态由程序中的变量和其它数据结构组成
  • 每一条执行指令都可能改变程序的状态
• 通过数据流分析，可以了解程序的状态。
  • 例如，如果得知在某条中间代码之后，无论程序在实际执行时通过哪条路径，某个变量都不会再被访问，那么该变量此前所保有的全局寄存器或临时寄存器就可以安全地被其他变量重新使用。
  • 例如，如果得知在程序的某个点上，对某个变量进行引用时，无论程序如何运行，该变量都仅具有某个唯一的常量值，那么就可以将该常量引入中间代码，在代码生成时生成更高效的指令。
• 一种常用的数据流分析方法：到达定义

2 数据流分析方程

• 考察在程序的某个执行点的数据流信息。
• out[S] = gen[S] ∪ (in[S] – kill[S])
  含义：当执行控制流通过 S 时，在 S末尾得到的数据流信息等于 S本身产生的数据流信息，加上进入S 时的数据流信息减去S注销的数据流信息后的数据流信息。
  • out[S] 代表在 S 末尾得到的数据流信息
  • gen[S] 代表 S 本身产生的数据流信息
  • in[S] 代表进入 S 时的数据流信息
  • kill[S] 代表 S 注销的数据流信息

3 到达定义分析

• 通过到达定义分析，希望知道：
  在程序的某个静态点 p，例如某条中间代码之前或者之后，某个变量可能出现的值都是在哪里被定义的？
• 在 p 处对该变量的引用，取得的值是否在 d 处定义？
  • 如果从定义点 d 出发，存在一条路径达到 p，并且在该路径上，不存在对该变量的其他定义语句，则认为“变量的定义点 d 到达静态点 p ”
  • 如果路径上存在对该变量的其他赋值语句，那么路径上的前一个定义点就被路径上的后一个定义点“杀死”，或者消除了

单个语句的到达定义数据流方程

• 对于基本块中的某一条中间代码：
  d1: u = v op w，v 和 w 为变量，op 为操作符
• 代码对应的到达定义数据流方程是：
  out[d1] = gen[d1] ∪ ( in[d1] – kill[d1] )
• 其中
  • gen[d1] = {d1}，表明该语句产生了一个定义点（定义了变量 u）
  • kill[d1] 是程序中所有对变量 u 定义的其他定义点的集合（包括 d1 之前或之后的定义点 --why？后面的语句可能跳转到当前语句）
  • 对于该代码在同一基本块中紧邻的后继代码，假设其为 d2，in[d2] 等价于 out[d1]

基本块的到达定义数据流方程

out[B] = gen[B]∪( in[B] – kill[B] )

• in[B] 为进入基本块 B 时的数据流信息
• kill[B] = kill[d1] ∪ kill[d2] … ∪ kill[dn]， d1~dn 依次为基本块中的语句
• gen[B] = gen[dn]∪
(gen[d(n-1)] – kill[dn])∪
(gen[d(n-2)] – kill[d(n-1)] – kill[dn])…∪
(gen[d1] – kill[d2] – kill[d3]… – kill[dn])

4 !!!算法：基本块的到达定义数据流分析

• 输入：程序流图，且基本块的kill 集合和 gen 集合已经计算完毕
• 输出：每个基本块入口和出口处的 in 和 out 集合，即 in[B] 和 out[B]
• 方法：
  1. 将包括代表流图出口基本块 的所有基本块的 out 集合，初始化为空集。
  2. 根据方程 的前驱基本块，out[B] = gen[B]∪( in[B] –kill[B] )，为每个基本块 B 依次计算集合 in[B] 和 out[B]。如果某个基本块计算得到的 out[B] 与该基本块此前计算得出的 out[B] 不同，则循环执行步骤 2，直到所有基本块的 out[B] 集合不再产生变化为止。

5 到达定义分析的代码实现

• 集合“∪”和“–”运算：可以采用位向量（Bit Vector）的方式完成。
• 将集合中的每个定义点，根据其下标映射为一个无限位二进制数的某一位，例如，可以将 d1 映射为第 1 位，d3 映射为第 3 位，以此类推。
  • 例如，out[B3] = { d2, d3, d4, d5, d7, d8}，其对应的二进制位向量为 11011110，该位向量从低位到高位依次对应 d1~d8。
  • 基于这样的设定，集合之间的“∪”运算等价于位向量之间的或运算，集合之间的“–”运算等价于将后者取反后，和前者进行按位与运算。
• 在数据流分析方法的实现中，位向量是常用的手段之一。

4.2 活跃变量分析

• 到达定义分析是沿着流图路径的，活跃变量分析是反方向计算的

• 活跃变量分析：

  • 了解变量 x 在某个执行点 p 是活跃的
    变量 x 的值在 p 点或沿着从 p 出发的某条路经中会被使用，则称 x 在 p 点是活跃的。
  • 通过活跃变量分析，可以了解到某个变量 x 在程序的某个点上是否活跃，或者从该点出发的某条路径上是否会被使用。如果存在被使用的可能，x 在该程序点上便是活跃的，否则就是非活跃，或者死的。

• 活跃变量信息对于寄存器分配，不论是全局寄存器分配还是临时寄存器分配都有重要意义。

  • 如果拥有寄存器的变量 x 在 p 点开始的任何路径上不再活跃，可以释放寄存器
  • 如果两个变量的活跃范围不重合，则可以共享同一个寄存器

1 活跃变量分析

• 数据流方程如下：
  • in[B] = use[B] ∪ (out[B] – def[B])
  • 的后继基本块 （后面的块还用得到这些变量，所以在进入这个块的时候这些量必须是活跃的）
  • def[B]：变量在 B 中被定义（赋值）先于任何对它们的使用 【先定义后使用】（这些变量是在这个块内被定义的，所以在进入这个块的时候它可以不是活跃的）
  • use[B]：变量在 B 中被使用先于任何对它们的定义 【先使用后定义】（这个块内用到了这些变量但没有定义，所以在进入这个块的时候这些变量必须是活跃的）
• 直观理解：如果在路径后方的某个基本块中，变量 x 被使用，则沿着执行路径的逆向直到 x 被定义的基本块，x 都是活跃的。
• 到达定义数据流分析，其数据流信息是沿着流图中路径的方向进行计算的
• 活跃变量分析的数据流信息，需要沿着流图路径的反方向计算得出

2 活跃变量分析与到达定义分析的区别

活跃变量分析：in[B] = use[B]∪(out[B] – def[B])
到达定义分析：out[B] = gen[B]∪(in[B] – kill[B])

• 采用 use[B] 代表当前基本块新生成的数据流信息（用了）
• 采用 def[B] 代表当前基本块消除的数据流信息 （定义的）
• 采用 in[B] 而不是 out[B] 来计算当前基本块中的数据流信息
• 采用 out[B] 而不是 in[B] 来计算其它基本块汇集到当前基本块的数据流信息
• 在汇集数据流信息时，考虑的是后继基本块而不是前驱基本块

3 !!!算法：基本块的活跃变量数据流分析

• 输入：程序流图，且基本块的use 集合和 def 集合已经计算完毕
• 输出：每个基本块入口和出口处的 in 和 out 集合，即 in[B] 和 out[B]
• 方法：
  1. 将包括代表流图出口基本块 在内的所有基本块的in 集合，初始化为空集。
  2. 根据方程 的后继基本块，in[B] = use[B] ∪ (out[B] – def[B])，
     为每个基本块 B 依次计算集合 out[B] 和 in[B]。如果计算得到某个基本块的 in[B] 与此前计算得出的该基本块 in[B] 不同，则循环执行步骤 2，直到所有基本块的 in[B] 集合不再产生变化为止。

4 冲突图

假设只有跨越基本块活跃的变量才能分配到全局寄存器，并且活跃范围重合的变量之间无法共享全局寄存器

4.3 定义-使用链、网和冲突图

• 冲突图：其结点是待分配全局寄存器的变量，当两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们之间便有一条边连接
  

• 冲突图中两个结点（变量）间存在边的条件约束为：其中一个变量在另一个变量的定义点处活跃
  

关于变量冲突的判断

两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们就是冲突的。

• 算法一：在每一个变量的定义点计算活跃变量。
• 算法二：计算基本块入口处的活跃变量（in 的集合），这些变量在该基本块中的定义点活跃，因而冲突。之后，在基本块内部，进一步计算每个定义点的活跃变量（基本块范围内计算），降低了计算的复杂度，因为基本块内部是线性的。

第一个循环的 i 和第二个循环的 i 其实没有关系，可以看做两个 i，这样画成冲突图后就只有两个颜色了

定义-使用链

• 定义-使用链：指变量的某一定义点，以及所有可能使用该定义点所定义变量值的使用点所组成的一个链
• 一个变量有几个定义点，就有几个定义-使用链
  

网

• 同一变量的多个定义-使用链，如果它们拥有某个同样的使用点，则合并为同一个网
  
• 判断冲突：网之间的交点是共同的活跃点
  

5 循环优化

减少循环部分的目标代码对提高整个程序的时间效率有很大作用。

5.1 循环不变式的代码外提

不变表达式：不随循环控制变量改变而改变的表达式或子表达式。

5.2 循环展开

循环展开是一种优化技术。它将构成循环体的代码(不包括控制循环的测试和转移部分)，重新产生许多次(这可在编译时确定)，而不仅仅是一次。以空间换时间

说明：

• 循环一次执行 5 条语句才给一个变量赋初值。展开后，一条语句就能赋一个值，运行效率高。
• 优化在生成代码时进行，并不是修改源程序。
• 必须知道循环的初值、终值及步长。
• 但非所有展开都是合适的。如上例中循环展开后节省了测试和转移语句：2*30=60 语句。但若循环体中不是一条而是 40 条，则展开将有 40*30=1200 条，但省的仍是 60 条，就不算优化了。
  判断准则：
  1. 主存资源丰富处理机时间昂贵
  2. 循环体语句越少越好

实现步骤

1. 识别循环结构，确定循环的初值、终值和步长。
2. 判断。以空间换时间是否合算来决定是否展开。
3. 展开。重复产生循环体所需的代码个数。

折中方法

在对空间与时间进行权衡时，还可以考虑一种折衷的办法，即部分展开循环。如上例展为：

5.3 归纳变量的优化和条件判断的替换

归纳变量(induction variable): 在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为归纳变量(induction variable)。即若当前执行循环的第 j 次迭代，归纳变量的值应为 c * j + c’ , 这里 c 和 c ’都是循环不变式

5.4 其它循环优化方法

• 把多重嵌套的循环变成单层循环。
• 把 n 个相同形式的循环合成一个循环等。

in_line 展开

• 把过程（或函数）调用改为 in_line 展开可节省许多处理过程（函数）调用所花费的开销。
• 省去了函数调用时参数压栈，保存返回地址等指令。
• 这也仅仅限于简单的函数。
  

12 目标代码生成

P381: 第 1，4，5，6 题

1 四种指令集架构 写指令序列

2 运行栈和静态数据区

3 启发式图着色算法

4 X86 汇编代码

1 现代微处理器体系结构简介

1.1 指令集架构

以 C=A+B 为例

1. 栈式指令集架构
   PUSH A
   PUSH B
   ADD
   POP C
2. 累加器式指令集架构
   LOAD A
   ADD B
   STORE C
   代码短了，开销不一定小。直接访问内存
3. 寄存器架构
   • 寄存器-内存指令集架构 CISC
     LOAD R1, A
     ADD R3, R1, B
     STORE R3, C
   • 寄存器-寄存器指令架构 RISC
     LOAD R1, A
     LOAD R2, B
     ADD R3, R1, R2
     STORE R3, C
     区别：是否可以直接内存寻址
     共性：内部有多个寄存器可以直接作为 ALU 指令的任一操作数
     优点：
   • 减少内存访问
   • 减少指令数

1.2 存储层次架构

• 为了提高效率，应尽可能少地访问寄存器之外的存储设备

  • 但寄存器的数量极其有限，所以分配策略很重要
  • 对缓存的利用，对于大型数据结构有用
    • 缓存的管理单位是：缓存行。（数十或上百字节）
    • 每次从内存载入的是一组地址连续的数据，而不仅仅是被访问数据

• 因此，出现了循环交换（Loop Interchange）

  • c 语言存储是行优先，因此下面两段代码中第二段代码运行速度更快
    • 第一段代码外层循环是 j（列），内层循环是 i（行）。- 当 j=0 时，内层循环 i 从 0 到 4999，访问的是 x[0][0], x[1][0], x[2][0], ... x[4999][0]。x[0][0] 和 x[1][0] 在内存中相隔了一整行（100 个元素）的距离。这种访问模式是跳跃式的、非连续的，缓存效率极低。
    • 第二段代码外层循环是 i（行），内层循环是 j（列）。当 i=0 时，内层循环 j 从 0 到 99，访问的是 x[0][0], x[0][1], x[0][2], ... x[0][99]。这种访问模式是连续的、顺序的，缓存效率高。
  • 循环交换就是一种通过改变嵌套循环的内外层顺序，来优化数据访问模式的编译器优化技术或手动优化技巧。

// 代码1
for (j = 0; j < 100; j = j+1)
    for (i = 0; i < 5000; i = i+1)
        x[i][j] = 2 * x[i][j];

// 代码2
for (i = 0; i < 5000; i = i+1)
    for (j = 0; j < 100; j = j+1)
        x[i][j] = 2 * x[i][j];

1.3 流水线

可以通过流水线来提高代码的运行效率

• 如左边的代码按照 I0, I1, I2, I3 的顺序来执行，需要 6 个时钟周期
• 但我们发现 I2 提前运行也不会影响其它代码的运行，因此选择让 I2 提前运行，并和其他代码同步并行运行
  

2 地址空间

• 代码区
  • 存放目标代码
• 静态数据区
  • 全局变量
  • 静态变量
  • 部分常量，例如字符串
• 动态内存区
  • 也被称为内存堆 Heap
  • 程序员管理：C、C++
  • 自动管理（内存垃圾收集器）：Java、Ada
• 程序运行栈
  • 活动记录
  • 函数调用的上下文现场
    • 由调用方保存的一些临时寄存器
    • 被调用方保存的一些全局寄存器

2.1 程序地址空间的实例分析

以 MS-WIN 下的应用程序为例，从高地址到低地址，自上而下的是：

• 静态数据区：全局和静态量表
• 代码区
• 程序运行栈
• 动态内存区：内存堆
  

2.2 程序运行栈的设计

• 子程序/函数运行时所需的基本空间：活动记录
• 进入子程序/函数时分配，地址空间向下生长（从高地址到低地址）
• 从子程序/函数返回时，当前运行栈将被废弃
• 递归调用的同一个子程序/函数，每次调用都将获得独立的运行栈空间，从而保证了递归程序和多线程程序的正确运行

一个典型的运行栈包括 （活动记录）

• 函数的返回地址
• 全局寄存器的保存区
• 临时变量的保存区
• 未分配到全局寄存器的局部变量的保存区
• 其他辅助信息的保存区：例，PASCAL/PL-I 类语言的 DISPLAY 区

3 寄存器的分配和指派

• 寄存器通常分为
  • 通用寄存器
    • X86：EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP, etc
    • ARM: R0~R15, etc
  • 专用寄存器
    • X86：浮点寄存器栈, etc
• 通用寄存器
  • 保留寄存器
    例如，X86 的 ESP 栈指针寄存器，ARM 的返回寄存器 LR
  • 调用方保存的寄存器——临时寄存器
    • 调用方（Caller）在调用函数前，如果需要保留这些寄存器的值，必须自己先保存到栈中（调用后再恢复）；否则，被调用函数修改后，调用方的原有值会丢失。
    • X86：EAX, ECX, EDX
    • ARM：R0~R3, R12, LR
  • 被调用方保存的寄存器——全局寄存器
    • 被调用函数如果要使用这些寄存器，必须先保存其原有值到栈中，函数返回前再恢复
    • X86：EBX, ESI, EDI, EBP （ESP 为运行栈寄存器，不参与寄存器分配）
    • ARM：R4~R11

3.1 全局寄存器分配

• 全局寄存器分配：
  • “全局”相对于“基本块”而言，不是“程序全局”
  • 全局寄存器分配的对象主要是函数的局部变量，包括函数入口参数。
• 分配原则
  • 优先分配给跨基本块仍然活跃的变量，尤其是循环体内最活跃的变量
  • 局部变量参与全局寄存器分配
    寄存器专属于线程！为了线程安全，全局变量/静态变量一般不参与全局寄存器分配。

• 常用全局寄存器分配方法
  • 引用计数
    通过统计变量在函数内被引用的次数，并根据被引用的特点赋予不同的权重，最终为每个变量计算出一个唯一的权值，根据权值的大小排序，将全局寄存器依次分配给权值最大的变量
  • 着色图算法
    通过构建变量之间的冲突图，在图上应用着色算法，将不同的全局寄存器分配给有冲突的变量。

1 引用计数

• 原则：如果一个局部变量被访问的次数较多，那么它获得全局寄存器的机会也较大
• 注意：出现在循环，尤其是内层嵌套循环中的变量的被访问次数应该得到一定的加权
• 分配算法：如果有 N 个全局寄存器可供分配，则前 N 个变量拥有全局寄存器，其余变量在程序运行栈（活动记录）分配存贮单元
• 问题：不再使用的变量不能及时释放寄存器
  如变量 a 在前期大量使用，后端程序中不适用了
• 解决办法：
  • 活跃变量分析、冲突图
  • 着色算法

2 图着色算法

• 一种简化的图着色算法
  步骤：
  1. 通过数据流分析，构建变量的冲突图
  2. 如果可供分配 k 个全局寄存器，那么我们就尝试用 k 种颜色给该冲突图着色

1. 通过数据流分析，构建变量的冲突图
   什么是变量的冲突图？
   • 它的结点是待分配全局寄存器的变量
   • 当两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们之间便有一条边连接。所谓变量 i 在代码 n 处活跃，是指程序运行时变量 i 在 n 处拥有的值，在从 n 出发的某条路径上会被使用（活跃变量分析）。
   • 直观的理解，可以认为有边相连的变量，它们无法共用一个全局寄存器，或者同一存贮单元，否则程序运行将可能出错
   • 无连接关系的变量，即便它们占用同一全局寄存器，或同一存贮单元，程序运行也不会出错
2. 如果可供分配 k 个全局寄存器，那么我们就尝试用 k 种颜色给该冲突图着色

!!!算法 12.2 一种启发式图着色算法

冲突图 G，寄存器数目为 k（假设 k=3）

1. 找到第一个连接边数目小于 K 的结点，将它从图 G 中移走，形成图 G’
   
2. 重复步骤 1，直到无法再从 G’中移走结点
   
3. 在图中选取适当的结点，将它记录为“不分配全局寄存器”的结点，并从图中移走
   
4. 重复步骤 1~步骤 3，直到图中仅剩余 1 个结点
   
5. 给剩余的最后一个结点选取一种颜色，然后按照结点被移走的顺序，反向将结点和边添加进去，并依次给新加入的结点选取颜色。（保证有链接边的结点着不同的颜色）
   

3.2 临时寄存器分配

为什么在代码生成过程中，需要对临时寄存器进行管理？

• 因为生成某些指令时，必须使用指定寄存器
• 临时寄存器中保存有此前的计算中间结果

临时寄存器的管理原则和方法

• 临时寄存器的生存范围
  • 不超越基本块
  • 不跨越函数调用
• 临时寄存器的管理方法：寄存器池

临时寄存器的分配和管理方法

• 进入基本块时，清空临时寄存器池
• 为当前中间代码生成目标代码时，无论临时变量还是局部变量（亦或全局变量和静态变量），如需使用临时寄存器，都可以向临时寄存器池申请
• 临时寄存器池接到申请后，
  • 如寄存器池中有空闲寄存器，则可将该寄存器标识为被该申请变量占用，并返回该空闲寄存器
  • 如寄存器池中没有空闲寄存器，则选取一个在即将生成代码中不会被使用的寄存器写回相应的内存空间，标识该寄存器被新的变量占用，返回该寄存器
• 在基本块结尾，或者函数调用发生前，将寄存器池中所有被占用的临时寄存器写回相应的内存空间，清空临时寄存器池

4 指令选择

不同的体系结构采用了不同类型的指令集，由于体系结构和指令集的差异，使得在生成代码时需要采用不同的指令选择策略