编译原理

一、词法分析：从字符到单词

任务：将字符序列转换为有意义的“单词”（Token）流

1.1 理论基础

• 正则表达式（RE）：形式化描述单词构成模式
  • 示例：标识符 → letter(letter|digit)*
• 有限状态自动机：词法分析器的数学模型
  • NFA：易于由RE构造
  • DFA：执行效率高
• 关键算法：
  • 子集构造法：NFA → DFA
  • DFA最小化算法

1.2 输出形式

• 二元式：(token_name, attribute_value)
• 示例：position = initial + rate * 60; → <id,1> <=> <id,2> <+> <id,3> <*> <num,60>

1.3 实现工具

• 手工实现：状态转换图
• 自动生成：Lex/Flex

二、语法分析：构建程序结构

任务：根据单词流识别语法结构，构造语法树

2.1 形式化基础

• 上下文无关文法（终结符、非终结符、产生式、开始符号）
• 二义性文法：同一句子有多棵语法树
  • 解决方案：重写文法 / 定义运算符优先级与结合性

2.2 两大分析方法

2.3 关键概念区分：最左推导 vs 最右推导

2.4 实现工具

• Yacc / Bison：LALR(1)分析器生成器
• 错误恢复策略：恐慌模式恢复

三、语法制导翻译与语义分析

任务：将语义动作（类型检查、生成中间代码）与文法规则关联

3.1 核心概念

• 语法制导定义：为产生式附加语义规则
• 属性分类：
  • 综合属性：自底向上（子→父）
  • 继承属性：自顶向下（父/兄弟→当前）
• 翻译方案：规定语义规则执行时机与次序

3.2 实现方式

• 语法树遍历（深度优先等）
• 在LR分析中嵌入语义动作

3.3 应用

• 类型检查
• 控制流检查
• 中间代码生成

四、中间代码生成

任务：生成介于源语言与目标代码之间、易于优化与移植的表示

4.1 常见形式

4.2 翻译内容

• 数组访问（地址计算）
• 结构体访问
• 控制流语句（if、while、for 的跳转逻辑）
• 过程调用

4.3 关键技术

• 回填：处理控制流中的跳转目标

五、运行时刻环境

任务：定义目标程序运行时的内存布局与管理机制

5.1 核心机制

• 活动记录：函数调用时在栈上分配的数据块（参数、返回地址、局部变量）
• 调用约定：调用者与被调用者协作管理栈和传递参数
  • 值传递 vs 引用传递

5.2 存储管理

5.3 其他职责

• 变量访问机制
• 过程间连接
• 与操作系统、I/O设备的接口

六、目标代码生成

任务：将中间代码映射到目标机器指令集，管理有限硬件资源

6.1 核心挑战与任务

6.2 相关优化

• 基本块优化
• DAG（有向无环图）优化

七、代码优化

任务：改进中间代码或目标代码，提升性能（速度/体积）

7.1 分析基础：数据流分析

• 核心方法：建立并求解数据流方程
• 典型分析：
  • 到达-定值分析：某个定值能到达哪些点
  • 活跃变量分析：变量在哪些点还会被使用
  • 可用表达式分析：表达式在哪些点已计算且值未变

7.2 经典优化技术

7.3 可能的考题形式

• 给定一个程序，进行优化
• 数据流分析框架的理解与应用

附录：自顶向下 vs 自底向上分析对比