第3章词法分析

1第3章词法分析

人们理解一篇文章（或一个程序）起码是在单词的级别上来思考的。同样，编译程序也是在单词的级别上来分析和翻译源程序的。

词法分析的必要性描述单词的结构比其它语法结构简单，仅用3型文法就够了；将单词识别从语法分析识别分离出来，可采用更有效的工具实现；有些语言的单词识别与前后文相关，不宜将其与语法分析合并；使编译程序各部分独立出来，有利于设计、调试和维护执行词法分析的程序称为词法分析器（扫描器）的输出是语法分析程序的输入本章讨论词法分析程序的手工构造方法和自动构造方法。2教学内容§3.1词法分析程序§3.2单词的描述工具§3.3有穷自动机§3.4正规文法和有穷自动机间的等价§3.5正规文法和有穷自动机间的转换§3.6词法分析程序的设计3学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具4§3.1词法分析程序词法分析器的功能是输入源程序，输出单词符号。通常把词法分析程序设计为语法分析程序的子程序。每当语法分析程序需要一个单词符号时，就向词法分析程序发出“取下一个单词符号”的调用命令。词法分析程序就从输入字符串中，识别出一个具有独立意义的单词符号，并传送给语法程序。字符串表示的

源程序词法分析器语法分析器字符单词符号取下一个

单词符号1.词法分析器的功能和输出形式5单词符号是一个程序语言的基本语法符号。称作token(记号)

具有独立意义的最小语法单位。语言的单词符号词法分析程序是以字符串形式的源程序作为输入，以单词符号或单词符号表示的源程序作为输出。将字符组合成记号与在一个英语句子中将字母构成单词并确定单词的含义很相像，此时的任务很像拼写。6关键字：是由程序语言定义的具有固定意义的标识符，也称保留字或基本字。如Pascal中的begin、end、if、integer等，C中的if、else、do、while，C++中的class、int、switch、break等都是保留字，它们一般不用作一般标识符。标识符：用来表示各种名字，如变量名、常量名、数组名、函数名、子程序名等。常数：程序中出现的各种类型的常量。常量的类型一般有整型、实型、布尔型、字符型等。如125、0.718、TRUE、“Hello”等。运算符：表达式中连接运算对象的符号。如+、-、*、/、<等。界符：程序中的定界符。如逗号、分号、括号、/*、*/等。程序语言的单词符号一般可分为下列五种：7词法分析程序输出单词的形式词法分析器所输出的单词符号常常表示成如下的二元式： （单词种别，单词符号的属性值）单词种别（它是语法分析需要的信息）

通常用整数编码。

一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上方便。

标识符一般统归为一种。

常数则按类型分种。

关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。

至于界符一般用一符一种的分法。8单词自身的值（单词符号的属性值，它是编译其它阶段需要的信息）

属性值是指单词符号的特性或特征，可以是标识符在符号表的入口地址、数值的二进制值等。如果是一符一种的分法，词法分析器只给出其种别编码，不给出其属性值。如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给出导出符号的属性值，以便把同一种类的单词区别开来。

标识符属性值是自身的符号串；也可是在符号表的入口地址。

常数自身值是常数的二进制数值。9【例】试给出程序段if(a>1)b=100;输出的单词符号串。假定基本字、运算符和界符都是一符一种，标识符自身的值是字符串，常数是二进制值。(2,)基本字if(29,)左括号((10,‘a’)标识符a(23,)大于号>(11,‘1’的二进制)常数1(30，)右括号)(10,‘b’)标识符b(17,)赋值号=(11,‘100’的二进制)常数100(26,)分号;10经词法分析器处理后，它将被转换为如下的单词符号序列：

(while,-)

(( ,-)

(id,指向i的符号表表项的指针)

(>=,-)

(id,指向j的符号表表项的指针)

(),-)

(id,指向i的符号表表项的指针)

(--,-)

(；,-)【例】考虑下述C++代码段：

while(i>=j)i--; 另一种表示假定基本字、运算符和界符都是一符一种，标识符自身的值是符号表的入口地址，常数是二进制值。112.词法分析器作为一个独立子程序

把词法分析器安排为一个独立的阶段的好处是，它可使整个编译程序的结构更简单、清晰和条理化。词法分析比语法分析要简单得多，可用更有效得特殊方法和工具进行处理。把词法分析器安排为独立的一遍，让它把整个源程序翻译成一连串的单词符号（二元式）存放于文件中，待语法分析程序进入工作时再对从文件输入的这些单词符号进行分析。把词法分析器安排为一个子程序，每当语法分析分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号。在后面的讨论中，我们假定词法分析器是按这种方式进行工作的。12相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokengettoken….13完全独立方式采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性源程序词法分析程序语法分析程序属性字序列….143.源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针搜索指针15识别标识符的若干约定和策略一般来说，单词的长度是有限制的在允许长度下，应按最长匹配原则进行识别有时需要超前扫描来进行单词识别。例如，FORTRAN语言中的算术条件句IF(e)=L1,L2,L3和语句函数定义句IF(x)=f(x)中的IF的识别；以及<和<=、<>等。在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。使用堆栈实现多字符回退的算法。16单词符号的构成规则

——标识符012字母(a-z)字母或数字(a-z0-9)其它*此时，超前搜索了一个字符17§3.2单词的描述工具作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具有:正规文法 正规式(RegularExpression)181.正规文法

多数程序设计语言单词的语法都能用正规文法(3型文法)描述正规文法回顾 文法的任一产生式α→β的形式都为A→aB或A→a，其中A，B∈VN

，a∈VT。 正规文法描述的是VT*上的正规集19例如:

用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为

<标识符>→l｜l<字母数字> <字母数字>→l｜d｜l<字母数字>｜d<字母数字>描述无符号整数的正规文法

<无符号整数>→d｜d<无符号整数>20为什么要引进正则表达式？对于字母表∑，我们感兴趣的是它的一些特殊字集－正规集。正规集是字母表Σ上的符合一定规则的符号串构成的集合正则表达式是一种适合描述符号的表示法，可由它定义正规集。212.正规式(regularexpression)定义（正规式和它所表示的正规集）：设字母标为1和都是上的正规式，它们所表示的正规集分别为{}和；2任何a，a是上的一个正规式，它所表示的正规集为{a}；3假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。（递归）4仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。22(e1),e1e2,e1e2,e1L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。

其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。23例令={a，b}，上的正规式和相应的正规集的例子有：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意个a的串}(ab) {,a,b,aa,ab……所有由a 和b组成的串}(ab)(aabb)(ab) {上所有含有两个相继 的a或两个相继的b组成 的串}24例={l，d}，r=l(ld)定义的正规集:{l,ll,ld,ldd,……}（标识符）例={d，.，e，+，-},则上的正规式d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。举例25例:2={A,B,0,1},则(A|B){A|B|0|1}5是2上的正则表达式(A|B){A|B|0|1}5的值，即

L((A|B){A|B|0|1}5)，是这样一个正则集，每个字符串都是以字母A或B打头，后跟以至多5个字母（A或B）或数字（0或1）(0|1)(0|1)*∑上的“数”的全体26正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：1。rs=sr “或”服从交换律2。r(st)=(rs)t “或”的可结合律3。(rs)t=r(st) “连接”的可结合律4。r(st)=rsrt (st)r=srtr 分配律5。r=r,r=r 是“连接”的恒等元素6。rr=r r=rrr…

“或”的抽取律

27程序中的单词都能用正规式来定义令l为a~z的字母，d为0~9的数字e1=l(l|d)* e1表示标识符集合e2=dd* e2表示无符号整数注(比较)： <标识符>→l｜l<字母数字><字母数字>→l｜d｜l<字母数字>｜d<字母数字>

正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。28两个正规式等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b

(ab)=(ab)293.正规文法和正规式间的转换等价性：对任意一个正规文法，存在一个定义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法30将∑上的一个正规式r转换成文法G=(VN,VT,S,P)VT=∑,首先形成产生式S→r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式规则1A→xyA→xBB→y规则2A→x*yA→xAA→y规则3A→x|yA→xA→y其中B为一新非终结符31例:将R=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a|d)*,然后变换S→aA A→(a|d)*A→(a|d)AA→εA→aAA→dA 最终有产生式：S→aA，A→ε，A→aA，

A→dA32将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式正规式规则1A→xBB→yA=xy规则2A→xA|yA=x*y规则3A→xA→yA=x|y33例：将文法G[S]转换成正规式

G：S→aA|aA→dA|d先由产生式得: S=aA|a A=d*d将A代入S中得: S=ad*d|a利用正规式变换得 S=a(d*d|ε)=ad*

说明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε=d* 所求正规式为ad*34

§3.3有穷自动机（FiniteAutomata）1.状态转换图2.确定有穷状态自动机（DFA）3.非确定有穷状态自动机（NFA）4.把NFA变为DFA5.DFA的化简351.正规文法和状态转换图正规文法定义了3型语言，常见的单词可由正规文法定义。状态转换图可用于识别3型语言；它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示36由正规文法构造状态转换图程序设计语言的单词都能用正规文法描述；例如，标识符可定义为

<标识符><标识符>字母<标识符><标识符>数字

<标识符>字母若把字母、数字视为终结符，则上述产生式为（左线性）正规文法若我们用d表示0-9间的数字，则C语言的<无符号数>的文法也是（右线性）正规文法（见P48）一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析。状态转换图由有限个结点所组成的有向图。每个结点代表在识别分析过程中扫描器所处的状态，其中含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）371)由右线性文法构造状态转换图设G=(VN,VT,P,S)是一右线性文法,并设|VN|=K,则所要构造的状态转换图共有K+1个状态(结点).用VN中的每个符号分别标记其中的K个结点,且令G的开始符S为初态结点;余下的一个结点作为终态结点,用F(VN)标记.我们用如下规则来连接这K+1个结点:(1)对于G中产生式AaB,从结点A引一有向边到结点B,并用a标记这一有向边;(2)对于G中产生式Aa,从结点A引一有向边到终态结点F,并用a标记这一有向边;(3)对于G中产生式A(若有的话),则将结点A设为终态.例如,P48中定义的无符号数的文法对应的~为(化简后):0452136dddddd.E+|-Edd38利用状态转换图识别符号串的方法对于已给的字符串w=a1a2…an,aiVT,利用~对w

识别的步骤如下:(1)从初始状态S出发,自左至右逐个扫描w的各个字符(当前为a1),此时在结点S所射出的诸矢线中,寻找标记为a1的矢线(若不存在,则表明w有语法错误),读入a1并沿矢线所指方向前进,过渡到下一状态(设为A1).(2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所射出的诸矢线中,寻找标记为ai+1的矢线(若不存在,则表明w有语法错误),读入ai+1,并进入状态Ai+1;(3)重复(2),直到w中所有字符被读完且恰好进入终态F时,宣告整个识别结束,w可被接受.显然,若我们从初态出发,分别沿一切可能的路径到达终态结点,并将中径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该~识别的语言39状态转换图与文法推导用状态转换图识别符号串w的过程，就是为w建立一个推导S*w的过程。在第一步（在初始状态S下，扫描到a1而过渡到下一状态A1），由状态转换图的构造规则可知，G中必有产生式Sa1A1;对于识别过程的后续步骤，由状态Ai识别ai+1后过渡到Ai+1恰好对应了使用产生式Aiai+1Ai+1,…,最后在状态An-1识别an后到达终态F，对应了使用产生式 Aan 进行推导：

Sa1A1a1a2A2……a1a2…an-1An-1a1a2…an40右线性文法与状态转换图设G是一右线性文法,M是相应的状态转换图,则从前面的讨论可以看出如下事实：(1)在利用M对符号串w进行识别时,M中每次状态的转换都模拟了一步直接推导,即识别方法(或称分析方法)是“”的;(2)因右线性文法只有形如AaB、Aa的产生式，所以推导的每一步所得句型只含一个非终结符，所以推导的规范的，每步所得的句型也必为规范句型；(3)对于M所识别的任一符号串x,必存在G中的一个推导S*x(即有xL(G);反之,对于L(G)中任一句子y,必存在一条从初态S到终态F的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为y412)由左线性文法构造状态转换图设G=(VN,VT,P,S)是一左线性文法,构造相应的状态转换图的方法是:首先用G的VN符标记M的结点,其中,开始符S对应的结点为终态结点.另外,再引入一个新结点R(VN)作为初态.矢线的连接规则为:(1)对于G中形如Aa

的产生式,引矢线:RA,且标记为a;(2)对于G中形如ABa

的产生式,引矢线BA,且标记为a.42由左线性文法构造状态转换图的例子已给文法G=({S,U},{0,1},{SS1|U1,UU0|0},S)RUSU00UU00SU11SS11用左线性文法构造出的状态转换图来识别文法的句子,其过程与前面右线性文法构造的状态转换图用法一样,这里不再赘述.不过,就识别的方法而言,它却属于“”分析.我们以句子00011为例,给出其识别的的步骤.见右表.步骤当前状态 余留的符号串1 R 000112 U 00113 U 0114 U 115 S 16 S (识别结束)43识别符号串与归约由构造状态转换图的方法可知,从初态R到下一状态A的转换,对应了形如Ba

的产生式,即将终结符a归约成非终结符B;类似地,从状态B转换到状态A,对应了形如ABa的产生式,即将Ba归约为A;如此下去,直到从某状态A转换到状态S(终态),对应了形如SAa的产生式,即将Aa归约为开始符S.此时归约成功,也恰好进入了终态,即状态转换图识别了(或接受)该符号串.前面识别00011的例子对应的归约过程见右图00011UUUSS44对句子ababaaa的分析步骤当前状态输入的其余部分

SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析过程(b)语法树45词法规则的描述状态转换图难于书写，非线性结构更好的方式的要求线性方式表达与状态转换图等价正规表达式[a-z][a-z|0-9]*462.有穷自动机(也称有限自动机)是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:

确定的有穷自动机

(DeterministicFiniteAutomata)

不确定的有穷自动机

(NondeterministicFiniteAutomata)47确定的有限自动机DFA1）抽象地看,状态转换图由五个部分组成:(1)有限个状态之集,记作K;(2)有限个输入符号组成的字母表,记作;(3)从K到K的转换函数

f:KK.f(p,a)=q表示若当前状态为p,且输入符号为a,则进入下一个状态为q;(4)S0K,初始(开始)状态;(5)若干个终态之集:Z(K)由上述五个要素组成的五元式M=(K,,f,S0,Z)称为一个确定的有限自动机

(DFA:DeterministicFiniteAutomata)由此可见,一DFA实际上是状态转换图的形式描述(数学定义),状态转换图是DFA的几何(图形)表示.“确定”即状态转换函数是单值函数！48DFA的接受集2）为定义DFA所接受(或识别)的符号串集合,我们先将其转换函数f的定义域拓广到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定义可知,对于x*,f^(s,x)=t

的含义是,当M从状态s出发,依次扫描完x的各个符号后将进入状态t.即只要f有定义,f^与f的效果是一致的.我们称DFAM接受(或识别)某符号串x*,用状态转换图来说,就是从初态S0出发,经一恰好标有x的路径后可达到某终态SZ

;用f^描述就是: SZ,f(S0,x)=S

M的接受集我们把一DFAM所接受的符号串的全体称为M的接受集,记为L(M),即L(M)={x|f(S0,x)Z,x*}49确定的有限自动机我们之所以把前面定义的有限自动机称为确定的FA，是因为在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地确定FA的下一状态。在转换图上看，若||=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。例如，P51图3-4所对应的DFA为M=({R,U,S},{0,1},f,R,{S})

其中，f的定义如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DFA。实际上，我们可以证明，正规文法G，DFAM，使 L(M)=L(G)，反之亦然。50从状态转换图构造有穷状态自动机例如：从下面状态图构造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 abSABabZbaa51运行DFA与识别一个字符串定义：对于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，则称符号串t可被DFAD所接受。运行一个DFA的过程：识别一个符号串是否被接受52举例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）

M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z

则：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z53正则集正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D)最小状态自动机：状态个数最少，唯一54DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。553.非确定的有限自动机若在一左线性文法中含有多个右部相同的产生式，如 AUaBUaCUaXUa,或在一右线性文法中同时含有形如 UaAUaBUaCUaX的产生式，在相应的状态转换图中，就会出现这样的结点U，它具有多条标记为同一输入符号a的矢线，如右图所示图3-8NFA的状态转换图由上图可知，在U状态下，输入符号为a时，FA的下一状态不唯一，而是在状态集{A,B,C,…,X}中任选其一。具有这种性质的FA称为非确定的FA（NFA:Nondeterministic

FA）UABCXaaaa...56非确定有限自动机的定义在形式上，NFAM同样可用五元式定义：M=(K,,f,S0,Z)，其中，K,,S0,Z的含义同DFA,转换函数f的定义为

f:K(K),即将(Si,aj)映射到K的一个子集{Sk1,…,Skm}

类似地，我们可把f的定义域拓广到K*

：(1)f^(S,)={S};(2)f^(S,aw)=f^(f(S,a),w)a,w*.再设f(S,a)=

{Sk1,…,Skm},且定义这样，我们已把f的定义域扩大到(K)*。根据类似的理由，我们将对f和f^不加区分57NFA的接受集对于x*,若集合f(S0,x)中含有Z中的元素（终态），则说明，至少存在一条从初态S0到某一终态的路径，此路径上的符号之连接恰为x，此时，我们称x为M所接受所有为M所接受的符号串之集称为NFAM的接受集（或识别集），记作L(M).即L(M)={x|f(S0,x)Z,x}例3.1

给定M=({S,A,B,C},{a,b},f,S,{C}),其状态转换图见右。由图可知M是一NFA。M识别符号串ababb的路径为S(a)A(b)B(a)A(b)B(b)C(接受)。(参见书中P60的表)SABCaa,babbaa注意，NFA识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（带回溯），这影响了FA的效率。能否提高其工作效率就是我们下一小节讨论的课题。事实上，对任一NFAM，总可构造一个DFAM’，使L(M’)=L(M)成立。这就是NFA与DFA的等价性。58DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合59举例前述文法G3.2对应的自动机NFAN=({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}abSABabZbaaaa60举例(字符串被NFA所接受)对于输入字符串babbabb，运行NFA步骤当前状态输入的其余部分可能的后继选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZabABabZbaaaaS61运行NFA运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态实质：用自底向上方法识别句子状态转换的下一状态不唯一，如何解决？62DFA和NFA的关系对于Σ*上的字符串β，如果存在一条从初态到终态的通路，且这条通路上的输入字符恰好连接成β，称为β可以此DFA、NFA识别DFA、NFA都可以识别一个字符集Σ上的字符串可以用DFA、NFA定义Σ上的字符串的集合DFA都是NFA、NFA可化为等价的DFA63构造与正规式等价的NFA方法XYααα|β12αβ12643αεε1αβ32αβ1221α*1265构造与正规式等价的NFA示例a(a|b)*XYa(a|b)*XYa1(a|b)*66XYa1(a|b)2XYa1a2bεεεε674.NFA的确定化方法初态的唯一化终态的唯一化从初态集开始，求对于每个输入符号的后继状态集合Si——新的状态对每个Si，求对于每个输入符号的后继状态集合Si+1直到不产生新的后继状态集合含有终态的状态集合为终态68举例例:为NFAN=({S,A,B,Z},{a,b},M,{S},{Z})构造DFA.

设它对应的DFAN’=(K’,{a,b},M’,[S],F’)abSABabZbaaaaK’={[S]}M([S],a)=[A]M([S],b)=[B]K’={[S],[A],[B]}M([A],a)=[Z]M([A],b)=[B]M([B],a)=[AB]M([B],b)=[Z]K’={S],[A],[B],[Z],[AB]}M([Z],a)=[AZ]M([Z],b)=φM([AB],a)=[ABZ]M([AB],b)=[BZ]K’={S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}M([AZ],a)=[AZ]M([AZ],b)=[B]M([BZ],a)=[ABZ]M([BZ],b)=[Z]M([ABZ],a)=[ABZ]M([ABZ],b)=[BZ]

69举例（续1）

输入状态ab[S][A][B][A][Z][B][B][AB][Z][Z][AZ][AB][ABZ][BZ][AZ][AZ][B][BZ][ABZ][Z][ABZ][ABZ][BZ]abSABabZbaaaa根据左边状态转换矩阵，可以得到DFAN’的状态集合（表的左列状态），即K’={[S],[A],[b],[Z],[AB],[AZ],[BZ],[ABZ]}70举例（续2）SBABABZAZBZAZbbbbbbbaaaaaaaa开始状态:[S]终止状态:[Z],[AZ],[BZ],[ABZ]

根据上面状态转换矩阵，同时可以得到N’的映像函数，根据该映像可以画出它的状态转换图（如下）。终态集合中的元素为：由新映像得到的状态、且这些状态包含原NFAN的终态集合中的状态。71NFA的确定化示例状态转换矩阵 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}XYa1a2bεεa(a|b)*72 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}

a

b{X} {1,2,Y}{} {1,2,Y}{2,Y}{2,Y}{2,Y} {2,Y}{2,Y}NFA状态转换矩阵1)(2)(3) a

b1) (2) (2) (3) (3)(3) (3) (3)等价的DFA状态转换矩阵73 a b1) (2) (2) (3) (3)(3) (3) (3)13aabab274NFA确定化的例子M=({S0,S1},{a,b},f,S0,{s1})S0S1abba|b_f_|_a____b___S0|{S0,S1}{S1}S1|{S0,S1}M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]})f’|ab.|newstate[]|[][]|[S0]|[S0S1][S1]|1[S1]|[][S0S1]|2[S0S1]|[S0S1][S0S1]|3123abb|ab75具有动作的FA若在一FA中,允许对也作状态转移,则这样的FA称为具有动作的FA(NFA).此时,有的矢线上标记为标记为的矢线对识别符号串无影响,但却改变了当前的状态.例如,右图中的FA中,从状态0到状态3存在路径:0(a)0(a)0()2(c)2(c)2()3,即M识别了aacc=aacc.~的定义

M=(K,,f,S0,Z),其中,f的定义为f:K({})(K).在~中,可以视为一个输入符号,在矩阵表示中,也有相应的列.0123abbcf也可以拓广到f’:K*(K).f’(S,x)是由这样的状态Q组成,存在从S到Q的路径,该路径上的连线标记组成的符号串恰好为x,其中,允许有有限个标记为76状态S的-闭包：-CLOSURE(S)为定义拓广的f’,我们首先引入每个状态S的-闭包的定义： -CLOSURE(S),它是从S出发经过若干标记为的矢线所能达到的全部状态之集，其归纳定义如下：(1)S-CLOSURE(s);(2)设Sj-CLOSURE(S),且SjSk,则Sk-CLOSURE(S);(3)有限地使用规则（2）所得的集合为-CLOSURE(S).例，在上页的NFA中，-CLOSURE(0)={0,1,2,3} -CLOSURE(1)={1} -CLOSURE(2)={2,3} -CLOSURE(3)={3}.进一步，-CLOSURE还可定义在-CLOSURE:(K)(K)，设QK(Q(K))，则77转换函数f的拓广利用-CLOSURE(S)，可定义f’如下：78f与f’的区别由f’的定义可知，f’(S,a)

与f(S,a)

不同，f’(S,a)是从S出发经过路径a据达的状态集（可走若干步）；而f(S,a)是从S出发经过矢线a所达状态之集（只走一步）其实，

f(S,a)-CLOSURE(f(S,a))f’(S,a)

只走一步a矢线

|多步，第一步必须走a矢线

|路径a：第一步可以是矢线例如，在前面的NFA中，f’(0,)=-CLOSURE(0)={0,1,2,3}f(0,)={1,2}f’(0,a)={0,1,2,3} f(0,a)={0}-NFA的接受集：L(M)={w|f’(S0,w)Z}79-NFA的用途：构造更复杂的FA有了-NFA，就可把识别各种不同单词的FA用矢线（并连）连接起来，组成一个单一的NFA，经确定化后可得识别所有单词的DFA，由此可设计编译程序的词法分析器。例如，某语言的单词有：1.BEGIN 2.END 3.IF 4.THEN 5.ELSE6.标识符 7.无符号整数 8.< 9.<= 10.= 11.<> 12.> 13.>=我们可容易地分别构造出识别各类单词的FA,然后将其合并为一个大FA,如书中P65图3-11所示(由于较难描绘,这里略去,请自行参阅教材)80ε闭包状态集I的ε_CLOSURE(I)如果q属于Iq属于ε_CLOSURE(I)从q出发经任意条ε弧到达的任何状态q’都属于ε_CLOSURE(I)81具有动作的NFA的确定化设已给具有动作的NFAM=(K,,f,S0,Z),构造相应的DFAM’=(K’,,f’,q0,Z’)的方法是，先令q0=[-CLOSURE(S0)],然后对每个a，令[-CLOSURE(f’(q0,a))]为新状态，如此反复，直到无新状态产生：1.令K’={[-CLOSURE(S0)]};f’=;2.对K’中尚未被标记的状态qi=[Si1,Si2,…,Sim]: (1)标记qi; (2)对于每个a,令Ta=f({Si1,Si2,…,Sim},a);qj=[-CLOSURE(Ta)]; (3)若qjK’,则令K’=K’{qj}; (4)令f’=f’{f’(qj,a)=qj};3.重复2.,直到K’中无未标记的状态;4.令Z’={qj|qjZ}(这里把qj

视为集合)82确定化具有动作的NFA的例子例3.4考虑前面引入的具有动作的NFA的例子(P63图3-10)1.q0=[0,1,2,3]==>K’;2.q0未标记,故(1)标记q0;(2)令f”(q0,a)=[-CLOSURE(f’(q0,a))]=q0; f”(q0,b)=[-CLOSURE(f’(q0,b))]=[1,3]=q1;q1==>K’; f”(q0,c)=[2,3]=q2;q2==>K’;3.此时,K’={q0,q1,a2},q1,q2arenotmarked.so,(1)markq1;(2)letf”(q1,a)=[-CLOSURE(f’(q1,a))]=; f”(q1,b)=…=q1; f”(q1,c)=…=;4.q2isnotmarked,so(1)markq2;(2)f”(q2,a)=f”(q2,b)=; f”(q2,c)=q2;K’isnotincreasedandallstatesaremarked.Z’={q0,q1,q2}q1q0q2abbcc83手工计算确定化的方法在人工进行NFA确定化时,可按下述的构造矩阵的方法实现:_____________|abc_q0:[0123]|[0123][13][23]q1:[13]|[][13][]q2:[23]|[][][23]需要说明的是,本算法也适合于不含产生式的NFA的确定化.例3.5

对于书中图3-13所示的NFA利用上述算法所得的DFA如P67图3-13所示.其中,圆圈中的数字是原NFA的状态编号,在图3-13中,q0={0,1,7,11,14,19,24,26,28,30,33,35,40}.标有“#”的状态为特殊状态,在该状态下,若遇非弧线上出现的字符,则转到状态25.845.DFA的化简状态的等价性能够识别相同的字符串划分为终态和非终态两个子集如果某个子集中的状态是可区分的，则进一步划分这个子集直到在每个子集内，各个状态都是不可区分的。同一子集内的状态合并。85DFA状态数的最小化对于一DFA来说,其状态数可能并不是最小的.原因是DFA中有些状态是“等价”的.为得到效率高的DFA,需将这些“等价”状态合并,这就是DFA的最小化.DFAM的最小化:构造等价的DFAM’其状态数达到最小.可区分状态:设s,tK,s,t由某w*所区分iff (f(s,w)Zf(t,w)Z)(f(s,w)Zf(t,w)Z)若w*,f(s,w)Zf(t,w)Z,则称s与t等价(不可区分)在一DFA中,等价状态可合并.86DFA最小化算法基本思想:将M的状态集K逐步地进行划分加细,以期将K划分为满足等价关系的等价类,使得在同一类中的状态不可区分;在不同类中的状态可区分.算法如下:1.先将状态集K划分为两个子集Z和K-Z,显然分属于这两个集合的状态是可(被)区分的.记={Z,K-Z}.2.设当前的划分中已含有m个子集:={I1,I2,…,Im},其中,属于不同子集的状态是可区分的,而属于同一子集中的状态则待区分.现对每个子集Ii={Si1,Si2,…,Sin}中的各状态Sir(SirK,1rn)进行考查,看其是否可区分.若存在a,使得Su=f(Sip,a)Ij,Sv=f(Siq,a)Ik

则由假设,Su和Sv被子某个w所区分,进一步,Sip

和Siq

可被aw

区分:f(Sip,aw)=f(Su,w)属于Z而f(Siq,aw)=f(Sv,w)不属于Z(或反之),即Siq

与Sip

可区分.将Ii细分,使其落入不同的更小的子集中.得到新划分new.

（细分Ii的方法见下页）。3.若new.不等于,则令

=new.

转2.4.对于最终的，从每个划分块中任选一状态为代表，构成K‘，S0的代表为初态。若IiZ，则Ii

的代表Z’；将引入(出)非代表的矢线引向代表.87DFA最小化的例子1.={{0,1,2,3},{4}}{0,1,2,3}a={1}未区分;{0,1,2}b={2,3},{3}b={4},所以3与0,1,2可区分;={{0,1,2},{3},{4}}2.{0,1,2}a={1},未区分;{0,2}b={2},{1}b={3},1与0,2可区分;={{0,2},{1},{3},{4}};3.{0,2}a={1},{0,2}b={2}不可区分,new=.结束.0123aaababbb定理3.2

最小状态数的DFA在同构意义下是唯一的.01324aaaaabbbbb88DFA化简的例子设有一个DFAM=(K，，f，S，Z)，其状态图如下图所示。对其进行化简。21ba03abbaab89DFA的化简示例 a b1) (2) (2) (3) (3)(3) (3) (3)划分1：{1},{2，3}{2,3}a={3}属于{2,3}{2,3}b={3}属于{2,3}状态2、3不可区分，应简化为{1,2}9013aabab21a2ab化简前的DFA化简后的DFA91练习字母表{a,b}上所有含有aa或bb的字符串组成的集合用正规式表达为(a|b)*(aa|bb)(a|b)*92(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa|bb)(a|b)*1Y(aa|bb)(a|b)*0(a|b)*1Y(a|b)*0(a|b)*2(aa|bb)931Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*0a2aa3bεεbb941Y(a|b)*0a2a3bεεb45ab951YXa2a3bεεb45ab6baεε96状态转换矩阵

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}97

a b0 1 21 3 22 1 43） 3 54） 6 45） 6 46） 3 5

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}98DFA的最小化一定可以区分的两个集合用e表示出错状态非终止状态集{0,1,2}——不认识ε终止状态集{3,4,5,6}——认识ε{0,1,2}中δ(0,a)=1,δ(1,a)=3,δ(2,a)=1{0,2}与{1}不同，可区分{0,2}中δ(0,b)=2,δ(2,b)=4{0}与{2}不同，可区分{3,4,5,6}a={3,6},{3,4,5,6}b={4,5}{3,4,5,6}内不可区分99最小化的DFA a b0 1 21 3 22 1 33 3 3 100显然DFA是NFA的特例。对于每个NFA

M，存在一个DFA

M`，使得L（M）=L（M`）。对于任何两个有穷自动机M和M`，如果

L（M）=L（M`），则称M与M`是等价的。对每个NFA

N存在着与之等价的DFA

M。与某一NFA等价的DFA不唯一。

§3.4NFA与DFA的等价性101§3.5正规文法与有穷自动机之间的转换设右线性文法G=(VN，VT，P，S)，下面介绍将其转换成有穷自动机M=(K，，f，S0，Z)，使得L(G)=L(M)的方法。令K=VNZ，Z是M中新增的终态；=VT，S0=S；f由下列方法确定：对于G的每条形如AaB的规则，在M中设转换函数f(A,a)=B；对于G的每条形如Aa的规则，在M中设转换函数f(A,a)=Z。102例对于正规文法G[S]：SaB|bBBbS|a|b，可以转换成自动机M=(K，，f，S0，Z)，其中：K={S，B，Z}，={a，b}，S0=S，Z={Z}，f为：

f(S,a)=B，f(S,b)=B，f(B,b)=S，

f(B,a)=Z，f(B,b)=Z。这是一个NFA。对应的状态图如下：SaBZbbab103有穷自动机转换成右线性文法若有限自动机是NFA则将其确定化，设确定的有穷自动机M=(K，，f，S0，Z)，则转换得到右线性文法G=(VN，VT，P，S)，其中：VN=K，VT=，S=S0，P中的规则用如下方法确定：对M中任一形如f(A,a)=B的转换函数，有规则AaBP；对M中的终态Z，则加一条规则ZP。104左线性文法转换成自动机的方法设左线性文法G=(VN，VT，P，S)，有穷自动机M=(K，，f，S0，Z)，则M中的K=VNS0，S0

是M中新增的初态；=VT，Z={S}；f由下列方法确定：对于G的每条形如ABa的规则，在M中设转换函数f(B,a)=A；对于G的每条形如Aa的规则，在M中设转换函数f(S0,a)=A。105设左线性文法G[S]：SSa|Aa|BbABa|aBAb|b，则按照上述方法构造的有穷自动机为M=(K，，f，S0，Z)，其中：K={S0，A，B，S}，={a，b}，Z={S}，f为：

f(S,a)=S，f(A,a)=S，f(B,b)=S，f(B,a)=A，

f(S0,a)=A，f(A,b)=B，f(S0,b)=B。其对应的状态图如下：baS0BSAabaab106

§3.6词法分析程序的设计主要内容：词法分析设计考虑的问题词法分析程序的流程107词法分析设计考虑的问题程序的预处理删除源程序的无用字符滤掉源程序中的注释进行宏替换实现文件包含命令和条件编译命令嵌入处理保留字（关键字）的识别与查表算法单词的识别与超前搜索108词法分析程序流程使用状态图设计词法分析程序的步骤对程序设计语言的单词按类构造相应的状态图。合并各类单词的状态图，构成一个能识别程序语言所有单词的状态转换图。具体方法：将各类单词的状态图的初态合并为唯一的初态；化简冲突和状态编号；增加出错处理终态。对状态图每一个终点编写一段相应的语义子程序。109例设一程序设计语言有下列单词组成：

关键字：int，for，if，while，cout，cin，do；标识符：<标识符><标识符>字母|<标识符>数字|字母；

无符号整数：<无符号整数><无符号整数>数字|数字；

运算符或界符：=，*，>，+，++，{，}。11010字母|数字3*2其它字母数字567101113*4其它*8其它9+数字=*+>{}其它12111词法分析程序流程图开始滤掉空格是字母?读标识符查保留字表查到否?保留字类码syYY返回是字母?取数Y整数类码sy数值NUM标识符类码

sy标识符ID是界符?界符或运算符类码sy出错处理NNYNN112词法分析程序的实现词法分析程序的构造方法词法分析程序的编写113构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。114词法分析程序实现中

要考虑的问题确定实现词法分析程序的执行方式确定属性字的结构缓冲区预处理，超前搜索,关键字的处理，符号表的实现查找效率，算法的优化实现词法错误处理115属性字词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字是符号的机内表示，有统一固定的长度116关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数117出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。118词法分析中使用的数据字符表：（字母表）列出源程序中所有可能的字符。特定符号与机内表示表：一切特定符号与相应编码。标识符表：登录一切源程序中出现的一切标识符。此表的序号作为属性字的值。常数表：登录一切源程序中出现的常数。此表的序号作为属性字的值。119使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。120201字母字母|数字其它3456数字数字其它+-78*/9101113<=>:;1617其它13=举例121词法分析程序的结构取字符子程序取符号子程序，一般有如下约定：进入子程序时，已经取到当前符号的一个字符。离开子程序时，已经取到其后继字符。查造标识符表子程序查造常量表子程序查符号机内表示对照表子程序122词法分析程序的自动生成（Lex)LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图。123图LEX及其编译系统的作用124一个LEX源程序由用“%%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为识别规则，最后一部分为用户子程序。其书写格式为：辅助定义式

%%

识别规则

%%

用户子程序125

其中，辅助定义式和用户子程序是任选的，而识别规则是必需的。如果用户子程序缺省，则第二个分隔符号“%%”可以省去；但如果无辅助定义式部分，第一个分隔符号“%%”不能省去，因为第一个分隔符号用于指示识别规则部分的开始。126下面给出一个简单语言的单词符号的LEX源程序例子，其输出单词的类别编码用整数编码表示。

AuxiliaryDefinitions /*辅助定义*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*识别规则*/1271while {return(1,null)}2do {return(2,null)}3if {return(3,null)}4else {return(4,null)}5switch {return(5,null)}6{ {return(6,null)}7} {return(7,null)}8( {return(8,null)}9)