《《词法分析lly》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《词法分析lly》PPT课件.ppt（63页珍藏版）》请在金锄头文库上搜索。
1、第四章 词法分析考查重点考查重点1.基本概念基本概念：正规式正规式、正规集、有穷自动、正规集、有穷自动机机(DFA与与NFA）2.基本方法：基本方法：由正规文法或自然语言描述求正规式由正规文法或自然语言描述求正规式由正规式构造有穷自动机由正规式构造有穷自动机(FA)确定化确定化(NFADFA)，DFA最小化最小化正规文法与有穷自动机转换正规文法与有穷自动机转换4.1词法分析程序的设计词法分析程序的设计1、词法分析、词法分析（lexicalanalysis）逐个读入源程序字符并按照构词规则切分成一系列单词。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语
2、法分析程序调用词法分析程序来获得当前单词供语法分析使用。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。2、词法分析程序、词法分析程序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokengettoken.主要任务主要任务：读源程序，产生读源程序，产生单词符号单词符号其他任务其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符追踪换行标志，标志出错源程序，追踪换行标志，标志出错源程序，宏展开，宏展开，单词符号一般可分为下列五种：1、基本字（关键字）：if,while,等2、标识符标识符：如常量名、变量名、过程名等3、常数（量）：25,
3、3.1415,TRUE,“ABC”等4、运算符：如+-*/=等5、界符：逗号，分号，括号等输出表示（单词类别，单词自身的值）例：A:=B+2(2,指向指向A的符号表的入口指针的符号表的入口指针）(4,:=)(2,指向指向B的符号表的入口指针的符号表的入口指针)(4,+)(3,2)词法分析工作独立的原因：简化设计：词法分析比语法分析简单，如果与语法分析一起，会导致程序结构复杂。改进编译效率：编译的大部分时间花在扫描字符区分单词上，专门的词法分析可加快编译速度。增加编译系统的可移植性。4.2单词的描述工具词法词法：单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字单词的描述
4、工具：单词的描述工具：正规文法正规式一、正规文法与单词描述一、正规文法与单词描述1、正规、正规文法文法G=（VN，VT，P，S），P中每一产生式的形式都为：右线性：AaBAa左线性：ABaAa 其中AVN ，BVN ，aVT注注：正规文法中可能既右线性文法又左线性文法正规文法中可能既右线性文法又左线性文法?。2、程序设计语言几类单词的描述、程序设计语言几类单词的描述如：程序设计语言(l表示az中的任一英文字母,d表示09中的任一数字。)l|ll|d|l|dd|d+|-|*|/|=|=if|while|else无符号实数无符号实数：（其中s表示正或负号)无符号实数d余留无符号数|.十进小数|e指
5、数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数|指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|如25.55e+5和2.1思考思考：以上文法为几型文法？：以上文法为几型文法？二、正规式二、正规式和正规集正规集1、正规式正规式和正规集递归定义：正规集递归定义：字母表字母表 ，辅助表，辅助表 = ， ， ， ， ， ， 和都是上的正规式，它们所表示的正规集分别为和；任何a，a是上的一个正规式，它所表示的正规集为a；假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1
6、),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。仅由有限次使用上述三步骤而定义的表达式才是上的正规式正规式，仅由这些正规式所表示的字集才是上的正规集正规集。相关说明相关说明：其中“”读“或”（也可用“+”代替“”的）“”读“连接”；“”读“闭包”（任意有限次的自重复连接）连接符“”一般可省略不写。“(”,“)”并非正规式的运算符。规定算符的优先顺序为“”、“”、“”。“”、“”和“”都是左结合的。在不致混淆时，括号可省去。如：(r(s*)|r)=rs*|rr*(s*|r)圆括号不可略去例例4.2令=a，b，
7、上的正规式和相应的正规集的例子有：正规式正规集（特点特点）aaaba,bababa,a,a,任意个a的串(ab),a,b,aa,ab所有由a和b组成的串(ab)(ab)aa,ab,ba,bb(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串思考思考：表示上所有以a开始，以b结尾串的正规式？程序设计语言中的单词都可由正规式来定义：程序设计语言中的单词都可由正规式来定义：例=l，d，r=l(l d) 定义的正规集:l,ll,ld,ldd,（标识符标识符）例4.3=d，.，e，+，-,则上的正规式dd (.dd )(e(+ -)dd )表示的是无符无符号数号数的集合的集合。其中
8、d为09的数字。如：2，12.59,3.6e2,4.71e-1（参考P49）2、若两个正规式e1和e2所表示的正规集相同,则说e1和和e2等价等价,写作e1=e2。例如：e1=(a|b)，e2=b|a又如：e1=b(a|b)*,e2=b(b|a)*3、正规式的运算律、正规式的运算律设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=rr=rrr“或”的抽取律4、正规文法、正规文法正规语言正规语言正规式正规式正规
9、集正规集：由正规文法产生的语言称正规集（正规语言）正规集正规集是一个有穷或者无穷的集合，可用正规式(RegularExpression,Re)来描述。正规式正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要的表示法(记号)，是定义正规集的数学工具。正规式描述的集合称作正规集。正规文法与正规式具有等价性等价性。单词更适合用正规式（直观直观）来定义。对对 上的正规式上的正规式r,存在一个存在一个G=(VN,VT,P,S)使得使得L(G)=L(r)，反之亦然反之亦然。三、正规文法与正规式的等价性三、正规文法与正规式的等价性1、正规文法转换成正规式、正规文法转换成正规式方法：
10、由正规文法方法：由正规文法G的各个产生式写出对应的正规方的各个产生式写出对应的正规方程式，联立方程组。程式，联立方程组。引进引进S作为识别符号作为识别符号,利用以下利用以下规则做变换规则做变换文法产生式文法产生式正规式正规式规则规则1AxBByA=xy规则规则2AxA|yA=x*yAAx|yA=yx*规则规则3AxAyA=x|y变元是非终结符变元是非终结符，求解正规方程式组，最后开始符，求解正规方程式组，最后开始符号号S的解：的解：S=,VT*，即为正规式即为正规式。例例：文法GSSaASaAaAAdAAaAd转换过程如下：S=aA|a=a(A|)A=(aA|dA)|(a|d)=(a|d)A|
11、(a|d)A=(a|d)*(a|d)S=a(a|d)*(a|d)|)S=a(a|d)*/S=a(a|d)+|)？求求：文法GSSSc|BcBBb|AbAAa|a得正规式。S=Sc|Bc=Sc|aa*bb*c=aa*bb*cc*思考思考:什么条件下需要正规文法转换成正规式什么条件下需要正规文法转换成正规式?2、将正规式转换成正规文法、将正规式转换成正规文法引进引进S作为识别符号作为识别符号,VT=，VN与与P利用以下利用以下规则做变换产生：规则做变换产生：正规式正规式rSr正规式正规式xyAxBByB新引进新引进VN？正规式正规式x*yAxA|y正规式正规式x|yAxAy直到每个产生式直到每个产
12、生式最多含有一个终结符为止最多含有一个终结符为止。注意注意：正规式的字母表与正规文法的字母表：正规式的字母表与正规文法的字母表？例例：将r=a(ad)转换成相应的正规文法。Sa(ad)SaAA(a d) A(a d)A AGS:SaAAaAAdAA思考思考：正规式对应的正规文法唯一？语言？GS：SS(ad)a思考思考:什么条件下需要正规式转换成正规文法什么条件下需要正规式转换成正规文法?4.3有穷自动机有穷自动机1.确定的有穷自动机(DeterministicFiniteAutomata)2.不确定的有穷自动机(NondeterministicFiniteAutomata)3.NFADFA的转
13、换4.DFA的化简自动机相关概念自动机相关概念1、如果语言是无穷的，找出语言的有穷表示。途经：生成方式生成方式（文法文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式识别方式（自动机自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是是”，若不属于，要么能停止并回答“不是不是”，（要么永远继续下去。）2、为了构造词法分析程序，要研究构词法，每种词类的结构模式以及识别它的数学模型数学模型有穷自动机有穷自动机。有穷自动机有穷自动机作为一种识别装置，它能准确地识别正规集，即正规文法所定义的语言或正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程
14、序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：DFA和NFA。1、DFA定义定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中：其中：K K是一个有穷集，它的每个元素称为一个是一个有穷集，它的每个元素称为一个状态状态；是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，所以也称所以也称为为输入符号字母表输入符号字母表；f f是是转换函数转换函数，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态就意味着，当前状态为为ki
15、，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把我们把kj称作称作kiki的一个后继状态；（的一个后继状态；（单值函数单值函数）S SK K是是唯一唯一的一个的一个初态初态；Z Z K是一个是一个终态终态集集，终态也称，终态也称可接受状态可接受状态或或结束状态结束状态。一、确定的有穷自动机一、确定的有穷自动机DFA例：M=（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）=Qf（U，b）=Vf（Q，b）=Q2、的表示的表示：状态转换图状态转换图：设有m个状态和n个输入字符，图含
16、有m个状态结点，每个结点最多只能有n条弧从结点射出并与别的结点相连结，每条弧上的标记是字母表上的一个字符。图只有一个初态结点，用双箭头双箭头射入的节点表示初态，终态可由若干个，用双圆圈双圆圈表示。状态转换矩阵：状态转换矩阵：行表示状态，列表示输入字符，矩阵元素表示f(s,a)的值。2-1、DFA的状态图表示的状态图表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V,b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bb2-2、DFA的矩阵表示的矩阵表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a
17、）=Qf（U，b）=Vf（Q，b）=Q字符状态01003、DFA接受的字符串接受的字符串为了说明DFA如何作为一种识别机制,我们还要理解下面的定义 3-13-1、*上的符号串上的符号串t t在在M M上运行上运行一个输入符号串t，（我们将它表示成at1的形式，其中a，t1*）在DFAM上运行的定义为：f（A，at1）=f（f（A，a），t1）其中AK扩充转换函数f，是K*K上的映射，且： f（A，）=A3-2、*上的符上的符号号串串t被被M接受接受对于*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串等于t，则称t可为DFAM所接受，若M的初态结
18、同时又是终态结，则空字可为M所接受（识别接受（识别）。若t*，f(S，t)=P，其中S为DFAM的开始状态，PZ，Z为终态集。则称t为DFAM所接受（识别）接受（识别）。4、例例：证明：证明t=baab被如下的被如下的DFA所接受所接受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）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb证明证明：f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f
19、（Q，b）=QQ属于终态。得证。属于终态。得证。5、从状态转换图看、从状态转换图看：5-1、能被接受的字符串：存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则t被DFA接受。若初态同时也是终态，则空串可被接受。5-2、不能被接受的字符串：读完输入串，状态不停在终态；在读过程中出现不存在映射，使自动机无法继续动作。6、DFAM接受的语言接受的语言DFAM接受的全体字符串为接受的全体字符串为M接受的语言接受的语言,记为记为()。结论结论：上的一个字符串集上的一个字符串集V*是是正规正规的，当且仅当存在的，当且仅当存在一个一个上的确定有穷自动机上的确定有穷自动机M使得使得
20、V=L(M)。二、不确定的有穷自动机二、不确定的有穷自动机NFA1、定义、定义：M=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集的映像（多值函数多值函数），SK是初始状态集(初始态可多个初始态可多个)，ZK为终止状态集。例例NFAM=（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,11112-1、状态图表示、状态图表示思考思考：DFA与NFA的主要区别？2-2表格表示表格表示(较少采用较少采用？)简化简化NFAM=（S，P，Z，0，1，f，S，P，Z）其中其中f（S，0）
21、=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P3、相关说明相关说明：*上的符号串t在NFAM上运行*上符号串t被NFAM接受（识别）DFA是是NFA的特例的特例。SPZ00,11114、有穷自动机有穷自动机M=(K,f,S,Z）行为模拟程序行为模拟程序：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是是”，若不属于，要么能停止并回答“不是不是”K:=S；c:=getchar;whileceofdoK:=f(K,c);/？c:=getchar;ifKisinZthenreturn(yes)elsereturn(no)bSUVQaaaba，b
22、b以文件存串以文件存串baab为为例例三、三、NFA的确定化的确定化1、定理、定理：对任何一个NFAN，都存在一个DFAM，使L(M)=L(N).证明思想证明思想：子集构造法从NFA的矩阵表示中可以看出，表项通常是一状态集合状态集合，而在DFA的矩阵表示中，表项是一个状态一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应的每一个状态对应NFA的一组的一组状态状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.注注：与某一NFA等价的DFA不唯一不唯一。2、定义对状态集合定义对状态集合I的几个有关运算的几个有关运算状态集合I的-闭包： -closur
23、e(I)定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。约定约定状态集合I的任何状态都属于-closure(I)状态集合I的a弧转换：move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。例例：I=1,-closure(I)=1,2；move(1,a)=5,4；move(1,2,a)=？；-closure(5,3,4)=？； -closure（move(1,2,a)）12534687aaa3、NFADFANFAN=(K, ,f,K0,Kt)DFAM=(S, ,D,S0,St）M的状态集S由K的一些子集组成。用S1S2.Sj表
24、示S的元素，其中S1,S2,.Sj是K的状态。约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态是S1S2；M和N的输入字母表是相同的，即是；转换函数转换函数是这样定义的： D(S1,S2,.,Sj,a)=R1,R2,.,Rt其中：R1,R2,.,Rt= -closure(move(S1,S2,.,Sj,a)S0=-closure(K0)为M的开始状态；St=Si,Sk,.,Se，其中Si,Sk,.,SeS且Si,Sk,.SeKt4、构造、构造NFAN的状态的状态K的的子集子集的算法的算法：假定所构造的子集族为C，即C=(T0,T1,.TI),其中
25、T0,T1,.TI为状态K的子集。开始，令 -closure(K0)为C中唯一成员，并且它是未被标记未被标记的。while（C中存在尚未被标记的子集中存在尚未被标记的子集Ti）do标记标记T；for每个输入字母adoTi:= -closure(move(T,a)；ifTi不在C中then将Ti作为未标记的子集加在作为未标记的子集加在C中中5、例例将下图的将下图的-NFAN转换成转换成DFAM023456789101bbbaaNFAN思考思考：如何鉴别上图为：如何鉴别上图为NFA而非而非DFA？023456789101bbbaa状态状态-closure(move(Ti,a)-closure(mo
26、ve(Ti,b)T0=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8已存在T11,2,4,5,6,7,9加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8已存在T11,2,4,5,6,7已存在T2T3=1,2,4,5,6,7,91,2,3,4,6,7,8已存在T11,2,4,5,7,10加入为T4T4=1,2,4,5,7,101,2,3,4,6,7,8已存在T11,2,4,5,6,7已存在T2 -closure(0)=0,1,2,4,7初态终态b02134abaaaabbbDFAM思
27、考思考：若若NFAN无无 ，运算有何不同？运算有何不同？状态状态S-closure(move(Ti,a)-closure(move(Ti,b)T0=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8已存在T11,2,4,5,6,7,9加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8已存在T11,2,4,5,6,7已存在T2T3=1,2,4,5,6,7,91,2,3,4,6,7,8已存在T11,2,4,5,7,10加入为T4T4=1,2,4,5,7,101,2,3,4,6,7,8已存在T
28、11,2,4,5,6,7已存在T2四、四、DFA的最小化（化简）的最小化（化简）1、有穷自动机最小状态、有穷自动机最小状态DFA要求：要求：没有多余状态(死状态)多余状态多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。没有两个状态是互相等价（不可区别）两个状态两个状态s和和t等价等价：满足一致性s与t同是终态或同是非终态蔓延性对于任意任意a,f(s,a)=p,f(t,a)=q,p和和q必须等价必须等价2、消除多余状态、消除多余状态s1s5s2s7s2s5s5s7s5s6s3s1s8s0s0s1s3s601011000110s0s1s2s3s4s
29、5s6s7s8s1s5s2s7s2s5s5s7s5s6s3s1s8s0s0s1s3s601011000110s0s1s2s3s4s5s6s7s8s1s5s2s7s2s5s5s7s3s1s0s101011001s0s1s2s3s5s7思考思考：状态图中如何鉴别多余状态？状态图中如何鉴别多余状态？状态0和4是可区别可区别的。状态2和3是可区别的，why思考思考：有多余状态的吗？此图中四种状态都是可区别的吗？判定两个状态判定两个状态s和和t不等价不等价：只要找到一个w*,使f（s,w)F且f（t,w)!F，或者相反。b02134abaaaabbbDFAM3、状态不等价、状态不等价4、DFA最小化最小
30、化 对于一个对于一个DFA M =DFA M =（K,f, kK,f, k0 0,k,kt t) )，存在一个存在一个最小状态最小状态DFAM= =（K,f, kK,f, k0 0, ,k,kt t)，,使使L(M)=L(M).算法的核心算法的核心：把一个把一个DFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使使得任何不同的两子集的状态都是可区别的得任何不同的两子集的状态都是可区别的，而，而同一子集中同一子集中的任何两个状态都是等价的的任何两个状态都是等价的.结论：结论：接受接受L的最小状态有穷自动机的最小状态有穷自动机不计同构不计同构是是唯一唯一的。的。5、将下图中的、将下图中
31、的DFAM最小化最小化1,2,3,4,5,6,7Ia:6,7,1,4,7,4,4Ib:3,3,5,6,3,1,21,2,3,45,6,71,23,456,71,23456,71352746aaaaaaabbbbbbb13546aaaaabbbbb4.4正规正规式式和和有穷自动机有穷自动机的等价性的等价性1.对于上的NFAM，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFAM，使得L(M)=L(R)。1、自动机自动机 NFA M NFA M 正规式正规式R R在在M的状态转换图上的状态转换图上加进两个结点加进两个结点，x与与y结点。从结点。从x结
32、点用结点用弧连接到弧连接到M的的所有初态结点所有初态结点，从，从所有终态结所有终态结点点用用弧连接到弧连接到y结点。形成一个与结点。形成一个与M等价的等价的M,M只只有有一个初态一个初态x和和一个终态一个终态y。利用利用消去规则消去规则消去消去M中所有结点，直至剩下中所有结点，直至剩下x和和y。x和和y结点间弧上的标记则为所求正规式结点间弧上的标记则为所求正规式R。123R1R213R1R213R1R213R1|R2123R1R3R213R1R2*R3例例：03124a,baaa,ba,bbb求该求该NFA所对应的正规式所对应的正规式R.03124a,baaa,ba,bbbxy024a|baa
33、a|ba|bbbxy加进加进x与与y结点结点利用利用消去规则消去规则消去所有结点消去所有结点024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)*|bb(a|b)*xy(a|b)*(aa|bb)(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*x和和y结点间弧上的标记为结点间弧上的标记为正规式正规式R（熟练可直接写熟练可直接写）2、正规式正规式R R自动机自动机NFAM首先将首先将正规式分解为一系列子表达式，然后正规式分解为一系列子表达式，然后使用以下规则为使用以下规
34、则为R R构造自动机。构造自动机。简单（未含运算符）正规式对应简单（未含运算符）正规式对应NFA：R= R=R=a, , 设设s,t为为正规式，对应的正规式，对应的NFA为N(s)与N(t)。R=s|tR=st,R=s*例例:为为R=(a|b)*abb构造构造NFAN，23a54bR=(a|b)*abbR=(a|b)*abbR=(a|b)*abb2354ab16求解方法一：求解方法一：R=(a|b)*abbR=(a|b)*abb2354ab1607继续加上继续加上abb即可得到结果即可得到结果。如何作？如何作？2354ab16R=(a|b)*abbxiy(a|b)*abbxjyabbia|bx
35、jyabbiab求解方法二：求解方法二：继续对继续对abb进行分解。进行分解。说明说明：实际中常采用实际中常采用方法二这种思维（直观）方法二这种思维（直观）求求：正规式R（ab）*（a|b*）b等价的NFA注意验证！（考试）注意验证！（考试）4.5正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换1.正规文法正规文法G构造有穷自动机构造有穷自动机NFAM，使得L(M)=L(G)，采用下面的规则（右线性为例右线性为例）字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取称相同的名字）G的开始符号是开始状态S；增加一个新状态增加一个新状态Z，作为作为NFA的的终态终态；对
36、G中的形如AtB的产生式（其中t为终结符或，A和B为非终结符），构造M的一个转换函数f(A,t)=B；对G中形如At的产生式，构造M的一个转换函数f(A,t)=Z。例例：与文法：与文法GS等价的等价的NFAMGS：SaASbBSAaBAbABaSBbABSABZaabbab2.有穷自动机有穷自动机NFAM转换成正规文法转换成正规文法G，使得L(G)=L(M)，采用下面的规则：G的终结符集与字母表相同；M的每一个状态对应G中的每个非终结符,开始状态S是G的开始符号；转换函数f(A,t)=B对应G中的形如AtB的产生式（其中t为终结符或，A和B为非终结符）；对终态结点Z,在G中增加形如增加形如Z的
37、产生式的产生式。例例：SPZ00,1111思考思考：多个初态如何处理：多个初态如何处理？例：SPZ00,11114.6词法分析程序的自动构造工具词法分析程序的自动构造工具（了解）（了解）把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。LEX是典型的词法分析器是典型的词法分析器LEX编译系统知识体系结构知识体系结构考查重点考查重点1.基本概念基本概念：正规式正规式、正规集、有穷自动机、正规集、有穷自动机(DFA与与NFA）2.基本方法：基本方法：由正规文法或由正规文法或自然语言描述求正规式自然语言描述求正规式由由正规式构造有穷自动机正规式构造有穷自动机(FA)确定化确定化(NFADFA)，DFA最小化最小化正规文法与有穷自动机转换正规文法与有穷自动机转换作业：作业：p663，4补充习题1.构造一个状态数最小的DFA，它接受=0,1上所有倒数第二个字符为1的字符串。2.将下图的NFA确定化为DFA，并最小化。
