编译原理学习笔记（一）概览

本节主要介绍了编译的基本概念，编译程序的逻辑结构、各部分的基本介绍。

参考自中国大学Mooc网上的哈尔滨工业大学的编译原理课程，用到的图也是从Mooc网中下载的原课程课件

What is 编译

计算机语言大题可以分成三类，自顶向下为高级语言、汇编语言、机器语言。

从汇编语言到机器语言的过程称为汇编。将高级语言翻译成机器语言的处理过程，称为编译。因此，在编译的过程中，高级语言称为源语言，机器语言称为目标语言。

编译器在语言处理系统中的位置：

• 预处理器Preprocessor：将存储在不同文件中对方源程序聚合在一起，并将宏展开。
• 编译器compiler：将经过预处理的源程序翻译成汇编语言程序
• 汇编器Assembler：生成可重定位的机器代码
• 链接器(linker)：将多个可重定位的机器代码文件（包括库文件）链接到一起，并解决一些外部内存地址的问题
• 加载器(loader)：修改可重定位的地址，并将指令和数据装入内存中运行

编译系统的结构

编译器是如何将高级语言翻译成汇编语言/机器语言的呢？

这里参考了一个人工英汉翻译的例子：

可见，翻译的过程大体分为两步，首先，从源语言（英语）的层面，去分析句子的意思（语义分析）得出了句子的语义，然后通过句子的语义（中间表示），将句子再用汉语说一遍（生成目标语言），这就完成了一个翻译的过程。

而分析句子的意思的过程中，又可以分成三步：

1. 词法分析：识别每个单词，确定各个单词的词类、词性（名词、介词、动词等）

   

2. 语法分析：根据词法分析得出的单词的词性，识别出句子中的各类短语，从而获得句子的结构

   

3. 语义分析：根据句子的结构，分析各个短语在句子中充当什么成分、从而分析出各个名词性成分和核心谓语动词之间的关系，从而得到整个句子的语义关系、生成中间表示（中间代码）

   

中间表示：这里的中间表示是一个桥梁的作用，他是独立于具体的语言的，也就是说，不管源语言是英语还是德语西班牙语日语，都可以用这个中间语言来表示。比如上面的英语句子，就可以用下面这个图来表示：

编译器的逻辑结构如下：

可以看到，总体可以分成两个部分，称之为“前端”和“后端”。

前端是生成中间表示之前的部分，它是与源语言相关的，包括词法分析、语法分析、语义分析、中间代码生成等逻辑部分，最终会生成中间代码。

后端是生成中间代码之后的部分，它是与目标语言相关的，它包括目标代码的生成和机器代码的优化，最终生成目标机器语言。

编译器前端概述

词法分析

词法分析的主要任务 从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。 将识别出的单词转换成统一的机内表示——词法单元(token)形式

token：< 种别码，属性值 >

程序中的单词大体可以分成五类：

	单词类型	种别	种别码
1	关键字	if、else、then、……	一词一码
2	标识符	变量名、数组名、函数名等	多词一码
3	常量	整形、浮点型、字符型、布尔型	一型一码
4	运算符	算术（ + - * / ++ — ） 关系（ > < == != >= <= ） 逻辑（ & \	~）	一词一码或一型一码
5	界限符	; ( ) = { } ……	一词一码

一个词法分析后得到token序列的例子：

语法分析

语法分析器（parser）从词法分析器输出的token序列中识别出各类短语，并构造语法分析树（parse tree）

语法分析树描述了句子的语法结构：

例如，一个赋值语句的语法分析树：

再例如，声明变量的语句语句：

声明变量语句的文法：

输入源代码：int a, b, c，可得到语法分析树：

语义分析

语义分析的主要任务：

• 收集标识符的属性信息

  • 种属：简单变量、复合变量（数组、记录）、过程（函数）、……
  • 类型：整型、实型、字符型、布尔型、指针型、……
  • 存储位置、长度
  • 值
  • 作用域
  • 参数和返回值信息：参数个数、参数信息、参数传递方式、返回值类型、…

  收集到的属性信息，会存放在符号表中

  

• 语义检查

  • 变量名或过程未经声明就使用
  • 变量或过程名重复声明
  • 运算分量类型不匹配
  • 操作符与操作数之间的类型不匹配
    • 数组下标不是整数
    • 对非数组变量使用数组访问操作符
    • 对非过程名使用过程调用操作符
    • 过程调用的参数类型或数目不匹配
    • 函数返回类型有误

中间代码生成

常用的中间表示形式：

• 三地址码

  三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数

• 语法结构树/语法数（Syntax Trees）

这里注意，三地址指令并不等于汇编指令。汇编指令与机器指令是一一对应的，是与机器有关的；而三地址指令是中间代码，是机器无关的中间语言。

常用的三地址指令：

三地址指令可以用四元式、三元式、间接三元式等形式来表示

三地址指令的四元式表示：

一个中间代码生成的例子如下图

编译器后端概述

目标代码生成

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

目标代码生成的一个重要任务是，为程序中使用的变量合理分配寄存器。

代码优化

代码优化是指为改进代码而进行的一些等价程序变换，使其运行得更快一些、占用空间更少一些，或者两者兼顾。

test