语法分析

语法(syntax)：组合token以形成phrases，clauses和sentences

对于某些式子的表示，比如带有嵌套深度比较大的括号时，有限自动机并不能识别出括号配对的情况，这是因为状态数为N的有限自动机无法记忆嵌套深度大于N的括号。

上下文无关文法

上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符，例如：

1
2

S->aSb
S->ab

这个文法的两个production的左边都只有一个非终结符，那么只需要找到符合production右边的字符串，就可以对其进行规约。

然而

1
2

aSb->aaSbb
S->ab

这就是上下文相关文法，因为第一个production的左边不止一个终结符，所以在匹配的时候必须要确保S有正确的“上下文”。

推导

为了证明某个文法的类型，我们必须要进行推导（derivation），即从开始符号出发，对其右部的每一个非终止符，用该非终止符production的任一个右部替代它。

• 最左推导：总是扩展最左边的非终止符；
• 最右推导：总是扩展最右边的非终止符；

语法分析树

parse tree就是将一个推导中的各个符号连接到从它推导出来的符号而形成的。不同的推导可以得到相同的parse tree。

二义性文法

如果一个文法能够推导出两颗不同的parse tree，则认为该文法具有二义性。这种情况下，编译器就无法利用parse tree去解析语义。以下就是一个二义性文法的例子：

但是二义性的文法是可以通过某些转换来消除，一般来说引入一些新的非终止符，来提高某些表达式的优先级。

文件结束符

语法分析器会读入文件结束符号，一般来说我们使用$符号表示文件的结束。

预测分析

使用一种叫做梯度下降(recursive descent)的简单算法可以对grammar进行分析，它只适用于每个子表达式的第一个终结符号能够为production提供足够的信息的情况。其中每个非终结符对应的，都有一个函数。

FIRST集合和FOLLOW集合

FIRST(S)是从S可以推导出的任意字符串中的开头终结符组成的集合，因此如果两个production有着相同的左部符号，但它们的右部有着重叠的FIRST集合，那么该文法不能使用预测分析。

能产生空字符串的符号，称呼为nullable。

记住下列结论：

• 若X可以推导出空字符串，那么nullable(X)为真；
• FIRST(S)是从S可以推导出的任意字符串中的开头终结符组成的集合；
• FOLLOW(X)是可以直接跟随于X之后的终结符集合；

构造一个预测分析器

由于非终结符X的分析函数对X的每个产生式都有一个子句，因此该函数必须根据下一个输入来选择其中的一个子句。我们需要的所有信息可以用一个二维表来表示，该表以文法的非终结符X和终结符T作为索引。

对于每个属于FIRST(X)的T，在表的X行T列填入该production X->y；如果y为nullable，那么对于每个属于FOLLOW(X)的T，在表的X行T列填入该production X->y。

像上图这种情况，一个表项里有多个表达式，就会产生二义性的文法。若一个文法的预测分析表不含有多重定义的项，则称为LL(1)文法。

LL(1): Left to right parse; Leftmost derivation; 1-symbol lookhead

消除左递归

看这样的文法：

1
2

E->E+T
E->T

在这种情况下，将会导致LL(1)的分析表中出现了双重定义的登记项，因此任何属于FIRST(T)的tokens必然属于FIRST(E+T)，这就是左递归。

为了消除左递归，我们可以这样重写：

1
2
3

E->TE'
E'->+TE'
E'->

LR分析

LL(k)的一个弱点就是，在我们仅仅看到右边的k个tokens时就需要做出预测。相比而言，LR(k)分析是一种更好的选择。

LR(k): Left to right parse; Rightmost derivation; k-token lookhead

来看一个典型的例子：

• shift：将第一个token压进栈；
• reduce：选择文法规则：X->ABC，依次将C,B,A从栈中弹出来，将X压进栈；

LR分析引擎

LR分析器是通过DFA作用于栈，来实现reduce和shift操作的。转换操作主要有以下4种：

• sn: shift into state n
• gn: goto state n
• rk: reduce by rule k
• a: accept

LR(0)分析器

LR(0)是一种只需要分析查看栈就可以进行分析的文法，它的shift、reduce操作不需要进行任何超前判断

SLR分析器

如果用LR(0)去构造分析表：

在状态3的时候，遇到符号+，就会出现多重定义的项，分析器既需要shift到状态4，也需要对production2进行reduce。这是一个reduce-shift冲突。

因此我们可以构造SLR分析器来解决这个问题。

SLR的构造与LR(0)基本一样，除了它只在FOLLOW集指定的地方放置规约操作。

LR(1)项和LR(1)分析表

之所以使用LR(1)，是因为即便使用了SLR(0)，还是不能完美地解决所有的冲突。考虑αF.β，我们知道，F的follow集合包含字符串β的first集合。因此我们在SLR（0）中使用的follow集合不一定能正确的预测出产生式。

因此，我们重新定义了项，它包含产生式，标记状态的点，超前查看符号集合。

我们可以使用下面的算法计算一个状态中每一项的具体内容：

LALR(1)分析表

由于LR(1)的状态可能太多了，因此我们可以合并那些除了超前查看的符号集合外都相同的两个状态。

词法分析

lexical analysis：将输入分解成一个个独立的符号，即tokens

词法单词

token是由字符组成的序列，例如在常见的程序设计语言都有这样的一些单词类型：

正则表达式

由于我们在谈论某种语言时，需要为其中的字符串赋予特别的意义，因此我们可以用正则表达式去表示。

正则表达式的表达符号：

但是，考虑这样一个字符串if8，到底是认为其为一个标识符，还是两个tokens：if和8呢？为了消除二义性，我们可以试用一下两个规则：

• Longest match：对于输入的字符串，取可以与任意正则表达式规则匹配的字符串中最长的那一个作为下一个token；
• Rule priority：给正则表达式赋予某些优先权，选择优先级高的；

有限自动机

虽然用正则表达式已经可以很好地指明词法规则，但我们还需要一种能用计算机程序来实现的的形式化方法。这就是有限自动机(DFA)所做的事情。有限自动机包含了有限状态的集合和一些从一个状态到另一个状态的边。

在DFA中，不会有从同一个状态出发的两条边却包含了相同的符号。若对n个字符的字符串，进行了n次的转换之后，如果自动机到达了一个终态，则选择接收该字符串。如果没有到达终态，或者找不到与输入字符匹配的边，则拒绝接收字符串。

识别最长的匹配

为了识别一个字符串是否会被接收，词法分析器往往会选择最长的匹配，作为合法的token。因此需要两个变量来记住自动机最近一次处于final states的时机。

非确定有限自动机

与确定有限自动机不同，非确定有限自动机(NFA)需要做出选择，对从一个状态出发的多条标有相同符号的边进行选择。

将正则表达式转换为NFA

有了NFA之后，我们可以很容易地将正则表达式转化为NFA，一个正则表达式要么是一个简单的primitive，要么是由多个较小的表达式组合而成。如图：

将NFA转换为DFA

先来看NFA的模拟算法：

1
2
3

d<-closure({s1})
for i<-1 to k
	d <- DFAedge(d, ci)

首先构造s1的eplison闭包，然后从该闭包的状态集合出发，吃进符号c，到达一个新的状态集合。

看一个例子：

以字符串in为例子，先计算出eplison闭包，即求得状态集合为{1,4,9,14}；接着要根据字符i来进行状态转换，从状态1可到状态2，4可以到5，9无处可去，14可以到15，因此得到状态集合{2,5,15}，但是我们还要计算一次闭包，因此得到最终状态集合为{2,5,6,8,15}；同理，根据字符n进行转换。

这样的自动机还不是最理想的，我们还可以构造最小的自动机。我们只会在这种情况下称两个状态是等价的，如果一个开始于s1的自动机接收字符串a，当且仅当一个开始s2的自动机接收字符串a。这样我们就可以使得所有进入s2的边指向s1，并删除s2。

决策树

基本流程

决策树是一种常见的机器学习方法，采取的是分而治之的策略。其中每个非叶节点对应于一个属性测试，而叶子节点则对应于决策结果，也就是类别。

在生成决策树的过程中，遇到以下三种情况时停止递归：

• 当前节点所包含的样本完全属于同一个类别
• 当前属性集为空，或是所有样本在所有的属性上取值相同，对于这种情况我们会将当前节点标记为叶节点，并设定类别为该节点所包含样本最多的类别
• 当前节点的样本集合为空，同样会将该节点设置为叶节点，类别为父节点中包含样本最多的类别

划分选择

决定决策树学习的关键在于如何选择最优的划分属性，保证每个分支节点所包含的样本尽量属于同一个类别，即节点的纯度越高。

信息增益(information entropy)

信息熵是度量样本集合纯度的常用指标。假定当前样本集合D中第x类样本所占比例为p(x)，那么D的信息熵就是：

信息熵的取值范围为[0, log|y|]，y为类别数目

那么如何去判断某个属性对于样本集信息熵的提升呢，这里就提到了信息增益：

利用总的熵减去某个分类标准对应的熵，往往我们也可以给某个分支节点赋予权重|Dv|/|D|，Dv就是该分类标准下第v个节点对应的样本

怎么去理解呢？这里表述的是：原来的总熵为info(S)，在某个划分条件下熵变为了infos(S)，又由于熵是不确定的意思，那么差值越大，就意味着这个划分选择越好。

增益率

因为在某些情况下，选择信息增益大的属性，可能会导致泛化能力减弱，比如“编号”属性可能产生n个分支，使得分支节点达到最大，但在这种情况无法进行进一步的划分。

所以著名的C4.5决策树算法不直接使用信息增益，还是使用增益率：

Gain_ration(D, a)= Gain(D, a)/IV(a)

其中IV(a)为：

因为这是属性a的固有值，往往属性a的可取值树木越多，那么改值越大。由于该算法可能会倾向于选择可取值树木少的属性，所以它是这样操作的：先根据信息增益选择出高于平均水平的属性，再从其中选出增益率最高的。

基尼指数

先来看看基尼指数的公式：

从公式可以看出，基尼指数反映了随机从样本中抽取两个样本，两个样本一致的概率，该概率越小意味着样本集的纯度越高。

则对于属性a的基尼指数则是：

剪枝处理

剪枝处理的目的是提高决策树的泛化能力，以应对算法出现的过拟合。

那么如何去评判泛化能力呢？我们可以将样本集分为两类：样本集和检验集，通过计算检验集的准确率来决定决策树的泛化性能

剪枝分为两种：预剪枝和后剪枝

预剪枝

预剪枝是在决策树生成过程中，对每个节点的划分前进行估计，估计其划分是否可以可以带来决策树性能的提升。若不能，则停止划分，并将当前节点标记为叶节点。

后剪枝

后剪枝是生成完成的决策树之后，自底向上对节点进行考察，若替换为叶节点后泛化能力有所提升，则进行替换

连续与缺失值

连续值处理

对于连续属性而言，由于可取值数目是无限的，因此我们需要采用连续属性离散化的处理思路。最简单的方法就是采用二分法对属性进行处理。

给定了样本集D和连续属性a，假设a在D上出现了n个取值，对这些取值进行排序：{a1,a2,...,an}，我们可以得到一个划分点集合，里面有n个元素：

Ta = {a(i)+a(i+1)/2 | 1<=i<=n-1}

对这一系列划分点进行考察，计算各个划分点的信息增益，选择信息增益最大对应的划分点。

缺失值处理

我们为每个样本取一个权重wx

将信息增益的计算式更新为以下：

若样本在属性的取值已知，则将该样本划入与其取值对应的子节点，并保持权重wx；若属性取值未知，则同时划入所有子节点，并更新权重为~r_v*w_x

多变量决策树

如果单纯地使用上面提到的决策树方法，对于多维变量而言，分类边界的每一段都是和属性对应的坐标轴平行的。

但这样会带来一个问题就是：当学习任务的分类边界比较复杂时，划分的时间成本过高。因此我们考虑多变量决策树，而不是单一的属性，每个叶节点此时就是一个线性的分类器，例如对于西瓜数据集：

其中一个节点，可以变成：-0.365密度+-0.366含糖度<-0.158?

聚类

聚类任务

在无监督学习中，由于训练样本是未标记的，因此如果希望对无标记的训练样本进行深入挖掘，可以采用聚类（clustering）的方法。

假设有样本集D = {x1,x2...xm}，则聚类算法就是将样本集D划分为k个不相交的簇{Cl|l=1,2,...,k}。

作为一种无监督学习的算法，它既可以用于寻找数据内在的分布结构，也可以作为其它学习任务的前驱过程。

性能度量

性能的度量主要是为了评估聚类结果的好坏，一般来说我们使用两种方法：

1. 将聚类结果与某个“参考模板”进行比较，也就是使用外部指标。

假设λ与λ分别表示C和C对应的簇标记向量，我们将样本两两配对考虑。

其中集合SS包含了在C中属于相同簇，且在C也属于相同簇的样本对； 集合SD则是包含了在C中属于相同簇，但在C中不属于相同簇的样本对； 如此类推。。。。

由于每个样本对(xi,xj)只能出现在一个集合中，因此有a+b+c+d=C(m,2)=m(m-1)/2。

最后导出以下的外部度量指标：

• Jaccard系数: JC = a/(a+b+c)
• FM指数：FMI = √(a/a+b)*(a/a+c)
• Rand指数：RI = 2(a+b)/(m*(m-1))

上述指标都在[0, 1]之间，值越大越好

2. 直接考虑聚类结果，不参考任何的模型

其中dist(.,.)用来计算两个样本之间的距离；diam(C)表示簇C内样本间的最远距离；dmin(Ci,Cj)对应于簇Ci与Cj最近样本的距离；dcen(Ci,Cj)表示簇Ci与簇Cj中心点间的距离

一般用以下的指标去评估聚类性能:

• DB指数：

• Dunn指数：

显然，DBI越小越好，表示簇内距离小，簇间距离大；而DI则相反，越大越好，表示簇间距离大，簇内距离小

距离计算

一般来说，我们希望函数dist(.,.)，也就是距离度量，满足以下的一些基本性质：

• 非负性：dist(xi,xj)>=0
• 同一性：dist(xi,xj)=0，当且仅当xi=xj
• 对称性：dist(xi,xj)=dist(xj,xi)
• 直递性：dist(xi,xj)<=dist(xj,xk)+dist(xk,xj)

在讨论距离计算时，属性是否有序很关键，例如定义域为{1,2,3}的属性，能直接在属性值上计算距离，这种就称为有序属性；而对于定义域为{飞机，火车，轮船}这些，称为无序属性

有序属性

给定样本xi=(xi1,xi2,...,xin)与xj=(xj1,xj2,...,xjn)，最常用的就是Minkowski distance

当p=2，也叫欧式距离

无序属性

首先来看几个假设：m(u,a)表示在属性u取值为a的样本数，m(u,a,i)则是表示第i个样本簇在属性u取值为a的样本数。于是得到以下的公式(VDN)来计算距离。

另外，还可以结合Minkowski distance和VDM，保证处理混合属性

但对于无序属性，有可能会出现直递性失效，以“人”，“马”，“人马”为例，“人”和“马”都与“人马”很接近，但“人”与“马”差距很大，这种就叫做非度量距离。

原型聚类

prototype-based clustering，此类算法假设聚类结构能够基于一组原型刻画

k-means 算法

对于一个样本集和目标簇数，我们希望最小化以下的误差，其中ui就是簇Ci的均值向量。

算法思想比较简单：

1
2
3
4
5

1. 随机选择k个样本作为初始的均值向量
2. 进入循环
3. 计算每个样本与各个均值向量的距离，将样本划分到距离最小的均值向量所代表的簇中
4. 根据划分的聚类，计算新的均值中心
5. 如果均值向量没有变化，则退出循环

学习向量量化

Learning Vector Quantization是针对带有标记的数据样本的。对于这种情况，我们可以根据簇数选择一组n维向量（维度与样本一致）

具体算法为：

1
2
3
4
5
6
7
8

1. 首先初始化一组原型向量
2. 从样本集中随机抽取样本(xi,yi)
3. 找出与样本距离最近的一个原型向量
4. 比较两者类别是否一致
5. 一致则通过公式逼近，否则则使其离得更远
6. 直到迭代次数最大或者原型向量不怎么更新为止
==========================================
7. 得到原型向量之后，再对样本进行相应的分类

这里的关键是如何更新原型向量：

• 如果类型一致：新的向量 p = pi + u(xj-pi);
• 如果类型不一致： p = pi - u(xj-pi);

这里的u是学习率，范围为[0,1]。之所以满足逼近或者离得更远：

|p-xj| = |pi+u(xj-pi)-xj| = (1-u)|pi-xj|

由此可见，这种情况下p会在更新之后逼近xj

高斯混合聚类

高斯混合聚类采用的是概率模型来表达聚类原型，我们定义高斯混合分布公式为：

该分布为k个高斯分布的叠加，其中ai为相应的混合系数,且权重和为1。

算法步骤为：

1
2
3
4
5
6

1. 初始化混合高斯分布的三个模型参数：ai，ui(平均值)，协方差矩阵

2. repeat：
3. 将样本投射到高斯分布中,计算其在各个高斯分布下的概率
4. 针对每一个高斯分布，计算每一个样本在该分布下的概率，即计算其对该分布的贡献。根据该贡献，重新去计算上面三个模型参数
5. 直到参数收敛，或者迭代次数达到最大

至于如何求解这三个参数，可以参考EM算法：https://blog.csdn.net/u011974639/article/details/78302024

简单概括，就是两步：

• 先根据上一轮的参数来计算每个样本属于每个高斯分布的后验概率；
• 再根据后验概率去更新参数；

密度聚类

这个算法假设聚类结构能够通过样本分布的紧密程度来确定，先来确定几个概念：

• 邻域：对于样本集中的xj，邻域包含了样本集中与xj距离不大于某个值的样本
• 核心对象：若xj的邻域包含了至少MinPts个样本，则xj就是一个核心对象
• 密度直达：若xj位于xi的领域中，则xj由xj密度直达
• 密度可达：若存在样本序列p1,...,pn，其中p1=xi，pn=xj，且pi+1可由pi密度直达，则称xj可由xi密度可达

具体算法：

1
2
3

1. 首先根据邻域参数选出所有的核心对象；
2. 从任意一个核心对象出发，找出其密度可达的样本生成聚类簇，并将簇中的核心对象从第一步找到的核心对象集合中删除；
3. 紧接着从更新后的核心对象集合中随机选取一个核心对象，重复第二步；

层次聚类

层次聚类可以采用“自底向上”或者“自顶向下”的策略，在这里我们介绍AGNES的策略，这是一种自底向上的聚合策略。

它首先将每个样本看成一个初始聚类簇，然后在每次算法运行时找出距离最近的两个聚类簇进行合并，因此这里的关键就是计算两个聚类簇之间的距离，显然最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，至于平均距离则是由两个簇的所有样本共同决定。

通用套接字选项

其实应该是通用套接字选项，标题写错了，就不改了，仅仅作为自己学习使用，如有错误，不负责任

因为之前面试有问到，但自己不大熟悉，就学习记录一下，主要参考UNP这本书

SO_DEBUG套接字选项

这是一个仅仅由TCP支持的选项，开启该选项之后，内核将为TCP在该套接字上的所有分组保留详细的追踪信息，保存在内核的环形缓冲区。

SO_ERROR套接字选项

当一个套接字发送错误时，内核会将套接字的名为so_error的变量设为标准Unix Exxx值的一个，称为待处理的错误。一般会以以下两种方式之一立即通知进程这个错误。

1. 进程阻塞在对该套接字的select调用上，那么无论是检查可读条件还是可写条件，select均返回并设置其中一个或所有两个条件；

2. 如果进程使用信号驱动式IO模型，那就给进程产生一个SIGIO信号；

SO_KEEPALIVE套接字选项

套接字设置该选项后，如果在2小时内在该套接字上都没有数据交换，TCP会自动给对端发送一个保持存活探测分节。这是一个对端必须响应的TCP分节，会导致以下三种情况：

• 对端以期望的ACK响应；

• 对端以RST响应，告知本端TCP，对端已崩溃且已经重新启动；

• 对端对保持存活探测分节没有任何响应；

SO_LINGER

本选项指定close函数堆面向连接的协议如何操作。默认操作是close立即返回，但是如果有数据残留在套接字发送缓冲区中，系统会试着将数据发送给对端。

本选项主要是在内核空间和用户进程之间传递以下的结构：

1
2
3
4

struct linger{
    int l_onoff;
    int l_lingger;
};

因此设置该选项时就会出现三种情况：

1. l_onoff为0，关闭本选项，忽略l_lnlinger。即默认操作，close立即返回；

2. l_onoff 非0，l_linger为0，这时调用close，会丢弃发送缓冲区的数据，并发送一个RST给对端，跳过TIME_WAIT的状态。当然这也会带来一个问题是，创建该连接的另一个化身时，有可能会导致刚刚被终止连接的旧分节被重复传递到新的化身上；

3. 两个都为非0时，调用close后，套接字发送缓存区如果还有残留数据，那么进程会进入睡眠，直到所有数据都已经发送完并且被对方确认或延滞时间到（如果是这种情况会返回EWOULDBLOCK错误）；

SO_RECTIMEO和SO_SNDTIMEO套接字选项

这两个选项允许我们给套接字的接收和发送设置一个超时值。

TCP套接字选项

TCP有两个套接字选项：

TCP_MAXSEG套接字选项

本选项允许我们获得或者设置TCP连接的最大分节大小。

TCP_NODELAY套接字选项

设置了该选项后会禁止TCP的Nagle算法。

Nagle算法：目的是减少广域网上小分组的数目。如果连接上有未被确认的小包（即小于MSS），那么下一个包会被缓存下来，直到上一个包得到确认或者缓存的包的大小达到最大值。

有两种情况不适用Nagle算法，一是其服务器不在相反方向产生数据以便携带ACK；二则是客户端是使用若干个小片数据向服务器发送单个逻辑请求的客户。

同步机制与原理

进程、线程的同步

先说结论：线程之间的叫同步，进程之间的叫通信。

对于进程来说，由于进程能够通信就意味是同步机制，所以先来说一下进程的同步机制：

• 信号量：用来实现进程间的同步与互斥，但不能存储通信数据；
• 消息队列：由链表，存放在内核中并由消息队列标识符标识。
• 共享内存：能实现内存被多个进程共享；
• 管道(pipe)：半双工的通信方式，单向通信，而且只能在具有亲缘关系的进程间通信；
• 命名管道：同样半双工，但允许非亲缘关系的进程通信；
• 信号：通知某个进程事件的发生；
• 套接字

由于进程有独立的地址空间，所以一般不会有互斥锁这些锁机制，除非是像文件锁这种大锁。而在这种情况下，由于线程共享同一进程下的内存空间，就会有锁机制来保证同步。

而对于线程来讲，主要的同步机制有以下几种：互斥锁，信号量，临界区，条件变量。

同步原理

互斥锁

互斥锁是一种时间和空间代价都比较低廉的，实现对资源互斥访问的手段。主要有两种状态：lock & unlock。

当一个线程想要进入临界区操作数据的时候会尝试给它加锁，如果锁已经处于unlock状态，该线程就会被阻塞，直到锁被释放。

条件变量

与互斥锁不同的是，条件变量是自动阻塞进程进入等待状态而不是用来上锁，它会等待某个信号的接收。

通常来说会用互斥锁来保护条件变量，避免多线程竞争条件变量。

另外，互斥锁和条件变量结合可以解决一个互斥锁的问题，就是避免互斥锁频繁地被线程进行加锁和释放锁。

信号量

信号量也是用来保护互斥区的。信号量是一个特殊的变量，程序对信号量的访问都是原子操作的，并且只允许对其进行两种操作P和V。

虽然信号量使得共享资源在一个时间内只有一个线程能够使用，这是二值信号量，但往往，我们可以使用计数信号量，来表明最多允许有多少个持有者。

内核信号量的原型：

1
2
3
4
5
6
7

#include<include\linux\semaphore.h>
struct semaphore
{
　　 atomic_t count;
　　 int sleepers;
　　 wait_queue_head_t wait;
}

与自旋锁不同的是，自旋锁会不断轮询锁的状态，而信号量会因为任务想要的信号量被占用了，只能进入等待队列，并进入睡眠状态（这时处理器可以去处理其它操作）。

所以信号量适用于锁会被长期占用的状态。

predictive parsing

能预测使用哪一个production：

• 通过观察接下来的tokens；
• 没有回溯；

predictIve parsers接收LL(k)语法（left to right，leftmost derivation），k代码向前看k个tokens

LL(1):每一个step，只能选择一个production

但这里有一个问题就是，对于这样的grammar：

1
2
3

E->T+E|T

T->int | int * T | (E)

很难去根据next token预测T和E；

解决方法就是：left factoring，即去除公共前缀；

1
2
3
4
5

E->TX
X->+E|epsilon

T->intX|(E)
X->*T|epsilon

First Sets

如果a->tB，即a能推导出在第一个位置的t,那么t属于First(a)

定义：

First(X) = {t|X->ta}并{ε|X->ε}

算法：

1. First(t)={t}
2. ε属于First(X)

• if X->ε
• if X->A1A2...Ana and ε属于First(Aj)for 1<=j<=n

3. First(a)属于Frist(X) if X->A1..An a and ε属于First(Aj) for 1<=j<=n

Follow Sets

定义：

Follow(X)={t|S->*βXtε}

follow sets没有ε

Intution:

if X->AB, then First(B)属于Follow(A) and Follow(X)属于Follow(B) * if B->*ε then Follow(X)属于Follow(B)

if S 是开始symbol，$属于Follow(S)

algorithm sketch

1. $属于Follow(S)
2. First(β)-{ε} 属于 Follow(X), when A->aXβ
3. Follow(A)属于Follow(X)

• 对于每一个production， A->aXB 都有B->ε

LL(1) Parsing tables

构建一个parsing tables：

对于每一个production：A->a:

• 对于每一个终止符t属于First(a): T[A, t] = a
• 如果ε属于First(a), 对于每一个终止符t属于Follow(A): T[A, t] = a
• 如果ε属于First(a)，并且$属于Follow(A): T[A, $] = a

如果parsing table中的entry有两项，就会有冲突：

比如：S->Sa|b

First(S) = {b};

Follow(S) = {$, a};

这种情况下，就不是LL(1)。

bottom up parsing

• bottom up比top down更加常用和有效

这种方式就是主键的规约，回到start symbol：

1
2
3
4
5
6

int * int + int    T->int
int * T + int      T->int * T
T + int            T->int
T + T              E->T
T + E              E->T+E
E

• trace a rightmost derivation in reverse

shift-reduce parsing

shift,reduce是bottom-up parsing的两个操作

• Shift a terminal to the left string
• apply an inverse production at the right end of the left string

Syntax-Directed Translation

error handling

编译器的两个作用：

• 检测无效的程序；
• 翻译有效的程序；

error handler的作用：

• 准确报告错误；

• 迅速从错误回复；

• 不影响有效部分的编译速度；

• panic mode：

考虑这样的错误：(1++2)+3

panic mode的测量是：跳过，到达下一个整数，然后继续；

• error productions

分辨出已知的语法错误

error correction：尝试去找出正确的接近的程序，对tokens进行插入和删除；

Abstract Syntax Tree

编译器需要一个数据结构去代表那个程序。

考虑grammar：E->int|(E)|E+E，字符串为5+(2+3)，lexical analysis之后变成int'+'('int'+'int')'，然后parse tree为

然后构造AST：

强调嵌套结构，更加抽象并且没有non-terminals

Recursive Descent Parsing

也叫top-down parsing，则parse tree是从上到下，从左到右去构建。

考虑grammar：

E->T|T+E T->int | int * T | (E)

token stream为：(int),匹配5个括号

在构造过程中，按照从上到下从左到右一个一个比对，找到正确的parse tree

Recursive Descent Algorithm

首先来看一些特别的tokens：INT,OPEN,CLOSE,PLUS,TIMES，全局的next指向下一个的输入token

定义个函数来检测匹配与否：

• 对于给定的终止符：**bool term(TOKEN tok){return *next++==tok;}**

• S中的第n个production：bool Sn(){...}

• 尝试所有的production：bool S(){...}

• 对于production：E->T: bool E1(){return T();}

• 对于production：E->T+E: bool E2(){return T()&&term(PLUS)&&E();}

• 对于所有的productions of E(带回溯的情况):

1
2
3
4

bool E(){
    TOKEN* save = next;
    return (next=save, E1()) || (next, save, E2()) ;
}

• non-terminal T:

bool T1(){return term(INT);}

bool T2(){return term(INT)&&term(TIMES)&&T();}

bool T3(){return term(OPEN)&&E()&&term(CLOSE);}

1
2
3
4

bool T(){
    TOKEN* save = next;
    return (next=save, T1()) || (next=save, T2()) || (next=save, T3());
}

如何开始parser:

• 初始化next指针
• 调用E()

接下来就可以按照从上到下，从左到右进行parse，如果mismatch就进行回溯。

Left Recursion

• 考虑这样的production：S->Sa

1
2

bool S1(){return S()&&term(a);}
bool S(){return S1();}

在这种情况下，S()进入了无限递归；

对于一个grammar，若存在P经过一次或者多次的递归，即推导出以P开头的式子，则称之为左递归。

elimination of left recursion

考虑这样的grammar：A→Aa1｜Aa2……｜Aan｜b1｜b2……｜bm

可以改写成：

A→b1A’｜b2A’……｜bmA’

A’ →a1A’｜a2A’……｜anA’｜ε

Introduction to parsing

Input: sequence of tokens from lexer

Output: parse tree of the program

Context-Free grammars

• 不是所有tokens都是有效的，怕parsers要进行区分

• 程序语言是具有递归结构的

CFG包含了以下内容：

• A set of terminals->T
• A set of non-terminals->N
• A start symbols->S
• A set of productions -> X->Y1...Y2

productions可以理解成rules，例如S->(S)，意味着左边的能被右边的替代

CFG的处理过程：

1. 从一个带有start symbol S的字符串开始
2. 替换所有字符串中所有non-terminal X，根据production X->Y1..Y2
3. 重复2，直到没有non-terminals

假设G是以S为start symbol的CFG，那么语言L(G)就是：

• {a1....an | 对于所有的terminal ai，都有 S->a1....an}

terminals是不能被替换，是永恒的，terminals就是语言的tokens；

因此CFG就是指所有的production的左边只有一个非终结符

Derivations

derivations: 一些列的productions，可以表示成一颗树，根就是start symbol，箭头右边的就是子节点，

叶节点都是terminals，根就是start symbol。这种推导就是left-most derivation，每一步都替代掉最左边的non-terminal。

同理，也有right-most derivation：

right-most和left-most有着相同的parse tree。

Ambiguity

考虑grammar：E->E+E|EE|(E)|id ， string为idid+id

会解释得到两个parse tree：

如果有两颗以上的parse tree，我们就认为一个grammar是ambiguous。

Member的各种调用方式

Nonstatic Member Functions

由于C++的一个设计标准就是使得nonstatic member function要有和一般的nonmember function有相同的效率；

这就带来了一个变化，就是编译器内部会将nonstatic member function转换为等价的nonmember function实体；

转化步骤：

• 改写函数的原型，安插一个新的参数，即this指针；
• 将每一个对nontatic data member的存取操作改写为通过this指针的操作；
• 将member function改写成一个外部函数，修改函数名称；

例如一个这样的函数：

1
2
3
4
5
6
7
8

Point3d Point3d::normalize() const
{
    register float mag = magnitude();
    Point3d normal;
    normal.x = x/mag;
    normal.y = y/mag;
    normal.z = z/mag;
}

将可能会改写成：

1
2
3
4
5
6

void normalize_7Point3dFv(register const Point3d *const this, Point3d &__result)
{
    register float mag = this->magnitude();
    __result.Point3d::Point3d(this->x/mag, this->y/mag, this->z/mag);
    return;
}

特别的，编译器内部会对名称进行mangling处理，虽然目前处理方式没有统一的标准，但一般来说会在member名称前面加上类名，甚至为了保证重载的操作，会加上函数参数的类型，当然如果声明了extern C，就会抑制了这种效果，这也是extern关键字的一个重要功能。

有时我们看到的编译器报错，显示了非常奇怪的函数名称报错，往往就是因为name mangling的原因。

Virtual member functions

如果normalize()是一个虚函数，那么以下调用会转化为：

1
2

ptr->normalize();
(*ptr->vptr[1])(ptr);

1就是virtual function slot的索引值，关联到normalize()函数。

而如果里面的magnitude()函数也是虚函数，那么由于normalize会先调用，决定了object的类型，所以编译器会使用更加明确的调用方式，而不是(*ptr->vptr[2])(ptr);例如：

1

register float mag = Point3d::magnitude();

Static Member Functions

如果normalize是一个静态函数，那么这两种调用会变为:

1
2
3
4

obj.normalize();
prt->normalize();
//会转为
normalize_7Point3dSFv();

由于static member function没有this指针，所以：

• 不能直接存取其中class的nonstatic members；
• 不能被声明为const, volatile或者virtual；
• 不需要经由对象调用（但是如果static member是一个private，就很可能要依赖于对象）；

如果要取一个static member function的地址，那么其类型会是：unsigned int (*)();