编译原理教程_1 引论

「爱情、让人受尽委屈。」 2022-11-10 01:37 191阅读 0赞

> 文章下载地址-关注我的gitee  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  1. 引论
 *   *  1.1 什么是编译原理
     *   *  1.1.1 常见概念
         *  1.1.2 流程
     *  1.2 编译器的结构和过程
     *   *  1.2.1 结构
         *  1.2.2 编译的五个阶段
         *   *  1) 词法分析
             *  2) 语法分析
             *  3) 语义分析和中间代码生成
             *  4) 代码优化
             *  5) 代码生成
         *  1.2.3 编译的七大程序
         *   *  1) 表格程序管理程序
             *  2) 出错处理程序
     *  1.3 编译程序生成
     *  1.4 总结

# 1. 引论 #

*  词法分析 --第三章
 *  语法分析- 第四章-第六章
 *  语义分析及中间代码生成 -第七章-第八章
 *  代码优化 第九章
 *  代码生成

## 1.1 什么是编译原理 ##

### 1.1.1 常见概念 ###

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>翻译程序</td> 
   <td>把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。</td> 
  </tr> 
  <tr> 
   <td>编译程序</td> 
   <td>把高级语言所写的源程序翻译成与之等价的低级语言（如汇编语言、机器语言等）的目标程序。如果编译阶段目标程序是机器语言程序，则分为编译阶段和运行阶段；如果生成的是汇编程序，则分为编译阶段、汇编阶段和运行阶段。</td> 
  </tr> 
  <tr> 
   <td>解释程序</td> 
   <td>也是一种翻译程序，将源程序作为输入，边解释边执行，但其不产生目标程序，而是按照源语言的定义解释执行源程序本身。</td> 
  </tr> 
  <tr> 
   <td>编译器</td> 
   <td>阅读以某一种语言（源代码）编写的程序，并把该程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序。</td> 
  </tr> 
  <tr> 
   <td>解释器</td> 
   <td>另一种常见的语言处理器，并不通过翻译的方式生成目标程序，直接利用用户提供的输入执行源程序中指定的操作。</td> 
  </tr> 
  <tr> 
   <td>预处理器</td> 
   <td>一个源程序可能被分割成多个模块，并存放于独立的文件中，把源程序聚合在一起的任务有时会由一个被成为预处理器的程序独立完成。</td> 
  </tr> 
  <tr> 
   <td>链接器/加载器</td> 
   <td>一个文件中的代码可能指向另一个文件中的位置，而链接器能够解决外部内存地址的问题。最后，加载器把所有的可执行目标文件放到内存中执行。</td> 
  </tr> 
  <tr> 
   <td>汇编器</td> 
   <td>对编译器产生的汇编语言程序进行处理，并生成可重定位的机器代码。</td> 
  </tr> 
 </tbody> 
</table>

### 1.1.2 流程 ###

![img][]

## 1.2 编译器的结构和过程 ##

### 1.2.1 结构 ###

> 编译器的两个组成部分：分析部分和综合部分。

![img][img 1]

### 1.2.2 编译的五个阶段 ###

一个编译器的各个步骤：

![img][img 2]

#### 1) 词法分析 ####

>  *  词法分析/扫描：词法分析器读入组成源程序的字符流，并且将它们组织成为有意义的词素的序列。
>  *  每个词素都被映射成如下语法单元，传送给语法分析：
> 
> <token-name, attribute-value>
> 
> 分隔词素的空格会被词法分析器忽略掉。
> 
>  *  描述词法规则的有效工具是正规式和有限自动机

#### 2) 语法分析 ####

>  *  语法分析/解析：语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。
>  *  赋值语句语法规则
>     
>      *  A::=V=E
>      *  E::=T|E+T
>      *  T::=F|T\*F
>      *  F::=V|(E)|C
>      *  V::=标识符
>      *  C::=常数
>  *  语法分析的两种放法
>     
>      *  推导
>      *  归约
>  *  计算机的做法是 语法树
>     
>     x=a+b\*50的语法树
>     
>     ![image-20210126113219603][]

#### 3) 语义分析和中间代码生成 ####

>  *  语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。
>  *  它同时也收集类型信息，并把这些信息存放在语法树或者符号表中，以便在随后的中间代码生成过程中使用。
>  *  三地址代码的中间表示形式
>     
>     （运算符，运算对象1 运算对象2 结果)

#### 4) 代码优化 ####

#### 5) 代码生成 ####

> 代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言。

### 1.2.3 编译的七大程序 ###

![image-20210126105021489][]

#### 1) 表格程序管理程序 ####

作用: 用来记录源程序的各种信息以及编译过程中的各种状况。

符号表一般有符号表，常数表，标号表，分程序入口表，中间代码表

![img][img 3]

*  将多个步骤组合成趟
 *  编译器构造工具

#### 2) 出错处理程序 ####

**流程**

> 一个赋值语句的翻译：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1amluZzFfMQ_size_16_color_FFFFFF_t_70_pic_center]

## 1.3 编译程序生成 ##

*  直接用机器语言编写编译程序
 *  用汇编语言编写编译程序
 *  用高级语言编写编译程序–常用方法
    
    c语言编写的编译程序 把源程序变成目标程序
    
    C语言编写的编写程序 --> c 语言的编译器 变成exe

## 1.4 总结 ##

**三种程序的解释**

*  翻译程序：把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。
 *  编译程序：把高级语言所写的源程序翻译成与之等价的低级语言（如汇编语言、机器语言等）的目标程序。如果编译阶段目标程序是机器语言程序，则分为编译阶段和运行阶段；如果生成的是汇编程序，则分为编译阶段、汇编阶段和运行阶段。
 *  解释程序：也是一种翻译程序，将源程序作为输入，边解释边执行，但其不产生目标程序，而是按照源语言的定义解释执行源程序本身。

**编译的五个阶段**：这五个阶段为逻辑关系而非执行上的先后顺序

*  词法分析：对构成源程序的字符串从左到右进行
    
     *  扫描和分解；
     *  根据语言的词法规则识别出一个一个具有独立意义的单词/单词符号/符号。
 *  语法分析：
    
     *  根据语法规则（是语法单位的形成规则，规定了如何从单词符号形成语法单位）从单词符号串中识别出各种语法单位（如表达式、说明等）；
     *  进行语法检查，即检查各种语法单位在语法结构上的正确性。
 *  语义分析及中间代码生成：对语言的各种语法单位赋予具体的意义
    
     *  对每种语法单位进行静态的语义审查；
     *  分析其含义；
     *  用另一种语言形式（更接近于目标语言的中间代码/目标语言，如一个完整表达式分解为多个子表达式）来描述该语义。
 *  代码优化：对前一阶段产生的中间代码进行等价变换或改造，目的是获取更高效的(时间、空间)目标代码。主要有局部优化和循环优化等。
 *  目标代码生成：将中间代码变换成
    
     *  特定机器上的绝对指令代码；
     *  可重定位的指令代码；汇编指令代码。

**编译的七大程序**

*  上述五个阶段的每个程序
 *  表格管理程序：  
    i. 记录源程序中所使用的变量的名字；  
    ii. 收集与名字属性相关的各种信息，如存储分配、类型、作用域，如果是函数名则还包含参数数量、传参方式、返回类型等；  
    iii. 各个阶段中需要构造、查找、修改或存取表中信息。
 *  出错处理程序：定位和跟踪错误，在五个阶段中都会用到。

**扫描遍数**：

>  *  指对源程序或者等价的中语言程序从头到尾扫描一遍并完成规定加工处理工作。
>  *  遍和阶段的含义毫无关系
>  *  多遍扫描程序：相比一遍扫描占用存储空间少，可使各遍所要完成的功能相对独立，逻辑结构更加清晰；但遍数增加会导致输入输出的开销，会降低编译效率。

**注意：**

> a) 编译程序是系统软件，而非应用软件；  
> b) 代码优化、中间代码生成并非必不可少的部分；  
> c) 含有优化部分的编译程序的执行效率不一定会高。

[img]: /images/20221023/3f6d8ed4c1854a59ac3510afdac27552.png
[img 1]: /images/20221023/cb4abf02d0e549ff952ec015cd95a155.png
[img 2]: /images/20221023/8323427fa8a54f83b67db500101b1dce.png
[image-20210126113219603]: /images/20221023/c44fd5da43ff4b9ea9cf001da56d2283.png
[image-20210126105021489]: /images/20221023/edd3a65b5d8c4d00b18d09f3c4e68425.png
[img 3]: /images/20221023/1442752db36342a3a8db6c2c1cdd4b9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1amluZzFfMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/388cab33646a4172b7f177f3a794feb3.png