Water's blog

深色模式

引论 ​

编译器 ​

编译器本身是一个程序.

一份源代码会先经过预处理器处理

  • 把存储在不同文件中的源程序聚合在一起
  • 把宏定义转换为原始语句

经过预处理器处理的源程序会被编译器编译成 汇编语言程序

汇编语言程序经过汇编器处理后会生成 可重定位 的 机器代码

可重定位: 机器代码中不包含绝对地址, 可以被加载到内存的任意位置. 在内存中存放的起始位置L不是固定的 绝对地址 = L + 相对地址

这份机器代码被链接器(Linker)/加载器(Loader) 处理后会生成最终的目标机器代码

链接器: 将多个可重定位的机器代码文件(包括库文件)连接到一起; 解决外部内存地址问题 加载器: 修改可重定位地址; 将修改后的指令和数据放在内存中适当的位置

编译器与解释器 ​

  • 编译器:

    • 读入以某种语言(源语言)编写的程序
    • 输出等价的用另一种语言(目标语言)编写的程序
    • 通常目标程序是可执行的

  • 解释器:

    • 直接使用用户提供的输入, 执行源程序中指定的操作
    • 不生成目标程序, 而是根据源程序的语义直接运行

  • 混合编译器

    • 先将源程序编译成中间代码
    • 再由解释器执行中间代码

编译器的结构 ​

编译器通常由前端和后端两部分组成

  • 前端Front End (分析部分)

    • 把源程序分解成组成要素, 以及相应的语法结构
    • 使用这个结构创建源程序的中间表示
    • 同时收集和源程序相关的信息, 存放到符号表

  • 后端Back End (综合部分)

    • 根据中间表示和符号表信息构造出目标程序
    • 同时对目标程序进行分析和优化

编译 ​

词法分析 ​

读入源程序的字符流, 输出为有意义的词素(Lexeme)的序列; 每个词素都会产生一个 词法单元(token)作为输出:

词法单元: <token-name, attribute-value> token-name是语法分析步骤使用的符号名称; attribute-value是词素的具体值

  • 例子

输入: position = initial + rate * 60 输出: <id, 1> < =, > <id, 2> < +, > <id, 3> <*, > <num, 60>

  • 词素position => 词法单元<id, 1>. 其中id是token-name, 标识符的抽象符号; 1是attribute-value, 表示符号表中position对应的条目(存放对应标识符的信息, 如名字,类型等)

  • 词素= => 词法单元< =, >. 不需要属性值, 因此attribute-value为空

  • 词素60 => 词法单元<num, 60>

分隔词素的空格会被词法分析器忽略掉

语法分析 ​

根据各个词法单元的第一个分量来创建树型的中间表示形式, 通常是语法树(Syntax Tree). 中间表示形式指出了词法单元流的语法结构

  • 例子

输入 int a, b, c; 输出:

语义分析 ​

使用语法树和符号表中的信息, 检查源程序是否满足语言定义的语义约束; 同时手机类型信息, 用于代码生成, 类型检查, 类型转换等

主要任务:

  • 收集标识符的属性信息, 构建符号表
    • 种属(简单变量, 复合变量...)
    • 类型
    • 存储位置, 长度
    • 值
    • 作用域
    • 参数和返回值信息

这里存在一个问题: 标识符的名字是字符串, 但是名字的长度可能是有长有短的(如int i; int ColculateTotalAmountWithTax), 如果为了存长字符串预留出足够的空间, 会浪费大量的内存

为了节约内存, 符号表使用了字符串表这一种数据结构. 符号表条目只存一个整数索引或者指针, 它们是定长的, 一般是4或8字节.

在字符串表中, 每个标识符的名字紧凑地存放在一个数组里. 比如第一个名字是"sum", 第二个名字是"average", 那么字符串表中就存放了"sum\0average\0".

这还带来一个好处: 在编译器后续工作中, 会频繁比较标识符的名字. 使用字符串表可以直接比较索引, 不需要一个一个的比较字符串.

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

中间代码生成 ​

根据语义分析输出, 生成类机器语言的中间表示

使用三地址码(Three-Address Code)

  • 每个指令最多包含三个运算分量

  • 很容易生成机器语言指令

  • 例子

输入: <id, 1> < =, > <id, 2> < +, > <id, 3> <*, > <num, 60> 输出:

t1 = id3 * 60
t2 = id2 + t1
id1 = t2

代码优化 ​

  • 为改进代码所进行的等价程序变换
  • 更快, 更短, 能耗更优
t1 = id3 * 60
id1 = id2 + t1

代码生成 ​

以源程序的中间表示形式作为输入, 并把它映射到目标语言

  • 指令选择
  • 寄存器分配

符号表管理 ​

记录源程序中使用的标识符, 收集各种属性, 提供一个名字的:

  • 存储分配
  • 类型
  • 作用域(什么地方可以使用这个名字)
  • 参数数量和类型
  • 每个参数的传递方法(值传递/引用传递)
  • 返回类型

所有的标识符都是名字, 但名字不一定是标识符.

名字可以是表达式, 如x.y表示x所指的结构中的字段y, 其中x和y是标识符

躺(Pass) ​

每趟读入一个输入文件, 产生一个输出文件

Copyright © 2024-present Water