小明学C++第三篇：编译原理

编程入门行业动态更新时间:2024-10-26 01:25:05

小明学C++第三篇：编译原理

懒惰是人类第一生产力，抽象是计算机伟大的思想。我们都知道计算机只认识0和1，而且是按照冯诺依曼结构组织起来的。数据跟指令都存放在主存里，根据不同的指令周期来区分是数据还是指令。在早期的计算机，人类必须编写很长只有0和1的机器语言来跟计算机交流，但这是非常低效的，因为0和1只要稍不留神，就会写错，最后可能造成很大的程序错误。于是人们就发明了以助记符为标志的汇编语言，这个已经好多了，毕竟可以通过语句直接知道每条语句的意义，但是其实每一个助记符跟二进制串是有唯一的对应关系的，也就是说，用汇编写的代码还是很长很长，最后人们发明了高级语言C，才比较接近于人类的思维和语法特点。于是问题就来了，一边接近于人类自然语言的高级语言，另一边是接近于机器的01串，如何完成这个转换呢？下面我们就来讲讲编译器的那些事情。

背景

前面的一篇博客里面写到小明写了一个多边形面积计算的C++程序（一个.cpp文件），然后小明点击了编译器的编译按钮，就生成了一个.exe可执行文件（即二进制代码）。下面我们就以面积计算函数calculate的这条语句为例，说明编译器是如何将其转化成二进制代码的：

S=( (A.x-B.x)*(A.y-C.y) - (A.x-C.x)*(A.y-B.y) )/2;

算术表达式的形式定义

大家请注意形式二字，这是抽象的象征。

好吧，怎么定义算术表达式呢？

我们先来看看中文“我喜欢你”吧。
这四个字可以组成很多排列：我喜欢你、你喜欢我、我你喜欢、喜欢你我、我喜你欢…
上面的排列有些是有意义的，有些是没有意义的。

我们是怎么定义一个完整的句子（合法有意义）的？
我们可以用下列的结构来判断句子是否合法：

定语主语状语谓语定语宾语

“我喜欢你”中，我是人称代词做主语，喜欢是一个动词做谓语，你是人称代词做宾语，整个句子符合定义，因此是一个合法的句子。
而“喜欢你我”中，喜欢是动词不能做主语，因此不是一个完整的句子。

伟大的乔姆斯基在研究了人类的语言以后，就从语言产生的角度去定义一门语言。
在他的理论中，它把语言分成四种，短语语言，上下文有关语言、上下文无关语言以及正则语言。而我们的C++语言是一种上下文无关语言。
至于具体他是怎么分的，我就不讲了，大家可以去找找有关形式语言的资料。

我们还是看看怎么定义这个算术表达式吧。
大家根据中文句子的定义可以去定义一下。
下面是我定义出来的算术表达式的结构：

上图包含四个式子。第一个式子是一个赋值表达式，由变量=表达式构成。
而表达式又由一些中间变量和终结符（+、-、*、/、（、）、number构成）。
上图叫做算术表达式的文法。
有了上面那个东西，就可以产生很多不同的算术表达式了。只有用上述表达式能够生成的式子才叫算术表达式，其它的都不是。
比如a=3+2*4可以经过下列步骤产生：

因此，式子a=3+2*4是算术表达式。
同样式子S=( (A.x-B.x)(A.y-C.y) - (A.x-C.x)(A.y-B.y) )/2也可以由上述文法产生，也是算术表达式。你们可以自己去推导。

token的识别

用一个文法来定义算术表达式是为了识别一个句子是不是该文法产生的，到底属不属于算术表达式。

那么为了识别一个句子，就必须识别句子里面的每一个元素，然后再判断是否符合句子的构成。
所以第一步是识别句子的元素，也就是token。
token就是句子中不同类别的一个整体，拿中文语法结构来讲，主语、谓语、宾语就是不同的token。第一步我们就是要识别出这些token出来。

在C++中，不同的token是有不同的定义的。比如变量的命名不能由数字开头，只能以字母或者下划线开头，而十进制数字开头必须为数字，而且不能为0，后面可以有小数点等。所以变量和数字是有差异的，根据这些差异，我们可以逐个字符读取代码，当读到数字时，它的期望是识别一个数字，当读到字母时，它希望是一个变量。而完成token识别的过程需要使用一个机器，叫做自动机（讲道理，图灵机也是一种自动机，只不过功能强大一些）。

自动机有很多状态，在众多状态之中，包含了开始状态和终止状态，每一个状态根据当前的输入，如果符合预期将会进入下一个状态。最终能够到达终止状态的就说明这个东西能够识别出来，是一个token。

举个例子，某个快递公司的物流系统就是一个自动机。当一个商品从青岛出发运往广东虎门，那么青岛是初始状态，表示我开始的时候是在青岛的；广东虎门是接收状态，表示最终的归属是在广东虎门。中途路过的所有地点都是中间状态。如果商品从青岛运到上海，而上海有到达广东虎门的通路，那么商品就会从上海运往下一个城市，比如是厦门。在这里，当前状态是在上海，输入是去广东虎门的商品，下一个状态是在厦门。自动机其实也就是这么一个东西。

那么C++识别token的自动机是怎样的呢？本人画了一个图可以参考一下：

现在我们来看看表达式S=( (A.x-B.x)(A.y-C.y) - (A.x-C.x)(A.y-B.y) )/2;是如何在自动机下识别出一个个token的。

首先我们在起始状态，读入一个S，就进入了INID的状态，然后在读入“=”，就进入了接收状态，于是S被接收，S是一个属于ID的token。同样“=”被识别成等号的token，A.x被识别成为一个变量，2被识别成为一个数字。

这样第一步工作就完成了。

语法树的生成

每一个token输出，作为语法分析器的输入。
下一步工作是生成一颗语法树。这颗语法树的作用是让机器明白表达式每个token的含义，它们的关系，以便生成中间代码。
下面就是表达式S=( (A.x-B.x)(A.y-C.y) - (A.x-C.x)(A.y-B.y) )/2;对应的语法树：

对于如何生成语法树是一个比较复杂的过程。你可以跳过这一部分。只要知道它的输出是语法树就可以了。
生成语法树的方法有很多，分为两大类，每大类又有不同的分析方法：
（1）自顶向下的分析方法：
a.递归下降分析法；
b.LL(1)分析法；
（2）自底向上的分析方法：
a.LR分析法；
b.算符优先分析法；

其中自顶向下分析法和自底向上分析法是两种相反的分析方法。自顶向下分析方法试图利用现在的产生式去找到一个句子的推导，它专注于选择使用哪个产生式。而自底向上分析方法是想找到句子的规约，它更倾向于找到一个句柄，也就是要进行规约的产生式的开头。下面我就讲一下LR分析法，它是现代编译器的语法分析器的基础。

LR分析法
LR分析法的关键在于构建一个LR语法分析自动机，再根据这个自动机构造出LR语法分析表，最后就根据这个表完成对某个句子的规约。
（1）LR语法分析自动机
（2）LR语法分析表
（3）对句子进行规约

为了简单起见，我们把算术表达式的文法删除减法和除法，剩下加法和乘法，变为以下的文法：

现在我们来分析表达式i+i*i语法树的构造过程：
（1）LR语法分析自动机（LR状态转移图）

你别看这个图非常复杂，只要你懂得了其中的窍门，还是看得明白的。
我们先看看状态，图中的状态包括I0-I11，一共有十二种状态，这么多状态是怎么来的呢？
原来我们先把I0状态看成初始状态，这个框框里面的东西叫做项，项里面有很多产生式，产生式有一个点。窍门来了。点表示当前状态，而后面的字符表示它所期望接收的字符。最开始我们希望接收一个E，一个E表示一个表达式，也是E’->.E表示的就是这个意思。但是E还有产生式，比如E->T，那么期望接收到E也意味着期望接收到E的产生式(E->T)的第一个字符T。于是E->.T也被加入到项集里面了。就这样，同一个项集的式子其实都表示同一种状态。它们经过不同的输入就会到达不同的状态。就这样不断产生新的状态，直到状态都是可归约的状态，也就是那个点到达了产生式的右端。比如状态I11：F->(E).表示可以规约了。
（2）LR语法分析表

这个表有三列，分别为状态、ACTION、GOTO。
这个表是根据步骤（1）的自动机得到的。
表的内容主要分为几种不同的元素，包括
（1）s+数字：表示移进，并将状态变成数字所代表的状态，s5表示移进字母，状态变成5；
（2）r+数字：表示规约，数字表示用第几条产生式规约。
（3）数字：纯数字表示直接改变状态，不需要移进和规约。
（4）acc：这是接收状态，到达这一状态表示语法树成功生成。
（5）内容为空：表示没有合法的动作，语法树生成失败。

LR语法分析表的解读：
我们来看一下状态为0的那一行，当输入为i的时候，我们看LR状态转移图是不是移进i,并且状态变成了I5了，因此当状态为0时输入i的动作是s5；
我们再来看看第四行，如果当前状态为3，输入+号时，根据LR状态转移图，应该使用第四条产生式T->F进行规约，于是动作为r4;
其它的也跟上述情况类似，你们可以自己推导。

（3）对句子进行规约
有了状态转移表，就可以对i+i*i进行规约了，也就是生成语法分析树。

总体来说，LR分析器的结构如上图所示，LR分析器的分析栈中有个初始状态s0，然后顺序读入输入串，依据LR分析表，分析栈的内容也做相应的变化。
比如句子i+i*i，开始时状态是0，读入i，根据LR分析表，执行的动作是s5，所以分析栈的状态变成了5，分析栈的符号变成了i#；
然后再读入+,根据LR分析表，执行的动作是r6，即用第6条产生式F->id进行规约,在规约的时候就可以生成一个树结构。这个结构F是父节点，它有一个孩子id。然后当前状态变成0，输入F时，执行动作3，于是分析栈的状态变成3。
下表是全部的LR分析过程：

每一次规约过程都会构造出一颗树（以之前构造的树作为孩子），这颗树越来越大，当分析栈的状态只剩下01时，表示分析成功，这颗树就是对应句子的语法分析树了。

中间代码生成

按照正常的思路，构造出语法分析树，我们就知道了语法结构了，如果给这个语法结构添加一些语义，就可以直接生产目标语言即二进制代码了，可是为何还要生成中间代码呢？
主要原因是中间代码独立于目标语言，便于编译器的实现和移植，也便于进行机器无关的代码优化。
我们试着想象这样的场景，小明写了多边形面积计算的C++代码，他想把这个代码发给另外两个同学去执行，但是这两个同学的机器（机器指令体系）是不同的，这时如果没有中间代码的话，小明只能发送源代码让这两位同学重新编译再运行。可是如果有中间代码的话，对token的识别和语法树的构造只需进行一次，这样就简化了流程，加快了效率。
中间代码的形式有很多种，其中包括了三地址码。
所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个结果地址。
如x+y*z三地址码为：t1 := y*z t2 := x+t1；
那么表达式S=( (A.x-B.x)(A.y-C.y) - (A.x-C.x)(A.y-B.y) )/2;的三地址码就可以是：

t1 = A.x-B.x;
t2 = A.y-C.y;
t3 = A.x-C.x;
t4 = A.y-B.y;
t5 = t1 * t2;
t6 = t3 * t4;
t7 = t5 -t6;
t8 = t7/2;
S = t8;

大家请注意，上述过程是根据语法分析树来生成的，因为处于语法分析树底端的分支，优先级是最高的，需要事先进行计算。
这样中间代码就生成了。

代码优化

代码优化分为机器无关的优化和机器有关的优化，机器无关的优化又分为局部块优化以及全局优化。具体的优化有很多技术，本人也还没有掌握，感兴趣的同学可以去看看龙书：机械工业出版社的编译原理。
在这里我就举一个我知道的优化吧。
乘法和除法的优化
在上述中间代码中：

t5=t1*t2;
t6=t3*t4;
t8=t7/2;

对二进制熟悉的话，一个二进制数乘以2相当于左移一位，除以2相当于右移一位。
所以上述代码可以变成移位操作。再后面的博客当中，我们将会看到乘法和除法比移位操作将会耗费好几倍的指令周期，因此移位操作更加快速。
所以
t8=t7/2 => t8 = t7>>1;
至于乘法的优化怎么做，你自己思考一下吧。

二进制代码生成

根据优化后的中间代码，就可以生成二进制代码了。
这个过程其实可以比较简单，就好像查字典一样。
每一条中间代码，判断是加法还是其它操作，然后找到相关的二进制指令，
最后翻译成二进制代码。
下面是中间代码(跟上面代码稍有改动):

t1 = t9-t10;
t2 = t11-t12;
t3 = t9-t13;
t4 = t11-t14;
t5 = t1 << 2;
t6 = t3 << 2;
t7 = t5 -t6;
t8 = t7>>1;

在MIPS指令集结构下翻译得到的二进制代码：

000000 00001 01001 01010 00000 100000
000000 00010 01011 01100 00000 100000
000000 01001 01101 00011 00000 100001
000000 01011 01110 00100 00000 100001
000000 00000 00001 00101 00010 000000
000000 00000 00011 00110 00010 000000
000000 00101 00110 00111 00000 100001
000000 00000 00111 01000 00001 000011