有梦就去追

1.1 什么是编译程序

• 把某一种高级语言程序等价转变为另一种低级语言（机器语言或汇编）的程序。
• 两种语言，一是解释型，二是编译型。

1.2 为何学习编译原理

学什么？

• 理解计算系统
• 设计计算系统
• 训练计算思维（computing thinking)
  • 定义：运用计算机科学的基础概念去求解问题，设计系统和理解人类的行为。
  • 包括：抽象、自动化、问题分解、递归、权衡、保护冗余容错纠错和恢复、利用启发式推理寻求解答、在不确定情况下的规划学习调度。

关于编译理论与技术

• 是计算机科学中理论与实践相结合的典范。
• 知识点：
  • 计算思维-抽象（从各地把握一般，从现象把握本质）。
    • ex:图灵机
      • 一条无限长的纸条
      • 一个读写头
      • 一个状态寄存器
      • 一套控制读写头工作的规则
    • 编程中的抽象有：
      • 有限自动机
      • 形式文法
  • 计算思维-自动化（将抽象思维的结果在计算机上实现，将计算思维物化的过程）
    • ex:有限自动机、预测分析程序、算符优先分析、LR分析
  • 计算思维-分解（将大规模复杂问题分成若干个较小规模、更简单的问题）
    • ex:编译程序引入中间语言、编译分成多个阶段、分析过程分成多遍
  • 计算思维-递归（问题的解决以来更小规模的类似问题）
    • ex:递归下降分析、基于树遍历的属性计算、语法制导翻译
  • 计算思维-权衡（理论可实现 VS 实际可实现）
    • ex:用上下文无关文法来描述和处理高级语言优化措施的选择

学习编译原理的意义

• 学习便宜程序的构造原理技术
• 更好的理解高级语言
• 构造实用工具

编译原理和方法的应用

• html/xml分析
• 语言处理工具
• 搜索引擎
• shell命令解释器
• SQL
• http协议

1.3 编译过程

编译程序如何把高级语言翻译成低级语言

• 以英文翻译成中文为例：
• 识别句子中的一个单词 对应 词法分析
• 分析句子中的语法结构 对应 语法分析
• 初步翻译 对应 中间代码分成
• 对译文进行修饰 对应 优化
• 写出最后译文 对应 目标代码生成

基本概念：词法分析

• 任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出单词和符号
• 原则：构词规则
• 描述工具：有限自动机

基本概念：语法分析

• 任务：在词法分析的基础上，根据语法规则把单词符号串分解成各类语法单位。
• 原则：语法规则
• 描述工具：上下文无关文法

基本概念：中间代码生成

• 任务：对各类语法单元按语言的语义进行初步翻译
• 原则：语义规则
• 描述工具：属性文法
• 中间代码：三元式，四元式，树形结构

基本概念：优化

• 任务：对前阶段产生的中间代码加工变换，以期获得更高效的目标代码
• 原则：等价变换规则

目标代码生成

• 任务： 把中间代码变换成特定机器上的目标代码，依赖于硬件系统结构和机器指令含义
• 目标代码三种形式
  • 汇编指令代码：需汇编
  • 绝对指令代码：直接运行
  • 可重新定位指令代码： 需要链接

1.4 编译程序的结构

出错处理

• 语法错误
• 语义错误

遍的概念

• 对源程序或者源程序的中间表示从头到尾扫一次

编译程序的前端和后端

源语言 --> 中间语言 --> 目标语言

• 前端
  • 与源语言有关，如词法分析、语法分析、语义分析与中间代码产生、与机器无关的优化
• 后端
  • 与目标机器有关，如与目标语言有关的优化，目标代码产生

1.5 编译程序的生成

高级语言书写

• 利用已有的某种语言的编译程序实现另一种语言的编译程序

移植方法

• 把一种机器上的编译程序移植到另一机器上

自编译方式

编译程序自动产生

• 编译程序的编译程序
• lex:词法分析程序产生器
• yacc：语法分析程序产生器