编译原理第3章：词法分析

第三章词法分析3.1词法分析概述3.2词法分析程序的设计3.3正规式与有限自动机3.4词法分析程序的实现3.5词法分析器的自动生成22023/12/93.1词法分析概述一、词法分析程序的任务二、词法分析程序的功能三、词法分析程序的安排四、词法分析程序的实现方式五、词法分析程序的输出形式32023/12/9词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。输入：源程序字符串输出：等价的属性字序列（内部表示形式）3.1词法分析概述42023/12/9一、词法分析程序的任务从左至右逐个字符地扫描源程序，产生一个个单词符号。把作为字符的源程序改造为单词符号串组成的中间程序，执行词法分析任务的程序称为词法分析器或称扫描器。3.1词法分析概述52023/12/9二、词法分析程序的功能词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）；把单词变换成长度统一的且为定长的属性字；其他功能：滤掉空格，跳过注释、换行符某些预加工处理3.1词法分析概述62023/12/9三、词法分析程序的安排常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。1、作为独立的一遍：语法分析前进行词法分析，把单词符号串形成中间文件存贮。3.1词法分析概述72023/12/9三、词法分析程序的安排2、作为被语法分析器词用的子程序：

3.1词法分析概述82023/12/9相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。四、词法分析程序的实现方式3.1词法分析概述92023/12/9相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokengettoken….四、词法分析程序的实现方式3.1词法分析概述102023/12/9完全独立方式采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性源程序词法分析程序语法分析程序属性字序列….四、词法分析程序的实现方式3.1词法分析概述112023/12/9单词--是程序语言的基本语法符号。如：基本字、标识符、常数、运算符、界符等。词法分析器中单词的输出形式：（单词类别、单词内部码值）五、词法分析程序的输出形式3.1词法分析概述122023/12/9词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）单词种别：表示单词种类，常用整数编码，它是语法分析需要的单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。五、词法分析程序的输出形式3.1词法分析概述132023/12/9语言的单词符号单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、<等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。五、词法分析程序的输出形式3.1词法分析概述142023/12/9例：若分类表为：试分析输入串：IFa1>0 THENb1:=c1*d1ELSEb1:=5

经词法分析后的输出。五、词法分析程序的输出形式3.1词法分析概述152023/12/9解：输出的单词串为：五、词法分析程序的输出形式3.1词法分析概述162023/12/9一、状态转换图状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。

SIE字母数字字母状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态3.2词法分析程序的设计例1：172023/12/9一、状态转换图例2：例3：182023/12/9方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。例1：二、状态转换图的实现PROCEDUREProc0;Getchar;casecharof‘A’…‘Z’:proc1;‘0’…‘9’:proc2;otherwiseerror;endofcase;192023/12/9为了描述方便，引入一些标准过程（函数）与变量:1.全程字符变量Char：存放最新读入的源程序字符；2.字符串TOKEN：存放构成单词符号的字符串；3.过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移；4.过程GETNBC：反复调用GETChar，直接读入的Char<>’’为止；5.过程CONCAT：把Char中字符连到TOKEN末尾去；6.函数Letter/digit：判别Char中是否为字母/数字；7.过程Return(c,val);8.过程Retract：搜索器指针回拔一个字符。

二、状态转换图的实现202023/12/9例2：PROCEDUREPro0;BEGINGetchar;IFcharIN[‘A’..‘Z’]thenpro1elseerror;END;Procedurepro1;begingetchar;whilecharIN[‘A’..‘Z’,‘o’..‘9’]DObeginconcat;getchar;End;pro2;End;procedurepro2;beginretract;return(101,TOKEN);end;212023/12/9一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、NFA和DFA的转换五、正规式和有限自动机的等价性六、DFA的化简3.3正规式与有限自动机222023/12/9一、基本概念1.字母表Σ：元素的非空有限集合。如Σ={‘A’,‘B’,‘O’}2.字符：字母表Σ的一个元素称为一个字符（符号）3.Σ上的字：

Σ上字符的有穷序列；例：Σ={a,b,c}4.空字ε：不含任何字符的字5.字的长度：|α|6.Σ上字的全体：Σ*7.字的连接：字α与字β的连接记为αβ3.3正规式与有限自动机232023/12/9一、基本概念8.字的方幂：字α的n次连接称为α的n次方幂,记为,特别地=ε9.字的集合A与B的乘积：记作,其中10.Σ*子集的方幂：

Aº={ε},A1=A,…,11.Σ*子集的正则闭包：12.Σ*子集的闭包：3.3正规式与有限自动机242023/12/9正规式与正规集正规集是字母表Σ上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。1.ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ2.任何a∈Σ,a是Σ上的正规式，它所表示的正规式为{a}3.假定u和v是正规式，它们所代表的正规集分别是L(u)和L(v)，则u|v,uv,u*都是Σ上的正规式，它们所表示的正规集分别为L(u)∪L(v),L(u)L(v),L(u)*仅由有限次使用上述三步而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集252023/12/9正规式与正规集优先级递增：

|(或)，·（连接），*,（正规式） ∪,∩,*’,（正规集）例1.Σ={0,1}，则正规式有0,1,ε,φ,1*,|0|,…，正规集有{0},{1},{ε},φ,{1}*,…若两个正规式所表示的正规集相同，则认为二者等价262023/12/9正规式的性质：1．交换律：U|V=V|U

证：L(u|v)=L(u)∪L(v)=L(v)∪L(u)=L(v|u)

因此，u|v=v|u 2．结合律：(u|v)|w=u|(v|w),(uv)w=u(vw)3．分配律：u(v|w)=uv|uw,(u|v)w=uw|vw4． εu=uε=u

证：L(εu)=L(ε)L(u)=L(u)0L(u)=L(u)

272023/12/9二、确定型有穷状态自动机一个确定的有穷自动机（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∈K是唯一的一个初态；

F

K是非空的终态集合。282023/12/9例1．DFAM=({0,1,2},{a,b},δ,0,{2})，其中δ(s,a)=S,δ(s,b)=2,s=0,1,2注：一个DFA可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素M[s,a]的值为δ(s,a)。例2．二、确定型有穷状态自动机292023/12/9一个DFAM也可用一张状态转换图表示，DFA的每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若δ(s,a)=S’，则从状态s画一条箭弧到S’，弧上标记为a。对Σ*中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字等于α，则称α可为DFAM所识别，或称DFAM可读出（或接受、识别）字α。DFAM识别的字的全体记为L(M)。二、确定型有穷状态自动机302023/12/9如果一个DFAM的输入字母表为∑，则我们也称M是∑上的一个DFA。可以证明：∑上的一个子集是正规的，当且仅当存在∑上的DFAM，使得V=L（M）。DFA的确定性表现在映射δ：S×Σ→S是一个单值函数。也就是说，对任何状态s∈S和输入符号a∈Σ，δ(s,a)唯一地确定了下一状态。特别地，若DFAM的初态同时又是终态，改DFAM可识别空字ε。显然，若DFAM中字母表Σ含n个字母，则任何一个状态顶多只有n条发出弧。

二、确定型有穷状态自动机312023/12/9从状态转换图构造有穷状态自动机例如：从下面状态图构造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 abSABabZbaa322023/12/9运行DFA与识别一个字符串扩充的映像M定义：

M(R,ε)=RM(R,Tt)=M(M(R,T),t)，其中t∈Σ*，

T∈Σ以上两个式子的含义是什么？定义：对于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，则称符号串t可被DFAD所接受。运行一个DFA的过程：识别一个符号串是否被接受332023/12/9举例如前例：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)=Z342023/12/9正则集正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D)最小状态自动机：状态个数最少，唯一如何减少自动机的状态数而不改变自动机所接受的语言呢？352023/12/9如何在计算机内表示映像？映像M：含义？映像在计算机内的表示法：矩阵表示法表结构表示法362023/12/9DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。372023/12/9引入M(R,T)是K×Σ到K的单值函数，即唯一确定下一状态如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b三、非确定有穷状态自动机382023/12/9一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，Σ，M，S，F）其中K：有穷非空的状态集合；Σ：有穷非空的输入字母表；M：转换函数，是在K×Σ到K的子集所组成集合的映像，M(R,T)={Q1,Q2,….Qn}S

K是非空的初态集合；F

K是非空的终态集合.三、非确定有穷状态自动机392023/12/9DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合402023/12/9举例前述文法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}abSABabZbaaaa412023/12/9扩充映像定义：

M(R,ε)={R}R为任意的状态

M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)

其中t∈Σ*，T∈Σ，M(R,T)={Q1,Q2,….Qn}M(R,Tt)=M({Q1,Q2,…,Qn},t)=∪M(Qi,t)422023/12/9举例(字符串被NFA所接受)对于输入字符串babbabb，运行G3.2的NFA步骤当前状态输入的其余部分可能的后继选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ432023/12/91．Σ上NFAM所能识别的字的全体是Σ上的一个正规集证明：设转换图中每条弧上可用一个正规式作标记，让NFAM的转换图中加进两节点X和Y，形成新的NFAM’，从X画ε弧指向原NFAM的所有初态，从原NFAM的所有终态画ε弧指向Y，显然L(M)=L(M’)

然后，对NFAM’消结，直至只剩下X、Y两个结点为止，符上标记为一正规式。所以，NFAM’识别的为一正规式；NFAM识别的是一正规集。

五、正规式和有限自动机的等价性X442023/12/9消结规则为五、正规式和有限自动机的等价性452023/12/9例1.消结点⑤五、正规式和有限自动机的等价性例2.消结点①462023/12/92．对于Σ上的每个正规集V，存在一个Σ上的DFAM，使得V=L(M)。证明：第一步，用替代办法构造一个NFAM’，使V=L(M’)，因为正规集V可用正规式u来描述，而u由一系列单个字符连接而成，故可用下述方法分解之：五、正规式和有限自动机的等价性SZe1e2SZe1e2SZe1|e2SZ{e}SZ

SZe1e2e472023/12/9具体方法：构造如下转换图：逐步分解，便可得到一个NFAM’，有L(u)=V=L(M’)。例1．第二步，把NFAM’确定化为DFAM，得证。五、正规式和有限自动机的等价性482023/12/9举例例：正则表达式(A|B){A|B|0|1}的转换系统的构造过程如下：SZ(A|B){A|B|0|1}SZ(A|B){A|B|0|1}SZAB

A|B|0|1SZAB

10AB492023/12/9概念1.假设I是NFAM’的状态集的一个子集，我们定义ε-CLOSURE(I)为（I的ε-闭包）。（1）若S∈I，则S∈ε-CLOSURE(I)（2）若S∈I，则从s出发经过任意条ε弧而达到的状态s’，有s’∈ε-CLOSURE(I)例1.五、正规式和有限自动机的等价性若I={1,3}，则ε-CLOSURE(I)={1,3,2,8}502023/12/9概念2.假定I是M’的状态子集，a是Σ中的字符，定义Ia=ε-CLOSURE(J),其中J是I中任意状态出发（跳过前面任意多条ε弧），经过一条a弧而能达到的状态结的全体。例2．同例1DFA，Ia={5,6,2}利用概念1和概念2，便可把NFA确定化。五、正规式和有限自动机的等价性512023/12/9五、正规式和有限自动机的等价性令，构造一张如下的表，此表第0列为状态子集I，第1至m列分别为状态子集，设第一行第0列为ε-CLOSURE(X),，其中X为NFAM’的初态，求出第一个的，如果某个Iai(i=1,…,m)未曾在第0列中列出，则把Iai补入状态子集集合I中，即列于第0列新的一行。重复上述各步，直至所有行的Iai(i=1,…,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。（因为S是有限状态集，所以S中状态的组合数也是有限的）

522023/12/9显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集看成一个状态，而状态转换表唯一地刻划了一个DFAM，其初态为该表的第1行第0列，含有原NFAM’终态的子集为新的终态。（证毕）推论：一个子集是正规的，当且仅当它可由一个DFA（或NFA）所识别。五、正规式和有限自动机的等价性532023/12/9例：设计一个DFAM，它识别二进制偶数（不以0开头的无符号数）解：1． 写出正规式1（1|0）*02． 画出NFAM’

细化为：3.确定化为DFAM五、正规式和有限自动机的等价性542023/12/9五、正规式和有限自动机的等价性或：552023/12/9字符串W把状态P和状态Q区别开：等价状态：无法区别开的两个状态基本思想：把状态集划分成互不相交的子集，使子集中的状态是等价的化简DFA的算法步骤：划分状态集合并状态:取每组状态中的代表状态，删去其他等价状态若有死状态或不可达状态，则把它们删去。死状态：无法达到终止状态的非终止状态不可达状态：不能从开始状态达到它的那些状态六、DFA的化简562023/12/9举例划分状态集为{4}和{0,1,2,3}对于{0,1,2,3}和输入字符a和b:M(0,a)={1}M(1,a)={1}M(2,a)={1}M(3,a)={1}M(0,b)={2}M(1,b)={3}M(2,b)={2}M(3,b)={4}只有状态3在输入为b时映像的后继状态不在{0,1,2,3}中，因此该状态集划分为{3}和{0,1,2}对于{0,1,2}:状态1在输入为b时的后继状态不在{0,1,2}中，因此划分为{1}和{0,2}02314bbbbbaaaaa对于{0,2}:对于相同输入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分最后划分为：

{4}{3}{1}{0,2}六、DFA的化简572023/12/9举例（续1）对于划分结果{4},{3},{1},{0,2}，把{0,2}合并为一个状态，其状态转换图如图：0213aaaabbb02314bbbbbaaaaab六、DFA的化简582023/12/9源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针搜索指针3.4词法分析程序的实现592023/12/9超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。3.4词法分析程序的实现602023/12/9关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数3.4词法分析程序的实现612023/12/9使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。3.4词法分析程序的实现622023/12/9201字母字母|数字其它3456数字数字其它+-78*/9101113<=>:;1617其它13=举例632023/12/9本节讨论：用正规式描述单词符号，并研究如何从正规产生识别这些单词符号的词法分析程序。3.5词法分析器的自动生成642023/12/9一、LEX语言一个LEX语言程序经过编译后得到的结果程序，其作用相当于一个DFA，可用来识别和产生单词也就是说其功能即为一个词法分析器。652023/12/9一个LEX源程序包括两部分：辅助定义式和识别规则1、辅助定义式

D1→R1

Dn→Rn

其中Ri为正规式，只允许出现∑上字符D1,…,Di-1；Di为这个正规式Ri的简名例1．Letter→A|B|…|ZDigit→0|1|…|9Id→Letter(Letter|Digit)*...662023/12/92.识别规则

P1{A1}...Pm{Am}其中，Pi称为词形，为正规式(∑∪{D1,…,Dm})Ai称为词形Pi的动作（程序）显然：一个LEX源程序产生的词法分析器只能识别形如Pi的单词。672023/12/9二、LEX的实现LEX编译程序的目的是把一个LEX程序改造为一个词法分析器L，这个词法分析器L将象自动机一样工作。1．词法分析器L的工作方法

L逐个地扫描输入串的每个字符，寻找一个最大的子串匹配某个Pi（即：当输入串已匹配某个词形时，并不立即返回，而是沿着此道路继续前进，直至不能前进为止，逐个字符地逆向搜索，找到第一个逆向搜索到的匹配词形），把这个子串放入TOKEN中，然后L调用动作子程序Ai（如果有二义，前面位置的词形优先），当Ai工作完后，L就把所得的单词符号（种别，内部码值）返回语法分析程序。下次调用L，接着往下分析。682023/12/92.LEX程序的编译过程（1）对每条识别规则Pi构造一个NFAMi;

（2）引入一个新的初态X，从X画ε弧到每一个NFAMi的初态，构造出一个NFAM;

（3）把NFAM改造为DFAM’，这个DFAM’就是能识别所有形如Pi词形的词法分析器。这样我们就可用程序实现之，即编制出词法分析程序L。

692023/12/9实例1编写程序，实现下述LEX源程序的功能辅助定义：(1)digit→0|1|...|9(2)letter→A|B|...|Z

识别规则:(1)digit(digit)*{Return(4,val)}(2)letter(letter|digit)*

{Return(5，Token)}(3)*{Return(6,_)}(4)**{Return(7,_)}702023/12/9解：1、各识别规则的NFA为：712023/12/92、加入新初态X，构成NFAM整体722023/12/93、确定化为DFAM’732023/12/94、写出实现其功能的程序PROGRAMLEX(input,output)BEGINTOKEN:=’’;getchar;CASEcharOF‘0’..’9’:[whilecharIN[‘0’..’9’]DOBEGINTOKEN:=TOKEN+char;getcharEND;retract;IFVAL(token,value)THENreturn(4,value)];‘A’..’Z’:[whilecharIN[‘A’..’Z’,’0’..’9’]DOBEGINTOKEN:=TOKEN+char;getcharEND;