引论

1. 主要内容

  • 引论
  • 高级语言及其文法
  • 语法分析
  • 自顶向下的语法分析
  • 自底向上的语法分析
  • 语法制导翻译与属性文法
  • 语义分析与中间代码生成
  • 符号表管理
  • 运行时的存储组织
  • 代码优化
  • 代码生成

2. 程序设计语言

  • 机器语言与汇编语言：01 代码与助记符，更接近于计算机硬件指令系统的工作

  • 高级语言：其表示方法更接近于带解决的表示方法

  • 命令语言：控制系统的工作，以功能封装为特征（如 UNIX 上的 shell）

3. 程序设计语言的分类

  • 强制性（命令式）语言（Imperative Language)
  1. 通过指明一系列可执行的运算及运算的次序来描述计算过程的语言
  2. 程序的层次性和抽象性不高
  3. FORTRAN（段结构）、BASIC、Pascal（嵌套结构）、C ⋯\cdots
  • 申述性语言（Declarative Language）
  1. 着重描述要处理什么，而非如何处理的非命令式语言
  2. 函数（应用）式语言（Functional Language），基本运算单位是函数（如 LISP、ML ⋯\cdots）
  3. 逻辑式（基于规则）语言（Logical Language），基本运算单位是谓词（如 Prolog、Yacc ⋯\cdots）
  4. 并发式语言（Concurrent Language），着重如何描述潜在的并行机制（如 ErLang、Fortran+MPI ⋯\cdots）
  • 面向对象语言（Object-Oriented Language）
  1. 以对象为核心（如 Smalltalk、C++、Java、Ada（程序包）⋯\cdots ）
  2. 具有认识性（对象）、类别性（类）、多态性和继承性

4. 程序语言的翻译

  • 翻译程序：将一种语言描述的程序（源程序）翻译成等价的另一种语言描述的程序（目标程序）
  • 解释程序：一边解释一边执行的翻译程序
  • 编译程序：将源程序完整地转换成机器语言程序或汇编语言程序，然后再执行翻译程序（比如汇编程序）进行处理转换为机器语言程序（高级语言程序 →\rightarrow 汇编/机器语言程序）

【注】解释程序和编译程序都属于翻译程序。

常见翻译程序

  1. 汇编语言（Assembler）
  2. 交叉汇编程序（Cross Assembler）
  3. 反汇编程序（Disassembler）
  4. 交叉编译程序（Cross Compiler）
  5. 反编译程序（Decompiler）
  6. 可变目标编译程序（Retargetable Compiler）
  7. 并行编译程序（Parallelizing Compiler）
  8. 诊断编译程序（Diagnostic Compiler）
  9. 优化编译程序（Optimizing Compiler）
  • 编译系统：编译系统 = 编译程序 + 运行系统（支撑环境、运行库等）

5. 编译程序总体结构

  • 词法分析
  1. 词法分析由词法分析器（Lexical Analyzer）完成，词法分析器又称为扫描器（Scanner）
  2. 词法分析器从左到右扫描组成源程序的字符串，并将其转换为单词（token）串，同时检查词法错误，进行标记符登记（符号表管理）
  3. 输入 ：字符串
    输出 ：序对 ——（种别码，属性值），其中，属性值为 token 的机内表示
  • 语法分析
  1. 语法分析器由语法分析器（Syntax Analyzer）完成，语法分析器又叫 Parser
  2. 功能：
  • Parser 实现「组词成句」（将词组成各类语法成分：表达式、因子、项、语句、子程序 ⋯\cdots ）
  • 构造分析树
  • 指出语法错误
  • 指导翻译
  1. 输入 ：token 序列
    输出 ：语法成分
  • 语义分析
  1. 语义分析一般和语法分析同时进行，称为语法制导翻译（Syntax-Directed Translation）
  2. 功能：分析由语法分析器识别出来的语法成分的语义
  • 获取标识符的属性：类型、作用域等
  • 语义检查：运算的合法性、取值范围等
  • 子程序的静态绑定：代码的相对地址
  • 变量的静态绑定：数据的相对地址
  • 中间代码生成
  1. 中间代码表示
  • 后缀表达式（逆波兰表达式）
  • 前缀表达式（波兰表达式）
  • 四元式表示（三地址码）
  • 三元式表示
  1. 中间代码特点
  • 简单规范
  • 与机器无关
  • 易于优化与转换
  • 代码优化
  1. 代码优化是指对中间代码进行优化处理，式程序运行能够尽量节省存储空间，更有效地利用机器资源，使得程序的运行速度更快，效率更高（【注】这种优化变换必须是等价的）。代码优化包括：与机器无关的优化和与机器有关的优化
  2. 与机器无关的优化

局部优化：常量合并、公共子表达式的提取等
循环优化：强度削减（较快操作代替较慢操作）、代码外提（循环不变量提出循环）

  1. 与机器有关的优化

寄存器的利用：常用量放入寄存器，减少访存次数
体系结构：MIMD、SIMD、SPMD、向量机、流水机
存储策略：根据算法访存的要求安排（Cache、并行存储体系——减少访问冲突）
任务划分：按运行的算法及体系结构，划分子任务（MPMD）

  • 目标代码生成
  1. 将中间代码转换成目标机上的机器指令代码或汇编代码
  • 确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）
  • 制定从中间代码到目标代码的翻译策略或算法
  1. 目标代码的形式
  • 具有绝对地址的机器指令
  • 汇编语言形式的目标程序
  • 模块结构的机器指令（需要链接程序）
  • 表格管理
  1. 管理各种符号表（常数、标号、变量、过程、结构 ⋯\cdots ），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息
  • 辅助语法检查、语义检查
  • 完成静态绑定、管理编译过程
  1. Hash 表、链表等各种表的查、填技术
  2. 「数据结构」与「算法」
  • 错误处理
  1. 进行各种错误的检查、报告、纠正，以及相应的续编译处理（比如错误的定位与局部化）

词法：拼写 ⋯\cdots
语法：语句结构、表达式结构 ⋯\cdots
语义：类型不匹配、参数不匹配

6. 模块分类

8 项功能对应 8 个模块：

  • 分析：词法分析、语法分析、语义分析
  • 综合：中间代码生成、代码优化、目标代码生成
  • 辅助：符号表管理、出错处理

7. 编译程序的组织

  • 根据系统资源的状况、运行目标的要求 ⋯\cdots，可以将一个编译程序设计成多遍（Pass）扫描的形式，在每一遍扫描中，完成不同的任务。单遍代码不太有效；遍可以和阶段相对应，也可以和阶段无关

比如，首遍构造语法树、二遍处理中间表示、增加信息等

  • 编译程序的设计目标
  1. 规模小、速度快、诊断能力强、可靠性高、可移植性好、可扩充性好
  2. 目标程序也要规模小、执行速度快
  • 编译系统规模较大，可移植性很重要。为提供可移植性，将编译程序划分为前端和后端
  1. 前端

与源语言有关、与目标机无关的部分
词法分析、语法分析、语义分析、中间代码生成、与机器无关的代码优化

  1. 后端

与目标机有关的部分
与机器有关的代码优化、目标代码生成

8. 编译程序的生成

  • 如何实现编译器？：自展——使用语言提供的功能来编译该语言自身

  • T 形图：表示语言翻译过程

其含义为：源语言通过实现语言翻译为目标语言

  • 自展

问题：如何在一个机器上实现 C 语言编译器？

  • 移植

问题：如何将 A 机上的 C 语言编译器移植到 B 机上的 C 语言编译器？

  • 交叉编译

问题：如何利用 A 机上的 C 语言编译器实现新语言 NEW 的编译器？

  • 编译程序自动生成
  1. 词法分析器的自动生成程序

输入：词法（正规表达式）、识别动作（C程序段）
输出：yylex() 函数

  1. 语法分析器的自动生成程序

输入：语法规则（产生式）、语义动作（C程序段）
输出：yyparse() 函数

9. 编译技术的应用

将复杂数据看作一条语句：

  • 数据格式的分析：利用词法、语法分析方法
  • 数据处理的框架：基于语法制导的语义处理框架

自然语言的理解和翻译：句子翻译、输入法、语音合成、翻译、内容过滤 ⋯\cdots
语法制导的结构化编辑器
程序格式化工具
软件测试工具
程序理解工具
高级语言的翻译程序
⋯\cdots