编译原理学习笔记(一)概览

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

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

What is 编译

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

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

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

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

编译系统的结构

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

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

image-20200420174358243

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

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

  1. 词法分析:识别每个单词,确定各个单词的词类、词性(名词、介词、动词等)

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

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

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

编译器的逻辑结构如下:

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

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

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

编译器前端概述

词法分析

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

token:< 种别码,属性值 >

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

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

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

语法分析

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

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

例如,一个赋值语句的语法分析树:

再例如,声明变量的语句语句:

声明变量语句的文法:

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

语义分析

语义分析的主要任务:

  • 收集标识符的属性信息

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

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

  • 语义检查

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

中间代码生成

常用的中间表示形式:

  • 三地址码

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

  • 语法结构树/语法数(Syntax Trees)

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

常用的三地址指令:

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

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

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

编译器后端概述

目标代码生成

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

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

代码优化

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

0%