编译原理--引入
且任容枯 Lv4
  2026-04-05 16:46:43 2026-04-05 16:46  

编译原理–引入

语言处理器

编译器：源程序（a语言）翻译成目标程序（b语言）
解释器：直接利用用户提供的输入执行源程序中指定的操作
java –>编译器 –> 字节码（bytecode）–> 解释器 –> 输出

源程序A –> 预处理器 –> 源程序B –> 编译器 –> 目标汇编程序 –> 汇编器 –> 可重定位机器代码 –> 链接器/加载器 –> 目标机器代码

编译器的结构

从源程序映射到目标程序， 这个映射的过程由俩个部分组成–> 分析（analysis） 和 综合 (synthesis)

分析(也叫前端):

  • 拆分源程序为多个组成要素，并且加上语法结构 形成一个中间表示
  • 源程序要是不正确，需要提供信息给用户改正
  • 将一些信息形成符号表 + 中间表示 送给综合

综合(后端):

  • 将符号表 + 中间表示 –> 目标程序

一个编译器的各个步骤：
字符流 –> 词法分析器 –> 符号流 –> 语法分析 –> 语法树 –> 语义分析 –> 语法树 –> 中间代码生成器/符号表 –> 中间表示形式 –> 机器无关代码优化器 –> 中间表示形式 –> 代码生成器 –> 目标机器语言 –> 机器相关代码优化器 –> 目标机器语言

词法分析

读入字符流形成词素序列， 对于每个词素产生词法单元（token）

attribute-value>``` token-name是语法分析步骤使用的抽象符号，attribute-value指向符号表中关于这个词法单元的条目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
```
position = initial + rate * 60

position --> <id, 1>
=  --> < = >
initial --> <id, 2>
+  --> < + >
rate --> <id, 3>
* --> < * >
60 --> < 60 >

<id, 1> < = > <id, 2> < + > <id, 3> < * > < 60 >

符号表
1 position
2 initial
3 rate

语法分析

语法树

1
2
3
4
5
6
7
          < = > 
        /       \
<id, 1>         < + >
             /         \
        <id, 2>         < * >
                    /          \
                <id, 3>        < 60 >

语义分析

  • 使用语法树和符号表来检查源程序是否和语言定义的语义一致
  • 类型检查，检查每个运算符是否有匹配的运算分量
  • 有些语言支持自动类型转换 < 60 > –> inttofloat

中间代码生成

三地址代码：

1
2
3
4
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

代码优化

1
2
3
4
5
6
7
8
t1 = inttofloat(60)  多余 直接用60.0
t2 = id3 * t1
t3 = id2 + t2   t3 是多余的
id1 = t3    


t1 = id3 * 60.0
id1 = id2 + t1

代码生成

代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言。如果目标语言是机器代码，那么就必须为程序使用的每个变量选择寄存器或内存位置。中间指令就被翻译成能够完成相同任务的机器指令序列

1
2
3
4
5
LDF R2, id3       // R2 = id3
MULF R2, R2, #60.0  // R2 = R2 * 60.0
LDF R1, id2      // R1 = id2
ADDF R1, R1, R2  //  R1 = R1 + R2 
STF id1, R1      // id1 = R1

符号表管理

记录使用的变量名字，并收集每个名字的属性（存储分配，类型， 作用域）
过程名字（参数数量，类型，传递方法（值传递，引用传递））

多个步骤组合成趟

就不写

编译器构造工具

  • 语法分析器的生成器:可以根据一个程序设计语言的语法描述自动生成语法分析器。
  • 扫描器的生成器:可以根据一个语言的语法单元的正则表达式描述生成词法分析器。
  • 语法制导的翻译引擎:可以生成一组用于遍历分析树并生成中间代码的例程。
  • 代码生成器的生成器:依据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言的规则，生成一个代码生成器。
  • 数据流分析引擎:可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。数据流分析是代码优化的一个重要部分。
  • 编译器构造工具集:提供了可用于构造编译器的不同阶段的例程的完整集合

程序设计语言基础

静态和动态的区别

在为一个语言设计一个编译器时，我们所面对的最重要的问题之一是编译器能够对一个程序做出哪些判定。如果一个语言使用的策略支持编译器静态决定某个问题，那么我们说这个语言使用了一个静态(static)策略，或者说这个问题可以在编译时刻(compile time)决定。另一方面，一个只允许在运行程序的时候做出决定的策略被称为动态策略(dynamic policy)，或者被认为需要在运行时刻(run time)做出决定。

静态作用域 和 动态作用域
static int x; 编译的时候就可以确定x在哪；int x； 运行时才知道x在哪；

环境和状态

名字 –环境–> 内存位置（变量） – 状态 –> 值