进程管理

进程

进程是处于执行器的程序和资源总称。而线程是进程中活动的对象，拥有独立的pc（程序计数器），进程栈和一组寄存器集。内核调度的对象是线程，而不是进程。

进程提供了虚拟机制——虚拟处理器和虚拟内存。这使得进程虽然可能是在共享一个处理器，但看起来像是拥有独立的内存地址和处理器。

在Linux中，进程通过fork创建一个新的进程，而fork又是clone()系统调用的结果。fork()系统调用从内核返回两次，一次回到父进程，一次回到子进程。然后可以调用exec()这组函数载入新的程序，创建新的地址空间，执行程序。

程序可以通过exit()系统调用退出，释放掉该进行所占有的资源。

父进程可以通过wait()查询子进程是否终结，终结的进程处于僵死状态，直到父进程调用wait()相关的系统调用。

进程描述符及任务结构

内核把进程的列表存放在task list的双向循环链表中，链表中每个结点类型为task_struct，该结构比较大，包含了一个进程所有信息。打个比方：

1
2
3
4
5
6

struct task_struct
{
    // ...  
    void *stack;    //  指向内核栈的指针  
    // ...
};

分配进程描述符

使用slab分配器动态生成task_struct，并且在堆栈的低地址区创建一个新的结构struct thread_info，该结构用来存放特定体系结构的汇编代码段需要访问的那部分进程的数据，这是因为Linux内核是支持不同体系的。然后在thread_info中嵌入指向task_struct的指针。

进程描述符的存放

内核通过一个唯一的进程描述符来标识每个进程——PID，最大值默认设置为32768，也就是允许同时存在进程的最大数目。

有些体系结构会把当前的task_struct放在特定寄存器里，有些体系结构则是通过thread_info，然后计算偏移间接查找task_struct，比如x86

进程状态

系统进程必然属于以下五种状态之中：

• TASK_RUNNING：该状态的进程可以在CPU上运行，或正在执行，或是在运行队列中等待执行，合并了常见操作系统书中——running和ready的两种状态
• TASK_INTERRUPTIPLE：该进程被阻塞，正在等待某些条件达成，比如等待socket的连接，某些信号的接收
• TASK_UNINTERRUPTIPLE：在该状态下，即便是接收到某些信号（比如kill ），该进程也不会被中断。这种状态用的比较少，一般用在不想被干扰的进程。比如内核的某些处理流程是不应该被中断，或者在进行硬件操作的时候，一旦进程被中断，就可能造成设备不可控
• __TASK_TRACED：被其它进程跟踪的进程，例如调用ptrace或者gdb进行调试的时候
• __TASK_STOPPED：进程停止执行，这种情况发送在接收到SIGSTOP,SIGTSTP,SIGTTIN,SIGTTOU等信号的时候

设置当前进程状态

使用该函数：

1
2

#include<linux/sched.h>
set_task_state(task, state);

进程家族树

Unix的进程之间存在着继承关系，所有进程都是PID为1的init进程的后代

进程创建

进程创建主要是先在新的地址空间里创建进程，然后读入可执行文件。一般可以将这些步骤分解到fork()和exec()两个函数去做。

写时拷贝

为了提高效率，内核在创建进程的时候采用的是写时拷贝，这种方法共享父进程的数据，在没有发生写入的时候，是不会复制数据，拥有新的拷贝。

线程在Linux中的实现

其实在Linux中是没有线程这一概念的，Linux把所有线程当做进程来实现，所以每个线程都会有自己的task_struct，只是线程之间会共享某些资源。

线程创建

线程的创建和进程类似，只是在线程创建的时候提供某些标识参数，以确保它们共享某些资源。

内核线程

内核线程可以用来执行某些内核在后台的工作，内核线程是没有独立的地址空间的，它只在内核空间运行，不会被切换到用户空间。

进程终结

进程的终结可能是显式调用exit系统调用，也可能是从程序主函数返回。然后进程会调用do_exit()去释放相关资源，进程进入EXIT_ZOMBIE状态，该状态的目的就是向父进程提供信息，由父进程检索或者通知内核后，释放进程的剩余内存，归还给系统。

如果子进程处于zombie状态，但是父进程已经退出了，会给子进程在当然的线程组中找一个线程作为父亲，或者使用init进程作为父亲。一旦找到了新的父进程，就不会有zombie进程占用内存的问题了，init进程会例行调用wait()来检查子进程，清除zombie进程。

Redis学习《一》

Redis 简介

Redis是一个远程的，高性能的，内存数据库。Redis有几个特点：

• 性能高——读写速度比传统数据库更快；
• 数据类型丰富——支持二进制的strings，lists，hash，sets和ordered sets五种类型；
• 支持数据备份——拥有两种不同形式的持久化方法，可以用小而紧凑的格式将内存中的数据写入到磁盘；

Redis安装

在Ubuntu下安装：

1
2

$sudo apt-get update
$sudo apt-get install redis-server

我用的是docker-redis：

1

$docker search redis

1
2

$docker pull redis
$docker run -p 6379:6379 -v $PWD/data:/data  -d redis redis-server --appendonly yes

命令说明：

-p 6379:6379 : 将容器的6379端口映射到主机的6379端口

-v $PWD/data:/data : 将主机中当前目录下的data挂载到容器的/data

redis-server --appendonly yes : 在容器执行redis-server启动命令，并打开redis持久化配置

1

docker exec -it 43f7a65ec7f8 redis-cli

执行redis-cli命令连接刚启动的容器服务器

redis基本类型

Backpropagation and Neural Networks

计算图：每个节点表示一个计算步骤

反向传播：链式法则的递归调用

用微积分可能无法求解

可以组合某些结点成更复杂的结点，只要能求解导数即可

add gate, max gate

如果有一个结点连接到了多个结点

雅克比矩阵

方向转播：利用链式法则递归计算表达式的梯度的方法

简单理解

其实学过微积分的同学应该都能理解导数的含义，简单概括就是变量变化导致的函数在该变量方向上的变化率，指明了整个表达式对于该变量的敏感度。 \[ f(x, y) = x + y -> \frac{df}{dx} = \frac{df}{dy} = 1 \] 同样对于取最大值的操作： \[ f(x, y) = max(x, y) -> \frac{df}{dx} = 1(x>=y) \frac{df}{dy} = 1(y>=x) \]

使用链式法则计算符合表达式

考虑这样的一个符合函数\(f(x, y, z)=(x+y)z\)，将其分为两个部分\(q=x+y和f=qz\)。根据链式法则，将梯度表达式连起来的方式就是相乘： \[ \frac{\alpha f}{\alpha x} = \frac{\alpha f}{\alpha q} \frac{\alpha q}{\alpha x} \]

这个计算线路图展示了计算的视觉化过程，前向传播从输入计算到输出（绿色），后向传播从尾部开始。

反向传播的理解

在前向传播过程中计算两个东西：输出和局部梯度。这样在反向传播的时候，就可以将上游回传的梯度乘以局部梯度。

至于常见的几种单元，诸如加法门单元、取最大值门单元、乘法门单元都比较好理解。例如在线性分类器中，权重和输入进行点积\(w^T x_i\)，假设所有的输入样本都乘以1000，那么权重的梯度将会增大1000倍，这样就必须降低学习率来弥补。

小结

反向传播，简单的理解就是复合函数的链式法则。

参考资料

http://www.cnblogs.com/charlotte77/p/5629865.html

损失函数与优化

##损失函数

线性分类器：高维空间下的线性决策边界。

loss function：判断我们分类器的效果，损失函数有多种版本：softmax和svm

svm的实现公式如下： \[ L = \frac1N\sum_{i}\sum_{j\neq y_i} [max (0, f(x_i, W)_j - f(x_i, W)_{y_i} + 1)] + \alpha R(W) \] 通过上面的公式可看到，如果基于参数集W做出的分类预测与真实情况比较接近，那么计算出来的L就会比较小。因此，我们需要做Optimization，寻找使得顺势函数最小化的参数W的过程。

multiclass svm

如果真实分类的分数比其他类分数高很多（一般我们可以加上一个边界），我们是满意的；否则，我们认为会得到一些loss。

svn损失函数最小值为0，最大值是无穷大，看hinge图。

如果所有的score都接近0，并且相差不大，那么损失函数为C-1。

使得loss为0的W不是唯一的，可以加倍，那么边界也会加倍。

不需要关心分类器在训练集上的表现，避免过拟合。因此，我们可以对loss进行正则化，增加一个正则项。

• L2正则化、L1正则化

softmax classifier

使得概率接近1

刚开始应该是-logC

最优化

SVM损失函数是一个凸函数，但我们最终的目标并不仅仅是对凸函数进行优化，而是能够最优化一个神经网络。

我们使用的策略是follow the slope。即根据梯度在权重空间W中寻找一个方向，沿着该方向能够降低损失函数的损失值。

计算梯度有两种方法：

• 有限差分法

为了计算梯度，我们是在梯度负方向进行更新，这样才能使得损失函数值降低；另外，我们要注意步长的影响，梯度指明了函数在哪个方向是变化率最大的，但步长则指明了在这个方向上走多远。步长也叫学习率。小步长下降稳定，但进度慢，大步长则是进展快，但风险高，容易错过最优点。

从效率来看，有限差分法每走一步就需要计算n次损失函数的梯度（n为参数数量），这是一种效率极低的策略

• 微积分计算梯度

用SVM的损失函数在某个数据点上的计算为例： \[ L_i = \sum_{j\neq y_i} \left[ \max(0, w_j^Tx_i - w_{y_i}^Tx_i + \Delta) \right] \] 然后对函数进行微分。比如对\(w_{y_i}\)进行微分： \[ \nabla_{w_{y_i}} L_i = - \left( \sum_{j\neq y_i} \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) \right) x_i \] 其中1是一个示性函数，如果括号中的条件为真，那么函数值为1，如果为假，则函数值为0。这是对正确分类的梯度，至于不正确的分类的梯度计算： \[ \nabla_{w_j} L_i = \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) x_i \] 以下就是，在梯度下降过程中，我们计算权重的梯度，然后使用它们来实现参数的更新

图像分类

数据驱动方法

图像识别时，计算机接收图像，并从固定的标签从选择一个标签，计算机看到的图像其实是一个多维数组。

但改变相机角度，环境光度，图像变形，遮挡，与背景重叠，类内差异等情况，计算机的识别算法应该是robust的。

实际上，我们不会考虑为某个是别的物体硬编码某个规则，而是收集图像数据和标签，然后用机器学习去训练分类器，再利用分类器去预测标签。这就是一种数据驱动的算法。

在比较图像时，我们可以使用L1 distance: \(d_1(I_1, I_2)=\sum_{p}|I_1^2-I_2^2|\)

对于NNC，最近邻分类器，它的train是O(1)，而predict是O(N)，而我们希望的是训练可以慢一点，而测试要快一点。另外就是，最近邻可能会使得分类不够泛化，因此我们使用knn来解决这个问题。

下面这张图很好地表示了knn带来的效果，使得分类更加平滑：

k最近邻算法

L1距离有坐标依赖，如果特征有特别的意义，一般选择L1距离。但最好都尝试一下。

L2距离

k和distance：hyperrparameters

超参数的设置：

• 将参数分为三组：train、validation、test，validation选择参数。
• cross-validation：将数据分成多组，轮流将每组选做validation，然后平均其结果。

knn很少在图像上使用，一方面是太慢了，另一方面则是距离向量的计算不适合图像像素

线性分类I

相对于knn，线性分类需要参数。

image->f(x, W)=Wx+b->10 number giving class scores

打个比方，以下的图可以看作

对于图像来说，我们可以将图像想象成高维空间的一个点，线性分类器就是一条分割线。

问题

1. 搭建环境时遇到了这个问题

   Unable to compile python Pillow

也就是无法编译pillow，导致在virtualenv中无法pip要求的库。从这里找到了答案：https://github.com/Microsoft/WSL/issues/256，把依赖装上

sudo apt-get install libtiff5-dev libjpeg8-dev zlib1g-dev libfreetype6-dev liblcms2-dev libwebp-dev tcl8.6-dev tk8.6-dev python-tk

2. 用脚本，下载数据集太慢了，还不如手动下载
3. pip install -r requirements.txt 时遇到了site无法安装，按照这里的说法，site是内置的。

site is internal to the Python interpreter, and is used to initialize machine-specific details of your Python installation.

What's telling you that you need to install this module? Ignore it. It's wrong.

活跃分析

liveness analysis：编译器在分析程序的中间表示时，需要确定哪些临时变量同时被使用。如果一个变量的值将来还需要使用，那么这变量就是live的。

为了对程序进行分析，我们可以看这样的控制流图：

因此可以得出：a的活跃范围是[1->2, 4->5->2]，b的活跃范围是[2->3,3->4]，至于变量c，在进入这段程序时就是活跃的，它有可能是一个形参。如果c是局部变量，活跃分析就可以发现它未初始化，从而给出warning。

数据流方程的解

活跃性：一个变量在一条边上的活跃是指，如果存在一条从这条边指向该变量的一个use的有向路径，并且路径不经过该变量的任何def。

活跃性计算

入口和出口活跃信息：

• 如果一个变量属于use[n]，那么它在结点n是入口活跃的；
• 如果一个变量在结点n是入口活跃，那么它在所有属于pred[n]的结点m中都是出口活跃的；
• 如果一个变量在结点n是出口活跃的，而且不属于def[n]，那么该变量在结点n是入口活跃的；

为了加快迭代速度，我们可以沿着箭头的反方向追踪

集合的表现

表示数据流方程的集合至少有两种较好的方法：位数组或有序变量表。

集合稀疏的可以用有序表；集合密集的话，应该用位数组。

时间复杂度

实际的算法运行时间在\(O(N)-O(N^2)\)之间

最小不动点

数据流方程的任何一个解都只是保守的近似解，它提供的是报收信息，虽然不够准确可以得到非最优的方程，但绝不会是错误的程序。

静态活跃性与动态活跃性

动态活跃：如果程序的某个执行从结点n到a的一个使用之间没有经过a的任何定义，那么变量a在结点n是动态活跃；

静态活跃：如果存在一条从n到a的某个使用的控制流路径，且此路径上没有a的任何定义，则是静态活跃的；

冲突图

阻止将变量a和b分配到同一个寄存器的条件就叫冲突（interference）。冲突可以用无向图表示，图中的结点表示变量，每条边连接相冲突的两个变量。

添加冲突边的方法：

• 对于任何对变量a定义的非传送指令，以及在该指令处是出口活跃的变量\(b_1,...,b_j\)，添加冲突边\((a, b_1),...,(a, b_n)\)；
• 对于传送指令a<-c，如果变量\(b_1,...,b_j\)在该指令处是出口活跃的，为每一个不同于c的\(b_i\)添加冲突边\((a, b_1),...,(a, b_j)\)

贝叶斯分类器

贝叶斯决策论

先来看几个公式：

• 条件风险：

其中λij是将一个真实标记为cj的样本错分类为ci所产生的损失，这里的条件风险也叫作expected loss

• 总体风险

R(h) = Ex[R(h(x)|x)]

其中，h就是我们希望找到的准则，使得R(h)最小化，显然只需要在每个样本上选择那个能使得条件风险R(c|x)最低的类别标记，即**h*(x) = arg min R(c|x)**

因此R(h)就是贝叶斯风险，而1-R(h)则反映了分类器能到达的最好性能。

若将误判损失λij表示为：λij = 1，if i = j; λij = 0, otherwise

那么条件风险将变成：

因此贝叶斯最小分类器就变成了：h*(x) = arg max P(c|x),然后根据贝叶斯定理有： 如果要根据贝叶斯判断准则来最小化决策风险，那么就要获得后验概率P(c|x)，总体有两种策略：给定x，通过直接建模P(c|x)来预测c，这叫discriminative models；也可以先对联合概率分布P(x, c)建模，由此得到P(c|x)，这是generative models。一般来说，决策树，BP神经网络，支持向量机，都是前者。

极大似然估计

这里的介绍说的很好，结合一下：https://www.zhihu.com/question/20447622

最好的理解就是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。

举个例子，麻袋里有白球和黑球，抽取十个球，有放回地抽到了七个黑球和三个白球，那么如果我们需要估计黑白球的比例时就可以用极大似然估计。假设抽到黑球的概率为p，也就是求解导致这个结果的参数值的最大可能性：P(七个黑球)=p7 (1-p)*3。要使得概率最大，那就需要求导。

往往求导之前，我们需要取对数，这样就变成了线性相加，避免下溢。

需要注意的是，这种方法需要预先假设概率分数，因此这十分依赖假设的概率分布是否符合真实数据分布。

朴素贝叶斯分类器

基于上面的贝叶斯公式可以看到，计算后验概率的主要困难是条件概率P(x|c)为所有属性上的联合计算，很难直接估计而得。为了避开这个问题，朴素贝叶斯分类器(naive Bayes classifier)采用了属性条件独立性假设。则将贝叶斯公式写成

由于对所有的类别P(x)都是一样的，因此贝叶斯的判断准则就变成了这样的分类器

假设Dc表示训练集D中第c类样本组成的集合，那么

对于离散属性则有

至于连续属性，则可考虑使用概率密度函数，假定

需要注意的是，若某个属性值在训练集中没有与某个类同时出现过，如果直接进行概率估计，那么概率就为0，在分类器的公式计算结果最后也为0。为了便民其它属性携带的信息被该属性值抹去，我们需要在估计概率值时进行拉普拉斯修正。则上面的式子会被修正为（其中N为类别数）：

半朴素贝叶斯分类器

在上面一节中，我们提到了用属性条件独立性假设来降低计算后验概率P(c|x)的困难，但独立性在现实中很难成立。因此人们便提出了半朴素贝叶斯分类器。

半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需要进行完全联合概率计算，也不至于彻底忽略了比较强的属性依赖关系

因此，公式改写成： 其中，为属性的父属性，即所依赖的属性。

那么现在的问题就是如何确定每个属性的父属性，有以下两种方法：

• 一种是假设所有属性都依赖于同一个属性，称为"超父"，即SPODE方法：
• 另一种则是TAN，在最大带权生成树的基础上，将依赖关系简约为树形结构；

AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制，更加强大的独依赖分类器。它会将每个维度的特征属性作为超父来构建SPODE，然后线性组合出最终的模型。

贝叶斯网

贝叶斯网（Bayesian network）借助有向无环图来刻画属性之间的依赖关系，另外还利用了条件概率表来描述属性的联合概率。所以贝叶斯网是由结构G和参数组成的。

结构

贝叶斯网的结构表示了属性间的条件独立性，因此所有属性的联合概率定义为： \[ P_B(x_1,x_2,...,x_d) = \prod_{i=1}^{d}P_B(x_i|\pi_i) = \prod_{i=1}^{d}\theta_&#123;&#123;x_i}|{\pi_i&#125;&#125; \] 下图展示贝叶斯网中三个变量之间的典型依赖关系

我们一个一个看

• 在同父结构中，给定父节点x1的取值，则x3与x4条件独立

• 在V型结构中，给定子结点x4，则x1与x2必不独立，若x4完全未知，则x1与x2独立

• 在顺序结构中，给定x的值，则y与z条件独立，先要通过贝叶斯公式转化

为了分析有向图中变量间的条件独立性，我们可以使用有向分离的方法将有向图转化为无向图，由上面的叙述可以知道除了V型图的非中间节点没有条件独立性之外，其它两个与依赖是否有向是无关的。

基于这种事实，我们可以找出图中所有的V型结构，在V型结构的两个父节点之间加上一条无向边，并且将所有的有向边改为无向边，构成道德图(moral graph)。

在道德图中，如果变量x和y能够被变量z分开，则称x和y被z有向分离，同时具有条件独立性：

学习

如果得到了贝叶斯网的结构，即得到了属性间的依赖关系，那么只需要对训练样本“计数”即对贝叶斯网进行学习。因此我们的首要任务就是找出结构最“恰当”的结构。

为了达到这个目的，我们定义一个评分函数（score function），来评估贝叶斯网与训练数据的契合度。给定训练集D={x1,x2,...,xm}，贝叶斯网B=<G, >在D上的评分函数为： 其中|B|为参数个数，为每个参数需要的字节数，至于LL(B|D)则是贝叶斯网B的对数似然，描述的是B对应的概率分布对D描述得有多好。

推断

贝叶斯网训练好之后就能通过一些属性变量的观测值来推测其它属性变量的取值了。但直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，是一个NP难的问题。

在现实应用中，往往采取的是吉布斯采样（Gibbs sampling）。具体算法原理不大懂，大致的步骤就是首先产生一个与证据变量一致的样本作为初始点，然后每步从当前样本出发产生下一个样本，然后逐个地对非证据变量进行采样以改变其初值。假定经过T次后采样得到的与q一致的样本共有nq个，那么后验概率就是：

EM算法

前面的讨论都是基于所有属性变量的值都已经被观测到了，但很多情况下，训练样本可能是不完整的，那么我们应该怎样对参数进行估计呢。

简单来说就是从某个参数值为起点，执行以下步骤，直至收敛：

• 基于推断隐变量Z的期望，记为；
• 基于已经观测的变量X和对参数做极大似然估计；

Course Introduction

开一个坑，开始学cs231n。其实以前也在学校学过计算机视觉了，对一些算法也有一定的了解，但也仅限于实现一些opencv已有的算法，还不够深入。另外，也学过了吴恩达的机器学习课程。因此，希望以计算机视觉为切入点学一下深度学习，并全面学习计算机视觉。

lecture 1主要讲的是计算机视觉的概述、历史背景以及课程计划，没什么好说的，就开个题吧。

这门课的作业用的是jupyter notebook发布的，毕竟是一门神课，网上有大量的资料，甚至答案。现在2018版本已经出来了，但视频只对Stanford的学生开发，所以我打算看2017的。官方在YouTube发布了视频，但我觉得去b站看即可，还有中文字幕。网站链接：https://www.bilibili.com/video/av17204303/

等到完成了，再来写个总结吧。。。反正也没人看哈哈哈哈

基本块和轨迹

在tree语言中含有一些与机器语言不一致的情况，但我们又必须将tree语言转换成汇编语言或者机器语言，例如

• CJUMP指令能够跳转到两个标号中的任意一个，但真正的机器指令在条件为false时是跳转到下一个指令；
• 在表达式中使用ESEQ会很不方便，因为它会使得子树的不同计算顺序产生不同的结果；
• CALL指令也可能会有问题；

因此我们必须要对任意一棵树进行转换，以避免上述情况：

• 将一棵树重写成不含SEQ和ESEQ的规范树；
• 将这一列树组合成其内不含标号和转移的基本块组合；
• 对基本快并形成一组trace；

规范树

什么是规范树：

1. 无SEQ或者ESEQ
2. 每一个CALL的父亲不是EXP，就是MOVE

ESEQ的转换

消除ESEQ的方法是，在树中一级一级地将它们提升，直至它们可以变成SEQ节点。

下面，介绍四种情况，其中三四两种情况的不同在于s1与e能否交换：

一般，常数和空语句可以与任何语句交换，其它假定不能交换。

一般重写规则

一般而言，对于每一种tree语言或者表达式，都会有等价的子表达式。

例如对于[e1, e2, ESEQ(s, e3)]，需要将s抽取出来放到e2和e1的左边。如果可以交换，则得到(s; [e1,e2,e3])，如果不能交换，则是上图中第三种情况。

利用函数reorder接收一个表达式，并返回由(语句，表达式表)组成的一个偶对。其中语句必须包含所有在表达式表之前执行的操作。传入reorder的是一个链表，它会抽出所有的ESEQ。reorder对参数的链表中的每一个表达式都调用de_exp，而do_exp的实现又只是对除了ESEQ之外的任何类型的表达式建立其子表达式的地址表并调用reorder。

将call移到顶层

由于在tree语言允许call节点作为子表达式，但实际中call的实现是，每一个函数将它的结果返回到同一个规定的返回值寄存器中，那么后面的调用就可能把前面的调用给覆盖掉了。

因此，我们可以重写：

CALL(func, args)--->ESEQ(MOVE(TEMP t, CALL(func, args)), TEMP t)

在这种情况中，do_stm不会调用reorder去处理CALL节点，而是把f和args看做MOVE节点的儿子

线性语句表

一旦整个函数体都已经用do_stm处理完毕之后，所有的SEQ节点都集中在树的顶部。函数linearize重复施加规则，使得SEQ(SEQ(a,b),c) ==> SEQ(a, SEQ(b,c))

但SEQ节点不提供任何结构性信息，只是简单列表。

处理条件分支

tree语言与多数机器指令集不一样的是，它具有两路分支CJUMP指令。为了便于将tree转换为机器指令，我们需要重新安排CJUMP，使得CJUMP(cond, lt, lf)后面跟随的LABEL(lf)。

我们分两步实现这一目的：取一颗规范树，并由它们形成基本块；对这些基本块进行排序，形成trace轨迹。

基本块

在分析程序的控制流时，任何非分支指令的程序语句对分析都没有意义，因此可以将非分支指令的序列集中到基本块中。

基本块是语句组成的一个序列，只能从序列的开始进入并从结尾处退出：

• 第一个语句是一个LABEL；
• 最后一个语句是JUMP或者CJUMP；
• 没有其他的LABEL, JUMP或者CJUMP；

划分基本块的算法：

从头到尾扫描语句序列，遇到一个LABEL就开始一个新的基本块并结束前一个基本块，遇到一个JUMP或者CJUMP就结束一个基本块；若过程遗留的基本块中，有任何基本块不是以LABEL开始的，则新生成一个标号插入到开始；若有不是以JUMP结束的，则在这个基本块的末尾假如一个转移到下一个基本块标号的指令。

轨迹

由于我们以任意顺序安排基本块，程序结果都是一致的，因此我们可以合理地安排基本块，以满足每个CJUMP之后都跟随它的false标号的基本块。

另外，也可以安排基本块使得JUMP之后跟随的是它们的目标标号，然后删除这些转移。

还有，需要安排轨迹使得重叠的轨迹越来越少。

完善

主要针对的是CJUMP指令：

• 所有后面直接跟随的false标号的CJUMP维持不变；
• 对任何直接跟随true标号的CJUMP，交换true标号和false标号，并将条件改为相反；
• 如果既不是true也不是false标号直接跟随着，则新生成一个标号lf'，重写CJUMP；

1
2
3

CJUMP(cond, a, b, lt, lf')
LABEL(lf')
JUMP(NAME lf)

抽象语法

Abstract: disassociated from any specific instance

语义动作

每个终结符和非终结符都可关联一个语义值类型。

递归下降

在递归下降的语法分析器中，semantic action是语法分析函数所返回的值，或者是这些函数所产生的副作用。

抽象语法分析树

为了有利于模块化，我们尽量将语法分析和语义分析分开处理，往往的一个做法就是由语法分析器生成一种数据结构——语法分析树，编译器在后面的阶段对其进行后序遍历。但如果遇到了引入新的非终结符和文法production的情况，我们应该尽量将这些细节限制在语法分析，而不应该干扰语义分析。

抽象语法就是起到了在语法分析与编译器等后面阶段之间建立接口的作用。

位置

有只过一遍的编译器中，词法分析，语法分析和语义分析是一起进行的。因此发送错误时，我们可以取得词法分析的当前位置，因为这里是最接近错误源的位置。而如果使用了抽象语法分析树之后，进行遍历时如果出现了语义错误，就不能简单地判断此时词法分析的位置，因为此时词法分析已经到了文件末尾。

因此，我们需要记录每一个节点在源程序中的位置。