首页
>
知识点讲解
编译程序基本原理
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 >
被考次数：
11次
被考频率：
高频率
总体答错率：
49%
知识难度系数：
由 软考在线 用户真实做题大数据统计生成
相关知识点：6个
编译过程概述
编译程序的作用是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言形式）。编译程序的工作过程一般可以分为6个阶段，如下图所示，实际的编译器中可能会将其中的某些阶段结合在一起进行处理。下面简要介绍各阶段实现的主要功能。
编译器的工作阶段示意图
词法分析
源程序可以简单地被看成是一个多行的字符串。词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（如标点符号、左右括号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词类别和单词自身的值。
词法分析过程依据的是语言的词法规则，即描述“单词”结构的规则。例如，对于某Pascal源程序中的一条声明语句和赋值语句：
词法分析阶段将构成这条语句的字符串分割成如下17个单词序列：
对于标识符X、Y、Z，其单词类别都是id（用户标识符），字符串"X""Y""Z"都是单词的值；而对于单词60，整常数是该单词的类别，60是该单词的值。这里用id1、id2和id3分别代表X、Y和Z，强调标识符的内部标识由于组成该标识符的字符串不同而有所区别。经过词法分析后，声明语句VAR X，Y，Z：real；表示为VAR id1，id2，id3：real，赋值语句X:=Y+Z*60；表示为id1:=id2+id3*60；。
语法分析
语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”“程序”等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树；否则就指出语法错误，并给出相应的诊断信息。对id1:=id2+id3*60进行语法分析后形成的语法树如下图所示。
语法树示意图
词法分析和语法分析本质上都是对源程序的结构进行分析。
语义分析
语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能翻译成正确的目标代码。
语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。
在确认源程序的语法和语义之后，就可对其进行翻译并给出源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，所以应进行符号表的填查工作。在下图所示的符号表中，每一行存放一个符号的信息。第一行存放标识符X的信息，其类型为real，为它分配的地址是0；第二行存放Y的信息，其类型是real，为它分配的地址是4。因此，在该语言中，为一个real型数据分配的存储空间是4个存储单元。对于可执行语句，则检查结构合理的表达式是否有意义。对id1:=id2+id3*60进行语义分析后的语法树如下图所示，其中增加了一个语义处理节点inttoreal，该运算用于将一个整型数转换为浮点数。
语义分析后的符号表和语法树示意图
中间代码生成
中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码，其实现方式常采用四元式。四元式的形式为：
例如，对语句X:=Y+Z*60，可生成以下四元式序列：
其中，t1、t2、t3是编译程序生成的临时变量，用于存放临时的运算结果。
语义分析和中间代码生成所依据的是语言的语义规则。
代码优化
优化是一个编译器的重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间方面的效率较差。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。由于中间代码不依赖于具体机器，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。例如，在生成X:=Y+Z*60的四元式后，60是编译时已知的常数，把它转换为60.0的工作可以在编译时完成，没有必要生成一个四元式，同时t3仅仅用来将其值传递给idl，也可以化简掉，因此上述的中间代码可转优化成下面的等价代码：
这只是优化工作中的一个简单示例，真正的优化工作要复杂得多。
目标代码生成
目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。例如，使用两个寄存器R1和R2，可对上述的四元式生成下面的目标代码：
这里用#表明60.0为常数。
符号表管理
符号表的作用是记录源程序中各符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
出错处理
源程序中不可避免地会有一些错误，这些错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标错误等。静态错误是指编译阶段发现的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误称为语法错误，而语义分析时发现的运算符与运算对象类型不合法等错误属于静态语义错误。
在编译时发现程序中的错误后，编译程序应采用适当的策略修复它们，使得分析过程能够继续下去，以便在一次编译过程中尽可能多地找出程序中的错误。
对于编译器的各个阶段，在逻辑上可以把它们划分为前端和后端两部分。前端包括从词法分析到中间代码生成各阶段的工作，后端包括中间代码优化和目标代码的生成及优化等阶段。这样，以中间代码为分水岭，把编译器分成了与机器有关的部分和与机器无关的部分。如此一来，对于各种程序语言可以开发各自的编译器前端，针对指令系统和体系结构都不同的各种处理器开发相应的后端，最后将每种程序语言的前端与各种处理器的后端有机结合，就形成了每种语言在各种处理器上的编译器。这样，当语言有改动时，只需要修改其编译器的前端部分，如果处理器有改变，仅替换该语言的编译器后端即可。
文法和语言的形式描述
语言L是有限字母表Σ上有限长度字符串的集合，这个集合中的每个字符串都是按照一定的规则生成的。下面从产生语言的角度出发，给出文法和语言的形式定义。所谓产生语言，是指制定出有限个规则，借助它们就能产生此语言的全部句子。
字母表、字符串、字符串集合及运算
.字母表Σ和字符：字母表是字符的非空有穷集合，字符是字母表Σ中的一个元素。例如Σ=｛
a
，
b
｝，
a
或
b
是字符。
.字符串：Σ中的字符组成的有穷序列。例如
a
，
ab
，
aba
，
aaaa
都是Σ的字符串。
.字符串的长度：指字符串中的字符个数。如｜
aba
｜=3。
.空串
ε
：由零个字符组成的序列，｜
ε
｜=0。
.连接：字符串
S
和
T
的连接是指将串
T
接续在串
S
之后，表示为
S
·
T
，连接符号“·”可省略。显然，对于字母表Σ的任意字符串
S
，
S
·
ε
=
ε·S
=
S
。
.Σ
*
：是指包括空串
ε
在内的Σ上所有字符串的集合。例如，设Σ=｛
a
，
b
｝，Σ
*
=｛
ε
，
a
，
b
，
aa
，
bb
，
ab
，
ba
，
aaa
，…｝。
.字符串的方幂：把字符串
α
自身连接
n
次得到的串，称为字符串
α
的
n
次方幂，记为
α
n
。
α
0
=
ε
，
α
n
=
αα
n
-1
=
α
n
-1
α
（
n
>0）。
.字符串集合的运算：设
A
，
B
代表字母表Σ上的两个字符串集合。
或（合并）：
A
∪
B
=｛
α
｜
α
∈
A
或
α
∈
B
｝。
积（连接）：
AB
=｛
αβ
｜
α
∈
A
且
β
∈
B
｝。
幂：
A
n
=
A
·
A
n
-1
=
A
n
-1
：
A
（
n
>0），并规
A
0
=｛
ε
｝。
正则闭包＋：
A
+
=
A
1
∪
A
2
∪
A
3
∪…∪
A
n
∪…。
闭包*：
A
*
+
A
0
∪
A
+
。显然，Σ
*
=Σ
0
∪Σ
1
∪Σ
2
∪…∪Σ
n
∪…。
文法
描述语言语法结构的形式规则称为文法。文法
G
是一个四元组，可表示为
G
=（
V
N
，
V
T
，
P
，
S
）。其中
V
T
是一个非空有限集，其每个元素称为一个终结符；
V
N
是一个非空有限集，其每个元素称为非终结符。
V
N
∩
V
T
=
Φ
，即
V
N
和
V
T
不含公共元素。令
V
=
V
N
∪
V
T
，称
V
为文法
G
的词汇表，
V
中的符号称为文法符号，包括终结符和非终结符。
S
∈
V
N
，称为开始符号，它至少要在一条产生式中作为左部出现。
P
是产生式的有限集合，每个产生式形如“
α
→
β
”。其中，
α
称为产生式的左部，
α
∈
V
+
且
α
中至少含有一个非终结符；
β
称为产生式的右部，且
β
∈
V
*
。若干个产生式
α
→
β
1
，
α
→
β
2
，…，
α
→
β
n
的左部相同时，可简写为
α
→
β
1
｜
β
2
｜…｜
β
n
，称
β
i
（1≤
i
≤
n
）为
α
的一个候选式。
（1）文法的分类。乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法
G
=（
V
N
，
V
T
，
P
，
S
）的每个产生式
α
→
β
，均有
α
∈（
V
N
∪
V
T
）
*
，
α
至少含有一个非终结符，且
β
∈（
V
N
∪
V
T
）
*
，则称
G
为0型文法。对0型文法的每条产生式分别施加以下限制，则可得以下文法：
.1型文法：
G
的任何产生式
α
→
β
（
S
→
ε
除外）均满足｜α｜≤｜β｜（｜
x
｜表示
x
中文法符号的个数）。
.2型文法：
G
的任何产生式形如
A
→
β
，其中
A
∈
V
N
，
β
∈（
V
N
∪
V
T
）
*
。
.3型文法：
G
的任何产生式形如
A
→
a
或
A
→
aB
（或者
A
→
Ba
），其中
A
，
B
∈
V
N
，
a
∈
V
T
。
0型文法也称为短语文法，其能力相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法，它意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成
ε
串。例如，若
αAβ
→
αγβ
是1型文法的产生式，
α
和
β
不全为空，则非终结符
A
只有在左边是
α
，右边是
β
的上下文中才能替换成
γ
。2型文法就是上下文无关文法，其非终结符的替换无需考虑上下文。3型文法等价于正规式，因此也被称为正规文法或线性文法。
若文法
G
1
与文法
G
2
产生的语言相同，即
L
（
G
1
）=
L
（
G
2
），则称这两个文法是等价的。
（2）句子和语言。设有文法
G
=（
V
N
，
V
T
，
P
，
S
）。
.推导与直接推导：推导就是从文法的开始符号
S
出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列（展开产生式用
表示），直到产生一个终结符的序列时为止。若有产生式
α
→
β
∈
P
，且
γ
，
δ
∈
V
*
，则
称为文法
G
中的一个直接推导，并称
γαδ
可直接推导出
γβδ
。显然，对
P
中的每一个产生式
α
→
β
都有
。若在文法中存在一个直接推导序列，即
，则称
α
0
可推导出
α
n
，
α
n
是
α
0
的一个推导，并记为
。用记号
表示
α
0
=
α
n
或者
。
.直接归约和归约：归约是推导的逆过程。若文法
G
中有一个直接推导
，则称
β
可直接归约成
α
，或
α
是
β
的一个直接归约。若文法
G
中有一个推导
，则称
δ
可归约成
γ
，或
γ
是
δ
的一个归约。
.句型和句子：若文法
G
的开始符号为
S
，那么，从开始符号
S
能推导出的符号串称为文法的一个句型，即
α
是文法
G
的一个句型，当且仅当有如下推导
，α∈
V
*
。若
X
是文法
G
的一个句型，且
，则称
X
是文法
G
的一个句子，即仅含终结符的句型是一个句子。
.语言：从文法
G
的开始符号出发，能推导出的句子的全体称为文法
G
产生的语言，记为
L
（
G
）。
词法分析
语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
正规表达式和正规集
对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：
（1）
ε
是一个正规式，它表示集合
L
（
ε
）=｛
ε
｝。
（2）若
a
是∑上的字符，则
a
是一个正规式，它所表示的正规集为｛
a
｝。
（3）若正规式
r
和
s
分别表示正规集
L
（
r
）和
L
（
s
），则：
①
r\s
是正规式，表示集合
L
（
r
）∪
L
（
s
）。
②
r
·
s
是正规式，表示集合
L
（
r
）
L
（
s
）。
③
r
*
是正规式，表示集合（
L
（
r
））
*
。
④（
r
）是正规式，表示集合
L
（
r
）。
仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式，其中运算符“｜”“.”“*”分别称为“或”“连接”“闭包”。在正规式的书写中，连接运算符“.”可省略。运算符的优先级从高到低顺序排列为“*”“.”“｜”。
设∑=｛
a
，
b
｝，下表列出了∑上的一些正规式和相应的正规集。
正规式与正规集示例
若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式
U
和
V
记为
U
=
V
。例如，
b
（
ab
）
*
=（
ba
）
*
b
，（
a
｜
b
）
*
=（
a
*
b
*
）
*
。设
U
、
V
和
W
均为正规式，正规式的代数性质如下表所示。
正规式的代数性质
有限自动机
有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
（1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是一个五元组（
S
，Σ，
f
，
s
0
，
Z
），其中：
.
S
是一个有限集，其每个元素称为一个状态。
.Σ是一个有穷字母表，其每个元素称为一个输入字符。
.
f
是
S
×Σ→
S
上的单值部分映像。
f
（
A
，
a
）=
Q
表示当前状态为
A
、输入为
a
时，将转换到下一状态
Q
。称
Q
为A的一个后继状态。
.
s
0
∈
S
，
s
0
称为开始状态，是唯一的。
.
Z
是非空的终止状态集合，
。
一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为
f
（
A
，
a
）=
Q
，则该有向弧从节点
A
出发，进入节点
Q
，字符
a
是弧上的标记。
（2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下：
①
f
是
S
×Σ→2
S
上的映像。对于
S
中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
②有向弧上的标记可以是
ε
。
（3）NFA到DFA的转换。
任何一个NFA都可以转换为DFA，下面先定义转换过程中需要的计算。
定义1：
状态集
I
的
ε
_闭包。
若
I
是NFA
N
的状态集合的一个子集，定义
ε
_CLOSURE（
I
）如下：
.状态集
I
的
ε
_CLOSURE（
I
）是一个状态集。
.状态集
I
的所有状态属于
ε
_CLOSURE（
I
）。
.若
s
∈
I
，那么从
s
出发经过任意条
ε
弧到达的状态
s
'都属于
ε
_CLOSURE（
I
）。
状态集
ε
_CLOSURE（
I
）称为
I
的
ε
_闭包。
由以上的定义可知，
I
的
ε
_闭包就是从状态集
I
的状态出发，经
ε
所能到达的状态的全体。
定义2：
状态集
I
的对字符
a
的状态转移。
假定
I
是NFA
N
的状态集的一个子集，
a
是Σ中的一个字符，定义：
I
a
=
ε
_CLOSURE（
J
）
其中，
J
是所有那些可从
I
中的某一状态节点出发经过一条
a
弧而到达的状态节点的全体。
用子集法将一个NFA转换为一个DFA。
设NFA
N
=（
S
，Σ，
f
，
s
0
，
Z
），与之等价的DFA
M
=（
S
'，Σ，
f
'，
q
0
，
Z
'），用子集法将非确定的有限自动机确定化的算法步骤如下：
①求出DFA
M
的初态
q
0
，即令
q
0
=
ε
_CLOSURE（｛
s
0
｝），此时
S
'仅含初态
q
0
，并且没有标记。
②对于
S
'中尚未标记的状态
q
i
=｛
s
i
1
，
s
i
2
，…，
s
im
｝，
s
ij
∈
S
（
j
=1，…，
m
）进行以下处理：
.标记
q
i
，以说明该状态已经计算过。
.对于每个
a
∈∑，令
T
=
f
（｛
s
i
1
，
s
i
2
，…，
s
im
｝，
a
），
q
j
=
ε
_CLOSURE（
T
）。
.若
q
j
尚不在
S
'中，则将
q
j
作为一个未加标记的新状态添加到
S
'，并把状态转换函数
f
'（
q
i
，
a
）=
q
j
添加到DFA
M
中。
③重复进行步骤②，直到
S
'中不再出现未标记的状态时为止。
④令
Z
'=｛
q
｜
q
∈
S
'且
q
∩
Z
≠
?
｝。
识别
ab
*
a
的DFA示意图
对上图所示的自动机进行化简所得的DFA如下图所示。
识别
ab
*
a
的最小化DFA示意图
正规式与有限自动机之间的转换
正规式与有限自动机间可以相互转换。
（1）有限自动机转换为正规式。
对于Σ上的NFA
M
，可以构造一个Σ上的正规式
R
，使得
L
（
R
）=
L
（
M
）。
拓广状态转换图的概念，令每条弧可用一个正规式作标记。为Σ上的NFA
M
构造相应的正规式
R
，分为如下两步：
第一步：在
M
的状态转换图中加两个节点，一个
x
节点，一个
y
节点。从
x
节点到NFA
M
的初始状态节点引一条弧并用
ε
标记，从NFA
M
的所有终态节点到
y
节点引一条弧并用
ε
标记。形成一个与
M
等价的
M
'，
M
'只有一个初态
x
和一个终态
y
。
第二步：按下面的方法逐步消去
M
'中除
x
和
y
的所有节点。在消除节点的过程中，用正规式来标记弧，最后节点
x
和
y
之间弧上的标记就是所求的正规式。消除节点的规则如下图所示。
有限自动机到正规式的转换规则示意图
（2）正规式转换为有限自动机。
同样地，对于Σ上的每个正规式
R
，可以构造一个Σ上的NFA
M
，使得
L
（
M
）=
L
（
R
）。
①对于正规式
R
，可用下图所示的拓广状态图表示。
拓广状态图
②通过对正规式
R
进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或
ε
，转换规则如下图所示。
正规式到有限自动机的转换规则示意图
最后所得的图即为一个NFA
M
，
x
为初态节点，
y
为终态节点。显然，
L
（
M
）=
L
（
R
）。
词法分析器的构造
构造词法分析器的一般步骤为：用正规式描述语言中的单词构成规则；为每个正规式构造一个NFA，它识别正规式所表示的正规集；将构造出的NFA转换成等价的DFA；对DFA进行最小化处理，使其最简；最后用手工编码或表驱动的方式从最简DFA构造词法分析器。
语法分析
语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即是否为合法的表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。语法分析方法有多种，根据产生语法树的方向，可分为自底向上（或自下而上）和自顶向下（或自上而下）两类。
上下文无关文法
上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法
G
［
S
］=（
VN
，
VT
，
P
，
S
），其产生式的形式都是
A
→
β
，其中
A
∈
V
N
，
β
∈（
V
N
∪
V
T
）
*
。
若不加特别说明，下面用大写英文字母
A
、
B
、
C
等表示非终结符，小写英文字母
a
、
b
、
c
等表示终结符号，
u
、
v
、
w
等表示终结符号串，小写希腊字母
α
、
β
、
γ
、
δ
等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以简写为其产生式集合的描述形式。
（1）规范推导（最右推导）。如果在推导的任何一步
其中
α
、
β
是句型），都是对
α
中最右边的非终结符进行替换，则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
（2）短语、直接短语和句柄。设
αδβ
是文法
G
的一个句型，即
，且满足
和
，则称
δ
是句型
αδβ
相对于非终结符
A
的短语。特别地，如果有
，则称
δ
是句型
αδβ
相对于产生式
A
→
δ
的直接短语。一个句型的最左直接短语称为该句型的句柄。
自顶向下语法分析方法
自顶向下分析法的基本思想是：对于给定的输入串
ω
，从文法的开始符号
S
出发进行最左推导，直到得到一个合法的句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右地为输入串
ω
建立语法树。整个分析过程是一个试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。若输入串是给定文法的句子，则必能成功，反之必然出错。
文法中存在下述产生式时，自顶向下分析过程中会出现下面的问题：
（1）若文法中存在形如
A
→
αβ
｜
αδ
的产生式，即
A
产生式中有多于一个候选项的前缀相同（称为公共左因子，简称左因子），则可能导致分析过程中的回溯处理。
（2）若文法中存在形如
A
→
Aα
的产生式，由于采取了最左推导，可能会造成分析过程陷入死循环的情况，产生式的这种形式被称为左递归。
因此，需要对文法进行改造，消除其中的左递归，以避免分析陷入死循环；提取左因子，以避免回溯。
（3）递归下降分析法。递归下降分析法直接以子程序调用的方法模拟产生式产生语言的过程，其基本思想是：为每一个非终结符构造一个子程序，每个子程序的过程体按该产生式候选项分情况展开，遇到终结符即进行匹配，而遇到非终结符则调用相应的子程序。该分析法从调用文法开始符号的子程序开始，直到所有非终结符都展开为终结符并得到匹配为止。若分析过程可以达到这一步，则表明分析成功，否则表明输入串中有语法错误。递归下降分析法的优点是简单且易于构造，缺点是程序与文法直接相关，对文法的任何改变都需要在程序中进行相应的修改。
（4）预测分析法。预测分析法是另一种自顶向下的语法分析方法，其基本模型如下图所示。
预测分析模型示意图
预测分析法的核心是预测分析表，可以用一个二维数组
M
表示，其元素
M
［
A
，
a
］（
A
∈
V
N
，
a
∈
V
T
∪#）存放关于
A
的产生式，表明当遇到输入符号为
a
且用
A
进行推导时，所应采用的产生式；若
M
［
A
，
a
］为error，则表明推导时遇到了不该出现的符号，应进行出错处理。
例如，根据文法
G
［
E
］=｛
E
→
TE
'，
E
'→+
TE
'｜
ε
，
T
→
FT
'，
T
'→*
FT
'｜
ε
，
F
→（
E
）｜
id
｜｝的构造的预测分析表如下表所示。
预测分析表
预测分析法的工作过程是：初始时，将“#”和文法的开始符号依次压入栈中；在分析过程中，根据输入串中的当前输入符号
a
和当前的栈顶符号
X
进行处理。
若
X
=
a
='#'，则分析成功；若
X
='#'且
a
≠'#'，则出错。
若
X
∈
V
T
且
X
=
a
，则
X
退栈，并读入下一个符号
a
；若
X
∈
V
T
且
X
≠
a
，则出错。
若
X
∈
V
N
且
M
［
X
，
a
］='
A
→
α
'，则
X
退栈，
α
中的符号从右到左依次进栈（
ε
无须进栈）；若
M
［
X
，
a
］='error'，则调用出错程序进行处理。
自底向上语法分析方法
常用的自底向上分析方法也称移进-归约分析法，工作模型是下推自动机，如下图所示。其基本思想是对输入序列
ω
自左向右进行扫描，并将输入符号逐个移进一个栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串（即句柄）时，就用某个产生式的左部非终结符来替代，这称为一步归约。重复这一过程，直至栈中只剩下文法的开始符号且输入串也被扫描完时为止，确认输入串
ω
是文法的句子，表明分析成功；否则，进行出错处理。
移进-归约分析模型
LR分析法是一种规范归约分析法。规范归约是规范推导（最右推导）的逆过程，下面举例说明规范归约的过程。
LR分析法根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的
k
个（
k
≥0）符号，就可唯一确定分析器的动作是移进还是归约，以及用哪条产生式进行归约，因而也就能唯一地确定句柄。当
k
=1时，已能满足当前绝大多数高级语言编译程序的需求。常用的LR分析器有LR（0）、SLR（1）、LALR（1）和LR（1）。
一个LR分析器由如下三个部分组成：
（1）驱动器。或称驱动程序。对所有LR分析器，驱动程序都是相同的。
（2）分析表。不同的文法具有不同的分析表。同一文法采用不同的LR分析器时，分析表也不同。分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分，它们都可用二维数组表示。
（3）分析栈。其包括文法符号栈和相应的状态栈。
分析器的动作由栈顶状态和当前输入符号决定（LR（0）分析器不需向前查看输入符号），LR分析器的模型如下图所示。
LR分析器模型示意图
其中SP为栈顶指针，
S
i
为状态，
X
i
为文法符号。ACTION［
S
i
，
a
］=
S
j
规定了栈顶状态为
S
i
且遇到输入符号
a
时应执行的动作。状态转换表GOTO［
S
i
，
X
］=
S
j
表示当状态栈顶为
S
i
且文法符号栈顶为
X
时应转向状态
S
j
。
LR分析器的工作过程以格局的变化来反映。格局的形式为（栈，剩余输入，动作）。分析是从某个初始格局开始的，经过一系列的格局变化，最终达到接受格局，表明分析成功；或者达到出错格局，表明发现一个语法错误。因此，开始格局的剩余输入应该是全部的输入序列，而接受格局中的剩余输入应该为空，任何其他格局或者出错格局中的剩余输入应该是全部输入序列的一个后缀。
在LR分析过程中，改变格局的动作有以下4种：
（1）移进（shift）。当ACTION［
S
i
，
a
］=
S
j
时，把
a
移进文法符号栈并转向状态
S
j
。
（2）归约（reduce）。当在文法符号栈顶形成句柄
β
时，把
β
归约为相应产生式
A
→
β
的非终结符
A
。若
β
的长度为
r
（即｜
β
｜=
r
），则弹出文法符号栈顶的
r
个符号，然后将
A
压入文法符号栈中。
（3）接受（accept）。当文法符号栈中只剩下文法的开始符号
S
，并且输入符号串已经结束时（当前输入符是“#”），分析成功。
（4）报错（error）。当输入串中出现不该有的文法符号时，就报错。
LR分析器的核心部分是分析表的构造，这里不再详述。
语法制导翻译和中间代码生成
程序语言的语义分为静态语义和动态语义。描述程序语义的形式化方法主要有属性文法、公理语义、操作语义和指称语义等，其中属性文法是对上下文无关文法的扩充。目前应用最广的静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予文法的产生式。在语法分析的推导或归约的步骤中，通过执行语义规则实现对属性的计算，以实现对语义的处理。
中间代码
从原理上讲，对源程序进行语义分析之后就可以直接生成目标代码，但由于源程序与目标代码的逻辑结构往往差别很大，特别是考虑到具体机器指令系统的特点，要使翻译一次到位很困难，而且用语法制导方式机械生成的目标代码往往是烦琐和低效的，因此有必要设计一种中间代码，将源程序首先翻译成中间代码表示形式，以利于进行与机器无关的优化处理。由于中间代码实际上也起着编译器前端和后端的分水岭作用，所以使用中间代码也有助于提高编译程序的可移植性。常用的中间代码有后缀式、四元式和树等形式。
（1）后缀式（逆波兰式）。逆波兰式是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用栈实现求值。对于表达式x:=（a+b）*（c+d），其后缀式为xab+cd+*:=。
（2）树形表示。例如，表达式x:=（a+b）*（c+d）的树形表示如下图所示。
表达式的树形表示
（3）四元式表示。四元式是一种普遍采用的中间代码形式，其组成成分为运算符OP、第一运算对象ARG1、第二运算对象ARG2和运算结果RESULT。其中，运算对象和运算结果有时指用户自定义的变量，有时指编译程序引入的临时变量，RESULT总是一个新引进的临时变量，用来存放运算结果。例如，表达式x:=（a+b）*（c+d）的四元式表示为：
①（+，a，b，t1）②（+，c，d，t2）③（*，t1，t2，t3）④（：=，t3，_，x）
常见语言结构的翻译
常见的程序语言结构主要有算术表达式、布尔表达式、赋值语句和控制语句（if、while）等。不同结构需要不同的处理方法，但翻译程序的构造原理是相似的。
对于各种语法结构的语法制导翻译，一般是在相应的语法规则中加入适当的语义处理，从而在对程序语句进行语法分析过程中的恰当时机同时完成语义处理，实现语义分析。
例如，语句if x
四元式表
动态存储分配和过程调用的翻译
过程（函数）说明和过程（函数）调用是程序中一种常见的语法结构，绝大多数语言都含有这方面的内容。过程说明和调用语句的翻译，有赖于形参与实参结合的方式以及数据空间的分配方式。
由于各种语言的不同特点，在目标程序运行时，对存储空间的分配和组织有不同的要求，在编译阶段应产生相应的目标来满足不同的要求。需要分配存储空间的对象有基本数据类型（如整型、实型和布尔型等）、结构化数据类型（如数组和记录等）和连接数据（如返回地址、参数等）。分配的依据是名字的作用域和生存期的定义规则。分配的策略有静态存储分配和动态存储分配两大类。
如果在编译时就能确定目标程序运行时所需的全部数据空间的大小，则在编译时就安排好目标程序运行时的全部数据空间，并确定每个数据对象的存储位置（逻辑地址）。这种分配策略称为静态存储分配。Fortran语言的早期版本可以完全采用静态存储分配策略。
如果一个程序语言允许递归过程和动态可变数据结构，那么就需采用动态存储分配技术。动态存储分配策略的实现有栈分配方式和堆分配方式两种。在栈式动态存储分配中，将程序的数据空间设计为一个栈，每当调用一个过程时，它所需的数据空间就分配在栈顶；每当过程执行结束时，就释放这部分空间。若空间的使用未必服从“先申请后释放”的原则，那么栈式的动态存储分配方式就不适用了，这种情况下通常使用堆分配技术。
中间代码优化和目标代码生成
优化就是对程序进行等价变换，使得从变换后的程序能生成更有效的目标代码。所谓等价，是指不改变程序的运行结果；所谓有效，是指目标代码运行时间较短，占用的存储空间较少。优化可在编译的各个阶段进行。最主要的优化是在目标代码生成以前对中间代码进行的，这类优化不依赖于具体的计算机。
目标代码的生成由代码生成器实现。代码生成器以经过语义分析或优化后的中间代码为输入，以特定的机器语言或汇编代码为输出。代码生成所需考虑的主要问题如下所述：
（1）中间代码形式。中间代码有多种形式，其中树与后缀表示形式适用于解释器，而编译器多采用与机器指令格式较接近的四元式形式。
（2）目标代码形式。目标代码可以分为两大类：汇编语言形式和机器指令形式。机器指令形式的目标代码又可以根据需求的不同分为绝对机器指令代码和可再定位机器代码。绝对机器代码的优点是可以立即执行，一般应用于一类称为load-and-go形式的编译模式，即编译后立即执行，不形成保存在外存上的目标代码文件。可再定位机器代码的优点是目标代码可以被任意链接并装入内存的任意位置，是编译器采用较多的代码形式。汇编语言作为一种中间输出形式，便于进行分析和测试。
（3）寄存器的分配。由于访问寄存器的速度远快于访问内存单元的速度，所以总是希望尽可能多地使用寄存器存储数据，而寄存器的个数是有限的，因此，如何分配及使用寄存器，是目标代码生成时需要着重考虑的。
（4）计算次序的选择。代码执行的效率会随计算次序的不同有较大的差别。在生成正确目标代码的前提下，适当地安排计算次序并优化代码序列，也是生成目标代码时要考虑的重要因素之一。
相关知识点：
汇编语言
解释程序基本原理
解释程序的基本结构
汇编程序
编译与解释方式的比较
汇编程序基本原理
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师
系统分析师
系统架构设计师
网络规划设计师
系统规划与管理师
初级资格科目
程序员
网络管理员
信息处理技术员
信息系统运行管理员
中级资格科目
系统集成项目管理工程师
网络工程师
软件设计师
信息系统监理师
信息系统管理工程师
数据库系统工程师
多媒体应用设计师
软件评测师
嵌入式系统设计师
电子商务设计师
信息安全工程师
本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。
工作时间：9:00-20:00
客服
商务合作
客服邮箱
service@rkpass.cn
京B2-20210865
|
京ICP备2020040059号-5
|
京公网安备 11010502032051号
|
营业执照
| Copyright ©2000-2023 All Rights Reserved 软考在线版权所有
