什么是编译程序
把某一种语言程序(称为源语言程序)等价地转换
成另一种语言程序(称为目标语言程序)的程序
高级语言程序需要编译程序的翻译才能变成机器语言程序（目标程序），机器程序可以运行成为结果
编译程序：
1.诊断编译程序(Diagnostic Compiler)
2.优化编译程序(Optimizing Compiler)
3.交叉编译程序(Cross Compiler)
4.可变目标编译程序(Retargetable Compiler)
解释程序(Interpreter)
把源语言写的源程序作为输入，但不产生目标
程序，而是边解释边执行源程序
为什么要学习编译原理
理解计算系统
设计计算系统
训练计算思维(Computational Thinking)
计算思维基本概念
Jeannette M. Wing, Computational Thinking,
Communications of ACM, Vol.49, No.3, 2006,
pp.33-35.
被认为是近十年来产生的最具有基础性、长期性的
学术思想，成为21世纪计算机科学研究和教育的热
点
- 计算思维是运用计算机科学的基础概念去求解问题、
设计系统和理解人类的行为，它包括了一系列广泛
的计算机科学的思维方法 - 计算思维和阅读、写作和算术一样，是21世纪每个
人的基本技能，而不仅仅属于计算机科学家 - 计算思维在生物、物理、化学、经济学、统计学等
其他学科中的影响已经显现
计算思维包括一系列广泛的计算机科学的思维方法：
- 抽象
- 忽略一个主题中与当前问题(或目标)无关的那些方面，
以便更充分地注意与当前问题(或目标)有关的方面 - 从众多的事物中抽取出共同的、本质性的特征，舍
弃其非本质的特征 - 是一种从个体把握一般、从现象把握本质的认知过
程和思维方法 - 图灵机就是一种抽象
- 编译原理中的"抽象"
- 有限自动机
- 形式文法
- 自动化
- 将抽象思维的结果在计算机上实现，是一个将计算
思维成果物化的过程，也是将理论成果应用于技术
的实践 - 自动化的思维方法不仅体现在编译程序本身的工作
机制上，更体现在了编译程序的生成工具的研究和
设计上 - 编译原理中的"自动化“
- 有限自动机
- 预测分析程序
- 算符优先分析
- LR分析
- …
- 问题分解
- 分解(Decomposition)
- 将大规模的复杂问题分解成若
干个较小规模的、更简单的问
题加以解决 - 对问题本身的明确描述，并对问
题解法作出全局性决策 - 把问题分解成相对独立的子问题
- 再以同样的方式对每个子问题进
一步精确化，直到获得对问题的
明确的解答 - 分解(Decomposition)
- 层次化管理
- 编译原理中的"问题分解"
- 为什么编译程序引入中间语言？
- 为什么编译分成多个阶段？
- 为什么分析过程分成多遍？
- …
- 递归
- 递归(Recursion)
- 问题的解决依赖于类似问题的解决，只不过后者的
复杂程度或规模较原来的问题更小 - 一旦将问题的复杂程度和规模化简到足够小时，问
题的解法其实非常简单 - 编译原理中的"递归"
- 递归下降分析
- 基于树遍历的属性计算
- 语法制导翻译
- …
- 权衡
- 权衡(折衷, Tradeoff )
- 理论可实现 vs. 实际可实现
- 理论研究重在探寻问题求解的方法，对于理论成果
的研究运用又需要在能力和运用中作出权衡 - 编译原理中的"权衡"
- 用上下文无关文法来描述和处理高级程序设计语言
- 优化措施的选择
- ...
- 保护、冗余、容错、纠错和恢复
- 利用启发式推理来寻求解答
- 在不确定情况下的规划、学习和调度
- ...
编译原理
- 编译理论与技术
- 计算机科学与技术中理论和实践相结合的最好典范
- ACM 图灵奖
- 授予在计算机技术领域作出突出贡献的科学家
- 程序设计语言、编译相关的获奖者是最多的
- 编译理论与技术
- 计算机科学与技术中理论和实践相结合的最好典范
- 体现了很多典型的计算思维方法
- 编译原理和方法的应用
- Html/XML 分析
- 语言处理工具
- 搜索引擎
编译过程
编译程序是怎样把高级语言(如C++)翻译成低
- 级语言(如机器指令)的？
- 把英文翻译为中文
- 识别出句子中的一个个单词---词法分析
- 分析句子的语法结构---语法分析
- 根据句子的含义进行初步翻译---中间代码产生
- 对译文进行修饰---优化
- 写出最后的译文---目标代码产生
以上是编译程序工作的五个阶段
- 编译过程——词法分析
- 任务: 输入源程序，对构成源程序的字符串进行
扫描和分解，识别出单词符号 - 依循的原则：构词规则
- 描述工具：有限自动机
for i := 1 to 100 do
基本字 标识符 赋值号 整常数 基本字 整常数 基本字
- 编译过程——语法分析
- 任务：在词法分析的基础上，根据语法规则把
单词符号串分解成各类语法单位(语法范畴) - 依循的原则：语法规则
- 描述工具：上下文无关文法
Z := X + 0.618 * Y（算术表达式--》算术表达式--》赋值语句）
- 编译过程——中间代码产生
- 任务：对各类语法单位按语言的语义进行初步翻译
- 依循的原则：语义规则
- 描述工具：属性文法
- 中间代码：三元式，四元式，树，...
- Z:=X + 0.618 * Y 翻译成四元式为
|序号 | OPR | OPN1 | OPN2 | RESULT | 注释|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|(1)| * | 0.618| Y | T1 | T1:=0.618*Y|
|(2)| + | X | T1 | T2 | T2:=X+T1|
|(3)| := | T2 | | Z | Z:=T2|
- 编译过程——优化(；例如乘法变成加法)
- 任务：对前阶段产生的中间代码进行加工变换，
以期在最后阶段产生更高效的目标代码 - 依循的原则：程序的等价变换规则
- 编译过程——目标代码产生
- 任务: 把中间代码变换成特定机器上的目标代码
- 依赖于硬件系统结构和机器指令的含义
- 目标代码三种形式
- 汇编指令代码: 需要进行汇编
- 绝对指令代码: 可直接运行
- 可重新定位指令代码: 需要连接
编译程序的结构
- 编译程序总框
- 词法分析器------源程序
- 语法分析器------中间代码(四元式)
- 语义分析与中间代码生成器------语法单位
- 优化段------目标代码
- 目标代码生成器------中间代码(四元式)
- 出错处理
- 出错处理程序
- 发现源程序中的错误，把有关错误信息报告给用户
- 语法错误
- 源程序中不符合语法（或词法）规则的错误
- 非法字符、括号不匹配、缺少 ；、...
- 语义错误
- 源程序中不符合语义规则的错误
- 说明错误、作用域错误、类型不一致、...
- 遍
- 所谓"遍"， 就是对源程序或源程序的中间表示
从头到尾扫描一次 - 阶段与遍是不同的概念
- 一遍可以由若干段组成
- 一个阶段也可以分若干遍来完成
- 编译前端与后端
- 编译前端
- 与源语言有关，如词法分析，语法分析，语义分析与
中间代码产生，与机器无关的优化 - 编译后端
- 与目标机有关，与目标机有关的优化，目标代码产生
- 带来的好处
- 程序逻辑结构清晰
- 优化更充分，有利于移植
编译程序的生成
- 以汇编语言和机器语言为工具
- 优点: 可以针对具体的机器，充分发挥计算机的系统
功能；生成的程序效率高 - 缺点: 程序难读、难写、易出错、难维护、生产的效
率低
- 高级语言书写
- 程序易读、易理解、容易维护、生产的效率高
- 利用已有的某种语言的编译程序实现另一语言的编
译程序 - 移植方法
- 把一种机器上的编译程序移植到另一种机器上
- 自编译方式
- 编译程序自动产生
- 编译程序-编译程序，编译程序产生器，编译程序书
写系统 - LEX：词法分析程序产生器
- YACC：语法分析程序产生器
