语言处理过程

源程序 --> 编译器 --> 目标汇编程序 --> 汇编器 --> 可重定位机器代码 --> 连接器 --> 机器码

翻译程序

把某一种语言程序等价地转换成另一种语言程序（目标语言程序）的程序

编译程序

把一种高级语言程序等价地转换成另一种低级语言程序的程序

解释程序

把源语言的源程序作为输入，不产生目标程序，边解释边执行源程序本身

编译过程

1. 词法分析
2. 语法分析
3. 语义分析和中间代码产生
4. 代码优化
5. 目标代码产生

词法分析

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

语法分析

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

语义分析和中间代码生成

任务：对各种不同的语法范畴按语义进行初步翻译 原则：语义规则 中间代码：三元式，四元式，逆波兰式，树形结构

代码优化

任务：对之前产生的中间代码进行加工变换 原则：等价原则

目标代码的生成

任务：把中间代码变换成特定机器上的目标代码 依赖于硬件系统结构

三种形式：

1. 绝对的指令代码：可直接运行
2. 可重新定位指令代码：需要连接装配
3. 汇编指令代码：需要进行汇编

编译前端与后端

编译前端：与源语言有关 编译后端：与目标机有关

高级语言及其语法描述

2.5 文法和语言分类

1. 0型文法(无限制) a -> b 都可以包含终结或者非终结符 a 至少含一个非终结

2. 1型文法（上下文有关） aAb -> aUb 都可以包含终结或者非终结符

3. 2型文法（上下文无关文法） A -> B A 属于非终结 B 可以包含终结或者非终结符

4. 3型文法 (正规文法)

右线性

A -> aB 或 A -> a a 属于终结符集合

左线性

A -> Ba 或 A -> a

同城定义程序设计语言规则的文法是正规文法

有害规则：引发文法的二义性 多余规则：始终不可能用到，或无法从它推导出任何终结符号串

词法分析和有穷自动机

3.1 词法分析程序的功能

字符串源程序 -> 单词符号源程序

3.2.1

程序语言的单词符号：

1. 关键字：if else
2. 标识符: 变量名，函数名，常量名
3. 常数: 123, true
4. 运算符: + -
5. 界符：如;

3.3.2 正规文法 -> 正规式

代入消元

正规式 -> 正规文法