编译程序基本原理

概述

编译程序的功能是把高级语言书写的源程序翻译成与之等价的目标程序(汇编语言或机器语言)，编译程序工作过程分为6个阶段

• 词法分析：
• 语法分析：在词法分析的基础上将单词序列组合成各类语法短语，用于判断源程序在结构上是否正确
• 语义分析：对结构上正确的源程序进行上下文有关性质的审查和类型审查
• 中间代码生成(非必须)：根据语义分析产生的需要经过优化链接，最终生成可执行的目标代码。目的是进行与机器无关的代码优化处理，有助于提高移植性
• 代码优化(非必须)：当需要生成高效的目标代码时，就进行优化，所依据的原则是程序的等价变换原则
• 目标代码生成：把中间代码变换成特定机器上的绝对指令代码，可重定位的指令代码或汇编指令代码

后缀式

• 后缀式及逆波兰式，这种表示方式把运算符写在运算对象的后面，优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号
• 后缀式简单求法：按运算的优先顺序依次将运算符写在运算对象的后面

编译程序原理

• 文法：描述语言结构的规则称为文法。一个形式文法是一个有序四元组 G = （Vn，Vt，P, S）
  • Vn：非终结符集合。不是语言组成部分，不是终结结果，可理解为占位符
  • Vt：终结符集合。是语言的组成部分，是终结结果
  • P：产生式集合。用非终结符推导出结果符的规则
  • S：起始符。是语言的开始符号

正规式

用于词法分析，对于字符表，其上的正规式及其表示的正规集可以递归定义

• 确定有限自动机（DFA）
• 非确定有限自动机（NFA）
• 对于每一个NFA都可以转换为DFA

  №	区别	确定的有限自动机	不确定的有限自动机
  0	初态	有且只有一个初态	可以有多个初态(非空)
  1	终态	非空终态集	可空终态集
  2	输入	仅能输入长度为1的单个字符	可以输入字符或正规式，同一个字符可以出现在同状态的多条弧上
  3	后继状态	若有后继状态，则后继状态是唯一的	后继状态不是唯一的
  4	其他	易于程序实现	易于人工设计

编译与解释

都是将高级语言翻译成计算机硬件认可的机器语言加以执行

№	区别	编译	解释
0	目标代码	生成并优化	不生成
1	独立的可执行文件	生成	不生成，逐行边翻译边执行
2	执行效率	较快(翻译一次，多次执行)	较慢(反复扫描源程序)
3	占用内存	较少	较多
4	灵活性	较低	较高(反复扫描源程序)
5	可移植性	较差	较高