编译原理简单介绍

---

• 编译原理简单介绍
  • 什么叫编译程序
    • 翻译程序
    • 编译程序
    • 翻译和编译的区别
  • 编译的过程
    • 词法分析
    • 语法分析
    • 语义分析和中间代码的产生
    • 优化
    • 目标代码生成
  • 编译程序的结构
    • 编译程序总框
    • 表格与表格的管理
    • 出错处理
    • 遍
    • 编译的前端与后端
      • 编译前端
    • 编译后端
  • 编译程序的生成
    • 编译程序的构造工具
    • T型图
    • 用高级语言L1构造编译程序
    • 编译程序的移植
    • 自编译方式
    • 构造工具

---

什么叫编译程序

翻译程序

翻译程序（Translator）是一种程序，其输入是某种语言的一系列语句，而其输出则是另一种语言的一系列语句，二者在逻辑上是等价的。就类似生活中的翻译官一样，把英语翻译成汉语，二者在意思上也是等价的。

编译程序

编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。
这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。

翻译和编译的区别

编译的过程

编译程序的工作过程一般可以分为5个阶段：
1. 词法分析
2. 语法分析
3. 语义分析和中间代码的产生
4. 优化
5. 目标代码生成

词法分析

词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（定义符、标识符、运算符、界符、常数）。

在词法分析阶段的工作中所依循的是语言的语法规则（或称构词规则）。
描述语法规则的有效工具是正规式和有限自动机。

语法分析

语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单元（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。

语法分析所依循的是语言的语法规则。
语法规则通常用上下文无关文法描述。
词法分析是一种线性分析，而语法分析是一种层次结构分析。

语义分析和中间代码的产生

这一阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。这一阶段通常包含两个方面的工作。
1. 对每种语法范畴进行静态语义的检查，例如，变量是否定义、类型是否正确等等。
2. 如果语义正确则进行中间代码的翻译。

这一阶段所依循的是语言的语义规则，通常使用属性文法描述语义规则。

优化

对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码　。
优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。

优化所依循的是程序的等价变换规则。

目标代码生成

这一阶段的任务是：把中间代码（经过优化处理之后的）变换成特定机器上的低级语言代码（绝对指令、可重定位指令、汇编指令
）。

编译程序的结构

编译程序总框

表格与表格的管理

编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。
最重要的是符号表，用来等级源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名还是变量名，还是过程名；如果是变量名，类型是什么，占多大内存，地址是多少等等。

编译各阶段均须维持表格并进行表格管理，建表的技术支持是数据结构，表格的分类、结构、处理方法决定于语言及机器，还有优化措施。

出错处理

如果源程序有错误，编译程序应设法发现错误，并把有关错误的信息报告给用户。一个好的编译程序：
1. 全
最大限度发现错误
2. 准
准确指出错误的性质和发生地点
3. 局部化
将错误的影响限制在尽可能小的范围内
4. 自动校正
若能自动校正错误则更好，但其代价非常高

源程序中的错误一般分为语法错误和语义错误。
1. 语法错误
指源程序中不符合不符合语法（或词法）规则的错误，例如：单词拼写错误、括号不匹配等等。
2. 语义错误
指源程序中不符合语义规则的错误，例如：说明错误、作用域错误、类型不匹配等等。
一般在语义分析时检出来，有的语义错误要在运行时才能检测出来。

遍

遍 是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。遍数多了，整个编译程序的逻辑结构就比较清晰，但是会增加输入和输出所消耗的时间。因此，在主存可能的前提下，一般还是遍数少的好。
分遍的依据：
1. 源程序的结构
2. 选用机型的内存大小
3. 设计目标的技术指标
4. 参加编译程序人员的数量、素质

好的编译程序的指标：
1. 符合语法规则的程序都可执行。
2. 任何非法的错误都有可能识别，并尽量少的产生连锁反应。
3. 错误不至于导致系统崩溃。
4. 可维护和可读性。
5. 模块化和结构化。

编译的前端与后端

概念上我们有时候把编译程序分成编译前端和编译后端。

编译前端

前端主要由源语言有关但与目标机无关的那些部分组成，通常包括词法分析、语法分析、语义分析与中间代码的产生，有的代码优化工作也可以包括在前端。

编译后端

后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。
通常后端不依赖源语言而仅仅依赖于中间语言。

编译程序的生成

编译程序的构造工具

以前人们构造编译程序大多数采用的是机器语言或汇编语言，现在只有为了充分发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，才会采用这种工具来构造编译程序（或编译程序的“核心”部分）。现在越来越多采用高级语言来构造编译程序。

T型图

为了便于说明，我们常采用T型图来表示源语言S、目标语言T、和比编译程序实现语言I之间的关系。
每个T型图相当于一个编译程序。

用高级语言L1构造编译程序

如果A机器上有一个使用A机器代码实现的某高级语言L₁的编译程序（黄色），则我们可以使用L1语言编写另外一种高级语言L₂的编译程序（橙色）。把写好的L₂编译程序经过L₁编译程序编译后就可以得到A机器码实习的L₂编译程序（绿色）。

编译程序的移植

通过上面用高级语言L1构造编译程序的原理，我们可以实现编译程序的“移植”。首先我们有一个可以在A机器上编译的高级语言L，

接下来我们使用L去写一个能够在B机器上运行的编译程序，

然后通过L的编译程序就可以生成在A机器上可以运行的产生B机器代码的编译程序（3）。

使用这个编译程序（3）去编译一遍（2）就可以得到能在B机器上运行的B机器代码的编译程序（4）.

自编译方式

先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以它为工具构造能编译更多语言成分的较大编译程序，如此不断扩展，最后形成整个编译程序（滚雪球），这种通过一系列自展途径而形成的编译程序的过程叫做自编译过程。

构造工具

现在人们已经建立了多种编制部分编译程序或者整个编译程序的有效工具。构造编译程序的工具称为编译程序-编译程序、编译程序产生器或翻译程序书写系统。
例如：
自动产生扫描器：LEX FLEX
自动产生语法分析器：YACC BISON