第 6章 编译技术
6.1 编译程序的工作过程
6.2 状态矩阵法的编译过程
6.3 词法分析
6.4 中间语言表示
6.5 语法的分析与加工
编译程序是一种将高级语言编
写的源程序编译成机器语言程序
（称为目标程序）的实用程序。
6.1 编译程序的工作过程
为了将源程序翻译成目标程序，一般
都要包括以下几个步骤。
① 输入源程序。
② 对以机内码表示的源程序进行词法
分析，辨认出一个个单词符号。
③ 根据源语言的语法规则进行语法
分析。
④ 在实际运行之前，通常还要对目
标程序的各部分进行连接装配 。
对于块结构的语言（如 C语言和
FORTRAN语言等），通常是进行分块
编译，分别得到半目标程序，最后可用
装配程序组装成一个完整的程序。
编译程序一般要包含以下几个程序模块。
（ 1）词法分析程序
（ 2）语法分析程序
（ 3）加工程序
（ 4）优化修饰部分
（ 5）装配程序或连接编辑程序
6.2 状态矩阵法的编译过程
6.2.1 状态矩阵法的基本原理
所谓“状态”，粗略地说，是表示过
去已经扫描了什么语法成分，以便当遇到
新的语法符号时，在不同的状态下对该语
法符号作出不同的处理。
状态矩阵法的核心是状态矩阵（也称
状态表），如表 6.1所示。
6.2.2 状态矩阵的压缩
在具体实现状态矩阵法时，为了节省
存储空间，通常要对状态矩阵进行压缩。
各列的意义如下：
① 状态 指状态栈栈顶项中所包含的
可能状态。
② 符号 指当前扫描到的可能符号。
③ 加工子程序 指当前遇到的相应状
态符号配对时编译程序应做的工作。
④ 状态改变 指出在做完相应的编
译工作后其状态栈如何改变。
综上所述，状态矩阵法的编译过
程是按照存放在内存中的状态表不断
地进行解释执行的。
6.3 词法分析
6.3.1 词法分析的任务
词法分析是编译过程各阶段的基础和
必要的准备。
词法分析的主要任务是从源程序语句
中识别出具有独立意义的语法单位（即语
法符号），并且建立一个符号表，用以保
存各语法符号的属性。
表 6.4中的符号最后都变成二进制
形式的代码串。
可以将这些通用符号建立一个通
用符号表，这些符号的代码可用较大
的编号来表示，如表 6.5所示。
在这种情况下，上述赋值语句经
词法分析后可以得到一张符号表如表
6.6所示 。
6.3.2 读字符程序
读字符程序的任务是从源程序字符串中顺
序读出基本符号，并作一些简单的处理后提供
给词法分析程序。
6.3.3 状态矩阵法的词法分析过程
词法分析程序可以用状态矩阵法来实现。
由图 6.4可以看出，每执行一次这
个程序，就顺序从源程序中读出一个
语法符号，并且将有关的信息存放在
一些工作单元中。
下面以 FORTRAN语言为例来说明用
状态矩阵法实现词法分析的过程。为简单
起见，作如下一些假设：
① 不考虑格式语句。
② 不考虑数的翻译。
③ 不考虑以 E开头的运算符，且运算
符只有两个字母。
6.3.4 算术常数的识别和翻译
在词法分析的过程中，不仅要识别出
常数，还需要将常数翻译成统一的格式。
经过词法分析后，所有的实数都分解
成两部分：一部分是有效数字的所有位组
成的正整数；另一部分是以 10为底的整数
指数部分。
6.4 中间语言表示
“中间语言”，为能用来表述源程序
并与之等效的一种编码方式。
6.4.1 波兰表示
一个表达式的波兰表示就是后缀表示，
即表达式中的运算对象写在前面，运算符
写在后面。
（ 1）赋值语句
X=e
其中 e为表达式。若将赋值号,=”
看作是一种双目运算符，则此赋值语
句的波兰表示定义为：
X?e?=
（ 2）无条件转向语句
GOTO n
的波兰表示为：
n? GOTO
（ 3）逻辑条件语句
IF C S
的波兰表示为：
C? S? LIF
（ 4）子程序调用语句
CALL S(y1,y2,…, yn)
的波兰表示为：
y1?,y2?,…, yn? S SUB
（ 5）维数说明语句
DIMENSION A(N,M)
的波兰表示为：
N M A DIM
（ 6）函数子程序段头语句
FUNCTION F(X1,X2,…, XN)
的波兰表示为：
X1,X2,…, XN F DEFF
6.4.2 三元组表示
波兰表示有一个缺点，就是不便于
作代码的优化。
三元组表示的一般形式为：
k,(θ o1 o2)
6.5 语法的分析与加工
语法分析和加工的主要任务有
以下几项。
① 识别出各种类型的语句，并
进行语法检查。
② 语法的加工处理。
③ 编译程序工作的最后结果是
产生目标程序或半目标程序。
6.5.1 优先矩阵法
优先矩阵法的基本思想如下。
将程序设计语言中的所有算符（广
义运算符，包括算术运算符、分隔符、
拼写定义符及界限符 ├和 ┤等）设置一
个优先关系，而这种优先关系用一张优
先矩阵表来表示。
6.5.2 优先数法
基于算符的优先数进行编译的方法称
为优先数法。
6.5.3 状态矩阵法
状态矩阵法用表格形式来描述编
译过程，因此条理十分清楚，这是其
他方法所不及的。
6.5.4 递归子程序法
递归子程序法的基本思想是：从整个
源程序开始，根据各种语法成分的形成规
则从大到小逐层往细分析处理，而对于每
个递归定义的语法成分，都用一个相应的
递归子程序来进行处理。
6.1 编译程序的工作过程
6.2 状态矩阵法的编译过程
6.3 词法分析
6.4 中间语言表示
6.5 语法的分析与加工
编译程序是一种将高级语言编
写的源程序编译成机器语言程序
（称为目标程序）的实用程序。
6.1 编译程序的工作过程
为了将源程序翻译成目标程序，一般
都要包括以下几个步骤。
① 输入源程序。
② 对以机内码表示的源程序进行词法
分析，辨认出一个个单词符号。
③ 根据源语言的语法规则进行语法
分析。
④ 在实际运行之前，通常还要对目
标程序的各部分进行连接装配 。
对于块结构的语言（如 C语言和
FORTRAN语言等），通常是进行分块
编译，分别得到半目标程序，最后可用
装配程序组装成一个完整的程序。
编译程序一般要包含以下几个程序模块。
（ 1）词法分析程序
（ 2）语法分析程序
（ 3）加工程序
（ 4）优化修饰部分
（ 5）装配程序或连接编辑程序
6.2 状态矩阵法的编译过程
6.2.1 状态矩阵法的基本原理
所谓“状态”，粗略地说，是表示过
去已经扫描了什么语法成分，以便当遇到
新的语法符号时，在不同的状态下对该语
法符号作出不同的处理。
状态矩阵法的核心是状态矩阵（也称
状态表），如表 6.1所示。
6.2.2 状态矩阵的压缩
在具体实现状态矩阵法时，为了节省
存储空间，通常要对状态矩阵进行压缩。
各列的意义如下：
① 状态 指状态栈栈顶项中所包含的
可能状态。
② 符号 指当前扫描到的可能符号。
③ 加工子程序 指当前遇到的相应状
态符号配对时编译程序应做的工作。
④ 状态改变 指出在做完相应的编
译工作后其状态栈如何改变。
综上所述，状态矩阵法的编译过
程是按照存放在内存中的状态表不断
地进行解释执行的。
6.3 词法分析
6.3.1 词法分析的任务
词法分析是编译过程各阶段的基础和
必要的准备。
词法分析的主要任务是从源程序语句
中识别出具有独立意义的语法单位（即语
法符号），并且建立一个符号表，用以保
存各语法符号的属性。
表 6.4中的符号最后都变成二进制
形式的代码串。
可以将这些通用符号建立一个通
用符号表，这些符号的代码可用较大
的编号来表示，如表 6.5所示。
在这种情况下，上述赋值语句经
词法分析后可以得到一张符号表如表
6.6所示 。
6.3.2 读字符程序
读字符程序的任务是从源程序字符串中顺
序读出基本符号，并作一些简单的处理后提供
给词法分析程序。
6.3.3 状态矩阵法的词法分析过程
词法分析程序可以用状态矩阵法来实现。
由图 6.4可以看出，每执行一次这
个程序，就顺序从源程序中读出一个
语法符号，并且将有关的信息存放在
一些工作单元中。
下面以 FORTRAN语言为例来说明用
状态矩阵法实现词法分析的过程。为简单
起见，作如下一些假设：
① 不考虑格式语句。
② 不考虑数的翻译。
③ 不考虑以 E开头的运算符，且运算
符只有两个字母。
6.3.4 算术常数的识别和翻译
在词法分析的过程中，不仅要识别出
常数，还需要将常数翻译成统一的格式。
经过词法分析后，所有的实数都分解
成两部分：一部分是有效数字的所有位组
成的正整数；另一部分是以 10为底的整数
指数部分。
6.4 中间语言表示
“中间语言”，为能用来表述源程序
并与之等效的一种编码方式。
6.4.1 波兰表示
一个表达式的波兰表示就是后缀表示，
即表达式中的运算对象写在前面，运算符
写在后面。
（ 1）赋值语句
X=e
其中 e为表达式。若将赋值号,=”
看作是一种双目运算符，则此赋值语
句的波兰表示定义为：
X?e?=
（ 2）无条件转向语句
GOTO n
的波兰表示为：
n? GOTO
（ 3）逻辑条件语句
IF C S
的波兰表示为：
C? S? LIF
（ 4）子程序调用语句
CALL S(y1,y2,…, yn)
的波兰表示为：
y1?,y2?,…, yn? S SUB
（ 5）维数说明语句
DIMENSION A(N,M)
的波兰表示为：
N M A DIM
（ 6）函数子程序段头语句
FUNCTION F(X1,X2,…, XN)
的波兰表示为：
X1,X2,…, XN F DEFF
6.4.2 三元组表示
波兰表示有一个缺点，就是不便于
作代码的优化。
三元组表示的一般形式为：
k,(θ o1 o2)
6.5 语法的分析与加工
语法分析和加工的主要任务有
以下几项。
① 识别出各种类型的语句，并
进行语法检查。
② 语法的加工处理。
③ 编译程序工作的最后结果是
产生目标程序或半目标程序。
6.5.1 优先矩阵法
优先矩阵法的基本思想如下。
将程序设计语言中的所有算符（广
义运算符，包括算术运算符、分隔符、
拼写定义符及界限符 ├和 ┤等）设置一
个优先关系，而这种优先关系用一张优
先矩阵表来表示。
6.5.2 优先数法
基于算符的优先数进行编译的方法称
为优先数法。
6.5.3 状态矩阵法
状态矩阵法用表格形式来描述编
译过程，因此条理十分清楚，这是其
他方法所不及的。
6.5.4 递归子程序法
递归子程序法的基本思想是：从整个
源程序开始，根据各种语法成分的形成规
则从大到小逐层往细分析处理，而对于每
个递归定义的语法成分，都用一个相应的
递归子程序来进行处理。
