编译原理
一、绪论
1.语言处理过程
- 骨架程序->预处理器->源程序->编译器->目标汇编程序->汇编器->可重定位机器代码
- 可重定位机器代码+可重定位目标文件库->装配连接编辑->绝对机器码
2.什么是编译
翻译程序：把某一种语言程序(源语言程序)等价地转换成另一种语言程序(目标语言)的程序。
编译程序：把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言)的程序。(如C语言、Pascal语言等是编译程序)
解释程序：把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。(如Basic、Python语言是解释程序)
编译与解释的区别可简单认为是：是否产生目标代码程序
3.编译过程
- 词法分析
- 任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号
- 依循规则：构词规则
- 描述工具：正规式和有穷自动机
- 语法分析
- 任务：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位
- 依循规则：语法规则
- 描述工具：上下文无关文法
- 语义分析和中间代码生成
- 任务：对各类不同语法范畴(语句、过程、表达式、函数等)按语言的语义进行初步翻译
- 依循规则：语义规则
- 中间代码：三元式、四元式(常用)、逆波兰式、树形结构等
- 代码优化
- 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。主要包括：提取公共子表达式、合并已知量、删除无用语句、循环优化等
- 依循规则：程序的等价变换规则
- 目标代码生成
- 任务：把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义。
- 目标代码的三种类型：
- 绝对指令代码：可直接运行
- 可重新定位指令代码：需要连接装配
- 汇编指令代码：需要进行汇编
4.编译程序总体框架
5.表格管理
常见的表格：符号名表、常数表、标号表、入口名表、过程引用表
格式： 名字+信息
6.出错处理
出错处理程序： 发现源程序中的错误，把有关错误信息报告给用户语法错误、语义错误。
编译程序一般很难检测出逻辑错误
7.代码段转换至表格
8.编译前端与后端
编译前端： 与源语言有关，如词法分析，语法分析，语义分析与中间代码生成，与机器无关的优化
编译后端： 与目标机器有关，与目标有关的优化，目标代码生成
优点：减少对内存容量的要求，程序逻辑结构清晰，优化更充分，有利于移植
缺点：编译程序运行的效率低
9.上下文无关文法
文法： 描述语言的语法结构的形式规则
一个上下文无关文法G是一个四元式
补充：
10.语法和语义
程序语言由语法和语义两方面定义。
a.语法： 一组规则，用它可以形成和产生一个合式(well-formed)的程序
- 词法规则： 单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括常数、标识符、基本字、算符、界符等。
- 描述工具： 有限自动机(FA)
- 语法规则： 语法单位等形成规则。规定了如何从单词符号形成语法单位。语法单位通常包括表达式、语句、分程序、过程、函数、程序等。
- 描述工具： 上下文无关文法
b.语义： 一组规则，用它可以定义一个程序等意义。目前大多数编译程序使用基于属性文法等语法制导翻译方法来分析语义。
11.程序语言的基本功能和层次结构
程序语言的基本功能：描述数据和对数据的运算
程序：本质上是描述一定数据的处理过程
12.集合相关概念
13.推导
定义：
最左推导&最右推导：
