1 程序设计语言和编译程序

1.1 相关定义

• 一条指令：计算机所能执行的每一种操作
• 指令系统：计算机能够执行的全部指令集合
• 低级语言：面向机器
  （1）机器语言：二进制形式的指令
  【注意】计算机唯一可直接识别并接受的语言
  （2）汇编语言：用助记符代替机器语言的语言
  【注意】必须翻译成机器语言才可被计算机直接识别
  高级语言：面向应用
  （FORTRAN、PASCAL、C、ADA、半解释半执行Java、解释BASIC）
• 汇编程序：将汇编语言翻译成机器语言的程序
• 翻译程序
  （1）编译程序：高级语言（源程序）→ 低级语言（目标程序）→ 执行目标程序
  （2）解释程序：高级语言（源程序）→ 逐条读出源程序，并解释执行（不产生目标程序）
• 编译程序的功能
  

1.2 高级语言程序执行阶段

1.2.1 编译程序

1. 编译阶段：源程序 → 目标程序
2. 汇编阶段（可选）：汇编语言目标程序 →（汇编程序）→ 机器语言目标程序
3. 运行阶段：目标程序 + 数据 → 计算结果

• 源程序的编译和运行阶段
  
• 源程序的编译、汇编和运行阶段
  

1.2.2 解释程序

2 编译程序的历史及发展

• 机器语言 → 汇编语言（汇编程序）→ 高级语言
• 文法
  （1）0型
  （2）1型
  （3）2型（上下文无关文法）—— 最有用
    ① 有限自动机
    ② 正规表达式
  （4）3型
• 编译程序的编译器（分析程序生成器）：对编译程序的自动生成，仅能够自动完成编译器的部分工作
• 语法分析器自动生成工具：YACC
  词法分析器自动生成工具：Lex
• 交互开发环境IDE
  （1）编辑器
  （2）链接程序
  （3）调试程序
  （4）项目管理程序
• 现代编译技术：并行编译

3 编译过程和编译程序结构

• 编译程序的工作过程：从整个源程序开始到输出目标程序为止的整个过程
  一个编译过程可分为一遍或多遍完成，每一遍完成所规定的任务，使编译程序的结构更加清晰
• 编译过程阶段
  （前端）
  1° 词法分析
  2° 语法分析
  3° 语义分析和中间代码生成
  （可选）
  4° 优化
  （后端）
  5° 目标代码生成
• 编译程序的结构示意
  

3.1 词法分析

• 任务：源程序→单词符号流（内部码）
• 规则：语言的构词规则

3.2 语法分析

• 任务：单词符号流 → 各类语法单位（语法范畴）
• 规则：语言的语法规则（文法规则）
• 文法：上下文无关文法

3.3 语义分析和中间代码生成

• 任务：对各类语法单位初步翻译
  （1）对每种语法范畴进行静态语言检查
  （2）检查正确后进行中间代码翻译
• 规则：语言的语义规则
• 中间代码：介于高级语言和低级语言之间的一种独立于具体硬件的记号系统
  （1）四元式
  （2）三元式
  （3）间接三元式
  （4）逆波兰记号

3.4 优化

• 任务：对中间代码进行等价交换或改造或对目标代码进行优化→更高效的目标代码
• 常用优化措施
  （1）删除冗余运算
  （2）删除无用赋值
  （3）合并已知量
  （4）循环优化
• 规则：程序的等价交换规则

3.5 目标代码生成

• 任务：中间代码→机器语言或汇编语言
• 与目标机器的硬件结构有关

3.6 表格管理程序

• 编译各阶段都涉及
• 编译程序的绝大部分时间都用在造表、查表和更新表格的事务上

3.7 出错处理程序

• 与编译各阶段都有联系，与前三个阶段联系尤为密切
• 为了尽可能多地发现错误，应在发现错误后还能继续编译下去

4 编译程序的开发

其中，I是编译器所用语言

• 编译开发过程中最关键的一步：确定编译程序的开发方案及方法
  作用：使编译程序具有易读性和易改性
• 编译程序的开发技术
  （1）自编译
  （2）交叉编译
  （3）自展
  （4）移植

4.1 自编译

• 定义：用某种高级语言编写自己的编译程序
• 图示：
  

4.2 交叉编译

• 定义：用A机器上的编译程序来产生可在B机器上运行的目标代码
• 图示：
  

4.3 自展

• 方法：
  1° 确定一个非常简单的核心语言 L 0 L_0 L0​
  2° 用机器语言或汇编语言编写出 L 0 L_0 L0​的编译程序 T 0 T_0 T0​
  3° 把 L 0 L_0 L0​扩充到 L 1 L_1 L1​，此时 L 0 ⊂ L 1 L_0⊂L_1 L0​⊂L1​，并用 L 0 L_0 L0​编写 L 1 L_1 L1​的编译程序 T 1 T_1 T1​（自编译）
  4° 把 L 1 L_1 L1​扩充到 L 2 L_2 L2​，此时 L 1 ⊂ L 2 L_1⊂L_2 L1​⊂L2​，并用 L 1 L_1 L1​编写 L 2 L_2 L2​的编译程序 T 2 T_2 T2​（自编译）
  5° ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ······ ⋅⋅⋅⋅⋅⋅不断扩展，直到完成所要求的编译程序

4.4 移植

• 定义：A机器上的某种高级语言的编译程序稍加改动后能够在B机器上运行
• 程序可移植：一个程序能较容易地从A机器上搬到B机器上运行
  移植具有一定的局限性

4.5 编译程序自动生成

5 构造编译程序所应具备的知识内容

• 对被编译的源语言，要深刻理解其结构（语法）和含义
• 必须对目标机器的硬件和指令系统有深刻的了解
• 必须熟练掌握编译方法，编译方法掌握的如何将直接影响到编译程序的成败

6 补充概念

• 趟（遍）：在一个特定的实现中，多个步骤的活动可以被组合成一趟
• 每趟读入一个输入文件并产生一个输出文件
• 前端趟
  可选趟
  后端趟