2.2 编译系统基本原理

2.2.1 编译概述

编译程序的职能是把使用某程序设计语言书写的程序翻译为等价的机器语言程序，所谓等价是指目标程序执行源程序预定的任务。一般来说，编译程序分为以下几个部分：词法分析、语法分析和语义分析、代码优化、代码生成和符号表管理。各部分之间的关系如图2-2所示。

词法分析程序是编译程序的第一个部分，它的输入是源程序中由字符组成的符号。编译程序需要把程序的这种外部形式转换成适合后续程序处理的形式，其功能有：

（1）识别出源程序中意义独立的最小词法单位——单词，并且确定其类型（例如，是标识符、关键字、操作符还是数字等）；

（2）删除无用的空格、回车和其他与输入介质有关的无用符号，以及程序注释；

（3）报告分析时的错误。

经过词法分析程序处理后，源程序就转化为单词串。每个单词都是一个意义独立的单位，其所包含的信息量个数固定。语法分析程序根据特定的程序设计语言文法规则，检查单词串是否符合这些规则。一旦语法分析程序分解出其中一个文法结构，该结果的语义分析程序就进行相应的语义检查，在有需要的时候输出相应的中间代码。这里的中间代码可以理解为假想的虚拟机的指令，其执行次序反映了源程序的原始定义。语法和语义分析程序是编译程序中的关键部分。

中间代码作为代码生成程序的输入，由代码生成程序生成特定的计算机系统下的机器代码。为了提高目标代码的运行效率和减小目标代码大小，也可以在语法语义分析程序与代码生成程序之间插入代码优化程序。代码优化程序在不改变代码所完成的工作的前提下对中间代码进行改动，使其变成一种更有效的形式。

编译程序在完成其任务的过程中，还需要进行符号表的管理和出错处理。在符号表中登记了源程序中出现的每一个标识符及其属性。在整个编译过程中，各部分程序都可以访问某标识符的属性，包括标识符被说明的类型、数组维数、所需存储单元数，以及所分配的内存单元地址等。错误管理程序是在分析程序发现源程序有错误而无法继续工作时进行其工作的。其任务是记录并向用户报告错误及其类型和位置，或者尝试进行某种恢复工作。

2.2.2 形式语言基本知识

首先介绍关于字母表和符号串的定义。

无论是自然语言还是形式语言，均是由特定的符号，如字母、数字等组合而成的，符号的非空有限集合被称为字母表。由某一字母表中的符号组成的有限符号序列称为该字母表的符号串。符号串α的长度是指α中出现的符号个数，记为|α|。空串的长度为0，用ε表示。

符号串α的前缀是指α的末尾删除零个或多个符号后得到的符号串，如pro是program的一个前缀。符号串α的后缀是指α的开头删除0个或多个符号后的得到的符号串，如gram是符号串program的一个后缀。符号串α的子串是删除了α的前缀和后缀后得到的符号串，如og是program的子串，α的前缀和后缀都是它的子串。对于任意符号串α ， 其自身和ε都是α的前缀、后缀，也是α的子串。符号串α的真前缀、真后缀和真子串是指除空串ε和α自身外，α的前缀、后缀和子串。

符号串α的子序列是从α中删除0个或多个符号（这些符号不要求是连续的）而得到的符号串。

下面介绍符号串之间的运算。

符号串α、β的连接αβ是指把β写在α的后面得到的符号串，从空串的定义可以推出εα=αε=α。符号串α的方幂α ⁿ 定义为：αα…α（n个），有α ⁰ =ε，α ¹ =α。

术语“语言”表示某个确定的字母表上符号串的任何集合。空集合{}和只包含空串的集合{ε}也是符合定义的语言。在字符串运算的基础上，我们可以定义语言的运算：

（1）语言L和M的合并，L∪M＝{s|s∈L或s∈M}

（2）语言L和M的连接，

（3）语言L的Kleene闭包，

（4）语言L的正闭包，

上面对语言的定义是非形式化的，下面要介绍形式化的语言定义，这里首先引入文法的概念。

所谓文法G是一个四元组，G={V _T ，V _N ，S，P}。其中V _T 是一个非空有限的符号集合，它的每个元素成为终结符号。V _N 也是一个非空有限的符号集合，它的每个元素称为非终结符号，并且有V _T ∩V _N ＝。S∈V _N ，称为文法G的开始符号。P是一个非空有限集合，它的元素称为产生式。所谓产生式，其形式为：α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α,β（V _T ∪V _N )*,α≠εβ，即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形如α→β，α→γ的产生式缩写为α→β|γ，以方便书写。

1956年，著名的语言学家Noam Chomsky首先对形式语言进行了描述，把文法定义为四元组，并且根据对产生式所施加限制的不同，把文法分成了4类，并定义了相应的4类形式语言。表2-1描述了4类文法，以及其产生的语言。

对于文法G[S]我们称αAβ直接推导出αγβ（也可以说αγβ是αAβ的直接推导），仅当A→γ是文法G的一个产生式，且 ，记作 。如果存在直接推导序列： ，我们称该序列为 到α _n 的推导，也称为 可以推导出α _n ，记作 。如果n=0，即 或 ，则记为 。如果在每一步的直接推导中，都对最左边的非终结符应用相应的产生式的右部来代替，则称这种推导为最左推导。类似地，如果在第一步的直接推导中，都对最右边的非终结符应用相应的产生式的右部来代替，则称这种推导为最右推导。

在文法G[S]中，如果存在 ，则称α是文法G的一个句型，仅含终结符号的句型是文法G的一个句子。语言L(G)是由文法G产生的所有句子组成的集合，其形式定义为： 且 。我们称文法G1和文法G2是等价的，如果有L(G1)=L(G2)。即有可能不同的文法产生相同的语言。

对于文法G，如果有 且 ，则称β是一个关于非终结符号A的，句型αβδ的短语。如果 ，则称βG是直接短语。一个句型的最左直接短语称为该句型的句柄。

要检查由符号串x是否是文法G的一个句型或者句子，就要检查是否存在一个由S到α的x的推导。推导树的每一个结点和终结符或者非终结符相关联。和终结符关联的结点是叶结点，而与非终结符相关联的结点可以是叶结点也可以是非叶结点，树的根结点为文法的开始符号S。已知符号串x在文法G中的一个推导，就可以构造相应的推导树。将x中的每一步产生式的应用表达从所替代的非终结符号生长出新的树杈，且子结点自左向右逐个地和产生式的右部符号相关联。因此，每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型，如果所有的终端结点都是与终结符关联，则该字符串是文法G的一个句子，此时该推导树是完全推导树。考察文法G=（{a, b}, {S, A}, S, P），其中P：

S→aAS|a

A→SbA|SS|ba

句型aabAa相对应的推导树构造的全过程，如图2-3所示。

这里我们再引入子树的概念。分析树的子树是树中一个特有的结点连同它的全部后裔和连接这些后裔的边，因此子树的根结点可能不是开始符号。子树和短语的关系十分密切。一棵子树的所有叶子自左至右所构成的字符串就是相对于子树根的短语，一个句型的分析树中最左那棵只有父子两代的子树的所有叶子自左至右所构成的字符串就是该句型的句柄。

如果一文法的句子存在两棵不同的分析树，我们称该句子是二义性的，如果一文法包含二义性的句子，则称该文法为二义性的，否则该文法是无二义性的。需要注意的是，文法的二义性和语言的二义性是不同的。可能出现的情况时有两个文法G和G'，且G有二义性而G'无二义性，但L(G)=L(G')，即文法G与文法G'产生相同的语言。因此，有时可以在不改变一个二义性文法的句子集合的情况下改变该文法，得到一个无二义性的文法。但是，也有一些语言，它们不存在无二义性的文法，这样的语言我们称为先天二义性的语言。

2.2.3 词法分析

词法分析是整个分析过程的一个子任务，它把构成源程序的字符串转换成语义上关联的单词符号（包括关键字、标识符、常数、运算符和分界符等）的序列。词法分析可以借助于有限自动机的理论与方法进行有效的处理。

1．有限自动机

有限状态自动机是具有离散输入和输出的系统的一种数学模型。系统可以处以内部状态的任何一个之中，系统当前状态概括了有关过去输入的信息，这些信息对在后来的输入上确定系统的行为是必需的。有限状态自动机与词法分析程序的设计有着密切的关系。下面是确定的有限状态自动机的形式定义。

一个确定的有限状态自动机M（记作DFA M）是一个五元组(∑，Q，q ₀ ，F, δ )

其中，

（1）Q是一个有限状态集合；

（2）Σ是一个字母表，其中的每个元素称为一个输入符号；

（3）q ₀ ∈Q，称为初始状态；

（4） ，成为终结状态集合；

（5）δ是一个从Q XΣ（Q与Σ的笛卡尔乘积）到Q的单值映射：

δ(q, a) = q' （q, q'∈Q, a∈Σ）

表示当前状态为q，输入符号为a时，自动机将转换到下一个状态q'，q'称为q的一个后继。

若 ， ，则 是一个n行m列矩阵，称为DFA M的状态转换矩阵，或称转换表。

有限状态自动机可以形象地用状态转换图表示。设有有限状态自动机：

DFA M = ({S, A, B, C, f}, {1, 0}, S, {f}, δ)，其中：

δ(S, 0) = B,δ(S, 1) = B,δ(A, 0) = f,δ(A, 1) = C,δ(B, 0) = C,δ(B, 1) = f,

δ(C, 0) = f,δ(C, 1) = f

其对应的状态转换图，如图2-4所示。

图2-4中的圈表示状态结点，其中双圈表示终结状态结点。而边表示状态的转换，代表映射。边上的符号表示此转换需要输入的符号，代表映射的输入。

对于Σ上的任何字符串 ，若存在一条从初态结点到终态结点的路径，在这条路径上的所有边的符号连接成的符号串恰好是w，则成w为DFA M所识别（或接受或读出）。DFA M所能识别的符号串的全体记为L(M)，称为DFA M所识别的语言。如果对所有 ，以下述的递归方式扩张δ的定义：

δ(q,ε)=q

δ(q,wa)=δ(δ(q,w),a)，对任何a∈Σ,q∈Q

我们则可以把DFA M所识别的语言形式定义为：

L(M)＝{w|w∈ ∑ *，若存在q∈F，使 δ (q ₀ ,w)＝q

前面介绍的是确定的有限自动机，即一个状态对于特定的输入字符有一个确定的后继状态。而当一个状态对于特定的输入字符有一个以上的后继状态时，我们称该有限自动机为非确定有限自动机（记作NFA M）。其形式定义为：

一个非确定的有限自动机M是一个五元组：

M＝( ∑ ，Q，q ₀ ，F, δ )

其中Σ，Q，q ₀ ，F的意义和DFA的定义一样，而δ是一个从Σ×Q到Q的子集的映射，即 δ ：Q× ∑ →2 ^Q ，其中2 ^O 是Q的幂集，即Q的所有子集组成的集合。

与确定的有限自动机一样，非确定有限自动机同样可以用状态转换图表示，所不同的是在图中，一个状态结点可能有一条以上的边到达其他状态结点。同样，对于任何字符串w∈ ∑ *，若存在一条从初态结点到终态结点的路径，在这条路径上的所有边的符号连接成的符号串恰好是w，则成w为NFA M所识别（或接受或读出）。若q ₀ ∈F，这时q ₀ 既是初始状态也是终结状态，因而有一条从初态结点到终态结点的ε-路径，此时空符号串可以被NFA M接受。NFA M所能识别的符号串的全体记为L(M)，称为NFA M所识别的语言。

对任何一个NFA M，都存在一个DFA M'使L(M')=L(M)，这时我们称M'与M等价。构造与M等价M'的基本方法是让M'的状态对应于M的状态集合。即如果有 ，则把 看做M'的一个状态，即M'中的状态集合Q'的一个元素。

对于一个非确定有限自动机，如果我们把δ扩展为从Q× ∑ ∪{ε}到2 ^Q 的映射，则称该自动机为带ε-转移的非确定有限自动机。同样，对于带ε-转移的非确定有限自动机，也可以构造与之等价的不带ε-转移的非确定有限自动机。

2．正规表达式

正规表达式是一个十分有用的概念，它紧凑的表达有限自动机所接受的语言。对正规表达式的递归定义为：一个正规表达式是按照一组定义规则由一些较简单的正规表达式所组成的。在字母表Σ上的正规表达式可以使用以下规则定义：

（1）ε和φ是Σ上的正规表达式，它们所表示的语言分别为{ε}和空集。

（2）如果a是Σ内的一个符号，则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)的正规表达式。

通常在正规表达式中，一元运算符“*”具有最高的优先级，连接运算具有次优先级，运算符“|”具有最低优先级，这3个运算都是左结合的。每一个正规表达式R都对应一个有限自动机M，使M所接受的语言就是正规表达式的值。经过以下步骤可以从一个正规表达式R构造出相应的有限自动机M。

首先定义初始状态S和终止状态f，并且组成有向图：

然后反复应用以下规则：

直到所有的边都以Σ中的字母或ε标记为止。由此产生了一个带ε-转移的非确定有限自动机，然后可以通过上面介绍的方法，把该自动机转换成确定有限状态自动机。

下面举一个例子说明自动机理论在词法分析程序中的应用。C语言中对标识符的规定为由“_”或字母开头的，由“_”、字母和数字组成的字符串，该标识符的定义可以表示为下面的正则表达式：

(_|a)(_|a|d)*

式中的α代表字母字符{A,…,Z,a,…,z}，d代表数字字符{0,1,…,9}。利用前面的方法构造出如图2-5所示的有限自动机。

该自动机所接受的语言就是C语言中的标识符。

在有限自动机的状态转换过程中，需要执行相关的语义动作。例如，当识别到一个标识符时，需要在符号表中添加该标识符，并且向语法分析程序输送表示该标识符的单词。

2.2.4 语法分析

1．下推自动机

为了帮助理解语法分析程序，在这里先介绍下推自动机的概念。下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象地理解为，把有限状态自动机扩展使之可以存取一个栈。

下推自动机存在确定与非确定两种形式，两者并不等价。

每一个下推自动机都接受一个形式语言。被非确定下推自动机接受的语言是上下文无关语言。如果把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。下面是下推自动机的形式定义：

下推自动机M是如下的一个七元组 ( Q, Σ, Γ, δ, q ₀ , Z ₀ , F )。

其中，

（1）Q是一个有限状态集合；

（2）Σ是一个字母表，称为输入字母表；

（3）Γ是一个字母表，称为栈字母表；

（4）q ₀ 属于Q，是初始状态；

（5）Z _{0 属于} Γ，是一个特殊的栈符号，称为栈起始符号；

（6）F包含于Q，是终结状态集合；

（7）δ：Q×(Σ∪{ε})×Γ→Q×Γ* 是 M 的动作函数。

我们可以把下推自动机想象为由一个状态寄存器、一个下推栈及一个读入头组成的自动机模型，每次从读入头读入下一个字符，并根据状态寄存器的状态及下推栈的栈顶符号进行动作，改变状态寄存器的状态值，弹出栈顶符号并下推入相应的符号。当字符串读入完毕，并且栈顶符号为Z ₀ 时表示接受该符号串。

2．自顶向下语法分析

该分析方法是以文法开始符号为根，试图寻找以输入符号串为端点的推导树。每次都以最左的那个非终结符为根，选择适当的产生式，往下扩展子树。

考虑上下文无关文法G=({a, b, c}, {S, B}, S, P)，其中P为：

（1）S→aBS

（2）S→b

（3）B→cBS

（4）B→d

设输入字符串为w=acdbb，如果w是G的一个句子，则可以从S出发构造一棵以w为端点的推导树。我们首先构造分析该文法的下推自动机，对于输入串acbb，则下推栈与输入的过程如表2-2所示。

这里的关键是，每个产生式都有一个由相应终结符组成的选择集合。只要产生式左部相同的选择集合两两不相交，则下推自动机就能确定性的工作。为此引入两个集合FIRST(α)、FOLLOW(A)来求选择集合。

（1）

特别是，若 ，则规定ε∈FIRST(α)。

求法如下。

①对每一文法符号X∈V计算FIRST(X)。

a．若X∈V _T ，则X加入FIRST(X)。

b．若X∈Vn，考察它的产生式：

若X→a…，a∈V _T ，则a加入FIRST(X)；

若X→ε，则ε加入FIRST(X)；

若X→R ₁ R ₂ …，R _k ，且R ₁ ∈Vn，则先将FIRST(R ₁ )/ε（所有非ε元素）加入FIRST(X)，然后在R ₁ R ₂ …R _{i -1} * ε(意味着对每个j：1≤j≤i–1，ε∈FIRST(Rj))时，将FIRST(Ri)/ε加入FIRST(X)。特别是，若ε∈FIRST(Rj)，j=1，2，…，k，将ε加入FIRST(X)。

c．反复执行b步直到每个符号的FIRST集不再增大为止。

②对α∈V*，计算FIRST(α)，设α=X ₁ X ₂ …X _n ，X _i ∈V，1≤i≤n。

a．置FIRST(α)=FIRST(X ₁ )/ε。

b．若ε∈FIRST(X _j )，j=1，2，…，i-1，2≤i≤n，则将FIRST(X _i )/ε加入到FIRST(α)中；特别是，若ε∈FIRST(X _j )，j=1，2，…，n，则ε*加入到FIRST(α)中。

（2）

其中，S是文法开始符。特别是 ，则规定#∈FOLLOW(A)。

求法如下。对每一个A∈Vn，逐个考察产生式：

①将#加入FOLLOW(S)，S为文法开始符。

②若A→αBβ是一条产生式，B∈Vn，则把*FIRST(β)/ε加入FOLLOW(B)。

③若A→αB是一条产生式或A→αBβ且 (即(ε∈FIRST(β))，则将FOLLOW(A)加入FOLLOW(B)。

④反复使用②、③直到每个非终对符的FOLLOW集不再增大为止。

现在我们根据FIRST集合和FOLLOW集合求SELECT集合，公式如下：

SELECT(A→α)=FIRST(α)∪FOLLOW(A)

即，当α不能推导出ε时，该产生式的选择集合就是α的头符号集合；否则，该产生式的选择集合式α的头符号集合和A的后继集合之和。对于上面的文法G[S]，其各个产生式的选择集合为：

SELECT(S→aBS) = {a}

SELECT(S→b) = {b}

SELECT(B→cBS) = {c}

SELECT(B→d) = {d}

设G是一个上下文无关文法，如果该文法中左部相同的产生式的选择集合两两不相交，则称G为LL(1)文法。

除使用下推自动机外，另一个自顶向下的语法分析方法是采用递归子程序技术。其基本思想是对每一个非终结符构造一个过程，由这个过程识别相应的非终结符所能生成的终结符串。过程执行时总是假定输入符号总是语法结构A所能产生的终结符号串的头符号。过程结束时，当前输入符号是非终结符A的后继符号。由于一个过程在识别时会调用其他分析过程（包括它自己）来识别其各自所能识别的符号串，实际上，递归程序法是使用允许递归过程调用的语言在运行时刻的调用栈来模拟下推自动机的下推栈。

3．自底向上语法分析

自底向上分析技术是从输入符号串出发，试图把它归约为识别符号。从语法树的角度看，这个技术首先以输入符号作为语法树的末端结点，然后向根结点方向构造语法树。

这里介绍的分析方法称为“移进—归约”方法。首先介绍规范归约的定义。

假定α是文法G的一个句子。我们称右句型序列 是α的一个规范归约，如果序列满足：

（1）a _n ＝a,a ₀ ＝S

（2）对于任何i（0＜i≤n），a _i-1 是从ai经过把句柄替换为相应产生式的左部符号而得到的。

可见，规范归约是关于α的一个最右推导的逆过程。因为规范归约也称为最左归约。在形式语言中，最右推导常被称为规范推导，由规范推导得到的句型称为规范句型。如果文法G是没有二义性的，则其规范推导的逆过程必定是规范归约。规范归约的中心问题是如何寻找或确定一个句型的句柄。

要进行移进—归约分析还是使用下推自动机，方法是尽可能从已输入的符号串或其已归约后的形式中寻找可以进行归约的句柄，只有当再找不到句柄时才读入下一个输入字符。据此，下推自动机的动作可以分为4类：

（1）把当前读入的符号移入到下推栈顶部，这一动作称为移进动作。

（2）弹出一个栈符号串（句柄），并把另一个栈符号串（通常是句柄产生式左部的非终结符）下推入栈，这一动作称为归约动作。

（3）当下推栈中只有最终归约符号S（在规范归约的情况下是文法G的开始符号），并且符号串被全部吸收，则接受符号串。

（4）当发现语法错误时，调用出错处理程序进行校正。

移进—归约的分析过程就是在从左至右将输入符号移进栈内的过程中，一旦发现栈顶出现可归约串就立即进行归约，直至接受符号串或发生语法错误。由于规范归约的最左性，因此在分析过程中，任何可归约串的出现都必定在栈顶。

正如规范归约的中心问题是如何确定一个句型的句柄一样，移进—归约分析的中心问题是如何精确定义可归约串。对可归约串的不同定义形成了不同的分析方法。

我们首先关注文法的符号之间的约束关系。设R和S是文法G的两个符号，且R、S∈V _T ∪V _N ，U、V和W是文法G的两个符号，且U、V、W∈V _N ，我们可以区分下面的4种情况：

（1）U→…RS…；

（2）U→…RV…，且 ；

（3）U→…VS…，且 ；

（4）U→…VW…，且 ， ；

要区分上面的情况，下推自动机需要每次比较栈顶符号R和当前输入符号S。在（1）中，R和S都在句柄中，此时相对于归约动作，R和S具有相同的优先级，必须同时被归约。在（2）中，S是当前句柄中的一个符号，而R不在该句柄中，这时S必须先参加归约，只有当S归约成V时，R才有可能参加归约，我们说R的优先级低于S的优先级。在（3）和（4）中，R属于某一句柄，而S不在该句柄中，我们称R的优先级高于S。只有当R是某产生式右部的尾符号时，才可能出现这种情况。在（3）和（4）中，S一定是终结符。对于上面的各种情况，我们为文法引入弱优先关系。对符合（1）和（2）的文法符号R和S，规定R＜·S，对符合（3）和（4）的文法符号R和S，规定R·＞S。根据前面的分析，当R·＞S时，R一定是句柄的尾符号，否则，R一定不是句柄的尾符号。

引入弱优先关系后，我们就可以定义弱优先文法：

设G是一个文法，如果G满足：

（1）文法G的任意两个符号之间至多只有一个弱优先关系成立；

（2）G的任何两个产生式右部各不相同；

（3）若U ₁ →xSy，U ₂ →y是G的两个产生式，则S和U ₂ 之间不存在任何弱优先关系

则称G为弱优先文法。

为了使语法分析有开始和终结，必须对下推栈的栈底符号Z ₀ 和输入字符串的终止符号“$”进行特殊处理：

这样，就可以根据文法符号及栈底符号，终止符号之间的弱优先关系构造弱优先矩阵。无论哪种语法分析方法，其工作实质均相同，就是在弱优先矩阵中标记“＜·”的元素对应的动作是移进动作；而标记“·＞”的元素所对应的动作是归约，即检查相关产生式的右部是否和栈顶符号串匹配，如匹配则用产生式的左部非终结符置换栈顶的符号串。当有可能涉及的产生式超过一条时，应遵循“最长产生式优先”的原则。对于在矩阵中开始符号S行和符号串终止符号$列中标记“·＞”的元素来说，对应的动作还需要检查栈中是否是Z ₀ S，即检查是否应接受符号串。

这里再介绍算符优先分析法。这是一种特别有利于分析表达式的方法，适用于下面形式定义的称为算符文法的文法类。

设G是一个文法，如果G中不存在形如A→ε及A→αBCβ的产生式（其中A、B、C为文法非终结符，α，β为文法符号串），即G中没有右部为ε或右部具有相邻非终结符的产生式，则称G为算符文法。

例如表达式文法：

E→E+E | E-E | E*E | E/E | E^E | (E) | -E | id

就是算符文法。

仿照弱优先关系的定义，我们为算符文法引入算符优先关系“=”、“·＞”和“＜·”：如果存在产生式U→…RS…或者U→…RVS…，则称R=S；如果存在产生式U→…RW…，且W S...或者W VS...，则R＜·S；如果存在产生式U→…WS…，且W ...R或者 _W ...R，则R·＞S。对于一个算符文法，如果任何两个终结符之间至多只存在一个优先关系，则成该文法为算法优先文法。

终结符之间的优先关系“=”可以直接从文法的产生式得出。优先关系“＜·”可以通过下面的方法求出：

（1）检查文法的各产生式，若U→S…或U→VS…，其中S是终结符，则S是U的最左终结符；

（2）若U→V…，则V的最左终结符是U的最左终结符；

（3）反复执行（2），直至得到文法的每个非终结符的最左终结符集合；

（4）检查文法中的所有形如U→…RV…的产生式，对于V的最左终结符集合中的每个元素，可得出R＜·S。

使用类似的方法，我们可以求出关系“·＞”。

运算符优先文法的语法分析可以表达成下面的算法形式：

2.2.5 语法制导翻译

1．中间代码

虽然编译程序可以直接把一个源程序翻译成目标程序，但是在许多编译系统的设计中，仍采用独立于机器的中间代码作为过渡。其优点是便于编译系统的建立和移植，并且便于进行独立于机器的代码优化。常见的中间代码表示有语法树，后缀式和三地址代码。这里介绍后缀式和三地址代码表示。

后缀表示又称为逆波兰表示，最初是用于表示表达式的计算次序。在后缀表示中，运算符紧跟在相应的运算对象后。例如表达式(A+B)*C，使用后缀表示为AB+C*。在后缀表示中，运算符既表示了对运算对象所执行的运算，也表示了这一运算之前的中间结果。因此在后缀表示中不需要使用括号。

通过使用栈，计算后缀表达式的算法如下：

（1）如果P的下一项是运算对象，则将它压入栈。

（2）如果P的下一项是二元操作符（即需要参数个数为2的运算符），则对栈顶两个对象实施运算，并且将运算的结果代替这两个运算对象而进栈。

（3）如果P的下一项是一元操作符（即需要参数个数为2的运算符），则对栈顶对象实施运算，并且将运算的结果代替这个对象而进栈。

（4）如果P的下一项是n元操作符（即需要参数个数为n的运算符），那么它的参数就是栈顶的n项，把该运算符作用于这n项，得到的结果作为操作数替代栈顶的n项。

（5）最后的结果留在栈顶。

例如，AB+C*的计算过程为：

（1）A进入堆栈；

（2）B进入堆栈；

（3）遇到二元运算符“+”，则AB出堆栈，并将A+B的结果X送入堆栈；

（4）C进入堆栈；

（5）遇到二元运算符“*”，则CX出堆栈，并将C*X的结果送入堆栈；

（6）现在堆栈顶部存放的是整个表达式的值。

把运算符扩展到n元后，后缀表达式可以表示为： ，其中θ是n运算符，运算对象的个数由运算符决定。

程序语言中的赋值语句通常形式为＜V＞ := ＜E＞，其中＜V＞是变量，而＜E＞是表达式。使用后缀形式表达时，赋值语句可以表示为＜V＞＜E＞:=。因此，表达式n:=(A+B)*C的后缀形式为nAB+C*:=。在扫描到赋值符号“:= ”时，我们需要把栈顶的值送到栈中第二个元素所指向的存储单元，然后把这两个元素从栈中弹出。

对于无条件跳转语句GOTO L的后缀表示是L BR。其中，BR是一元运算符，表示跳转到L指出的位置上继续执行。在这个基础上，我们可以设立条件跳转运算，其后缀形式为，＜E＞ L BZ，其中BZ是一个二元运算符，表示当表达式＜E＞的值为真时跳到L指出的位置继续执行，否则向下顺序执行。有了这两个运算符，我们可以把形如if b1＜b2 then a:=b+c else a:=c使用后缀表示为b1 b2 ＜ L1 BZ a c := L2 BR(L1) a b c + := (L2)。其中带括号的L1和L2表示L1和L2标号出现的位置。在实际应用中，通常L会以标明位置的偏移表示。

三地址代码，也称为带有结果的四元组表示，是另外一种较常见的中间代码。三地址代码与汇编语言代码是类似的。语句可以带有用符号命名的标号，而且存在各种控制流的语句。下面列出了三地址代码的表示方法。

（1）赋值语句：对于二元算术运算符或逻辑运算符op，其形式为x := y op z，或 (op, y, z, x)，表示op作用在y与z上的结果赋予x，对于一元算术运算符，其形式为x := op y或（op, y, , x），表示op作用于y上的结果赋予x，对于简单的复制语句，其形式为x := y或（:=, y, , x），表示y的值赋予x；

（2）无条件转移语句：其形式为GOTO L，或(BR, , ,L)，表示无条件跳转到L指出的语句继续执行；

（3）条件转移语句：其形式为if x GOTO L或(BZ, x, , L)，表示当x为逻辑真时跳转到L指出的语句继续执行。

前面使用后缀表达式表示的条件赋值语句，可以用三地址代码表示，如表2-3所示。

其中t1是编译程序生成的用于存放结果的临时变量。

2．表达式的翻译

在进行适当的改造后，下推自动机就可以进行语义分析工作。下面以自底向上进行语法分析的下推自动机为例进行说明。

考察文法G(E)：

（1）E→E+T ；

（2）E→T ；

（3）T→T*P ；

（4）T→P ；

（5）P→(E)；

（6）P→i ；

设输入的表达式为i+i，为方便说明起见，我们把两个i分别称为i1和i2。自底向上语法分析是规范推导的逆过程，而该表达式句子的规范推导为：

在进行分析时，当把i2归约成P，我们可以输出i2，当i1归约成P，我们可以输出i1，当E+T归约为E，我们则最后输出+，而完成分析。这时，就需要对文法进行改动，使其能表达使用产生式时的语义动作。这些语义动作通常附在相关的产生式下面。改动后的文法如下。

G(E)：

（1）E→E'+T

Generate(+)

（2）E→T

（3）T→T*P

Generate(*)

（4）T→P

（5）P→(E)

（6）P→i

Generate(i.Value)

其中，Generate是输出子程序，其作用是把参数放到中间代码中，i.Value是变量的值属性。在分析中，如果一个非终结符出现在句柄产生式中，那么与该非终结符有关的语义工作已经完成。

下面把翻译为三地址代码的讨论扩展到中缀表达式。为了能存放中间结果，我们定义能生成临时变量的过程newtemp。其作用为申请合适大小的存储区，将临时变量标记T和序号填入相应的单元，然后返回该存储区的首地址。此外，表达式中各参数的类型可能有不同，编译程序需要根据程序语言的类型系统作出相应的处理。为此，还需要引入量的类型属性，通过E.Type进行标记。为方便起见，我们现在只讨论有两种类型的情况，一种是整型，一种是实型。考虑两个变量相加，只有当两个变量类型都为整型时，得到的结果的类型才为整型，当两个变量类型都为实型时，结果类型也为实型，当一个变量类型为整型，另一个为实型时，编译程序首先需要把整型变量类型转换为实型，以避免数据丢失，然后进行加法运算，得到的结果的类型为实型。为此，需要引入数据类型转换的一元运算：

(FLOAT I, R)

它将整型量I转换成实型量并存放在R中。另外，原来的加法运算也需要分为实型加法和整型加法，分别记为REAL+和INTEGER+。对于上面文法G(E)的产生式（1）——E→E'+T的语义动作可以表示成：

当产生式（1）被用于归约时，应将E连同它的属性E.Value和E.Type一起下推入栈。产生式（3）的语义动作可以类似写出。产生式（2）、（4）、（5）和（6）的动作比较简单，以产生式（4）为例，其语义动作为：

赋值语句S→V:=E也可以类似推得，需要注意的是赋值符号左边变量的类型是主类型，如果右边的变量类型不符则必须根据程序语言的类型系统进行类型转换，我们这里假设类型系统只允许整型到实型的转换而不允许实型到整型的转换。上面的产生式的语义动作如下：

2.2.6 代码生成

代码生成是编译程序的最后一个阶段，它将程序的中间代码表示作为输入，并产生等价的目标代码作为输出。

类似于中间代码，目标代码也有若干种形式，绝对机器代码、可再定位机器语言和汇编语言等。为了讨论方便，我们假定代码生成程序产生用汇编语言书写的目标程序。

为此，必须对目标机器及其指令系统做出定义。这里，我们将采用具有多个通用寄存器的机器作为目标机器。目标机器是一个按字节编址的机器，以4字节为一个字，有n个通用寄存器R ₀ ，R ₁ ，R _n -1，并有形如op src, dest的两地址指令。其中op为操作码，src和dest成为源和目标，是数据域。此目标机器有如下的基本指令：

MOV （将源移到目标中）

ADD （将源加到目标中）

SUB （在目标中减去源）

源和目标域并不足以用来存放存储地址，因此一条指令的源和目标是通过将寄存器与带有地址方式的存储单元结合起来确定的。下面的contents(a)，表示由a所代表的存储单元或寄存器的内容。表2-4是各地址方式及它们的汇编语言中的形式。

寄存器分配是代码生成中的一个重要问题。寄存器是有限的资源，并且用途广泛。利用这些寄存器是否有效，直接涉及目标代码质量的好坏。

首先介绍基本块的概念。一个基本块是这样一个连续语句序列：其中控制流从第一条语句（称为入口语句）进入，从最后一条语句离开，没有中途停止或分支。下面是划分三地址程序基本块的方法：

首先，确定基本块的入口。

（1）代码序列的第一条语句是一条入口语句；

（2）任何一个条件或无条件转移语句转移到的那条语句是一条入口语句；

（3）任何紧接在一条条件或无条件转移语句后面的语句是一条入口语句。

其次，对于上述求出的每一个入口语句，其基本块是由该语句到下一条入口语句（不包括这一条入口语句），或到一条转移语句（包括转移语句），或到一个停止语句（包括停止语句）之间的语句序列组成。

为了有效利用寄存器，我们首先设立一个寄存器工作表RVALUE，表中的每个单元对应一个寄存器，用以记录运行时刻寄存器中值的情况。开始时，各寄存器的值为空。当我们向一个寄存器中存放变量时，我们只要将变量挂在对应的RVALUE单元上。这样，RVALUE中的单元值就反映了运行时刻中寄存器的值。每当需要将某变量的值取至寄存器时，代码生成程序首先检查寄存器中是否有该值，如果有，则不必生成相应的取数指令。

除了关心寄存器的值，我们还要关心寄存器的状态。一般状态会分为以下几种情况：

（1）寄存器不含有任何值，即该寄存器处于空闲状态。

（2）寄存器中的值是程序中某变量的值，但与正在处理的中间代码基本块中的后续语句无关。

（3）寄存器中的值是与正在处理的中间代码无关的中间变量的值。

（4）寄存器中的值是正在处理的中间代码基本块中后续语句需要引用的。

（5）寄存器中的值是当前要处理的中间代码的某操作数的值。

上面的状态对寄存器的分配有至关重要的意义，为此，我们设立一张寄存器状态表RSTATE，表中每个单元对应一个寄存器，它的值反映寄存器的状态。代码生成程序应该先选择状态为1的寄存器进行分配，其次是状态为2的寄存器，再次是状态为3的寄存器，以此类推。这样可以避免生成不必要的存取指令。

至此，所谓的分配寄存器，就是往某一约定工作单元j送一个该寄存器的号码，并将RVALUE中对应的单元内容送到工作单元jvalue。代码生成程序在处理每一条三地址代码前，必须根据代码分量及寄存器当时的值之间的关系修改RSTATE。在处理完后，必须及时修正RSTATE和RVALUE的值，以正确反映寄存器的值和状态。

由于机器指令位移区的位数是有限的，因此与内存有关的指令只能访问有限范围内的存储单元。要存取超过此范围的存储单元，我们需要使用前面介绍的地址方式，把特定的寄存器定义为变址寄存器。通过设定变址寄存器的值，并运用各种地址方式则可以灵活地访问各存储单元。

访问变量的过程为：按照程序语言的作用域规则，沿活动记录的访问链定位该变量所在的活动记录；把变址寄存器定位为该活动记录的相应存储工作区的首地址；使用该变量的偏移和变址寄存器的值访问该存储单元。这里的关键是要准确定位变量所在的块及其首地址。

最后，介绍一下简单的代码生成算法。代码生成程序的工作过程为：逐个地处理三地址代码，每次处理一条三地址代码前，将该三地址代码放在固定的地方，然后根据三地址代码的操作码转入相应的处理程序，直至所有的三地址代码全部处理完毕。这样，代码生成程序可以简单表达为输入三地址代码和处理三地址代码。

根据上面的预备，我们可以把将变量赋值a:=b的代码生成算法写出如下：

（1）检查RVALUE表，b的值是否在寄存器中。

（2）如果b的值不在寄存器中，则

● 即为其分配一个寄存器R ₁ ；

● 定位变量b的地址，设置变址寄存器R _d ，使其指向b所在块的首地址A，输出语句MOV Rd, A；

● 根据b的偏移D，把b挂在R ₁ 对应的RVALUE单元中，输出MOV R1, *D(Rd)。

（3）如果b的值在寄存器中，我们为描述方便也假定其为R ₁ 。

（4）定位变量a的地址，设置变址寄存器R _d ，使其指向a所在块的首地址A，输出语句MOV Rd, A。

（5）根据a的偏移D，把b挂在R1对应的RVALUE单元中，输出MOV *D(Rd), R1。

其他的语句也可以使用类似的过程生成目标代码。 jEy+gKGFxZR6BoRWjlmB9d/PzprAYJl3jVqPGh8UW91bb7B3pZCINPWoQ4eqYwCP