4、编译、解释程序翻译过程

前面说到了高级语言程序要经过编译或解释程序才能运行

编译程序和解释程序都不可省略词法分析、语法分析、语义分析且顺序不可交换
编译程序的中间代码生成、代码优化不是必要的，可以省略。

符号表

不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。
记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。

第一阶段：词法分析（了解）

流程

输入是源程序（看成多行字符串）
从前到后（从左到右）逐个字符地扫描
识别出一个个“单词”符号，这是最基本的语法单位
单词一般由类型（关键字（保留字）、标识符、常数、运算符、分隔符等）和值组成
输出是一个记号流

作用

分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定

工具

正规式

正规式	正规集
Ab	字符串 ab 构成的集合
a\|b	字符串 a、b 构成的集合
a*	由 0 个或多个 a 组成的集合
( a \| b)*	所有字符 a 和 b 构成的串的集合
a ( a\| b)*	以 a 为首字符的 a、b 字符串的集合
(a \| b)*abb	以 aab 为结尾的 a、b 字符串的集合

有限自动机

它能正确地识别正规集

确定的有限自动机（DFA）：对每个状态来说识别字符后转移的状态是唯一的
不确定的有限自动机（NFA）：对每个状态来说识别字符后转移的状态是不唯一的
要在终态结束
初态和终态可以重合

第二阶段：语法分析（爱考）

流程

输入是词法分析的记号流
输出是语法树（分析树）

作用

对各条语句的结构进行合法性分析
分析程序中的句子结构是否正确
语法分析阶段可以发现所有语法错误

语法规则

上下文无关文法

被广泛地用于表示各种程序设计语言的语法规则。

开始符号 -> A ｜ B（不能继续推就是终结符号）

语义分析

流程

输入是语法分析的语法树

作用及注意事项

语义分析是进行类型分析和检查
语义分析阶段不能发现程序中所有的语义错误
语义分析阶段可以发现静态语义错误
不能发现动态语义错误，动态需要运行时发现

动态的语义错误

除数为零
死循环
....

中间代码生成

常见

后缀式
三地址码
三元式
四元式
树（图）

后缀式（逆波兰式）

把运算符放到后面（ab？）,而中缀式是（a？b）

中缀转后缀

优先级最高的是括号，其次是乘除，最后是加减
逻辑表达式中优先级最高的是括号，其次是大小符号，然后是逻辑与，最后是逻辑或
优先级相同从右向左

后缀转中缀

从左向右依次入栈，遇到符号取出栈顶数为 b，符号为？，栈次顶数为 a

二叉（语法）树的遍历

中序遍历（左中右）：中缀式
后序遍历（左右中）：后缀式

特征

与具体机器无关，有利于进行与机器无关的优化处理和提高编译程序的可移植性
将不同的高级语言翻译成同一种中间代码，可以跨平台
最常用的中间代码是与汇编指令相似的三地址码

代码优化

最后一个阶段：目标代码生成（了解即可）

与具体的机器密切相关
寄存器的分配属于此阶段