什么是编译?

计算机程序语言可以分为:

  • 机器语言(Machine Language):
    • 特点:可以被计算机直接理解
    • 与人类表达习惯相去甚远
    • 难记忆、编写、阅读,易写错
  • 汇编语言(Assembly Language):
    • 特点:在机器语言的基础上引入助记符
    • 依赖于特定机器,非专业人员使用受限制
    • 编写效率依然很低
  • 高级语言(High Level Language):
    • 特点:类似于数学定义或自然语言的简洁形式
    • 接近人类表达习惯
    • 不依赖于特定机器
    • 编写效率高

一个例子:人工英汉翻译

编译(Compiling):将高级语言(源语言)翻译为汇编语言或机器语言(目标语言)的过程

  • 即:高级语言->编译->汇编语言->汇编->机器语言
  • 或:高级语言->编译->机器语言
  • 例:x=2 -> MOV x,2 -> C706 0000 0002(用十六进制表示的二进制数)

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

为了建立可执行目标程序,除编译器还需要一些其他工具进行配合:

  • 预处理器(Preprocessor):
    • 一个源程序可能分成几个模块存放在不同的文件里,需要预处理器把存储在不同文件中的源程序聚合在一起
    • 把称为宏的缩写语句转换为原始语句
  • 编译器(Compiler):
    • 将高级语言翻译成汇编语言或机器语言
  • 汇编器(Assembler):
    • 将汇编语言翻译成可重定位的机器语言
    • 若在编译器阶段已经直接将高级语言翻译成机器语言,则可以省略汇编器
    • 可重定位(Relocatable)/可再装配
      • 数据在内存存放的起始位置L不是固定的,起始位置+相对地址=绝对地址)
  • 链接器(Linker):
    • 将多个可重定位的机器代码文件(包括库文件)连接到一起
    • 解决外部内存地址问题(一个文件中的代码可能指向另一个文件中的位置)
  • 加载器(Loader):
    • 修改可重定位地址
    • 将修改后的指令和数据放到内存中适当的位置(然后执行)

编译器结构:分析部分(前端)+综合部分(后端)

  • 前端(front end):与源语言相关
    • 字符流——词法分析器——词法单元流——语法分析器——语法树——语义分析器——语法树——中间代码生成器
  • 前端——中间表示形式——机器无关代码优化器——中间表示形式——后端
  • 后端(back end):与目标语言相关
    • 中间表示形式——目标代码生成器——目标机器语言——机器相关代码优化器——目标机器语言

在分析过程中需要收集标识符的属性信息,使用符号表(Symbol Table)存放属性信息,生成的符号表可供编译的各个步骤使用

  • 符号表是用于存放标识符的属性信息的数据结构
    • 名字(name):字段以字符串表形式存储
      • 将所有name字段组织成一个长的字符串,符号表中存储指向其起始位置的字符即可
      • name=标识符在字符串表中的起始位置+长度
    • 种属(Kind):简单变量、复合变量(数组、记录、…)、过程、…
    • 类型(Type):整型、实数型、字符型、布尔型、指针型、…
    • 存储位置、长度
    • 作用域(实际上是访问链的嵌套关系)
    • 参数和返回值信息:参数个数、参数类型、参数传递方式、返回值类型、…
  • 符号表的作用
    • 辅助代码生成
    • 一致性检查

词法分析

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

token:<种别码,属性值>

种别码由语法分析部分使用,属性值为指向符号表中关于此词法单元的条目(不是指单词对应的实际存储的值)

  • 在上下文无关文法中,种别码一般是一个终结符号
  • 种别码:
    • 可以使用抽象符号作为种别码的名字,也可以使用单词本身
    • 属性值可以为空
序号 单词类型 种别码 token类型
1 关键字 programme,if,else,then,… 一词一码
2 标识符 变量名,数组名,记录名,过程名,… 多词一码
3 常量 整型,浮点型,字符型,布尔型,… 一型一码
4 运算符 算术、关系、逻辑… 一型一码/一词一码
5 界限符 ;,(),{},… 一词一码

例:程序中语句经词法分析后得到的token序列

输入:while(value!=100){num++;}
输出:

序号 程序符号 token
1 while < WHILE, - >
2 ( < SLP, - >
3 value < IDN, value >
4 != < NE, - >
5 100 < CONST, 100 >
6 ) < SRP, - >
7 { < LP, - >
8 num < IDN, num >
9 ++ < INC, - >
10 ; < SEMI, - >
11 } < RP, - >

语法分析

主要任务:从词法分析器输出的token序列中识别出的token,通过token中的第一个分量(种别码)构造语法分析树(parse tree),语法分析树描述句子的语法结构

例:赋值语句的分析树

position = initial + rate * 60
token序列:
<id,1> <=> <id,2> <+> <id,3> <*> <\number,4>

例:变量声明语句的分析树
文法:

<D> -> <T> <IDS>;
<T> -> int|real|char|bool;
<IDS> -> id|<IDS>,id

输入:int a,b,c;

语义分析

主要任务:进一步收集类型信息,将这些信息放入语法树或符号表

语义检查

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

中间代码生成及编译器后端

常用中间表示形式

  • 三地址码(Three-address Code)

    • 三地址码由类似于汇编语言的指令序列组成,每个指令最多有三个操作数(operand)
    • 可唯一确定运算完成的顺序(右部至多只有一个运算符)
  • 语法结构树/语法树(Syntax Trees)

    • 注意这里的语法格式树(AST)和语法分析阶段的语法分析树不同
  • 三地址码中地址的形式可能是:

    • 源程序中的名字(name)
    • 常量(constant)
    • 编译器生成的临时变量(temporary)
  • 三地址指令的表示

    • 四元式(Quadruples)
      • (op,y,z,x)
      • 四元式之间的联系是通过临时变量实现的(注意是四元式之间)
      • 四元式的优点是便于优化处理和表的变动
    • 三元式(Triples)
    • 间接三元式(Indirect triples)

常见的三地址指令

序号 指令类型 指令形式 四元式表示
1 赋值指令 x = y op z (op,y,z,x)
2 复制指令 x = y (=,y,-,x)
3 条件跳转 if x relop y goto n (relop,x,y,n)
4 非条件跳转 goto n (goto,-,-,n)
5 参数传递 param x (param,-,-,x)
6 过程调用 call p,n (call,p,n,-)
7 过程返回 return x (return,-,-,x)
8 数组引用 x = y[i] (=[],y,i,x)
9 数组赋值 x[i] = y ([]=,y,x,i)
10 地址及指针操作 x = & y (&,y,-,x)
10 地址及指针操作 x = *y (=*,y,-,x)
10 地址及指针操作 *x = y (*=,y,-,x)

例:中间代码生成

while a<b do
    if c<5 then
        while x>y do
            z=x+1;
    else x=y;

100:(j<,a,b,102)
101:(j,-,-,112)
102:(j&lt;,c,5,104)
103:(j,-,-,110)
104:(j>,a,b,102)
105:(j,-,-,100)
106:(+,x,1,t1)
107:(=,t1,-,z)
108:(j,-,-,104)
109:(j,-,-,100)
110:(=,y,-,x)
111:(j,-,-,100)
112:

编译器后端

目标代码生成器以源程序的中间表示形式作为输入,并将其映射到目标语言

  • 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器
  • 代码优化
    • 为改进代码所进行的等价程序交换,使其运行得更快一些,占用空间更少一些,或二者兼顾