第四章词法分析精选文档.ppt

《第四章词法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章词法分析精选文档.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章词法分析本讲稿第一页，共八十一页4.1词法分析程序的设计4回顾回顾 什麽是词法分析（lexicalanalysis）程序又称词法分析器或扫描器，又称词法分析器或扫描器，主要功能是逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。本讲稿第二页，共八十一页词法分析程序和语法分析程序的关系字符串源程序词法分析符号串源程序图4.1a词法分析单独作为一遍 字符串源程序词法分

2、析器语法分析器取符号送符号图4.1b词法分析作为语法分析子程序本讲稿第三页，共八十一页词法分析程序的任务词法分析程序的主要任务：扫描源程序，识别出具有独立意义的单词词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，将行号与出错信息相联系起来。宏展开，本讲稿第四页，共八十一页词法分析程序的输出格式4词法分析的输出常采用二元式：（单词类别，单词自身的值）（单词类别，单词自身的值）4单词类别通常用一个整数类码或单词记号表示，单词记号比整数码含义明确。4若还需记录单词的一些其它属性值:如标识符的类别、层次等，可将这些属性统一放到符号表中，并将单词的二元式表示为：（标识符，指向该标识符所在

3、符号表中位置的指针）（标识符，指向该标识符所在符号表中位置的指针）本讲稿第五页，共八十一页词法分析程序的结构将词法分析从语法分析部分独立出来的原因使整个编译程序的结构更简洁、清晰、条例化改进编译效率增加编译系统的可移植性本讲稿第六页，共八十一页4手工构造首先确定出能够识别程序中单词的确定的有穷自动机（DFA），然后可以采用直接编程的方法或者表驱动的方法来构造词法分析器。4借助相关工具的自动构造如：Lex编译系统词法分析程序的常用设计方法本讲稿第七页，共八十一页多数程序设计语言的单词的语法均可用正规文法来表示。4回顾：正规文法(3型文法)：任一产生式的形式都为：任一产生式的形式都为AaB或或Aa

4、，其中，其中AVN，BVN，aVT*4正规文法描述的是VT上的正规集。4例：程序设计语言中几类单词的描述规则：标识符、无符号整数、运算符。（参见课本P52）4.2单词的描述工具-正规式正规式本讲稿第八页，共八十一页4.2单词的描述工具-正规式正规式4正规式（正规式（regularexpression也叫正则表达式）也叫正则表达式）正规式是定义正规集的数学工具，是说明单词的模式(pattern)的一种表示法，用它描述单词符号时一般比正规文法更简洁。4正规式和正规集(即其描述的语言）的定义可以用递归的形式给出。本讲稿第九页，共八十一页4.2单词的描述工具-正规式正规式正规式正规式设是有穷字母表，并

5、定义辅助字母表=,|,.,*,(,)1.,都是上的正规式，它们所表示的正规集为,;2.任何a是一个正规式，若a，它所表示的正规集为a；3.如果R1和R2是正规式，其表示的正规集分别为L1和L2，则1)正规式R1|R2或R1+R2表示的正规集为L1L22)正规式R1.R2或R1R2表示的正规集为L1L23)正规式R1或R1*表示的正规集为L1*4)正规式(R)表示的正规集仍是L1，但调整优先权，使括号内的运算符优先权高于括号外的。本讲稿第十页，共八十一页4.仅有有限次使用上述三步骤而定义的表达式才是上的正规式，仅有这些正规式表示的字集才是上的正规集。4.2单词的描述工具-正规式正规式注意：不要混

6、淆注意：不要混淆和和，正则表达式，正则表达式描述的语言只含一个空字描述的语言只含一个空字符串符串，而，而表示的语言不含有任何字符串。表示的语言不含有任何字符串。本讲稿第十一页，共八十一页例4.2.1:令=a,b,则上的正规式和相应正规集为(1)a(2)ab(3)ab(4)(ab)(ab)(5)a(6)(ab)(7)(ab)(aabb)(ab)(1)a(2)a,b(3)ab(4)aa,ab,ba,bb(5),a,aa,任意个a的串(6),a,b,aa,ab,bb所有由a和b组成的串(7)上所有含有两个相继的a或两个相继的b组成的串本讲稿第十二页，共八十一页例4.2.2:令=l，d,则上的正规式r

7、=l(ld)定义的正规集为程序设计语言的单词都能用正规式来定义。若两个正规式e1,e2表示的正规集相同，则称它们等价。记作:e1=e2l,ll,ld,ldd,其中l代表字母,d代表数字,即:字母(字母|数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,即Pascal和多数程序设计语言允许的的标识符的词法规则.本讲稿第十三页，共八十一页正规式服从的代数运算规律：设r,s,t为正规式，则它们满足如下运算规律：1.r|s=s|r2.r|(s|t)=(r|s)|t3.(rs)t=r(st)4.r(s|t)=rs|rt;(s|t)r=sr|tr:或的分配律5.r=r;r=r:是“连接”

8、的恒等元素6.r|r=r:“或”的抽取律本讲稿第十四页，共八十一页4一个正规语言可用正规文法表示也可用正规式表示，两者具有等价性。一般而言正规式在描述语言时比正规文法更为简洁。正规文法和正规式的等价性例如，用正规文法表示标识符的文法规则如下：标识符a|b|z|标识符a|标识符b|标识符z|标识符0|标识符1|标识符9而采用正规表达式则为：标识符=(a|b|c|z)a|b|z|0|1|9或简写成标识符=字母字母|数字本讲稿第十五页，共八十一页4将将 上的正规式上的正规式r转换成正规文法转换成正规文法G=(VN,VT,S,P).令VT=，产生式和VN按如下方法确定：1.选择一非终结符S生成类似产生

9、式的形式Sr，并将S定为文法G的识别符。2.若x,y是正规式，对形如Axy的正规式产生式，重写成：AxB,By，B为新选的非终结符。3.对形如Ax*y的正规式，重写成:AxB,Ay,BxB,By，B为新选的非终结符。4.对形如Ax|y的正规式，重写成:Ax,Ay。不断利用上述规则做变换，直到每个产生式都符合正规文法的形式即可。正规文法和正规式的等价性本讲稿第十六页，共八十一页例4.2.3：将r=a(a|d)*转换成相应的正规文法正规文法和正规式的等价性本讲稿第十七页，共八十一页4将正规文法转换为正规式将正规文法转换为正规式4基本上是正规式到正规文法转换过程的逆过程。可反复采用以下三条规则，直到

10、只剩下一个开始符号定义的正规式为止。1.产生式AxB,By对应正规式A=xy;2.产生式AxA|y对应正规式A=x*y;3.产生式Ax,Ay对应正规式A=x|y;正规文法和正规式的等价性本讲稿第十八页，共八十一页例4.2.4:将GS转换为正规式SaASaAaAAdAAaAd正规文法和正规式的等价性解：由文法GS得S=aA|aA=(aA|dA)|(a|d)则S=a(a|d)*(a|d)|a=a(a|d)*(a|d)|)=a(a|d)*本讲稿第十九页，共八十一页4.3有穷自动机有穷自动机有穷自动机(有限自动机)作为一种识别装置，它能准确地识别正规集(即正规式所表示的集合)。有穷自动机为词法分析程序

11、的自动构造提供了有效的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata:DFA)不确定的有穷自动机(NondeterministicFiniteAutomata:NFA)本讲稿第二十页，共八十一页4.3关于有穷自动机有穷自动机将主要讨论如下问题1确定的有穷自动机DFA2不确定的有穷自动机NFA3NFA的确定化4DFA的最小化本讲稿第二十一页，共八十一页一、确定的有穷自动机DFADFA定义:一个确定的有穷自动机（DFA）M是一个五元组:M=(K,f,S,Z),其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元

12、素称为一个输入符号，所以也称为输入符号表；本讲稿第二十二页，共八十一页DFA定义(续):3.f是转换函数，是在KK上的单值单值映射，即如存在f(ki,a)=kj,(kiK,kjK)，则当前状态为ki且输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态或结束状态。一、确定的有穷自动机DFA本讲稿第二十三页，共八十一页一、确定的有穷自动机DFA例4.3.1:DFAM=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a

13、）=Qf（U，b）=Vf（Q，b）=Q本讲稿第二十四页，共八十一页u上例中DFA的状态图表示bSUVQaaaba，bb一、确定的有穷自动机DFA本讲稿第二十五页，共八十一页u上例中DFA的矩阵表示字符字符状态状态0001一、确定的有穷自动机DFA本讲稿第二十六页，共八十一页u概念：概念：*上的符号串上的符号串t被被DFAM接受接受一、确定的有穷自动机DFA4定义定义1:对对*中的任何符号串中的任何符号串t，若存在一条从初态结点某，若存在一条从初态结点某一终态结点的道路，且这条道路上所有弧连接成的符号串一终态结点的道路，且这条道路上所有弧连接成的符号串等于等于t，则称，则称t可为可为DFAM所接

14、受，若所接受，若M的初态同时又是终态的初态同时又是终态结点，则空字可为结点，则空字可为M所接受。所接受。4定义定义2:若若t*,f(S,t)=P，其中，其中S为为DFAM的开始状态的开始状态,PZ,Z为终态集为终态集,则称则称t可为可为M所接受所接受(识别识别)。DFAM所能接受的符号串的全体记为L(M)。DFA的确定性表现在f:KK是一个单值函数。本讲稿第二十七页，共八十一页一个输入符号串t(表示为t1tx),其中t1,tx*,则t在DFAM上运行运行的定义为:f(Q,t1tx)=f(f(Q,t1),tx)其中QK,f(Q,)=Q。一、确定的有穷自动机DFAu概念：概念：*上的符号串上的符号

15、串t被被DFAM上运行上运行u 上一个符上一个符号号串集串集V 是正规的，当且仅当存在一个是正规的，当且仅当存在一个 上的上的DFAM，使得，使得V=L(M)。本讲稿第二十八页，共八十一页一、确定的有穷自动机DFA例例4.3.2:证明证明t=baab被下图的被下图的DFA所接受所接受bSUVQabba,baaf（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。得证。属于终态。得证。本讲稿第二十九页，共八十一页4DFA行为的程序模拟.DFAM=（K，f，S，Z）的行为的模拟程序

16、1.K:=S；2.c:=getchar;3.whileceofdo4.K:=f(K,c);5.c:=getchar;6.;7.ifKisinZthenreturn(yes)8.elsereturn(no)一、确定的有穷自动机DFA本讲稿第三十页，共八十一页二、不确定的有穷自动机NFAnNFA定义定义:NFAN=(K,f,S,Z)，其中K为有穷状态集，为有穷输入字母表，f为K到K的子集的映射，SK是一个非空初态集，ZK为终态集。4NFA与DFA的区别主要有:1.NFA中状态转换函数为多值函数。2.NFA中起始状态可以有多个，但从正规文法出发构造的NFA起始状态是唯一的。本讲稿第三十一页，共八十一

17、页二、不确定的有穷自动机NFA例4.3.3:NFAN=(S,P,Z,0,1,f,S,P,Z)其中f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111状态图表示本讲稿第三十二页，共八十一页矩阵表示简化为二、不确定的有穷自动机NFA本讲稿第三十三页，共八十一页类似类似DFA,NFAN=(K，f，S，Z)也有如下定义：也有如下定义：符符号号串串t在在NFAN上运行上运行一个输入符号串t(将它表示成Tt1的形式,其中T,t1*)在NFAN上运行运行的定义为：f(Q,Tt1)=f(f(Q,T),t1)其中QK.符符号号串串t被被NFAN接受接受若f(S

18、0,t)=P,其中t*,S0S,PZ,则称t为NFAN所接受(识别)二、不确定的有穷自动机NFA本讲稿第三十四页，共八十一页符号串符号串t被被NFAN接受接受也可以这样理解也可以这样理解对于任何一个符号串t(t*)，若存在一条从某一初态到某一终态的道路，且这条道路上所有弧的标记字依序连接成的串(不计弧)等于t，则称t为NFAN所接受。二、不确定的有穷自动机NFA4有了上述定义后，实际上也就是对有了上述定义后，实际上也就是对NFA的转换函数的转换函数f进行了如下扩充进行了如下扩充:f:KK的子集f:K*K的子集本讲稿第三十五页，共八十一页二、不确定的有穷自动机NFA例例4.3.4:下列符号串哪下

19、列符号串哪些可以被图中些可以被图中NFANFA所接所接受？受？11110100010001100本讲稿第三十六页，共八十一页二、不确定的有穷自动机NFA例例4.3.4:下列符号串哪些下列符号串哪些可以被图中可以被图中NFANFA所接受所接受？11110100010001100本讲稿第三十七页，共八十一页若将NFAN所能接受的符号串的全体记为L(N)，则有如下结论：对每个NFAN存在着与之等价的DFAM，使得L(M)=L(N)。并且最小的DFAM是唯一的。将NFA转换成等价的DFA的算法-子集法子集法。二、不确定的有穷自动机NFA本讲稿第三十八页，共八十一页有关状态集合有关状态集合I I的两个运

20、算：的两个运算：1.状态集合状态集合I的的-闭包闭包，记为-closure(I)，定义为一状态集，是由状态集I中的任何状态S经任意条弧而能到达的状态所构成的集合。状态集合I的任何状态都属于-closure(I)。2.状态集合状态集合I I的的a a弧转换弧转换，记为move(I,a)，是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。三、NFA的确定化本讲稿第三十九页，共八十一页12534687aaa三、NFA的确定化有关状态集合有关状态集合I的运算实例的运算实例计算下列各式的值计算下列各式的值1)move(1,2,a)2)-closure(5,3,4)运算结果：运算结果：1)=5,

21、3,4;2)=2,3,4,5,6,7,8;例4.3.5:若I1=1,则-closure(I1)=1,2;move(I1,a)=4,5;-closure(move(1,2,a)本讲稿第四十页，共八十一页三、NFA的确定化子集法子集法:假设NFAN=(K,f,K0,Kt)，按如下方法可构造一个DFAM=(S,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K K的一些子集的一些子集组成。用S1,S2,.,Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定:状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1,S2；本讲稿第四十一页

22、，共八十一页2M和N的输入字母表是相同的，即是；3转换函数是这样定义的：d(S1,S2,.Sj,a)=R1,R2,.,Rt其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)为M的开始状态；5St=Si,Sk,.,Se,其中Si,Sk,.,SeS且Si,Sk,.,SeKt三、NFA的确定化本讲稿第四十二页，共八十一页构造构造NFAN中状态中状态K的子集的算法：的子集的算法：假定所构造的子集族为CS，即CS=(T1,T2,.Ti)，其中T1,T2,.,Ti为状态K的子集，则其构造步骤如下：1.令-closure(K0)为CS中唯一成员，且

23、它是未被标记的。2.while(CS中存在尚未被标记的子集T)do标记T；for每个输入字母adoU:=-closure(move(T,a)；ifU不在CS中then将U作为未标记的子集加在CS中三、NFA的确定化本讲稿第四十三页，共八十一页例4.3.6:将下图NFAN=(K,f,K0,Kt)转换为等价的DFAM其中M=(S,d,S0,St)。4f35621iaaaabbbb三、NFA的确定化本讲稿第四十四页，共八十一页表1NFA状态子集的构造结果4f35621iaaaabbbb本讲稿第四十五页，共八十一页aDECBFFAbaaaaabbbbbabG三、NFA的确定化转换为DFA后的状态图本讲

24、稿第四十六页，共八十一页四、DFA的化简结论：结论：对于任何给定的对于任何给定的DFA，都存在一个与之等价的最少状，都存在一个与之等价的最少状态态DFA，并且该最少状态，并且该最少状态DFA是唯一的。是唯一的。最少状态最少状态DFA应满足应满足：1).没有多余状态；没有多余状态；2).没有等价状态。没有等价状态。多余状态多余状态:从自动机的开始状态出发，任何输入串也不能到达的状态；或者是没有通路到达终态的状态。两个状态两个状态s和和t等价等价是指它们具备以下特性:a.一致性(兼容性):即两状态同是终态或同是非终态b.蔓延性:对所有输入符号，状态s和t必须转换到等价的状态里。或者说从两状态出发所

25、接受的符号串集合相同。本讲稿第四十七页，共八十一页四、DFA的化简例4.3.7:判断下图中那些状态是多余状态。012345bbbaa0234bba删除多余状态后的状态图本讲稿第四十八页，共八十一页四、DFA的化简例4.3.8:判断下图中那些状态是等价状态。解：因为f(1,a)=3，f(2,a)=3，所以状态1和状态2是等价的02134abaab4本讲稿第四十九页，共八十一页上图DFA中D、E、F、G为等价状态。四、DFA的化简例4.3.9:判断下图中那些状态是等价状态。aDECBFFAbaaaaabbbbbabG本讲稿第五十页，共八十一页结论：结论：一个DFA可以通过消除多余状态和合并等价状态

26、而转换成一个与之等价的最小DFA。DFA的最小化算法（分割法）的最小化算法（分割法）算法的核心思想：算法的核心思想：把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。算法具体步骤：算法具体步骤：以DFAM=(K,f,k0,kt)的最小化为例1.构造自动机的初始划分:终态集kt和非终态集K-kt两组四、DFA的化简本讲稿第五十一页，共八十一页2.对各状态集按下面方法进行划分，直到所有状态集合不再产生新的划分为止。设第m次划分将K分成n个状态集合(K=S1S2Sn)。对状态集合Si中的各状态逐一检查，设q1,q2是状态集合Si中的

27、两个状态，对任意输入符号a，有f(q1,a)=S,f(q2,a)=S”，若状态S和S”不属于同一状态集，则将q1和q2分为两个集合。3.重复第2步，直到所有状态集合都不能划分。4.将每个状态集中的等价状态合并成一个状态。5.删除多余状态。四、DFA的化简本讲稿第五十二页，共八十一页四、DFA的化简对S1=0,1,2划分:因为f(0,a)=1,f(1,a)=3,f(2,a)=1,故1,2不属于同一状态集,所以将S1分成S3=0,2,S4=1对S3=0,2划分:因为f(0,b)=2,f(2,b)=4,故S3应分成S5=0,S6=2对S2=3,4划分:因为f(3,a)=3,f(4,a)=3,f(3,

28、b)=4,f(4,b)=4,故3,4属于同一状态集,所以S2不能划分,也就是说状态3和4等价。至此，不再能继续划分01234bbbaaabaab例4.3.10:对下图DFA进行化简。解：首先将状态集合分成非终止状态集S1和终止状态集S2，即S1=0,1,2;S2=3,4本讲稿第五十三页，共八十一页四、DFA的化简最终得到不能划分的状态集有:S2=3,4,S4=1,S5=0,S6=2每个状态集留一个状态得:S2=3,S4=1,S5=0,S6=2所以化简后的DFA如下图所示0123bbbaaaab化简后的化简后的DFA本讲稿第五十四页，共八十一页四、DFA的化简0:A,B,C,D,E,F,G1:A

29、,B,C 2:aA,C,BD,E,F,GbA,CaDCBAaaabbbb例4.3.11:对例4.3.9的DFA进行化简。至此，不能再进行划分，所得状态集为A,S,B,C,D,E,F，每个状态集留一个状态后得到化简后的DFA如右图所示DECBFGAbaaaaaabbbbbba本讲稿第五十五页，共八十一页n正规式和有穷自动机的等价性表现在以下两个方正规式和有穷自动机的等价性表现在以下两个方面：面：1.对于上的一个正规式R，可以构造一个上的NFAN,使的L(N)=L(R)。2.对于上的一个NFAN，可以构造一个上的正规式R,使得L(R)=L(N)。4.4正规式和有穷自动机的等价性本讲稿第五十六页，共

30、八十一页4.4.1为上的正规式R构造相应的NFAM“语法制导”构造方法首先将正规式分解成一系列子表达式，然后按下列规则来构造NFAM：1)基本正规式基本正规式,a(a)对应的对应的NFA为：为：图4.4.1,a对应的状态转换图SSSaS1ZS1ZS1Z本讲稿第五十七页，共八十一页2)连接连接:设设R1和和R2都是正规式，则构造与正则表达式都是正规式，则构造与正则表达式R1R2等价的等价的NFA如图如图4.4.2：4.4.1为上的正规式R构造相应的NFAM图4.4.2R1.R2的状态转换图3)选择选择:设设R1和和R2都是正规式，则构造与正则表达式都是正规式，则构造与正则表达式R1|R2等价的等

31、价的NFA如图如图4.4.3：图4.4.3R1|R2的状态转换图SS1R1R2SS1S1R1R2S1ZS1ZSS1R1|R2SS1R1R2S1ZS1Z本讲稿第五十八页，共八十一页4.4.1为上的正规式R构造相应的NFAM4)重复重复:设设R是正规式，则构造与正规式是正规式，则构造与正规式R*等价的等价的NFA如图如图4.4.4图4.4.4R*的状态转换图对于任何正规式对于任何正规式,都可根据上述规则构造出等价都可根据上述规则构造出等价的的NFASS1R*SS1S1RS1ZS1Z本讲稿第五十九页，共八十一页4.4.1为上的正规式R构造相应的NFAM例4.4.1构造出与正规式R=(a)*(|b)(

32、a|b)*等价的NFA。解：设初始状态为0，目标状态为1，将整个正则表达式(a)*(|bb)(a|b)*看成一个整体,则状态图如图4.4.5所示01(a)*(|bb)(a|b)*图4.4.5正规式到NFA转换图1因R由(a)*,(|bb),(a|b)*连接而成，故展开连接后如图4.4.602(a)*31|bb(a|b)*图4.4.6正规式到NFA转换图2本讲稿第六十页，共八十一页4.4.1为上的正规式R构造相应的NFAM将重复展开后如图4.4.7所示0231|bba|b45a图4.4.7正规式到NFA转换图3将选择展开后，最终得到的NFA状态图如图4.4.8所示图4.4.8正规式到NFA转换图

33、40231a45a6bbb本讲稿第六十一页，共八十一页例4.4.2:构造正规式(0|1)*(000|111)(0|1)*对应的NFA，并对其进行化简。本讲稿第六十二页，共八十一页4.4.1将NFAM变为相应的正规式R由NFAM构造正规式相对较容易，处理方法与根据正规式构造NFAM的方法互逆。具体如下:1添加两个新的结点S和T，将S与NFAM上的所有初态结点相连，将T与所有终态结点相连，所有连接弧线上均标记为，从而使NFAM只有一个初态S和一个终态T。2逐步去掉NFAM中的结点，直到只剩下结点S和T。在去掉结点的过程中，逐步用正则表达式来标记弧线。去掉结点的规则如下:连接：设R1和R2都是基本正

34、则表达式，去掉结点，用弧线直接连接结点1和3，弧线上标记R1R2，如图4.4.9所示:13R1R2123R1R2图4.4.9由NFA构造正则表达式R1R2本讲稿第六十三页，共八十一页4.4.1将NFAM变为相应的正规式R选择:设R1和R2都是正规式，去掉标记为R1和R2的弧线并用一根弧线直接连接结点1和2，弧线上标记R1|R2。重复:设R是正规式，则构造与R*等价的NFA如图4.4.11图4.4.10由NFA构造正规式R1|R212R1|R212R1R213R*123R图4.4.11由NFA构造正规式R*例题4.4.1的逆过程即可作为此处实例来学习本讲稿第六十四页，共八十一页4.5 正规文法和

35、有穷自动机的等价性n从正规文法G直接构造一NFAN1.取N的字母表和G的终结符集相同。2.为G的每个非终结符生成N中的一状态，G的开始符对应N的开始状态。3.增加一个新状态Z作为NFA的终态。4.对G中形如AtB的规则，构造一转换函数f(A,t)=B5.对G中形如At的规则，构造一转换函数f(A,t)=Z反复使用上述规则对文法G中的规则进行替换即可得到等价的NFAN。本讲稿第六十五页，共八十一页4.5 正规文法和有穷自动机的等价性例题例题1：本讲稿第六十六页，共八十一页n从NFAN构造正规文法G1.对转换函数f(A,t)=B，可写一产生式AtB2.对可接受状态Z，增加一产生式Z3.有穷自动机的

36、初态对应文法开始符，字母表为文法的终结符集。4.5 正规文法和有穷自动机的等价性本讲稿第六十七页，共八十一页例题2：4.5 正规文法和有穷自动机的等价性本讲稿第六十八页，共八十一页4.6 词法分析程序的构造n根据DFA构造词法分析程序的方法直接编程的方法表驱动的实现方法n借助自动生成器Lex的构造方法本讲稿第六十九页，共八十一页1.直接编程的词法分析器直接编程的词法分析器直接编程的词法分析器是将DFA识别过程转化为程序，即用程序来模拟DFA的行为。可按下列步骤将DFA转换成程序流程图：1)初始状态对应程序的开始；2)终止状态对应程序的结束3)状态转移对应条件语句或分支选择语句；4)状态图的环对

37、应程序中循环语句；5)终态返回时，应满足最长匹配原则。4.6.1根据DFA构造词法分析程序的方法本讲稿第七十页，共八十一页4.6.1根据DFA构造词法分析程序的方法这种方法适合手工实现，编写出的词法分析程序比较精简，分析速度快。但这种词法分析程序与要识别的语言单词密切有关，通过程序的控制流转移来完成对输入字符的响应，程序中的每一条语句都与要识别的单词符号有关，一但语言的单词符号集发生变化，则要重新编写程序。故这种方法仅适合编写比较简单的词法分析程序。本讲稿第七十一页，共八十一页4.6.1根据DFA构造词法分析程序的方法2.表驱动的词法分析程序表驱动的词法分析程序表驱动的词法分析程序的模型如图4

38、.6.1所示。它由输入字符序列、分析表和控制程序组成。分析表就是DFA的状态转换矩阵，如图4.6.2。控制程序有两个参数，一个参数接受扫描的字符a，另一个参数为DFA的状态i。输入字符序列分析表控制程序图4.6.1表驱动的词法分析程序的模型状态 01S*BAACSBSCCAB图4.6.2分析表本讲稿第七十二页，共八十一页4.6.1根据DFA构造词法分析程序的方法其控制程序的算法是：1)在输入字符序列后面加一个字符#，叫结束符。将扫描指针设在输入序列的最左端，状态参数i设为开始状态。2)扫描下一字符a，如果是结束符#，则停止；否则，根据状态参数i和输入的字符a查分析表，将状态参数i设为查分析表（

39、i，a）后得到的状态。3)如果i是终态，则表示识别出一个单词转到4；否则转到2。4)处理识别出的单词，输出单词符号。状态参数i设为开始状态，转到2。本讲稿第七十三页，共八十一页4.6.1根据DFA构造词法分析程序的方法表驱动的词法分析程序是根据分析表的内容进行操作，与要识别的单词符号无关,是一种典型的数据与操作分离的工作模式。构造不同的词法分析程序实质上是构造不同的分析表，而控制程序是不变的。这为词法分析程序的自动生成提供了极大的方便。表驱动的词法分析程序相对直接编程方法来说，程序较复杂。由于在工作中需要查表确定分析动作，因此分析速度也慢一些。本讲稿第七十四页，共八十一页4.6.2借助工具Le

40、x的词法分析程序构造LEX（lexicalAnanlyzerGenerator）是一个词法分析程序的自动生成器。LEX是1972年贝尔实验室首先在UNIX上实现的。FLEX（FastlexicalAnanlyzerGenerator）是对LEX的扩充，它可在MS-DOS下运行。LEX能根据给定的正规式自动生成相应的词法分析程序。LEX的输入是用LEX语言写的源程序，生成一个用C语言描述的词法分析器，所以LEX本身就相当于LEX语言的编译程序。本讲稿第七十五页，共八十一页4.6.2借助工具Lex的词法分析程序构造一.使用Lex的一般步骤：单词的结构用正规式描述正规式NFADFAminDFA构造词

41、法分析程序二.用LEX建立词法分析程序的过程LEX源程序LEXYYLEX.CYYLEX.CC编译器YYLEX.EXE字符串源程序YYLEX.EXE符号串源程序本讲稿第七十六页，共八十一页三、lex源程序的格式lex源程序的一般格式是：说明部分%转换规则部分%辅助过程部分其中用花括号起来的各部分都不是必须有的。当没有“辅助过程部分”时，第二个%也可以省去。第一个%是必须的，因为它标志着识别规则部分的开始，最短的合法的lex源程序是：%它的作用是将输入串照原样抄到输出文件中。4.6.2借助工具Lex的词法分析程序构造本讲稿第七十七页，共八十一页转换规则部分是Lex源程序的核心。它是一张表，左边一列

42、是正规式，右边一列是相应的动作。下面是一条典型的识别规则：integerprintf（foundkeywcrdINT）;这条规则的意思是在输入串中寻找词形“integer”，每当与之匹配成功时，就打印出“foundkeywordINT”这句话。4.6.2借助工具Lex的词法分析程序构造本讲稿第七十八页，共八十一页4.6.2借助工具Lex的词法分析程序构造四、四、LEX使用步骤：使用步骤：1、编写LEX源程序，如“Cffx.l”，将“Cffx.l”与FLEX.EXE保存在同一文件夹下。2、进入DOS环境FLEX.EXE所在文件夹，运行FLEX.EXE程序。FLEXcffx.l3、运行FLEX后，

43、产生“LEXYY.C”程序4、用VC打开“LEXYY.C”程序，编译后产生“LEXYY.EXE”程序。5、编写TEST语言源程序，保存为AAA.TEST，并与“LEXYY.EXE”保存在同一文件夹下。6、进入DOS环境“LEXYY.EXE”所在文件夹，运行“LEXYY.EXE”程序。LEXYY.EXEAAA.TESTBBB.TXT7、打开“BBB.TXT”，看词法分析的结果。本讲稿第七十九页，共八十一页本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去进一步处理。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动自动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。本讲稿第八十页，共八十一页作业作业一：4课后习题1,2,3,4作业二：4上网查找整理Lex用法资料，下载信箱中的关于Test语言的资料并学习，准备实验一。邮箱：密码：computer2008本讲稿第八十一页，共八十一页