钟鼓楼

一、定义

$k$ 阶、齐次、常系数、差分方程

$$y_{n + k} + a_{k - 1}y_{n + k - 1} + a_{k - 2}y_{n + k - 2} + \dots + a_0y_{n} = 0$$

$k$ 阶、非齐次、常系数、差分方程

$$y_{n + k} + a_{k - 1}y_{n + k - 1} + a_{k - 2}y_{n + k - 2} + \dots + a_0y_{n} = f(n)$$

$k$ 阶、齐次、常系数、差分方程的特征方程

$$\lambda_{n + k} + a_{k - 1}\lambda_{n + k - 1} + a_{k - 2}\lambda_{n + k - 2} + \dots + a_0\lambda_{n} = 0$$

---

一、例子

之后的所有讲解，都是基于这个例子的，所以在头部统一列出

假定某消费者购房需要贷款 30 万元，期限为 30 年，已知贷款年利率为 5.1%，问每月应还款多少？

符号约定如下

一、正交矩阵

正交矩阵的定义如下

$$UU^T = I$$

$UU^T$ 这种写法虽然看似独特，但是并不是很晦涩的，当我们形容向量 $X$ 与其自身做内积的时候，用的就是 $XX^T$，$UU^T$ 无非是利用“矩阵可以看成向量组”的特性，对于多个向量同时进行内积运算，当

$$UU^T = diag$$

也就是只要结果是一个对角阵，就说明 $U$ 里面的向量彼此之间是正交的（也就是内积结果为 0），而 $UU^T = I$ 这个条件相比于彼此正交要更加强，他指的是不但正交，而且具有一种归一化的性质。

将 $U$ 用于变换，产生的结果被称为“正交变换”，也就是“旋转，轴对称”这种保持图形形状和大小不变的变换。

一、直观意义

行列式（determinant）可以看做在多维空间上的向量组形成“有向体积”，这种认识可以辅助我们理解一些性质：

• 可以利用行列式求解四边形面积、六棱锥体积。

• 交换构成行列式的向量，并不会改变行列式的绝对值，而可能会改变行列式的正负。这是因为改变边的顺序不会影响体积。

• 一旦有一行或者一列为 0，或者这个方阵没有满秩，就会导致行列式为 0。某一个向量为 0，肯定会导致体积为 0，当没有满秩，就说明有两条“边”方向重合了，也会导致体积为 0。

• 将一行（列）的 $k$​ 倍加进另一行（列）里，行列式的值不变。类似于固定了底面和高，其实第三条楞只要在平行于底面的边上变化，就不会导致体积的改变

  $${\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\a_{j1}&a_{j2}&\dots &a_{jn}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}}={\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\a_{j1}{\color {blue}+ka_{i1}}&a_{j2}{\color {blue}+ka_{i2}}&\dots &a_{jn}{\color {blue}+ka_{in}}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}}$$

• 在行列式中，某一行（列）有公因子 $k$，则可以提出 $k$。类似于一条边的倍数发生变化的时候，会导致体积的倍数发生相同的变化。

  $${\displaystyle D={\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\ddots &\vdots \\{\color {blue}k}a_{i1}&{\color {blue}k}a_{i2}&\dots &{\color {blue}k}a_{in}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\color {blue}k}{\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\ddots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\color {blue}k}D_{1}}$$

• 在行列式中，某一行（列）的每个元素是两数之和，则此行列式可拆分为两个相加的行列式。类似于在计算高的时候，将高拆分成两个部分计算。 $${\displaystyle {\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\ddots &\vdots \\{\color {blue}a_{i1}}+{\color {OliveGreen}b_{i1}}&{\color {blue}a_{i2}}+{\color {OliveGreen}b_{i2}}&\dots &{\color {blue}a_{in}}+{\color {OliveGreen}b_{in}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\ddots &\vdots \\{\color {blue}a_{i1}}&{\color {blue}a_{i2}}&\dots &{\color {blue}a_{in}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}+{\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\ddots &\vdots \\{\color {OliveGreen}b_{i1}}&{\color {OliveGreen}b_{i2}}&\dots &{\color {OliveGreen}b_{in}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}}$$

---

一、理论

• 前端：分析部分，包括词法和语法分析，符号表建立，语义分析，中间代码生成，错误处理
• 后端：综合部分，包括与机器有关的代码优化，目标代码生成，符号表操作，错误处理
• 编译有 5 个阶段，分别是：词法分析，语法分析，语义分析和中间代码生成，代码优化，生成目标程序。有两个事件贯穿其中，即符号表管理和错误处理。也就组成了 7 个逻辑部分。
• 字母表和符号串
  • 符号：可以理解为一个个的字母，比如说 $a, b, c, \phi$
  • 字母表：是符号的集合，比如说 $\sum = \{a,b,\phi\}$
  • 符号串：是符号的序列：比如说 $abababa$
  • 空符号串：无任何符号的符号串，即 $\epsilon$
  • 符号串集合：由符号串构成的集合
  • 语言：一种特殊的符号串集合
• 文法就是语法，规定了语言的结构。
• 左递归文法只是无法采用自顶向下的分析方法，并不是一无是处

• 运行时存储组织与管理要回答的问题是

  • 数据结构在内存里是如何表示的

  • 函数在内存中是如何表示的

    • 需要记住调用前的状态,以便在调用结束后返回。
    • 需要提供一种办法,在调用函数和被调函数之间传递参数,返回值
    • 满足 Scope 的要求,能够找到所有的数据结构

  • 他们在内存中如何放置,如何管理（这里面有个专题是垃圾回收机制）

  • 感觉这里很有意思，操作系统将内存封装成了一个数组，编译器决定了这个数组的使用方式。
• 存储管理主要有两个方面：
  • 静态存储管理，对应的就是实验中对于 .data 的处理
  • 动态存储管理，这部分在编译实验中被拆成了两个部分，一个部分在 llvm 翻译的时候完成，比如说栈式符号表之类的东西就出现在此处，一部分在 mips 翻译的时候完成，比如说函数运行栈的结构。这就导致似乎没法建立一个统一的体系，只能说和理论在表面上看有些出入。
• 非分程序的结构语言：每个可独立进行编译的程序单元时一个不包含有子模块的单一模块。如 FORTRAN 语言。另外常说的 Module 这个概念，也可能是来自这个语言
• IR(Intermediate representation)：不同层次的 IR 代表了不同层次的抽象(类型、操作)通过分层抽象,实现最大限度的重用。
• 错误分类：
  • 语法错误：不符合词法和语法规则的错误。
  • 语义错误：
    • 程序不合语义规则。比如说未定义，就使用。
    • 超越具体计算机系统的限制，比如说栈溢出，类型溢出等。

二、压缩文法

需要压缩文法包括两种：

• 有害规则，就是 $U::=U$ 这种，这种十分显然，所以就不说了。
• 多余规则，针对语法规则的左部（左部是一个符号），又分为
  • 不可达符号：就是这个左部没法由识别符号推出，那么就是不可达的。这种非常好识别，只需要进行一个符号的 BFS 即可。
  • 不活动符号，就是形如 $A ::= Aa $ 这样的规则，会导致一直循环，没完没了。

一、构造控制流图（CFG）

关于优化，真的是一个令人生畏的事情，大致来说，一个优化分为两个部分：

• 分析
• 改写

但是在课程中大多只交第一个部分，而不讲第二个部分，这就导致一种“无意义性”，如果分析不能用于改造程序，那么就没有什么学习的动力。所以如果想要学好理论，那么必须要有一个宏观的角度去看发生的一切事情。

按照 《Engineering a Complier》的观点，按照优化的范围去给优化分类，大致可以分为以下四类

类型	范围	举例
局部优化	限制在某个基本块中	公共子表达式提取，局部值编号，树高平衡，窥孔优化
区域性优化	某几个有联系的基本块	循环展开
全局优化（过程内优化）	组成一个完整过程的基本块	图着色寄存器分配
过程间优化	多个过程	函数内联，过程间常数传递

至于为什么有这么多分类，是因为优化是一个很严谨而且需求具有多样性的事情，不同的范围对应的条件和限制是不一样的，那么可以进行优化的力度和策略也就是不一样的。

对于局部优化，因为它在一个基本块内，所以有两个极好的性质可以应用

• 语句是顺序执行的。
• 如果一条语句被执行，那么整个基本块的语句都会被执行。

从某种意义上讲，基本块让人们不再直面指令，而是变成面对一个数据流图。

而其他三种方法，都需要建立在对于 CFG 图上，也就是说，首先就是分析 CFG 图。另外还有一段话很有意思：

在进行区域性优化的时候，我们可以考虑通过某种图论性质定义的 CFG 子集，比如说支配图或者强联通分量。

通过一道题来介绍一下分法，不过介绍之前，还是说一下，此时的代码一定是 ir 了，但是对于课设用到的是那种 ir 呢？应该是某种神秘的四元式（这里插一嘴，llvm 也可以被认为成一种神秘四元式，即只有一小部分指令有大于 2 个的操作数）。

有三条规则：

• 程序入口第一条语句
• 任何可以被当做跳转目标的语句
• 跳转语句后面的一条语句