编译技术1-3

The Structure of a Compiler 编译器的结构

​​From Description to Implementation 从描述到实现​​

A compiler is a multi-phase program that translates high-level code into machine-executable code. 编译器是一个 多阶段程序，将 高级代码 转换为 机器可执行代码。

The compilation process can be divided into two main parts: 编译过程可分为 两个主要部分：

  1. Analysis (Front-End 前端) – Understands the source code. • 分析阶段（前端） – 理解源代码。
  2. Synthesis (Back-End 后端) – Generates the target code. • 综合阶段（后端） – 生成目标代码。

1. Lexical Analysis (Scanning) 词法分析（扫描） ​​Purpose 目的​​ • Breaks the source code into tokens (keywords, identifiers, operators, etc.).

• 将 源代码 分解为 词法单元（关键字、标识符、运算符等）。

• Removes whitespace & comments.

• 移除 空白符和注释。

Example 示例

1
int x = 10 + 5;

→ Tokens: int, x, =, 10, +, 5, ;

Tools 工具 • Finite Automata (有限自动机)

• Lex/Flex (词法分析器生成器)

2. Syntax Analysis (Parsing) 语法分析（解析） ​​Purpose 目的​​ • Checks if the tokens follow the grammar rules of the language.

• 检查 词法单元 是否符合语言的 语法规则。

• Builds a parse tree or abstract syntax tree (AST).

• 构建 语法分析树 或 抽象语法树 (AST)。

Example 示例

1
int x = 10 + 5;

→ AST:

1
2
3
4
5
  =
 / \
x   +
   / \
  10  5

Tools 工具 • Context-Free Grammars (上下文无关文法)

• Yacc/Bison (语法分析器生成器)

3. Semantic Analysis 语义分析 ​​Purpose 目的​​ • Ensures the program is meaningful (e.g., type checking, scope resolution).

• 确保程序 有意义（如类型检查、作用域解析）。

• Detects logical errors (e.g., undeclared variables, type mismatches).

• 检测 逻辑错误（如未声明变量、类型不匹配）。

Example 示例

1
int x = "hello";  // Error: Type mismatch (类型不匹配)

Key Tasks 关键任务 • Type Checking (类型检查)

• Symbol Table Management (符号表管理)

The first three phases of a compiler (lexical analysis, syntax analysis, semantic analysis) can be understood by analogy to how humans process language. 编译器的前三个阶段（词法分析、语法分析、语义分析）可以类比 人类理解语言的过程。

4. Intermediate Representation (IR) Generation 中间代码生成 ​​Purpose 目的​​ • Converts the AST into an intermediate form (e.g., three-address code).

• 将 AST 转换为 中间表示（如三地址码）。

• Makes the code easier to optimize & translate.

• 使代码 更易于优化和翻译。

Example 示例

1
x = 10 + 5;

→ Three-address code:

1
2
t1 = 10 + 5  
x = t1

Common IR Forms 常见中间表示 • Three-Address Code (三地址码)

• Static Single Assignment (SSA, 静态单赋值形式)

5. IR Optimization 中间代码优化 ​​Purpose 目的​​ • Improves performance & efficiency without changing functionality.

• 在不改变功能的前提下提升 性能与效率。

Optimization Techniques 优化技术

Technique 技术 Example 示例
Constant Folding (常量折叠) x = 10 + 5 → x = 15
Dead Code Elimination (死代码删除) Remove unused variables/functions
Loop Optimization (循环优化) Reduce loop overhead

6. Code Generation 代码生成 ​​Purpose 目的​​ • Translates IR into machine/assembly code.

• 将 中间代码 转换为 机器/汇编代码。

Example 示例

1
2
3
MOV R1, 10  
ADD R1, 5  
MOV [x], R1

Challenges 挑战 • Register Allocation (寄存器分配)

• Instruction Selection (指令选择)

7. Target Code Optimization 目标代码优化 ​​Purpose 目的​​ • Further improves execution speed & memory usage.

• 进一步优化 执行速度与内存使用。

Techniques 技术 • Peephole Optimization (窥孔优化)

• Example: Replace MOV R1, 0 → XOR R1, R1 (faster).

• Inlining (内联展开)

Summary 总结 ​​Compiler Phases 编译器阶段​​

Phase 阶段 Key Task 关键任务 Output 输出
Lexical Analysis Tokenize source code Tokens
Syntax Analysis Build parse tree AST
Semantic Analysis Check meaning Annotated AST
IR Generation Convert to IR Three-address code
IR Optimization Optimize IR Optimized IR
Code Generation Generate machine code Assembly
Target Optimization Final optimizations Optimized binary

Key Concepts 关键概念 • Front-End (前端) = Lexical + Syntax + Semantic Analysis

• Back-End (后端) = IR Generation + Optimization + Code Generation

• Optimization (优化) happens at both IR & machine code levels.

"A compiler is a bridge between human thought and machine execution." “编译器是人类思维与机器执行之间的桥梁。”

例子

Compiler Processing Stages with Visual Examples ​​编译器处理阶段可视化示例​​

1. Lexical Analysis (词法分析) ​​Input Code (输入代码)​​

1
2
3
4
while (y < z) {
    int x = a + b;
    y += x;
}

Token Stream (词法单元流)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
T_While        // 关键词 while
T_LeftParen    // 左括号 (
T_Identifier(y) // 标识符 y
T_Less         // 运算符 <
T_Identifier(z) // 标识符 z
T_RightParen   // 右括号 )
T_OpenBrace    // 左大括号 {
T_Int          // 类型声明 int
T_Identifier(x) // 标识符 x
T_Assign       // 赋值运算符 =
T_Identifier(a) // 标识符 a
T_Plus         // 运算符 +
T_Identifier(b) // 标识符 b
T_Semicolon    // 分号 ;
T_Identifier(y) // 标识符 y
T_PlusAssign   // 复合赋值 +=
T_Identifier(x) // 标识符 x
T_Semicolon    // 分号 ;
T_CloseBrace   // 右大括号 }

2. Syntax Analysis (语法分析) ​​Abstract Syntax Tree (抽象语法树)​​

image-20250501123023869

3.Semantic Analysis

加了一些属性！

image-20250501123023869

4. IR Generation Three-Address Code (三地址码)

1
2
3
4
5
Loop:
	x = a + b
    y = x + y
    _t1 = y < z
    if _t1 goto Loop

5.IR Optimization

Optimized Version (优化版本)

1
2
3
4
5
x = a + b
Loop:
    y = x + y
    _t1     =  y  <  z
   if  _t1   goto   Loop

6. Code Generation (目标代码生成) MIPS Assembly (MIPS汇编)

1
2
3
4
5
    add $1, $2, $3    # x = a + b
Loop:
    add $4, $1, $4    # y = x + y
    slt $6, $4, $5    # tmp = (y < z)
    beq $6, $0, Loop  # if (y < z) goto Loop

这段MIPS汇编代码是编译器生成的最终机器指令，我来逐行解释其工作原理和寄存器分配：

代码解析 

1
2
3
4
5
    add $1, $2, $3    # x = a + b
Loop:
    add $4, $1, $4    # y = x + y
    slt $6, $4, $5    # tmp = (y < z)
    beq $6, $0, Loop  # if (y < z) goto Loop

寄存器分配假设

寄存器 变量 说明
$1 x 存储 a + b 的结果
$2 a 输入变量
$3 b 输入变量
$4 y 循环变量（会动态更新）
$5 z 循环终止条件
$6 _t1 临时比较结果

逐行执行流程 1. 初始化计算

1
add $1, $2, $3    # x = a + b
• 将寄存器 $2（a）和 $3（b）相加，结果存入 $1（x）。

  1. 循环标签

    1
    Loop:
    • 标记循环的起始位置（跳转目标）。

  2. 更新循环变量

    1
    add $4, $1, $4    # y = x + y
    • 将 $1（x）与 $4（当前 y 值）相加，结果写回 $4（实现 y += x）。

  3. 条件比较

    1
    slt $6, $4, $5    # tmp = (y < z)
    • slt (Set Less Than)：若 $4（y） < $5（z），则 $6 = 1，否则 $6 = 0。

  4. 条件跳转

    1
    beq $6, $0, Loop  # if (y < z) goto Loop
    • beq (Branch if Equal)：若 $6 == $0（即 y < z 为假），则跳出循环；否则跳回 Loop 标签继续执行。

关键指令说明 • slt 指令

• 功能：比较两个寄存器的值，若 Rs < Rt 则 Rd = 1，否则 Rd = 0。

• 示例：slt $6, $4, $5 → 若 y < z，则 $6 = 1。

• beq 指令

• 功能：若 Rs == Rt 则跳转到目标标签。

• 此处逻辑：beq $6, $0, Loop → 若 $6 == 0（即 y >= z），则不跳转（顺序执行退出循环）；否则继续循环。

优化点 1. 寄存器复用
• x（$1）在循环中作为常量复用，避免重复计算。

  1. 复合条件
    • 直接通过 slt + beq 实现 while (y < z)，无需显式布尔变量。

  2. 标签跳转
    • 使用标签 Loop 简化控制流，避免绝对地址计算。

对应高级代码

1
2
3
4
int x = a + b;
while (y < z) {
    y += x;
}

常见问题 Q1: 为什么 beq $6, $0, Loop 表示 "如果 y < z 则继续循环"？
• 因为 slt 的结果是反的：

• 当 y < z 时，$6 = 1，此时 $6 != $0，不跳转（继续执行循环体）。

• 当 y >= z 时，$6 = 0，此时 $6 == $0，跳转（退出循环）。

Q2: 如何修改为 "如果 y >= z 则退出循环"？
• 改用 bne（Branch if Not Equal）：

1
bne $6, $0, Loop  # if (y < z) goto Loop

7.Optimized Assembly (优化汇编)

1
2
3
4
    add $1, $2, $3
Loop:
    add $4, $1, $4
    blt $4, $5, Loop  # 直接使用分支指令

编译流程总结

1. 核心编译阶段 （1）前端处理（Front-End） | 阶段 | 功能 | 关键输出 | |------|------|----------| | 词法分析（Scanner） | 将源代码拆分为词法单元 | Tokens（标记流） | | 语法分析（Parser） | 检查语法结构，构建语法树 | Syntax Tree（语法树） | | 语义分析（Semantic Analyzer） | 验证逻辑正确性（类型/作用域） | Annotated Tree（带注释的语法树） |

（2）中端处理（Middle-End）

阶段 功能 关键输出
中间代码生成（Intermediate Code Generator） 转换为平台无关的中间表示 Intermediate Code（三地址码等）
中间代码优化（Intermediate Code Optimizer） 提高代码效率（常量折叠/死代码删除等） Optimized Intermediate Code

（3）后端处理（Back-End）

阶段 功能 关键输出
目标代码生成（Code Generator） 生成目标机器代码（汇编/二进制） Target Code
目标代码优化（Target Code Optimizer） 针对硬件的最终优化（寄存器分配/指令调度） Optimized Target Code

2. 关键辅助组件 | 组件 | 作用 | 交互阶段 | |------|------|----------| | 符号表（Symbol Table） | 记录变量/函数信息（类型/地址） | 语义分析 → 代码生成 | | 字面量表（Literal Table） | 管理常量数据（字符串/数字） | 词法分析 → 代码生成 | | 错误处理器（Error Handler） | 收集并报告编译错误 | 全阶段 |

3. 流程特点 1. 分层处理
• 前端：语言相关（分析源代码结构）

• 中端：平台无关（优化中间表示）

• 后端：机器相关（生成目标代码）

  1. 数据流可视化
    • 蓝色箭头明确展示阶段间的输入/输出关系

    • 粉色标注辅助组件与主流程的交互

  2. 优化贯穿全程
    • 中端优化：逻辑层面的优化（如循环展开）

    • 后端优化：硬件相关的优化（如指令级并行）

4. 典型输入输出示例 

1
2
3
4
5
6
7
8
9
10
// 源代码（Source Code）
int x = 10 + 5;

// 中间代码（Intermediate Code）
t1 = 10 + 5
x = t1

// 优化后的目标代码（Target Code）
MOV R1, 15  ; 常量折叠优化
MOV [x], R1