一
什么叫编译程序
翻译程序：
将某一种语言（源语言）程序转换为与其逻辑上等价的另一种语言（目标语言）程序
编译程序：
源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序
汇编程序：
源语言为汇编语言，目标语言为机器语言的翻译程序
解释程序：
源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身
编译器和解释器
首先是编译阶段，用户输入源程序，经过编译器的处理，生成目标程序。然后是目标程序的运行阶段，根据目标程序的要求进行适当的数据输入，最终得到结果
解释器不像编译器那样，把源程序的翻译和目标程序的运行分割开来，而是把翻译和运行结合在一起进行，这种方式被称为解释。在计算机应用中，凡是可以采用编译方式的地方，几乎都可以采用解释的方式
解释器和编译器的主要区别在于：运行目标程序时的控制权在解释器而不在目标程序
解释器的优点：
1.具有较好的动态特性
2.具有较好的可移植性
解释器的缺点
1.时间上，降低了程序的运行速度
2.空间上，占据内存空间不能叠加
编译过程概述
编译程序的工作过程可划分为五个阶段：
- 词法分析
- 语法分析
- 语义分析和中间代码生成
- 代码优化
- 目标代码生成
词法分析
从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词
语法分析
在词法分析的基础上将单词序列分解成各类语法短语，如程序、语句、表达式等等
语义分析
语义分析是语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集信息
主要进行语义检查，并为代码生成收集类型信息（类型检查、变量是否声明、类型是否一致、变量是否已有值等）
中间代码生成
完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统
代码优化
可以在不同的编译阶段进行，其中对中间代码的优化尤其重要
代码生成
目标代码生成阶段的任务就是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码
符号表
作为进行语法的合法性检查的依据
作为目标代码生成阶段地址分配的依据
错误检测
错误检测处理与符号表管理工作一样，贯穿整个编译过程
编译程序的结构
前端--与目标价无关的部分
包括分析部分（词法、语法、语义分析）、中间代码生成与优化以及这部分的符号表管理错误处理
后端--与目标机有关的部分
包括代码生成、与目标机有关的优化以及这部分的符号表管理和错误处理工作
不同前端和不同后端相互配合可以得到不同的编译器
二
程序语言的定义
形式化
词法规则：
单词符号的形成规则，也就是规定了字母表中哪些字符串是一个单词符号。
正规式和有限自动机理论
语法规则：
是语法单位的形成规则，也就是规定了如何从单词符号形成更大的语法单位
上下文无关文法和有限自动机
语义：
可以定义程序意义的规则
语法制导翻译法
名字的左值和右值
左值：指它所代表的存储单元的地址
右值：指它所代表的存储单元里的内容
程序语言的语法描述
符号串的运算
- 连接
符号串的长度
符号串的前缀与后缀
- 幂
符号串集合的运算
- 乘积
- 幂
- 闭包
上下文无关文法
规则（产生式）
：：= 或
表示由……组成
句子的推导
用规则（产生式）按一定方式去推导或产生句子的过程
若干步推导
文法和语言的形式定义
产生式（规则）
文法
推导与归约
规范（最右）推导
句型和句子
等价文法
递归产生式和递归文法
可见，对于文法中任一非终结符号，若能建立一个推 导过程，在推导所得的符号串中又出现了该非终结符号 本身，则文法是递归的。应当注意，一般的文法都是递 归的，文法G只有递归定义，L(G)中句子才是无穷的 。
总之，使用递归文法，可用有穷的产生式来描述无 穷的语言，反之，一个语言若是无穷的，则描述语言的 文法必定是递归的。(程序设计语言一般是无穷的)。
短语、简单短语和句柄
高级语言的一般特性
程序语言的语法描述
语法树和文法的二义性
文法的分类
有关文法的使用限制
扩充的巴科斯范式（EBNF）表示