第三章词法分析

1、第三章词法分析知识结构:厂功能r词法分析器的要求<单词符号分类词法分析器的设计单词内部形式设计方发I词法分析器的设计状态图I词法分析器组成正规表达式单词描述工具<正规集词法分析器I正规文法确定有限自动机（DFA）单词识别工具<非确定有限自动机（NFADFA的最小化广正规式与FA的等价转换等价转换正规文法与FA的等价转换第一节对词法分析器的要求一、词法分析器的功能输入源程序，输出单词符号（二元式表示）源程序输入亍词法分析器输出！.二兀式（字符流）（单词流）二、单词符号的分类关键字：是由程序语言定义的具有固定意义的标识符。标识符：用来表示各种名字，如变量等。常数：常数的类型有整型

2、，实型等。运算符：算术运算符，关系运算符，逻辑运算符。界限符：逗号，分号等。三、单词符号内部的表示形式内部的单词符号TOKEN?（二元式），TOKEf字占用机器字的长度，依据信息量的多少而定。1、TOKEN?结构CLASS用整数表示。CLASS（单词种别码）VALUE（单词符号得属性）VALUE表示单词符号的属性（符号表指针）。2、TOKEN勺作用CLASS:用于语法分析器对源程序结构的分析。VALUE:用于语义分析器对源程序具体操作的分析。3、单词种别码划分原则CLASS:关键字，运算符，界限符（编译程序定义的符号）使用一字一种编码。VALUE®省略。VALUE:标识符，常数（用户

3、定义的符号），存放符号表常数表的指针。标识符，常数每一类为一种编码。例：BEGINA:=BEND;词法分析结果：符号表名字属性AB(BEGIN-)(A,K1)K1(:=,-(B,K3)K3(END,-)；,-四、词法分析器的结构1、一遍扫描（交互式结构）2、多遍扫描（独立式结构）第二节词法分析器的设计一、设计步骤1、确定词法分析器的接口关系；2、确定单词分类和TOKENS的结构;3、对每一类单词构造状态转换图；4、根据状态转换图设计算法。二、功能描述1、组织源程序输入；2、按词法规则拼读单词符号，并转换成二元式;3、删除注解行，空格和无用符号；4、检查词法错误。三、设计方法1、输入（读取原文件

4、）原文件存储方式：一种方式将原文件一次读入内存，另一种方式利用缓冲区技术将原文件分批读入内存。缓冲区的设置：输入（扫描）缓冲区，存放输入的原文件（双缓冲区）1起点扌1旨针扫描指针2、预处理功能描述：删除无用符号，出错信息的列表打印。单词符号的识别：语句格式 标识符不能被无效字符隔开。 标识符与关键字，关键字与关键字之间用空格符隔开。标识符的个数不能超过限定的个数。单词符号的格式 标识符，关键字的首字符必须是字母。 常数的首字符必须是数字。3、识别算法（P39）标识符的识别；常数的识别；算符的识别；界符的识别。四、状态转换图1、状态转换图的表示形式是一张有向图，结点代表状态（用O表示），结点间用

5、箭弧线连接（）,箭弧线上的符号，表示射出结点到达射入结点可能识别的输入符号，终态结点代表分析结束。初态O初始状态,表示识别符号串的开始。O初始状态,表示识别符号串的开始。双圈终态，表示识别符号串的结束。©表示多读入一个字符例1:标识符的状态转换图其它其它2字母，数字状态字母数字其它0111122状态转换矩阵例2:标识符“AB1”的识别例4:无符号数状态转换图状态数字其它0111222、识别过程从初态开始，逐步读入字符，转到下一个状态（或出错）至终态（或不能到达终态出错）。例3:字符串“AB+12'的识别12（数字）:2识别出单词AB，多读入一个字符+。由另一张状态转换图识别单

6、词符号+继续识别剩余字符上述识别过程把AB+12字符串分解为三个单词符号“AB“+”、“12”。3、状态转换图的实现状态转换图非常容易用程序实现，每一个状态对应一段程序。不含回路的分叉状态结点的程序设计利用多分支语句CASE或选择语句IFTHENELSE含回路状态结点的程序设计利用循环语句WHILE.DO。词法分析程序的组成状态转换图是一种特殊的流程，它可直观清晰地描述单词符号的识别过程，只要把每一个结点加入语义动作，就构成了词法分析程序。4、词法分析程序的组成(八个模块)主控模块；初始化模块；判定源程序文件是否存在模块；从源程序文件中读一个字模快；拼读一个单词模块；查关键字模块；输出单词模块

7、；错误处理模块。第三节正规式、正规集、正规文法一、正规式的定义中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。运算符优先级：重复用“*”表示；连接用“?”表示或省略；选择用“”表示。例：a，ab*，ab，(ab)c都是正规式。、正规集由正规表达式所表示的字符串的集合称为正规集。如正规式用V表示，正规集L(V)表示。三、正规文法正规文法是上下文无关文法的一种特殊情况，所有产生式的右部至多含有一个非终结符号，左线性文法，右线性文法都属于正规文法。左线性文法：ABA右线性文法：AB*A其中：A，BVN，V*T*T四、正规式与正规集的递归定义1、正规式与正规集的递归定义P46

8、(1)£和都是艺上的正规式，正规集为£和。任何aX,a是上的正规式，正规集为a。假定U和V是上的正规式，正规集为L(U),L(V)UUV是正规式，正规集为L(U)UL(V)oUV是正规式，正规集为L(U)L(V)o*(U)*是正规式，正规集为(L(U)*。例1：令艺=a,b，贝U正规式a|b的正规集是a,b。正规式(a|b)(a|b)的正规集是aa,ab,ba,bb*正规式a的正规集是£,a,aa,aaa。*正规式(a|b)的正规集是£,a,b,aa,ab,ba,bb,aaa相继aaa相继。(a|b)=(ab)，即所有a和b的符号串集合。*a|b)(aa

9、|bb)(a|b)的正规集是所有含有两个a或两个相继b的字符串集合。例2：=a,b,c乙0,1,9*正规式(a|b|z)(a|b|z|0|1|9)代表标识符,2、正规式与正规集的等价性若两个正规式代表的正规集相同，则认为正规式等价。U=V表示L(u=L(V)*例3：U=100，L(U)=10*V=10*，L(V)=10*则100=10*例4：b(ab)=(ba)b(ab)工ab(a|b)*=(a*b*)*b)*工(a*|b*)3、正规式的代数定律(1)UV=VU交换律(2)UVW=(UV)W结合律(3)U(VW)=(UV)W结合律(4)U(VW)=UVUW分配律(5)£U=U

10、3;=U*+6) U=UU*=U*+*8)U=UU=UU例1:选择规则UV,则描述的正规集L(UV)=L(U)UL(V)令U=a,V=b：则L(UV)=L(U)UL(V)=L(a)UL(b)=aUb=a，b例2:连接规则UV则描述的正规集L(UV)=L(U)L(V)。令U=ab，V=c:则L(UV)=L(U)L(V)=L(ab)L(c)=a，bc=ac,bc例3:重复规则U，则描述的正规集L(U)=(L(U)。*U*12=UUUUU.nUUU=（aab）L(U*)=(L(U)*=(L(a*ab)=(L(a)UL(ab)*=a,ab012=a,abUa,abUa,abU=Ua,abUa,aba,

11、abU=,a,ab,aa,aab,aba,abab,五、正规式与正规文法的转换正规式与正规文法都有相同的表达能力,用以描述语言（单词符号）的结构,使得所描述的语言是等价的（即L（V）=L（G）。1、正规式与正规文法的特点正规式描述的语言结构清晰,简洁；而正规文法描述的语言于识别。2、正规定义式d1r1d2r2其中:di为定义式的名字；ri是Udi,d2,.,di-i构成的正规式；ri中不含有di，di+1，.。3、正规式与正规文法的转换算法例：高级语言标识符的正规式字母（字母数字）*根据正规定义式规则，给正规式分量、正规式定义名称字母ABC数字012id字母（字母数字）*对定义式的子表达式定义

12、名称rid（字母数字）对定义式的子表达式展开（字母数字）*=（字母数字）+=（字母数字）（字母数字）=字母（字母数字）*数字（字母数字）*把展开式代入定义式rid字母（字母数字）数字（字母数字）把rdi（字母数字）代入定义式id、rid，将得到正规文法：id字母ridrid字母rid数字rid其中:id，ridVN；字母，数字VT。六、正规文法与正规式的转换建立正规文法的联立方程组，求描述同一语言的正规式。1、右线性文法到正规式，使得L（G）=L（V）。产生式XrXt，其中r，tVTXVN论断1：方程X=rX+t，有形如*X=rt的解。例：文法GSaSbAbAaS立联立方程组S=aS+bA+b

13、A=aS式，代入式S=aS+baS+bS=（a+ab）S+b由论断得方程解*S=（a+ab）b=（aab）b对于同一方程式采用不同的结合方式，可以得到不同形式的正规式，但是所描述的语言（正规集）是等价的。S=aS+baS+b=aS+（baS+b）*=a（baS+b）*=abaS+ab*=（aba）ab*所以（aba）ab=（aab）b。2、左线性文法与正规式的转换算法产生式XXrt，其中r，tVTXVN。论断2：方程X=Xr+t，有形如X=tr的解。例：文法Gidid字母id数字字母其中:idVN；字母，数字VT。建立方程id=id字母+id数字+字母=id（字母+数字）+字母=字母（字母数字

14、）*3、正规文法与正规式的转换规则产生式AxB，By对应的正规式A=xy；产生式AxAy对应的正规式A=xy；产生式Ax，Ay对应的正规式A=xy例：文法GSaA，SaAaA，AdA，Aa，Ad根据规则先有正规式S=aAaA=（aAdA）（ad）再将A的正规式变换为A=（ad）A（ad）根据规则将A的正规式变换为*A=（ad）（ad）再将A式的结果代入S的正规式*S=a（ad）（ad）a再利用正规式的代数性质得到的正规表达式为S=a（ad）（ad）因为（ad）+ad）=（ad）+所以S=a（ad）a=a（ad）+*又因为（ad）=（ad），所以S=a（ad）第四节有限自动机（FA）有限自动机是

15、具有离散输入和输出系统的一种数学模型，它能准确地识别正规文法所定义的语言和正规式表示的正规集，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法。有限自动机的分类：确定有限自动机（DFA。非确定有限自动机（NFA）。一、有限自动机的表示形式状态图一个有限自动机可以用一个状态图（状态转换图）表示，即含有m个状态，n个输入符号，若f（ki,a）=kj，则从状态结点ki到状态结点kj画标记为a的弧。弧上标记的符号表示当前识别的符号。状态表一个有限自动机可以用一个矩阵表示，该矩阵的第一列表示状态，第一行表示输入字符，矩阵元素表示相应状态和输入字符到达的下一状态，即k行a列为f（k，a）

16、的值。二、有限自动机的应用翻译器有限自动机（FAM作为转换器将输入串变换为输出串。M=（S，R，S0，F）串产生器有限自动机（FAM如果只有输出没有输入。M=(S,R,So,F)串识别器有限自动机(FAM)如果只有输入没有输出。M=(S,So,F)状态转其中：S状态集；输入字母表；R输出字母表；换函数；So初态；F终态三、有限自动机的工作原理例：有限自动机识别无符号实常数的过程dd'接受从初始状态出发所识别的字符串结束时能够到达终态结点例：35.67为有效字符串。阻塞(出错)从初始状态出发所识别的字符串结束时没能到达终态结点例：356.为无效字符串。四、确定有限自动机DFA确定有限自动

17、机(DFAM是一个五元组：DFA(M)=(S,S,5,so,F),其中：S是一个状态的有穷集一自动机所有状态的集合。是有穷字符集合，它的每一个元素为一个输入字符。S状态转换函数5(S,a)=S,当现行状态为S,输入字符为a时，将转换到下一个状态S。SS单值映照函数。SoS唯一的初始状态。FS终态集。若DFAM上有m个状态，n个输入符号(中的元素有n个)，则状态转换图上有m个状态结，每个状态结最多有n个射出弧线与后续的状态连接状态矩阵表状态ab0121322133331,2,3。该DFAM有4个状态0,2=a,b。So=0为初始状态。F=3为终态。为状态转换函数：(0,a)=1,(0,b)=2(

18、1,b)=2(1,b)=2(1,a)=3,(2,b)=3(2,b)=3(3,b)=3(2,a)=1,(3,a)=3,1、DFAM所识别的符号串DFAM所识别的符号串宀:对宀艺，若存在一条从初始状态结点到终态结点的道路，在这条路上所有弧线标记符号连接成的符号串恰好是宀，则称宀为DFAM所识别。上例DFAM所识别的符号串为艺=a,b上的含有二个相继a或二个相继b的符号串的集合。例1:“aab”是DFAM所能识别的符号串。不能被DFAM识别的符号串：被识别的符号串不能从初始状态结点到终态结点，有下列两种情况：不能到达终态（已识别完）例2：“abab”不是该DFAM所能识别的符号串（上例）其中：2状态

19、不是终态结点。某一状态射出弧线上标记与所识别的符号不同（多态性）例3:给定DFAMbb“abb”不能被DFAM识别。2、DFAM所识别的语言L(MDFAM所能识别的符号串的集合，称DFAM所识别的语言:L(M)=(SO,)F,*例4：L(M)=a开头的，a,b符号串DFAM=(1，2；a,b，1，2)3、空字符串的识别如果DFAM的初始状态又是终态，则空串可被DFAM识别。例5：.例6：串五、非确定有限自动机NFAM1、非确定有限自动机的特性某一结点射出多条标记相同字符的弧线到达不同的结点(0,a)=0,1(0,b)=1(1,b)=0(1,b)=1两个状态(1,b)=0,1某一结点射出标记有E

20、字符的弧线2、非确定有限自动机NFAM定义NFA(M=(S,S,S,So,F)S同上；艺同上；*sS是一个从S到S的子集的映照，即S:S2;SoS为一个非空初态集；FS，为一个终态集(可空)。3、NFAM与DFAM的区别NFAM状态转换函数具有多值性；即3(S,a)=Si,S2,SnNFAM可以存在有£弧；'Si»SjNFAM可以有多个初态(初态集)六、非确定有限自动机(NFAM的识别例M=(1,2。3,4,a,b,c,1,)1、映射函数值(1,)=4,(2,)(3,)=,(4,)(1,a)=2,3,(2,a)=2,(3,a)=,(4,a)一5(1,b)=,(2,b

21、)=4,(3,b)=,(4,b)=,(1,c)=,(2,c)=,(3,c)=3,4,(4,c)=2、构造对应的状态转换矩阵字符状态aabc142,322433,443、构造非确定有限自动机NFAM4、非确定有限自动机NFAM识别的有效字符串例1：字符串“aaab”被识别的语言L(M)=anbn>1n被识别的语言L(M=acn>1。所以L(M)=abn>1acn>1。第五节非确定有限自动机(NFAM的确定化一、非确定有限自动机(NFAM确定化的目的1、取消识别到达的状态结点；2、合并识别相同字符到达的状态结点。二、£-CLOSURE闭包的定义假设I是NFAM的状

22、态集的一个子集。1、I的£丄£-CLOSUREI)定义：若SI，贝US£-CLOSURED);若SI，那么从S出发经过任意条弧而能到达的任何状态S都属于£-CLOSURED)。2、Ia定义:假定I是NFAM的状态集的一个子集，a是中的一个字符，Ia的定义:Ia=£-CLOSUR(J)其中：J是所有那些可从£-CLOSUREI)中的某一状态出发，经过一条a弧线而到达的状态及由当前状态出发经空弧线连接到达状态的全体。若匸，£_CLOSUREI)=1,2Ia=5,3,4,6,2,8,7若匸5,£_CLOSUREI)=5,

23、6,2Ia=3,8三、NFAM的确定化构造一个与NFA(M)等价的DFAM':使得L(M)=L(M')1、状态转换矩阵表的形式若中有k个元素a，状态转换矩阵形式为：IIa1Ia2IaCLOSURE(s)第一列是DFAM中的初始状态，为NFAM中的初始状态集闭包(CLOSURES)；用NFAM的初始状态集(空闭包)中的每一个状态，分别构造Iai,Ia2,Iak的后继状态子集。每一个状态子集均为DFAM的一个状态。如同步骤，直至没有出现新的状态子集为止。2、由NFAM构造DFAM'的具体步骤：求NFAM的_CLOSUREI）；求Ix的_CLOSUREJ）；（X）；构造DFA

24、M'的转换矩阵；确定DFAM'的初始状态和终态； 含有NFAM初始状态的子集为DFAM'的初始状态结点； 含有NFAM终态的子集为DFAM'的终态结点； 不包含NFAM初始状态、终态的子集为DFAM'的内部状态结点； 构造确定化有限自动机DFAM'，使得L（M=L（M'）。四、带弧NFA的确定化其中:=，a，b，cS=1，2，3,4So=1F=4求NFAM的_CLOSUREI)I=_CLOSUR（E1）=1，4令S0=1，4。求Ix的_CLOSUR（EJ）,（X，X=a，b，Ia=_CLOSUR（EJ）=_CLOSUR（E（1，a)U(4

25、，a)=_CLOSUR（E2，3U)=2，3令S1=2，3。Ib=_CLOSUR（EJ）=_CLOSUR（E（1，b)U(4，b)=_CLOSUR（EU)Ic=_CLOSUR（EJ）=_CLOSUR（E（1，c)U(4，c)=_CLOSUR（EU)同理可求出从S1出发识别某一字符能到达的后继结点S1=2，3_CLOSUR（ES1，a）=（2，a）U（3，a）=2令S2=2_CLOSURESi,b)=（2，b）U(3，b)=4令S3=4。_CLOSURESi,c)=(2，c)U(3，c)=3，4令S4=3，4。再分别求出(S2,x），(S3，x)，(S4，x)直到不出现新的子集为止。构造DFAM

26、'的子集转换矩阵表确定DFAM'的初始状态和终态IIaIbIc1,42,32,3243,422443,434 含有NFAM初始状态的子集为DFAM'的初始状态结点； 含有NFAM终态的子集为DFAM'的终态结点； 不包含NFAM初始状态、终态的子集为DFAM'的内部点;其中：S0=1，4为DFAM'的初始状态和终态结点；Si=2，3，S2=2为DFAM'的内部结点；S3=4，S4=3，4为DFAM'的终态结点;将子集矩阵表变换成状态矩阵表。字符状态、at)cSoS5iSiS52S；3S4SS52S3S3S4S4构造确定化有限自动机

27、DFAM'该DFAM识别的语言是L(M')=该DFAM识别的语言是L(M')=nacn>1。ab1用子集法构造转换矩阵见下表IIaIbX，5，15,3,15,4,15，3，15,3,1,2,6,y5,4,15，4，15,3,15,4,1,2,6,y5，3，1,2，6,y5,3,1,2,6,y5,4,1,6,Y5，4，1,6，y5,3,1,6,y5,4,1,2,6,y5，4，1,2，6,y5,3,1,6,y5,4,1,2,6,y5,3,1,6,y5,3,1,2,6,y5,4,1,6,y对上表中的所有子集重新命名，形式成下表的转换矩阵Sab01213221533446

28、5565634构造相应的DFAM五、不带弧NFA的确定化例：将NFAM转换为DFAM'由于从初始状态出发没有弧线所能到达的终点，因此NFAM的_CLOSUREI）（空闭包）只有初始状态。I=_CLOSURE0)=0用子集法，求DFAM的状态矩阵表IlaIb00,110,10,10,110,1,b第六节确定有限自动机（DFAM的化简一、确定有限自动机化简的方法对于任意的DFAM，寻找一个状态个数比M少的DFAM，使得L（M）=L（M）。1、可区别的定义设s，t为DFAM同一子集的两个不同状态，如果从s出发输入某一字符w到达终态，从t出发输入某一字符w到达非终态，称s，t是可区别的（不等价

29、）。s，w）F，（t，w）F2、不可区别的定义如果从s，t状态出发，输入某一字符w总是同时能到达终态（或非终态），称s，t是不可区别的（等价）。（s，w），（t，w）F或（s，w），（t，w）F二、DFAM的最小化的算法将DFAM的状态集s逐步分划，按可区分的等价关系，将s分划为r个（rws）互不相交的子集。1、将DFAM中的状态划分成终态集F和非终态集S-F，构成初始分划，记作：=F，S-F12m2、设当前的划分中m个子集，即=1,1，I,其中:对每一个子集中Ii=Si1,Si2,.,Sin中各状态Sir（SirS,1wrwn）进行考察,看是否还能对它们进行划分。求Iia'a=_CL

30、OSUREJ）即到达状态的集合；如Sip，Siq是Ii中的两个状态，使得（Sip，a）=Sju，（Siq，a）=Skv。而状态Sju，Skv分别属于中两个不同的子集，从而Sip，Siq为可区别，故应将I进一步划分，使Sip，Siq是分ii别属于I的不同子集。即对于每一个子集I及a进行考察。每细分一次，就得到一个新的划分new,且划分中的子集数也由原来的m个变为m+p+1个。3、重复步骤2直至子集个数不再增长为止4、从每个子集中选取一个状态代表该子集。例1已知DFAM求最小化。分为:0,1,2,3非终态集和4终态集=0,1,2,3,4对每一个子集及每一个a进行考察0,1,2,3a=10，1,2，

31、30，1,2,3b=2,3,40,1,2,3对于输入a子集0,123是不可区别，对于输入的，将0,123分为0,1,2和。new=0,1,2,对new进行考察0,1,2a=10,1,2,0,1,2b=2,30,1,2将0,1,2分为0,2和1。new=1,0,2,对new进行考察0,2a=110,2b=20,2则0,2不可划分合为一个状态。最终的结果是：new=1,0,2,3,4b是可区别3,4，根据最小化的结果构造矩阵表字符状态、ab0,210,23314410,2第七节正规式与有限自动机的等价性、正规式与有限自动机的等价性若给定一个正规式V都存在一个FAM,使得L（V）=L（M）;同样任何

32、NFAM都存在一个正规式V使得L（M）=L（V）。二、证明L（M）=L（V）首先在NFAM上增加两个结点X（初态）、Y（终态），并用£弧分别连接NFAM'的初态和终态。使得L（M）=L（M'）。逐步消去NFAM'中所有结点，直到只剩下初态和终态。三条消结规则三条消结规则代之33代之2V2V代之33、卜I亠、卜:注意消结为33V3而不是3=LV413VV225V2构造按下列三条规则引进新的状态转换成FAML(M')(UL2)Vi所以，只要使得1V2证明L(V)=Li(V2V3)V4设置初态结X,终态结Y消去V中的运算符，直到每V1条弧线上只标记艺中的一个符号或2U字符为止。*ViV2V3V21»2V-X/-UX(V)。也就证明了L(M)=L(V)。1(U1U2)*W1V1V2)-7例1%2(U1U2)W2r2.5V-X*V1(V2IV3)V4(Ui直)1症；2转换成U转换成YXXVXbbaaX26baaaX26Y5aX26xV例：将正规式ab利用替换规则可以证明L(V)利用上述转换规则构造NFAM转换成等价的最小化的DFAM'。aabb(aabb)-ab)*转换成NFAM*(ab)(aabb)*ab*ab)(aabb)*ab)XU并'bi鱼4a、3、a利用子集法构造转换矩阵表