大学期间的笔记补全。编译原理内容太多分几次。
课本《编译原理》第三版，陈火旺等编著。
笔记总目录：
一、引论
二、高级语言及其语法描述
三、词法分析
四、语法分析——自上而下分析
五、语法分析——自下而上分析
六、属性文法和语法制导翻译
七、语义分析和中间代码生成
八、优化
九、目标代码生成

编译原理结束！

六、属性文法和语法制导翻译

6.1 属性文法

在上下文无关文法的基础上，在描述语义动作时，为每个文法符号（终结符和非终结符）配备若干相关的“值”，如“类型”，“地址”等，称为属性。

对文法的每个产生式配备一组属性计算规则称为语义规则。

每个文法符号联系于一组属性，且对每个产生式都给出其语义规则的文法称为属性文法。

6.1.1 属性和语义规则

1. 属性的特征

   • 代表与文法符号相关信息，如类型、值、代码序列、符号表内容等；
   • 可以进行计算和传递；

2. 属性的分类

   • 综合属性

   • 继承属性

     
     
     继承属性

   对于一些产生式中的属性而言，

   任意一个产生式左边的非终结符带有的属性是：

   • 综合属性：产生式右边包含语法生成树子节点的属性，
   • 继承属性：产生式右边仅仅由语法生成树兄弟节点或父节点属性构成。

   若所有产生式（不再有还未写出的产生式），属性仅在产生式右边的非终结符出现，则是继承属性。

3. 注意：

   • 终结符只有综合属性，由词法分析器提供。

   • 非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

   • 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性；

     出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。

     这也是为什么之前说的时候前提是 “对于一个产生式中的属性而言“。

4. S-属性文法

   仅仅使用综合属性的属性文法。

   • 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。
   • 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。

   S-属性文法非常适合配合LR分析法进行计算。

5. L-属性文法

   如果每个产生式的每条语义规则计算的属性 的综合属性；或者是 的继承属性，但它仅依赖：

   • 该产生式中 左边符号 的属性；
   • 的继承属性

   S-属性文法属于L-属性文法。

   左递归文法不可用LR(1)分析法。

6.2 语法制导翻译

直观上说就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并且在语法分析的同时执行它。

语义动作一方面规定了产生式产生的符号串的意义，另一方面又按照这种意义规定了生成中间代码应做的基本动作。

定义：在语法分析过程中，当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，此产生式对应的语义子程序进入工作，完成既定翻译任务，产生中间代码。

1. 作用

   • 如果语义动作不是简单的计值程序，而是某种中间代码的产生程序，那么随着语法分析的进展，这种代码也逐步生成。

   • 语法制导翻译的作用

     • 产生中间代码
     • 产生目标指令
     • 对输入串进行解释执行

七、语义分析和中间代码产生

7.1 中间语言

中间语言（复杂性界于源语言和目标语言之间）的好处：

• 便于进行与机器无关的代码优化工作
• 易于移植
• 使编译程序的结构在逻辑上更为简单明确

7.1.1 常用中间语言

1. 后缀式，逆波兰表示

   • 表达式：-(a+b)*(c+d)-(a+b+c)
   • 后缀式：ab+-cd+*ab+c+-

2. 图表示

   • DAG
   • 抽象语法树

3. 三地址代码

   • 三元式
   • 四元式
   • 间接三元式

7.1.2 三地址代码

1. 四元式

   一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result。

   例子：计算a:=b*(-c)+b*(-c)：

   
   
   计算过程
   • 四元式之间的联系通过临时变量实现。
   • 单目运算只用arg1域，转移语句将目标标号放入result域。
   • arg1,arg2,result通常为指针，指向有关名字的符号表入口，且临时变量填入符号表。

7.2 说明语句

7.3 赋值语句的翻译

翻译模式

7.4 布尔表达式的翻译

• 布尔表达式：用布尔运算符把布尔量、关系表达式联结起来的式子。

  • 布尔运算符：and, or, not ；
  • 关系运算符 ＜,≤,＝, ≠，＞ ,≥

• 布尔表达式的两个基本作用:

  • 用于逻辑演算,计算逻辑值;
  • 用于控制语句的条件式.

• 产生布尔表达式的文法:

  • E→E or E | E andE | E | (E) | id rop id | id
  • 运算符优先级：布尔运算由高到低：not > and > or，同级左结合关系运算符同级，且高于布尔运算符

• 两种计算方法：

  1. 计算逻辑值

     • 如同计算算术表达式一样,一步步算
     • 采用优化措施（短路计算）

  2. 作为条件控制：

     条件语句 if E then S1 else S2 。赋予 E 两种出口：一真一假。
     

     6-3.png

     if语句（条件语句）的四元式怎么写？

     • 和 ：因为在归约B的时候并不知道 以及他们的入口地址，跳转位置不明确，所以必须要把跳转信息记录下来等待之后补充具体跳转的地址。故将跳转信息存入 。

     • 两遍扫描

       • 为给定的输入串构造一棵语法树；
       • 对语法树进行深度优先遍历，进行语义规则中规定的翻译。

     • 如何一遍扫描？

       四元式merge时改变的第四位的数值不是表示跳转，而是表示（暂时的）链接，便于之后找到了跳转地址全部遍历重写。

       四元式序列求解过程
       
       
       思路总结_1
       
       
       思路总结_2
       
       
       思路总结_3

7.5 控制语句的翻译

控制语句在归约的时候：

• if-then-else：只有N的时候会产生jump中间语句，其他操作都只是改变跳转地址
• while-do：只需要在最后生成新的jump中间语句，其他操作都只是改变跳转地址

If语句的翻译

if语句翻译

• N的作用：为了在if-then-else归约时不需要在两种结果之间加上强制跳出的中间代码。

while语句的翻译

while语句翻译

• 不需要N，因为跳转语句插入在末尾，不需要复杂的操作。
• while-do语句在归约为 时要产生一条中间代码，用户在do的内容执行完之后跳回while的开始重新循环
• while-do语句归约后false的出口地址写成 。
• 只要是 （Statement）归约出来时，一定会产生一个空链表指向next（但不会产生中间代码）

goto语句

• goto L1 有两种情况：

  1. 先定义L1，再出现goto L1
  2. 先出现goto L1（L1地址未知），再出现L1

• 解决：符号表

  当出现情况1，扫描到L1时先将L1的信息填入符号表，定义否为“是”，地址为L1的起始地址

  当出现情况2，每当扫描到goto却没有L1，先将L1插入，定义否为“否”，地址为goto语句的next信息；直到扫描到L1，将定义否改为“是”，为地址中goto语句的next信息赋值，再将地址改为L1的起始地址。

  名字	类型	定义否	地址
  L1	标号	是/否	L1起始地址 / 传递的goto语句的next

case语句

• 翻译法1：L1-if-goto-L2-if-goto-......
• 翻译法2：L1-L2-......-if-goto-if-goto-......

7.6 过程调用的处理

• 过程调用文法：
  • S -> call id (Elist) ：for队列queue中的每一项p，有emit('param' p)；循环之后emit('call' id.place)
  • Elist -> Elist, E ：将E.place加入到queue的队尾
  • Elist -> E ：初始化queue仅包含E.place

八、优化

优化：对程序进行等价变换，使得从优化后的程序出发，能生成更有效的目标代码。

8.1 概述

1. 优化原则：
   • 等价原则：优化前后不改变程序运行结果
   • 有效原则：使优化后产生的目标代码运行时间较短，占用储存空间较小
   • 合算原则：较低的代价取得较好的效果
2. 三个不同级别
   • 局部
   • 循环
   • 全局
3. 优化的种类
   • 删除多余运算（删除公用子表达式）
   • 复写传播
   • 删除无用赋值
   • 代码外提（循环等）
   • 强度消弱（如：幂运算->乘法运算，乘除->加减）
   • 变换循环控制条件
   • 合并已知量（包括一些简单的预计算）

8.2 局部优化

1. 基本块：

   指程序中一顺序语句执行序列，其中只有一个入口（第一条语句）和一个出口（最后一条（goto）语句）

   一条三地址语句x:=y+z，则称x定值并引用y和z。

   活跃：某个变量是活跃的，意味着这个变量在之后的程序（此基本块或其他基本块）中被引用。

   • 划分基本块：

     • 求出入口语句

       • 第一个语句

       • 能由条件转移/无条件转移语句转移到的语句

       • 紧跟在条件转移语句后面的语句

         无条件转移后面的语句不作为入口语句原因：下一句除非有别的语句跳转（在跳转逻辑被作为入口），否则永远都无法被访问到，不需要作为入口语句。

     • 确定基本块

       • | 入口语句 -> |下一个入口语句
       • | 入口语句 -> 转移语句 |
       • | 入口语句 -> 停语句 |

     • 未被纳入某一基本块的语句从程序中删除

2. 基本块中的优化措施

   • 删除公共子表达式
   • 删除无用赋值
   • 合并已知量
   • 临时变量改名
   • 交换语句的位置
   • 代数变换

3. 基本块的DAG表示

   基本块的DAG是一种带有下述标记或附加信息的DAG

   • 叶节点以一标识符或常数作为标记，表示该点代表该变量或常数的值

   • 内部节点以一运算符作为标记，表示该节点应用该运算符对其后继节点的值进行运算

   • 任意节点可能附加一个或多个标识符，表示这些变量具有该节点所代表的值

     
     
     构建DAG_1
     构建DAG_2
     构建DAG_3

8.3 循环优化

九、目标代码生成

9.1 基本问题

代码生成是把语法分析或优化后的中间代码变换成目标代码。

着重考虑的问题：

• 目标代码长度
• 充分利用寄存器，减少访问贮存器的次数
• 充分利用指令系统的特点

代码生成器的输入：源程序中间代码，符号表的信息

代码生成器的输出：目标代码（3种形式：立即执行的机器语言代码、待装配的机器语言模块、汇编语言代码）

考虑方法：

1. 指令选择
2. 寄存器分配
3. 计算顺序选择

9.2 目标机器模型

机器指令_1

机器指令_2

9.3 一个简单的代码生成器

简单的代码生成器_1

简单的代码生成器_2

1. 计算信息

   计算信息_1
   计算信息_2
   计算信息_3

2. 分配寄存器

   尽量延迟 STORE 的时间。

   
   
   寄存器分配