编译器编译原理详解

￡神魔★判官ぃ 2021-06-10 20:42 582阅读 0赞

**第一篇摘自：http://www.21ic.com/app/embed/201103/79359.htm**

**1. 词法分析**

词法分析器根据词法规则识别出源程序中的各个记号（token），每个记号代表一类单词（lexeme）。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器的输入是源程序，输出是识别的记号流。词法分析器的任务是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。

**2. 语法分析**

语法分析器根据语法规则识别出记号流中的结构（短语、句子），并构造一棵能够正确反映该结构的语法树。

**3. 语义分析**

语义分析器根据语义规则对语法树中的语法单元进行静态语义检查，如果类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的。

**4. 中间代码生成**

中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式，它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码，它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。

**5. 中间代码优化**

优化是编译器的一个重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上有很大浪费。当需要生成高效目标代码时，就必须进行优化。

**6. 目标代码生成**

目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。编译器生成的目标程序代码可以有多种形式：汇编语言、可重定位二进制代码、内存形式。

**7 符号表管理**

符号表的作用是记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的查找和操作。符号表中的某些内容甚至要保留到程序的运行阶段。

**8 出错处理**

用户编写的源程序中往往会有一些错误，可分为静态错误和动态错误两类。所谓动态错误，是指源程序中的逻辑错误，它们发生在程序运行的时候，也被称作动态语义错误，如变量取值为零时作为除数，数组元素引用时下标出界等。静态错误又可分为语法错误和静态语义错误。语法错误是指有关语言结构上的错误，如单词拼写错、表达式中缺少操作数、begin和end不匹配等。静态语义错误是指分析源程序时可以发现的语言意义上的错误，如加法的两个操作数中一个是整型变量名，而另一个是数组名等。

第二篇摘自：http://jpkc.nwpu.edu.cn/dzjc/jsjrj/text/chapter01/section01/r2a.htm

<table> 
 <tbody> 
 <tr> 
 <td> 
 <div> 
 计算机能读懂的语言是机器码，但对人来说由1和0组合的二进制序列既难写又难读。于是出现了用英文字母代表操作码的汇编语言，汇编语言是机器语言的符号化，汇编语言是面向机器的，使用汇编语言编程需要直接安排存储，规定寄存器、运算器的动作次序，汇编语言与计算机紧密相关，不同的计算机在指令长度、寻址方式、寄存器数目、指令表示等方面都不一样，由于汇编语言不便于进行数学描述，而且不可移植，于是出现了高级语言。高级语言是面向计算过程的和面向问题的语言，只与解题的步骤有关，而将高级程序设计语言"翻译"成机器语言的工作则是由编译程序来完成的。程序员的工作则是把要计算的问题化成高级程序设计语言的表达式、语句、过程/函数、对象，而不是机器指令序列。 　　把高级语言程序翻译成机器语言程序有两种做法：编译和解释，相应的翻译工具也分别叫做编译器和解释器。以下分别讲述。 1．编译器工作原理<a rel="nofollow"></a> 　　编译器逐行扫描高级语言程序源程序，编译的过程如下： (1)词法分析(Lexical Analysis)。识别关键字、字面量、标识符 (变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。 (2)语法分析 (Syntax Analysis)。一个语句看作一串记号 (Token)流，由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存，否则报错。直至检查完整个程序。 (3)语义分析 (Semantic Analysis)。语义分析器对各句子的语法做检查：运算符两边类型是否相兼容；该做哪些类型转换 (例如，实数向整数赋值要"取整")；控制转移是否到不该去的地方；是否有重名或者使语义含糊的记号，等等。如果有错误，则转出错处理，否则可以生成执行代码。 (4)中间代码生成。中间代码是向目标码过渡的一种编码，其形式尽可能和机器的汇编语言相似，以便下一步的代码生成。但中间码不涉及具体机器的操作码和地址码。采用中间码的好处是可以在中间码上做优化。 (5)优化。对中间码程序做局部优化和全局 (整个程序)优化，目的是使运行更快，占用空间最小。局部优化是合并冗余操作，简化计算，例如x:=0可用一条"清零"指令替换。全局优化包括改进循环、减少调用次数和快速地址算法等。 (6)代码生成。由代码生成器生成目标机器的目标码 (或汇编)程序，其中包括数据分段、选定寄存器等工作，然后生成机器可执行的代码。 　　高级语言源程序经编译后得到目标码程序，还不能立即装入机器执行，因为程序中如果用到标准函数（它们生成的目标码已存放在模块库中），还需对编译后得到的目标模块进行连接。连接程序 (Linker)找出需要连接的外部模块，然后到模块库中找出被调用的模块，调入内存并连接到目标模块上，形成可执行程序。执行时，把可执行程序加载 (Loading)到内存中合适的位置 (此时得到的是内存中的绝对地址)，就可执行了。其示意图为图1.1所示 　　　 
 </div> </td> 
 </tr> 
 <tr> 
 <td> <img src="http://jpkc.nwpu.edu.cn/dzjc/jsjrj/images/chapter01/1.1.jpg" width="589" height="71" alt=""> 图1.1 编译、连接和执行程序的过程 </td> 
 </tr> 
 <tr> 
 <td> 
 <div> 
 2．高级语言程序的解释执行<a rel="nofollow"></a> 　　编译型语言由于可进行优化 ( 有的编译器可做多次优化 ) ，目标码效率很高，因此是目前软件开发的最主要编程语言。常见的程序设计语言，如 C/C++ 、 Pascal 、 FORTRAN 等都是编译型语言，用这些语言编写的源程序，都需要进行编译、连接，才能生成可执行程序。这对于大型程序、系统程序、支持程序来说是十分有利的，虽然编译时花费了不少时间，但程序的执行效率是很高的。不过，在有些场合，对程序的执行效率要求不高的场合，没有必要在编译上花费大量的时间，可以对高级语言源程序采取解释执行的方式。 　　解释执行需要有一个解释器 (Interpreter) ，它将源代码逐句读入。第一步先作词法分析，建立内部符号表；再作语法和语义分析，并作类型检查 ( 解释语言的语义检查一般比较简单，因为它们往往采用无类型或动态类型系统 ) 。完成检查后把每一语句压入执行堆栈，并立即解释执行。因为解释执行时只看到一个语句，无法对整个程序进行优化。但是解释执行占用空间很少。 　　操作系统的命令、Visual Basic、Java、JavaScript 都是解释执行的 ( 其中有些语言也可以编译执行 ) 。解释器不大，工作空间也不大，不过，解释执行难于优化、效率较低，这是这类语言的致命缺点 。&nbsp; 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

第三篇摘自：http://apps.hi.baidu.com/share/detail/32154894

《Visual C 编译器原理》

Jan Gray在1994曾经写了一篇叫做C++ under the Hood的文章，介绍了Visual C++的实现细节。这篇指南就是基于Jan的文章之上，我同时会将Jan文章中让人难于理解的地方详细阐述。希望这篇指南可以让更多的人了解C++的底层实现机制。

The layout of a Class

struct B \{  
public:  
int bm1;  
protected:  
int bm2;  
private:  
int bm3;  
\};  
Struct B 在内存中的layout是怎么样的？ Visual C++保证B中的member variables 在内存中的layout与它们生命的顺序一致。Struct B在内存的中layout应该是这个样子的：

![11.JPG][]

Single Inheritance

struct C \{  
int c1;  
void cf();  
\};  
struct D : C \{  
int d1;  
void df();  
\};  
在Visual C++中保证在C的member variables 在内存中的位置永远在D的起始位置。就像这样:

![2.JPG][]

这样做的好处是当C\* pC = new D();Visual C++不需要为pC做额外的displacement 转换。pC 的address equal D\* pD = new D();中的pD.

Multiple Inheritance

比较复杂： 
struct E \{ 
int e1; 
void ef(); 
\}; 
struct F : C, E \{ 
int f1; 
void ff(); 
\}; 
多重继承比较复杂，他们的Base和Derived的指针的位置不再相同。 
F f; 
// (void\*)&f == (void\*)(C\*)&f; 
// (void\*)&f < (void\*)(E\*)&f; 
通过如下的Diagram of layout你可以看得更加清楚：

![3.JPG][]

为什么在图中C在E的上面？这是Visual C++ 的convention罢了，基类在内存中的layout correspond to 他们的的声明顺序。因为C的声明在E的前面，所以我们看到的F在内存的layout就是这样子的。  
由此图可知，E \*pE = new F() 与C \*pC = new F()中的pE 和pC指向的内存位置并不相同，对于pC 来说compiler不需要额外做任何事情，但是对于pE，为了让它指向E在内存中的位置compiler需要进行一种叫做displacement的调整。

Virtual Inheritance

请考虑这种情形：  
struct Employee \{ ... \};  
struct Manager : Employee \{ ... \};  
struct Worker : Employee \{ ... \};  
struct MiddleManager : Manager, Worker \{ ... \};  
  
无疑，按照我们之前的叙述，MiddleManager在内存中的layout应该是这个样的:

![4.JPG][]

在内存中的有两个Employee的实例，如何Employee 很小那么这种冗余是可以忽略的，可是如果Employee很大呢？ 那么有没有什么方法可以让Manager 和Worker在内存中共享同一个Instance呢？这就是Virtual Inheritance需要解决的问题。  
在享受这种优化的服务之前，你应该将你的类体系结构编程这样：  
struct Employee \{ ... \};  
struct Manager : virtual Employee \{ ... \};  
struct Worker : virtual Employee \{ ... \};  
struct MiddleManager : Manager, Worker \{ ... \};  
  
也就是在希望被sharing 的基类前面加上Virtual关键字，多么直观啊。  
struct G : virtual C \{  
int g1;  
void gf();  
\};  
struct H : virtual C \{  
int h1;  
void hf();  
\};  
struct I : G, H \{  
int i1;  
void \_if();  
\};  
  
之后你的类在内存中的就应该是这个样子：

![5.JPG][]

其中vbptr中存储的是对Employee的相对displacement.  
Data Member Access  
在没有继承的情形：  
C\* pc;  
pc->c1; // \*(pc + dCc1);  
  
c1 的访问类似于\*(pC + displacement of c1 within C);在本例子中根据Class C的定义和Diagram of layout我们可以发现displacement == 0.  
在单继承的情形中：  
D\* pd;  
pd->c1; // \*(pd + dDC + dCc1); // \*(pd + dDCc1);  
pd->d1; // \*(pd + dDd1);  
  
根据我们之前的Diagram不难看出pd->c1 == \*(pd + displacement from D to C + displacement from C to c1).这种情形中displacement == 0。  
pd->d1 == \*(pd + displacement from D to d1). 这种情形中 displacement == 4。  
在多重继承中，情形稍微复杂些，但所有的displacement 还都是常量(constant)。  
F\* pf;  
pf->c1; // \*(pf + dFC + dCc1); // \*(pf + dFc1);  
pf->e1; // \*(pf + dFE + dEe1); // \*(pf + dFe1);  
pf->f1; // \*(pf + dFf1);  
我想何以根据我们之前的Diagram轻松的算出每一个displacement。  
虚拟继承又是怎么的呢？  
I\* pi;  
pi->c1; // \*(pi + dIGvbptr + (\*(pi+dIGvbptr))\[1\] + dCc1);  
pi->g1; // \*(pi + dIG + dGg1); // \*(pi + dIg1);  
pi->h1; // \*(pi + dIH + dHh1); // \*(pi + dIh1);  
pi->i1; // \*(pi + dIi1);  
I i;  
i.c1; // \*(&i + IdIC + dCc1); // \*(&i + IdIc1);  
  
对g1,h1,以及i1的访问很容易理解，我想说说对c1的访问。  
pi->c1是一种动态的访问。在runtime的时候编译器不知道pi的真正type是什么，这时就要用到之前说过的vbptr，(\*(pi + dIGvbptr))\[1\]是指在特定的vbptr中(不论vbptr是属于 G还是H)其对于base virtual class的偏移地址。至于为什么是(\*(pi + dIGvbptr))\[1\] 而不是 (\*(pi + dIGvbptr))\[0\]，我猜这也是Visual C++的设计使然吧。 如果你知道(\*(pi + dIGvbptr))\[0\]中放的什么，请让我知道? br />对于i.c1的访问，因为这是一种静态的访问，为了节省开销C++对它的处理直接而干脆。之所以C++敢于这么做是因为在I中displacement of i在这种静态声明中是固定不变的。

Casts

理解了以上概念相信Casts between 2 types就不是什么问题了，一下是我们常见的一些cast在Visual C++中的实现手段。  
对于多重继承来说：  
F\* pf;  
(C\*)pf; // (C\*)(pf ? pf + dFC : 0); // (C\*)pf;  
(E\*)pf; // (E\*)(pf ? pf + dFE : 0);  
对于虚拟继承来说：  
I\* pi;  
(G\*)pi; // (G\*)pi;  
(H\*)pi; // (H\*)(pi ? pi + dIH : 0);  
(C\*)pi; // (C\*)(pi ? (pi+dIGvbptr + (\*(pi+dIGvbptr))\[1\]) : 0);  
  
什么，没看懂？那么就再看一遍我对Data Member Access的描述吧。  
Member Functions  
struct P \{  
int p1;  
void pf(); // new  
virtual void pvf(); // new  
\};  
对于一个non-static 成员变量的访问应该是这样的(我想因该大部分程序员都会了解吧)member function被调用的的时候会被传入一个this指针他的类型是:  
Type X \* const。(有人想过为什么是会是这样的声明而不是const Type X \* const 或者const Type X \*么？  
如果声明为const Type X \*那么我们将无法通过this指针修改member variables。至于const Type X \* const么实际上当你 将pf定义成：void pf() const;那么传入的this就是const Type X \* const的。通过Type X \* const 我们不能擅自修改this指针本身，不信你试试。)  
所以对于pf的调用实际上应该是这个样子的：  
void P::pf() \{ // void P::pf(\[P \*const this\])  
\++p1; // ++(this->p1);  
\}

Overriding Member Functions

考虑以下声明：  
struct Q : P \{  
int q1;  
void pf(); // overrides P::pf  
void qf(); // new  
void pvf(); // overrides P::pvf  
virtual void qvf(); // new  
\};  
Overridden member function包括 static 和 dynamic 调用。在C++中使用virtual关键字来区分。  
情形1：static resolution:  
当一个member function被重写且没有virtual那么，对他的调用在compiling 的时候就已经determined.  
P p; P\* pp = &p; Q q; P\* ppq = &q; Q\* pq = &q;  
pp->pf(); // pp->P::pf(); // P::pf(pp);  
ppq->pf(); // ppq->P::pf(); // P::pf(ppq);  
pq->pf(); // pq->Q::pf(); // Q::pf((P\*)pq);  
pq->qf(); // pq->Q::qf(); // Q::qf(pq);  
  
当pp->pf() 以及 ppq->pf()这两种情形，调用它们的指针类型在compiling是就已经安插。因为没有Virtual 那么就没有多态的干扰，Visual C++将忠实于->运算符左侧的类型，并且将此类型作为this传入此函数。

情形 2：dynamic resolution：  
pp->pvf(); // pp->P::pvf(); // P::pvf(pp);  
ppq->pvf(); // ppq->Q::pvf(); // Q::pvf((Q\*)ppq);  
pq->pvf(); // pq->Q::pvf(); // Q::pvf((P\*)pq);  
  
可怜的C++编译器，将如何决议overridden member function 的类型呢？为了解决这个问题vfptr被引入。  
通常被安插在memory layout的第一个位置，它指向此class的 vftable。 Vftable中存储的是所有virtual functions的地址。就像这样：

![6.JPG][]

当子类重写了父类的方法那么vftable中相应的entry 就应该被改写，如图：

![7.JPG][]

C++就是通过这种方式来进行overridden member function 的dynamic resolution。

Virtual Functions: Multiple Inheritance

这是本指南最刺激和有趣的一部分，我要向你介绍著名的Thunk技术。  
考虑一下情形：  
struct R \{  
int r1;  
virtual void pvf(); // new  
virtual void rvf(); // new  
\}；  
struct S : P, R \{  
int s1;  
void pvf(); // overrides P::pvf and R::pvf  
void rvf(); // overrides R::rvf  
void svf(); // new  
\};  
  
这样的layout应该如何画？我猜是这样的：

![8.JPG][]  
S s; S\* ps = &s;  
((P\*)ps)->pvf(); // ((P\*)ps)->P::vfptr\[0\])((S\*)(P\*)ps)  
((R\*)ps)->pvf(); // ((R\*)ps)->R::vfptr\[0\])((S\*)(R\*)ps)  
当我lunching以上两种调用，我所期望的的函数语义应该是就像每个函数注释后面的一样。毕竟->运算符左侧的是一个S\*对吧，所以传入member function的指针也应该是S\*。当使用P\*是问题很简单，P\*和S\*指向的是相同的内存地址，C++ compiler不需要做任何事情。但是当使用R\*后有点问题，R\*和S\*指向的内存地址不同。那么我们就要使用一些技巧让R\*指针转化为S\*。对于这个问题的解决办法基本上就是使用一种叫做Thunk的技术。重写 entry of pvf within vftable。  
重写的方法很多，在VC++中重写后的结果像这样：  
  
S::pvf-adjust: // MSC++  
this -= SdPR;  
goto S::pvf()  
呵呵，很简单是么，将原先指向R\*的this指针- displacement of S from R, 然后jump 到真正的S::pvf()的函数地址中。

Constructors and Destructors

Constructor 和 Destructor我们常见，但是不能使用。通常有compiler将其分解成为多部构造。  
Constructor 被分解后应该是这样的：  
1)对于一个most derived类，初始化vbptr，并调用virtual base 的构造函数。  
2)调用non-virtual base classes 的构造函数。  
3)调用data members的构造函数  
4)初始化vfptr。  
5)执行用户写在constructor中的代码。  
Destructor被分解后应该是这样的：  
1） 初始化vfptr  
2） 执行用户卸载destructor中的代码。  
3） 调用data member 的析构函数，顺序是与data member 在类中声明的顺序相反。  
4） 调用non-virtual bases的析构函数，与声明的顺序相反。  
5） 对于一个most derived 的类，调用它的virtual base的析构函数。

[11.JPG]: /images/20210522/65372a07b1ed4aca908687ca15978d4b.png
[2.JPG]: /images/20210522/15db3ba1b905424884e857d8b5a2906d.png
[3.JPG]: /images/20210522/1e93b9fba97d4b3ca78fac2cd1a00a0b.png
[4.JPG]: /images/20210522/0bd692e1d25b4d6b9cc9fd3c5456abcb.png
[5.JPG]: /images/20210522/a29fcf5ffeb94620a8243a9fe2748048.png
[6.JPG]: /images/20210522/262b66d685af4246b42163c28f4ac6c2.png
[7.JPG]: /images/20210522/43a74c866a374eaf9bd5a28f0b366b1b.png
[8.JPG]: /images/20210522/c090bb9911ba458ea539166389021df7.png