编译原理第3章

第三章词法分析这一章将讨论词法分析程序的构造。词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。前一部分讨论手工构造方法，后一部分讨论自动构造方法。3.1对于词法分析器的要求

词法分析器的功能和输出形式词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种。(1)关键字（保留字或基本字）(2)标识符(3)常数（整型、实型、布尔型、文字型等）(4)运算符。(5)界符(逗号、分号、括号、／*，*／等)。词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）考虑下述c＋＋代码段：while（i＞=j）i--;经词法分析器处理后，它将被转换为如下的单词符号序列：＜while，-＞＜（，-＞＜id，指向i的符号表项的指针＞＜＞＝，-＞＜id,指向i的符号表项的指针＞＜），-＞＜id，指向i的符号表项的指针>＜--，-＞＜；，-＞词法分析器作为一个独立子程序可使整个编译程序的结构更简沽、清晰和条理化。也可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输人串中识别出一个单词符号，把它交给语法分析器。3.2词法分析器的设计一、设计第一步：输入、预处理词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。设想构造一个预处理子程序，他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。设计第二步：二、单词符号的识别：超前搜索

分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。起点指示器搜索指示器超前扫描关健字的识别：（如FORTRAN语言)1D099K＝1，102IF（5．EQ．M）I=103D099K＝1．104IF(5)＝55这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以某基本字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。◆从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。※语句1、3的区别在于等号之后的第一个界符：一个为逗号，另个为句末符。※语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。

★为了识别1、2句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。对于1、3来说，尽管都以‘D’和‘O’两个字母开头，但不能一见‘DO’就认定是DO语句。我们们必须超前搜索，跳过所有的字母和数字，看看是否有等号。如果有，再向前搜索。若下一个界符是逗号，则可以肯定DO应为关键字。否则，DO不构成关键字，它只是用户标识符的头两个字母。所以为了区别1和3，我们必须超前扫描到等号后的第一个界符处。★对于2和4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母，则得逻辑IF。若此字符为数字，则得算术IF。否则，应认为是用户自定义标识符IF.

标识符的识别、常数的识别及算符和界符的识别相类似可以参考课本P40,P41这里就不再多述。标识符的识别常数的识别算符和界符的识别

三、状态转换图

转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。一个状态转换图可用于识别（或接受）一定的字符串。123XY012字母字母或数字其它012数字数字其它06123457.数字数字数字数字数字数字数字E或DE或D+或-其它*其它.四、状态转换图的实现(1)ch

字符变量，存放最新读进的源程序字符。(2)strToken

字符数组，存放构成单词符号的字符串。(3)GetChar

子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。(4)GetBC

子程序讨程．检杳ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符(5)Concat

子程序过程，将ch中的字符连接到strToken之后。(6)IsLetter和IsDigit

布尔函数过程，它们分别判断ch中的字符是否为字母和数字。(7)Reserve

整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）。(8)Retract

子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。(9)InsertId

整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。(10）InsertConst

整型函数过程，将strToken中的常数插入常数表，返回常数表指针。对于不含回路的分叉结点来说，可让它对应一个switch语句或一组if...then...else语句。例如，下图状态结点i所对应的程序段可表示为：

GetChar(）；

if（IsLetter（））{…状态J的对应程序段…；｝

elseif（IsDigit（））{…状态k的对应程序段…；｝

elseif（ch＝‘／’）{…状态I的对应程序段…；｝

else{…错误处理…；｝ijkl字母数字/对于含回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段。例如，下图的状态结点i所对应的程序段可为：

CetChar(）；

while（IsLetter(）orIsDigit(））

CetChar（）；

…状态j的对应程序段…ij字母或数字其它终态结点一般对应一个形如return（code，value）的语句。其中，code为单词种别编码；value或是单词符号的属性值，或无定义。3.3正规表达式与有限自动机一、正规式与正规集

正规式和正规集的递归定义：（1）ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ(2)任何a€Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；(3)假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(U·V)和(U)*也都是正规式，它们所表示的正规集分别为L(U)UL(V),L(U)L（V）（连接积）和（L（U））*（闭包）。仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式。仅由这些正规式所表示的字集才是Σ上的正规集。正规式的运算符，’|”读为“或”，“·”读为“连接”，“*”读为“闭包”（即，任意有限次的自重复连接）。规定算符的优先顺序为：先“*”，，次“·”．最后”|”。连接符”·”一般可省略不写。例3.1:令Σ=｛a,b}，下面是Σ上的正规式和相应的正规集：正规式正规集

ba*Σ上所有以b为首后跟任意多个a的字。

a(a|b)*Σ上所有以a为首的字。

(a|b)*（aa|bb)（a|b)*Σ上所有含有两个相继的a或两个相继的b的字。例3.2令Σ={A，B，0，1｝，则正规式正规集

(A|B）（A|B|0|1)*Σ上的“标识符”的全体

(0|1)(0|1)*Σ上的“数”的全体。若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为

U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。令U、V和W均为正规式，显而易见，下列关系普遍成立：（1）U|V=V|U（交换律）；

(2）U|（V|W）=（U|V）|W（结合律）

(3)U（VW）=（UV）W（结合律）；

(4）U（V|W）＝UV|UW（分配律）

(V|W)U＝VU|WU；

(5）εU=Uε＝U二、确定有限自动机（DFA)1、定义：

一个确定有限自动机（DFA）M是一个五元式

M＝（S，Σ,δ,s0，F)其中（1)S是一个有限集，它的每个元素称为一个状态。

(2)Σ是一个有穷字母表，它的每个元素称为一个输入字符。

(3)δ是一个从SxΣ至S的单值部分映射。δ(s，a)＝s’意味着：当现行状态为s、输入字符为a时，将转换到下一状态s’。我们称s’为s的一个后继状态。

(4)s0∈S,是唯一的初态。

(5)F⊆S,是一个终态集（可空）.2、状态转换矩阵：显然，DFA可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元表示δ(s,a）的值，该矩阵称为状态转换矩阵。例如，有DFAM=({0,1,2,3}，{a,b}，δ，0，{3})其中δ为δ(0,a)＝1δ(0,b)＝2δ(1,a)＝3δ(1,b)=2δ(2,a)＝lδ(2,b）=3δ(3,a)＝3δ(3,b）=3它所对应的状态转换矩阵如表所列状态ab0121322133333、一个DFA也可表示成一张（确定的）状态转换图。假定DFAM

含有m个状态n个输入字符，那末，这张图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用上的一个不同字符作标记，整张图含有唯一的初态和若干个（可以是0个）终态结点。1203aaabbba/b对于∑*中的任何字α，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α，则称α可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字ε可为M所识别（或接受）。DFAM所能识别的字的全体记为L(M）。如果一个DFAM的输入字母表为∑，则我们也称M是∑上的一个DFA。可以证明：∑上的一个字集V⊆∑*是正规的，当且仅当存在∑上的DFAM,使得V＝L(M)。[例]有DFAM=({0,1,2,3},{a,b},,0,{3})其中：（0,a)=1;（0,b)=2

（1,a)=3;（1,b)=2

（2,a)=1;（2,b)=3

（3,a)=3;（3,b)=3问：有几个状态？几个输入字符？并画出其转换图。L(M)=?解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如右L(M)为在上所有含相继两个a或相继两个b的字。三、非确定有限自动机（NFA)一个非确定有限自动机（NFA)M是一个五元式

M＝（S，∑，δ，S0,F)

其中（1）S同3.3.2的1；

(2）∑同3．3．2的2；

(3)δ是一个从S×∑*到S的子集的映照，即δ:S×∑*→2的s次方

(4)S0⊆S，是一个非空初态集；

(5)F⊆S，是一个终态集（可空）。一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用∑*中的一个字（不一定要不同的字而且可以是空字ε）作标记（称为输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点。某些结点既可以是初态结点也可以是终态结点。对于∑*中的任何一个字α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为ε的弧）等于α,则称α可为NFAM所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的ε通路，那么，空字ε可为M所接受。显然DFA式NFA的特例。对于每个NFAM存在一个DFAM”，使L(M)=L(M”)。其证明如下（略）（这个证明需要掌握）在这个证明中我想特别强调的是课本P49页下边提到的对M的状态转换图进一步施行图3。7所示的替换，其中k是新引入的状态。

书中的这个图3。7同时也是从正规式画有限自动机状态转换图的重要方法。对于正规式中的连接可按1式画其转换图，对于或可用2式，对于闭包可用3式将正规式转换为状态转换图灵活使用这些规则非常重要的。如：正规式：R=(a*b)*ba(a|b)*

可以画为：

例如，下图就是一个NFA,这个NFA所能识别的也是所有含有相继两个a或相继两个b的字5XYaabε62431ababbεεε四、DFA与NFA的等价显然,DFA是NFA的特例。但是，对于每个NFAM存在一个DFAM'',使L(M)=L(M''）。证明过程如下：(1)假定NFAM＝＜S,∑,δ,s0,F＞，对M的状态转换图进行以下改造：

①引进新的初态结点X和终态结点Y，

X，Y∈S,从X到s0中任意状态结点连一条ε箭弧，从F中任意状态结点连一条ε箭弧到Y。②对M的状态转换图进一步施行图3.7所示的替换．其中k是新引入的状态。重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为ε，或为∑中的单个字母。将最终得到的NFA记为M'，

显然L(M'）=L(M）。ijABijA/BijA*ikjABijABikiAεε(2)将M'进一步变换为DFA，方法如下：①假定I是M'的状态集的子集，定义I的ε闭包=CLOSURE(I)为:(a)若q∈I,则q∈CLOSURE(I)；(b)若q∈I,那么从q出发经任意条ε弧而能到达的任何状态q‘都属于ε_CLOSURE（I)；②假定I是M'的状态集的子集，a∈∑，

定义Ia＝ε_CLOSURE(J)

其中，J是那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。③假定∑＝｛a1，…，ak｝。我们构造一张表，此表的每一行含有k十1列。置该表的首行首列为ε_CLOSURE(X)。一般而言，如果某一行的第一列的状态子集已经确定，例如记为I，那么，置该行的i十1列为Iai（i＝1，…，k)。然后，检查该行上的所有状态子集，看它们是否已在表的第一列中出现．将未曾出现者填入到后面空行的第一列。重复上述过程，直至出现在第i＋1列（i＝1，....k)上的所有状态子集均已在第一列上出现。因为M'的状态子集的个数是有限的，所以上述过程必定在有限步内终止。例3.3：正规式(a|b)*(aa|bb)(a|b)*对应的NFA5XYaabε62431ababbεεε子集法构造出的状态转换矩阵IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}对上表所有状态子集重新命名．得到以下状态转换矩阵sab012132215334465565634相对应的状态转换图如图1052634aaaaaabbbbbba五、正规文法与有限自动机的等价性对于正规文法G和有限自动机M,如果L(G)=L(M),则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：

(1)对每一个右线性正规文法G或左线性正规文法M，都存在一个有限自动机(FA)M，使得L(M）=L(G）。

(2）对每一个FAM,都存在一个右线性文法Gr和左线性正规文法Gl，使得L(M)=L(Gr)=L(Gl)六、正规式与有限自动机的等价性（1)对任何FAM,都存在一个正规式r,使得L(r)=L(M）。

(2）对任何正规式r,都存在一个FAM,使得L(M)=L(r)。说明正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。由正规式构造等价的NFAM

由正规式构造等价的NFAM的方法：

(1)将正规式R表示为拓广转换图。X2YR

(2)采用下述三条转换规则构造NFAM。

sisjr1|r2*1.r1r2ee2.3.sjsjsisir1r2sisisir1r1r1r2sjsjsjsksk对正规式R,先将其表示为拓广转换图,其中X为初态,Y为终态,再逐步运用三条转换规则不断加入新结点,直至每条有向边上仅标识Σ的一个字母或ε为止,至此NFAM构造完成。例2.6构造b*(d|ad)(b|ab)+对应的NFA。解:首先用R+=RR*把正规式改造为

b*(d|ad)(b|ab)(b|ab)*

然后构造其NFAM，如下图所示：b*(d|ad)(b|ab)(b|ab)*XY(b|ab)*d|adb*b|ababadεεbεεdb|abb41235εεbX41d26εεbb3578adbaabXX132YYY确定有限自动机的化简

NFA确定化所得的DFA可能含有多余的状态,需化简。所谓DFAM的化简：是指寻找一个状态数比M少的DFAM'，使得L(M)=L(M')。

化简后的DFAM'满足下述条件：

(1)无多余状态；

(2)状态集中无相互等价的状态。假定s和t是M的两个不同状态，我们称s和t是等价的：如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。如果DFAM的两个状态s和t不等价，则称这两个状态是可区别的。例如，终态与非终态是可区别的。因为，终态能读出空字ε，非终态则不能读出空字ε。一个DFAM的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。DFAM的化简方法：(1)首先将DFAM的状态集S中的终态与非终态分开,形成两个子集,得到基本划分。(2)对当前已划分出的I(1),I(2),…,I(m)子集,看每个I是否能进一步划分。对某个I(i)={s1,s2,…,sk},若存在输入字符a∈Σ使得Ia(i)不全包含在当前划分的某个子集I(j)中,即跨越两个子集,则将I(i)一分为二。(3)重复(2),直到每个子集均不能再分。

不能再分是指子集要么仅有一个状态，要么有多个状态但这些状态不可区分。如何进行子集的划分呢？

假定当前子集I(i)={s1,s2,…},其中s1和s2经过有向边a分别到达状态t1和t2,而t1和t2分属于当前已划出的两个不同子集I(j)和I(k),则应将I(i)分为两部分：

I(i1)={s|s∈I(i)且s经有向边a到达t1}I(i2)=I(i)−I(i1)

由于t1和t2可区分，因此I(i1)中的状态与I(i2)中的状态可区分。划分结束后,子集个数不再增加,从每个子集中选一个状态形成新的DFA。

例如，I(i)={s1,s2,s3}

若挑选s1作为I(i)的代表，则原来指向s2和s3的有向边均改为指向新DFA中的s1。若I(i)中含原来的初态，则s1为新初态；

若I(i)中含原来的终态，则s1为新终态。例3．6图3．8所示的DFAM的化简过程是：首先，把M的状态分成两组：终态组{3,4,5，6}，非终态组{0,1,2｝。其次，考察{3,4,5,6}，由于{3,4,5,6}a⊂{3,4,5,6}和{3,4,5,6}b⊂{3,4,5,6}，所以，它不能再分划。再考察{0,1,2}，由于{0,1,2}a=｛1，3}．它既不包含在{3,4,5,6}之中也不包含在{0,1,2}之中，因此，应把{0,1,2｝一分为二。由于状态1经a弧到达状态3，而状态0,2经a弧都到达状态1，因此，应把1分出来，形成{1｝、{0,2｝。现在，整个分划中含有三组：｛3,4,5,6}、{1｝和{0,2}.由于{0,2}b={2,5}未包含在上述三组中的任一组之中，故{0,2}也应一分为二：{0}，{2}.化简下图,使其最小化CDBAEFSbaaaaabbbbbabFa∏0:

{S,A,B}

{C,D,E,F}CDBAEFSbaaaaaabbbbbba∏1:

∏2:b{S},{B}a{A}，{S,B}{S,A,B}DBASaaabbbba3.4词法分析器的自动产生--LEX

由于不同高级语言中单词的结构大致相同,基本上都可用一组正规式描述,因而希望构造一自动生成系统:只要给出某高级语言单词的一组正规式及识别各类单词时应采取的语义动作,该系统便可自动产生该语言的词法分析程序。

LEX源程序LEX编译系统词法分析程序L输入串词法分析程序L单词符号串

LEX是美国Bell实验室研制的一个词法分析程序的自动生成工具。对任一高级程序语言，用户必须用正规式描述该语言的各个词法类(LEX的源程序)，LEX就可自动生成该语言的词法分析程序。LEX及其编译系统作用如下:

LEX所产生的目标程序L（词法分析器）工作原理：书59页

LEX可用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具(如YACC)结合起来使用，用以生成一个编译程序的扫描器和语法分析器。[例3.1]写能被5整除的十进制整数的文法及正则表达式。[例3.2]写一个文法，使其语言是奇数集，且每个奇数不以0开头。[例3.3]写出能被3整除十进制整数的文法和正则表达式：[例3.4]请构造与正则式R=(a*b)*ba(a|b)*等价的状态最少的DFA（确定有限自动机）例题与习题解答[例3.1]解：能被5整除的文法：

G[Z]:Z→(+|-

)A(0|5)

A→0|1|2|3|4|5|6|7|8|9|AA如果要求：除零以外不以0开头，责文法为：

G[Z]:Z→(+|-)A(0|5)A→AB|CB→0|C|BBC→0|1|2|3|4|5|6|7|8|9正则表达式：G[Z]:Z=(+|-)A*(0|5)A∈(0,1,2,3,4,5,6,7,8,9)

[例3.2]解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

[例3.3]解：能被3整除的文法：

G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P,)其中P为：S->(0|3|6|9)S|εS->(1|4|7)A|(2|5|8)BA->(0|3|6|9)A|(1|4|7)B|(2|5|8)SB->(0|3|6|9)B|(2|5|8)A|(1|4|7)S正则表达式：

Z=a*|(bc)*|(cb)*|(a|cibi)*|(ciabi)*(i>=1)a∈(0,3,6,9)b∈(1,4,7)c∈(2,5,8)

[例3.4]解：（1）首先构造转换系统图：（2）由系统转换图构造DFA（NFA确定化）

设初态为[S,A,B,G,F]

NFA确定化为DFA的过程：

IIa

Ib(1)[S,A,B,G,F](2)[G,F](3)[A,B,C,G,F](2)[G,F](2)[G,F](4)[A,B,G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](3)[A,B,C,G,F](4)[A,B,G,F](2)[G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](6)[G,F,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](7)[A,B,E,Z,G,F](6)[G,F,E,Z](8)[A,B,C,E,Z,G,F](8)[A,B,C,E,Z,G,F](5)[D,F,G,E,Z](8)[A,B,C,E,Z,G,F]

DFA这状态图如下：

确定有限自动机图如下：（3）将DFA最小化：先将终态和非终态分成两个集:K1={1,2,3,4},K2={5,6,7,8}对于K1中的3态输入a则进入K2集，而1，2，4态输入a仍然在K1中，故K1可一分为二K11={1,2,4}和K12={3};考察K11对于1，4态输入b到达3态而2态输入b到达4态。故K11可一分为二K111={1,4};K112={2}最后考察K2输入a或b都到达K2集。则DFA化简为{1，4}，{2}，{3}，{5，6，7，8}四个子集。其状态图如下：[例3.5]：已知有限自动机如图(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的有限自动机DFA.

[例3.5]

解：（1）L={W|W{0,1