钟鼓楼

一、线性规划（LP）

1.1 标准型

线性规划可以转化成标准型，但是可以发现有两种标准型，分别对应软件程序和数学形式，如下所示：

LP 求解器一般接口

一、定义

$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 $ 这样的规则，会导致一直循环，没完没了。