第三章 词法分析

第三章词法分析词法分析概述正则表达式与有穷状态自动机词法分析程序的实现词法分析程序的自动生成1第一节词法分析程序词法分析是编译过程中的第一个阶段，其任务是：从左到右逐个字符地对源程序进行扫描，产生一个个单词符号。源程序（字符串形式）中间程序（单词符号串形式）问题：1、什么是单词符号？2、单词符号该如何表示？3、如何识别出单词？21、单词符号单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、<等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。32、单词的表示形式词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）单词种别：表示单词种类，常用整数编码，它是语法分析需要的单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。4单词符号种别begin1if2then3while4do5end6identifier10digit11+13……5例如：程序段if(a>1)b=10;假定基本字、运算符、界符都是一符一种。

它所输出的单词符号是：(2,)基本字if(29,)左括号((10,’a’)标识符a(23,)大于号>(11,’1’的二进制)常数1

(30,)

右括号)(10,’b’)标识符b(17,)赋值号=(11,’10’的二进制)常数10(26,)分号；63、单词的识别在词法分析中，可以用状态转换图来识别单词。例如状态转换图是有限的有向图，结点表示状态，用圆圈表示；结点之间可以用有向边连接，有向边上可标记字符。7词法分析程序的设计对于状态图中每一个状态构造一段代码，代码功能为：（1）从输入串中读入一个字符；（2）判明读入的字符与由此状态出发的哪条弧上的标记相匹配，则转至相匹配的那条弧所指向的状态。（3）均不匹配时便失败。8第二节正则表达式正则表达式是一种适合描述符号的表示法，可由它定义正规集。正规集即为正规式所描述的串的集合。一般用L()表示。采用正则表达式的原因：词法规则简单，容易被理解；从它容易构造高效识别程序；可由正则表达式构造词法分析程序；可用于其他各种信息流的处理。91、正则表达式的定义设为字母表，则的正则表达式按照下列规则递归地定义：(1)都是上的正规式，表示为L()={}；(2)是上的正规式，表示为L()={}；(3)对于任何a，a是上的一个正规式，表示为L(a)={a}；(4)（递归定义）若r和s都是上的正规式，则(r)是上的正规式，表示集合L((r))=L(r)；rs是上的正规式，表示集合L(r|s)=L(r)∪L(s)；rs是上的正规式，表示集合L(rs)=L(r)L(s)；r*是上的正规式，表示集合L(r*)=(L(r))*。10例：令={a，b}，上的正规式和相应的正规集的例子有：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意个a的串}11

(ab)表示正规集{,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab)

表示正规集{上所有含有两个相继的a或两个相继的b组成的串}12例：若={a，b}，则字符串集合S={anban|n≠0}可以用正规式描述吗？132、程序设计语言中的正规式实例令Σ={letter,digit}，则Σ上的正规式r=letter(letter|digit)*可以用来表示标识符。令Σ={d,.,e,+,-}，则Σ上的正规式r=d*(.dd*|ε)(e(+|-|ε)dd*|ε)可以用来表示无符号浮点数。其中d表示digit,即0-9数字。143、正则表达式的等价如果正则表达式r与s表示的正则集相同，即值相等，则称它们是等价的。记为

r=s例：b{ab}={ba}b{a|b}={{a}{b}}15例：判断下述正规式之间是否等价。1）(a|b)*与a*|b*2）(ab)*与a*b*3）(a|b)*与(a*b*)*答：1）、2）不等价，3）等价164、正则表达式的性质设e、e1、e2、e3均为正则表达式，则e|=|e=ee=e=(零正则表达式)e=e=e(单位正则表达式)e1|e2=e2|e1(交换律)e1|(e2|e3)=(e1|e2)|e3e1(e2e3)=(e1e2)e3(结合律)e1(e2|e3)=e1e2|e1e3

(e1|e2)e3=e1e3|e2e3(分配律)17举例1、在字母表Σ={a,b,c}中，考虑仅包括一个b的所有串的集合。2、给出字母表Σ={a,b,c}上的一个正则表达式，((b|c)*a(b|c)*a)*(b|c)*简要描述它所生成的语言。3、试为Pascal语言的注释部分编写正则表达式。

18状态转换图确定有穷状态自动机（DFA）非确定有穷状态自动机（NFA）把NFA变为DFADFA的化简第三节有穷状态自动机（FA）19有穷自动机是依据某些输入而改变状态的机器或程序。可以用状态转换图来表示。有穷自动机是有向图这种通用结构的一个实例，在动态数据结构和高级搜索方面有许多应用。序201、状态转换图有向图，结点表示状态，用圆圈表示；结点之间可以用有向边连接，有向边上标记影响状态改变的可能输入的字符；21状态转换图举例例1：字符串必须以空格开始和结束，中间可以有0个或任意多个由a~z组成的字符串。22例2：Pascal语言中关系运算符识别的状态转换图。

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始<=>=>=**otherother23123开始letterotherletter或digitreturn(id)例3：标识符识别的状态转换图。24思考：无符号浮点数的状态转换图。252、确定的有穷状态自动机一个确定的有穷自动机（DFA）D是一个五元组D=（K，Σ，M，S，F），其中

K：有穷非空的状态集合；Σ：有穷非空的输入符号字母表；M：转换函数，是在K×Σ→K上的映像，即，如M（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；

S:S∈K是唯一的一个初态；F:FK是非空的终态集合。26从状态转换图构造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}），其中M定义为：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa例1：从下面状态图构造DFA。27例2：构造一个识别语言(a|b)*ab的有穷自动机。从正则表达式构造有穷自动机12开始a0abb输入符号ab0{0,1}{0}1{2}2状态28例设ＤＦＡＭ＝（｛０,１,２,３｝，｛ａ,ｂ｝，f，０，｛３｝）其中f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３29转换矩阵3b012aaaabbb3状态转换图易存储30

从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受(识别)。DFAM所能识别的字的全体即L(M)。字集V是正规的ifV=L（M）012aaaabbb3b31非确定有穷状态自动机一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，Σ，M，S，F）其中K：有穷非空的状态集合；Σ：有穷非空的输入字母表；M：转换函数，是在K×Σ到K的子集所组成集合的映像，M(R,T)={Q1,Q2,….Qn}S:SK是非空的初态集合；F:FK是非空的终态集合.32DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合33举例与右图所示对应的有一个NFA，N=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abaaaabSABabZbSABabZaabSABabZ34对于输入字符串babbabb，运行该NFA步骤当前状态输入的其余部分可能的后继选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ35练习：某操作系统下合法的文件名为device:name.extention其中第一部分（device:）和第三部分（.extention）可缺省，若device、name和extention都是字母串，长度不限，但至少为１，画出识别这种文件名的DFA。36第四节

由正则式构造有穷自动机A为有穷状态自动机，e为正则表达式，则存在L(A)=|e|，即正则表达式与有穷自动机之间具有等价性。任何两个有穷自动机M和M’，若它们识别的语言相同(L(M)=L(M’))，则称M和M’等价。37一、由正则表达式构造等价的NFAM1、由正则表达式R表示成如图所示的拓广转换图。XYR2、对正则式采用如下规则构造对应的NFAM。SiSjr1|r2SiSjr1r2SiSjr1r2SiSjSkr1r2SiSjr*SiSjSkεεr3、逐步运用上述3个规则不断在1、图中增加新结点进行分解，直到每条有向边上仅标识有Σ中的一个字母或ε为止，则NFAM构造完成。38举例对给定正规式b*(d|ad)(b|ab)+，构造其NFAM。εεεεbbbbbaaadd39定义1：集合I的ε-闭包：令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。状态集ε-closure（I）称为I的ε-闭包为了使得NFA确定化，我们首先给出两个定义：56432aεaaε1例：如图所示的状态图：令I={1}，求ε-closure（I）=？根据定义：ε-closure（I）={1，3}40将NFAN=（Q，，f，S，Z）确定化为DFAM的方法（子集法）（举例说明）（1）置DFAM中的状态集Q‘,Z’为集（2）给出M的初态S’=E-CLOSER({S}),并把S’置为未标记状态后加入到Q’中。（未标记状态为新状态）(3)如果Q’中存在未标记的状态T={q1,q2…qn},qi∈Q则进行如下变换：1）对于每个a∈,置J=f({q1,q2…qn},a)=f(q1,a)f(q2,a)…f(qn,a)U=E-CLOSER(I)如果U不在Q’中，则将U置为无标记的状态添加到Q’中，且把状态转移f’(T,a)=U添加到M中，如果U至少含有一个元素是N的终态，则把U置为M的终态，即把U添加到Z’中。2）对T置标记（表示T不再是新加入Q’中的状态）。（4）重复进行步骤（3）,直到Q’中不再含有未标记的状态为止。（5）重新命名Q’中的状态，最后获得等价的DFAM.41——J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合.——Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态定义2:令I是NFAM’的状态集的一个子集,a∈Σ定义:Ia=ε-closure(J)其中J=∪δ(s,a)S∈I56432aεaaε1例：令I={1}，求Ia=?Ia=ε-closure(J)=ε-closure(δ(1，a)）=ε-closure({2，4}）={2，4，6}42例：有NFAM，求DFAM’。a1234startabaccεI=ε-closure({1})={1,4}Ia=ε-closure(δ(1,a)∪δ(4,a))=ε-closure({2,3}∪φ）=ε-closure({2,3})={2,3}Ib=ε-closure(δ(1,b)∪δ(4,b))=ε-closure(φ）=φIc=ε-closure(δ(1,c)∪δ(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}…IIaIbIc

{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}初态43startIIaIbIc

{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}符号状态abc02341221________3344DFAM’状态转换矩阵将求得的状态转换矩阵重新编号01423{1,4}{2,3}{4}{2}acabbc{3,4}44结论：NFAM通过“子集法”可以确定化为DFAM″，它们接收语言的能力是等价的，通常不区分（确定化时除外），合称为有限自动机(finiteautomata)（FA）。

45“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有穷自动机是化简的

它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。3.4.5DFA的化简(最小化)46定义：(1)有穷自动机的多余状态：从该自动机的开始状态出发，任何输入串也不能到达那个状态。01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s1例:s0为初始状态画状态图可以看出s4,s6,s8为不可达状态应该消除01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s647等价状态状态s和t的等价条件是:对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）一个DFAM的状态最少化过程：将M的状态集分割成一些不相交的子集，任何不同的两子集中的状态都是可区别的，同一子集中的任何两状态都是等价的；最后，在每个子集中选一个状态作代表，消去其他状态，得到最少状态的等价DFAM’。48“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.例1:最小化5724361srartaaaaaaabbbbbbb状态集的划分将所有DFA的终态与其它状态划分成两个子集G1,G2;分别从两个子集G1,G2中寻找等价状态进行化简。49解:(一)区分终态与非终态12345663731546737414212ab567374142ab123463731546123区号区号5724361srartaaaaaaabbbbbbb将所有DFA的终态与其它状态划分成两个子集50123456637315467374142ab12431243123456637315467374142ab5区号区号12345ab5214355231155243aaaaabbbbb567374142ab123463731546123区号将区号代替状态号得:51练习：有正则式(a|b)*(aa|bb)(a|b)*，试为其构造最简的DFA。521、NFA的确定化X13ba2y6ba45aabb采用子集构造法对NFA进行确定化。53

状态Sdabd:Sd1aSd2d:Sd1bSd2Sd0={x,3,1}{3,4,1}{3,5,1}{3,4,1}{3,2,4,1,6,y}{3,5,1}{3,5,1}{3,4,1}{3,2,5,1,6,y}{3,2,4,1,6,y}{3,2,4,6,1,y}{3,5,6,1,y}{3,2,5,1,6,y}{3,4,6,1,y}{3,2,5,6,1,y}54

状态Sdabd:Sd1aSd2d:Sd1bSd2{3,5,6,1,y}{3,6,4,1,y}{3,2,6,5,1,y}{3,4,6,1,y}{3,2,6,4,1,y}{3,6,5,1,y}55{x,3,1}{3,4,1}{3,5,1}{3,2,4,1,6,y}{3,2,5,1,6,y}{3,5,6,1,y}{3,4,6,1,y}abaabababbabab560123456abaabababbabab57