《词法分析》PPT课件

.,1,第四章词法分析,考查重点基本概念：正规式、正规集、有穷自动机(DFA与NFA）基本方法：由正规文法或自然语言描述求正规式由正规式构造有穷自动机(FA)确定化(NFADFA)，DFA最小化正规文法与有穷自动机转换,.,2,4.1词法分析程序的设计,1、词法分析（lexicalanalysis）逐个读入源程序字符并按照构词规则切分成一系列单词。,词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。,.,3,2、词法分析程序,主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，标志出错源程序，宏展开，,.,4,单词符号一般可分为下列五种：1、基本字（关键字）：if,while,等2、标识符：如常量名、变量名、过程名等3、常数（量）：25,3.1415,TRUE,“ABC”等4、运算符：如+-*/=if|while|else,.,8,无符号实数：（其中s表示正或负号)无符号实数d余留无符号数|.十进小数|e指数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数|指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|如25.55e+5和2.1思考：以上文法为几型文法？,.,9,二、正规式和正规集,1、正规式和正规集递归定义：字母表，辅助表=，和都是上的正规式，它们所表示的正规集分别为和；任何a，a是上的一个正规式，它所表示的正规集为a；假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。,.,10,相关说明：其中“”读“或”（也可用“+”代替“”的）“”读“连接”；“”读“闭包”（任意有限次的自重复连接）连接符“”一般可省略不写。“(”,“)”并非正规式的运算符。规定算符的优先顺序为“”、“”、“”。“”、“”和“”都是左结合的。在不致混淆时，括号可省去。如：(r(s*)|r)=rs*|rr*(s*|r)圆括号不可略去,.,11,例4.2令=a，b，上的正规式和相应的正规集的例子有：正规式正规集（特点）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结尾串的正规式？,.,12,程序设计语言中的单词都可由正规式来定义：例=l，d，r=l(ld)定义的正规集:l,ll,ld,ldd,（标识符）例4.3=d，.，e，+，-,则上的正规式dd(.dd)(e(+-)dd)表示的是无符号数的集合。其中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)*,.,13,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“或”的抽取律,.,14,4、正规文法正规语言正规式正规集：由正规文法产生的语言称正规集（正规语言）正规集是一个有穷或者无穷的集合，可用正规式(RegularExpression,Re)来描述。正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要的表示法(记号)，是定义正规集的数学工具。正规式描述的集合称作正规集。正规文法与正规式具有等价性。单词更适合用正规式（直观）来定义。,.,15,对上的正规式r,存在一个G=(VN,VT,P,S)使得L(G)=L(r)，反之亦然。,三、正规文法与正规式的等价性,1、正规文法转换成正规式方法：由正规文法G的各个产生式写出对应的正规方程式，联立方程组。引进S作为识别符号,利用以下规则做变换文法产生式正规式规则1AxBByA=xy规则2AxA|yA=x*yAAx|yA=yx*规则3AxAyA=x|y变元是非终结符，求解正规方程式组，最后开始符号S的解：S=,VT*，即为正规式。,.,16,例：文法GSSaASaAaAAdAAaAd转换过程如下：S=aA|a=a(A|)A=(aA|dA)|(a|d)=(a|d)A|(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*,思考:什么条件下需要正规文法转换成正规式?,.,17,2、将正规式转换成正规文法引进S作为识别符号,VT=，VN与P利用以下规则做变换产生：正规式rSr正规式xyAxBByB新引进VN？正规式x*yAxA|y正规式x|yAxAy直到每个产生式最多含有一个终结符为止。,注意：正规式的字母表与正规文法的字母表？,.,18,例：将r=a(ad)转换成相应的正规文法。,Sa(ad),SaAA(ad),A(ad)AA,GS:SaAAaAAdAA,思考：正规式对应的正规文法唯一？语言？,GS：SS(ad)a,思考:什么条件下需要正规式转换成正规文法?,.,19,4.3有穷自动机,确定的有穷自动机(DeterministicFiniteAutomata)不确定的有穷自动机(NondeterministicFiniteAutomata)NFADFA的转换DFA的化简,.,20,自动机相关概念,1、如果语言是无穷的，找出语言的有穷表示。途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）2、为了构造词法分析程序，要研究构词法，每种词类的结构模式以及识别它的数学模型有穷自动机。有穷自动机作为一种识别装置，它能准确地识别正规集，即正规文法所定义的语言或正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：DFA和NFA。,.,21,1、DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中：K是一个有穷集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；f是转换函数，是在KK上的映射，即，如f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；（单值函数）SK是唯一的一个初态；ZK是一个终态集，终态也称可接受状态或结束状态。,一、确定的有穷自动机,.,22,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）=Q,2、的表示：状态转换图：设有m个状态和n个输入字符，图含有m个状态结点，每个结点最多只能有n条弧从结点射出并与别的结点相连结，每条弧上的标记是字母表上的一个字符。图只有一个初态结点，用双箭头射入的节点表示初态，终态可由若干个，用双圆圈表示。状态转换矩阵：行表示状态，列表示输入字符，矩阵元素表示f(s,a)的值。,.,23,2-1、DFA的状态图表示,f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V,b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q,.,24,2-2、DFA的矩阵表示,f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q,0,1,0,0,.,25,3、DFA接受的字符串为了说明DFA如何作为一种识别机制,我们还要理解下面的定义3-1、*上的符号串t在M上运行一个输入符号串t，（我们将它表示成at1的形式，其中a，t1*）在DFAM上运行的定义为：f（A，at1）=f（f（A，a），t1）其中AK扩充转换函数f，是K*K上的映射，且：f（A，）=A,.,26,3-2、*上的符号串t被M接受,对于*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串等于t，则称t可为DFAM所接受，若M的初态结同时又是终态结，则空字可为M所接受（识别）。若t*，f(S，t)=P，其中S为DFAM的开始状态，PZ，Z为终态集。则称t为DFAM所接受（识别）。,.,27,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）=Q,证明：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（Q，b）=QQ属于终态。得证。,.,28,5、从状态转换图看：5-1、能被接受的字符串：存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则t被DFA接受。若初态同时也是终态，则空串可被接受。5-2、不能被接受的字符串：读完输入串，状态不停在终态；在读过程中出现不存在映射，使自动机无法继续动作。6、DFAM接受的语言DFAM接受的全体字符串为M接受的语言,记为()。结论：上的一个字符串集V*是正规的，当且仅当存在一个上的确定有穷自动机M使得V=L(M)。,.,29,二、不确定的有穷自动机NFA,1、定义：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）=P,2-1、状态图表示,思考：DFA与NFA的主要区别？,.,30,2-2表格表示(较少采用？),简化,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）=P,.,31,3、相关说明：*上的符号串t在NFAM上运行*上符号串t被NFAM接受（识别）DFA是NFA的特例。,.,32,4、有穷自动机M=(K,f,S,Z）行为模拟程序：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”K:=S；c:=getchar;whileceofdoK:=f(K,c);/？c:=getchar;ifKisinZthenreturn(yes)elsereturn(no),以文件存串baab为例,.,33,三、NFA的确定化,1、定理：对任何一个NFAN，都存在一个DFAM，使L(M)=L(N).证明思想：子集构造法从NFA的矩阵表示中可以看出，表项通常是一状态集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.注：与某一NFA等价的DFA不唯一。,.,34,2、定义对状态集合I的几个有关运算,状态集合I的-闭包：-closure(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)）,.,35,3、NFADFA,NFAN=(K,f,K0,Kt)DFAM=(S,D,S0,St）M的状态集S由K的一些子集组成。用S1S2.Sj表示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,.SeKt,.,36,4、构造NFAN的状态K的子集的算法：,假定所构造的子集族为C，即C=(T0,T1,.TI),其中T0,T1,.TI为状态K的子集。开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。while（C中存在尚未被标记的子集Ti）do标记T；for每个输入字母adoTi:=-closure(move(T,a)；ifTi不在C中then将Ti作为未标记的子集加在C中,.,37,5、例将下图的-NFAN转换成DFAM,NFAN,思考：如何鉴别上图为NFA而非DFA？,.,38,-closure(0)=0,1,2,4,7,.,39,初态,终态,DFAM,思考：若NFAN无，运算有何不同？,.,40,四、DFA的最小化（化简）,1、有穷自动机最小状态DFA要求：没有多余状态(死状态)多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。没有两个状态是互相等价（不可区别）两个状态s和t等价：满足一致性s与t同是终态或同是非终态蔓延性对于任意a,f(s,a)=p,f(t,a)=q,p和q必须等价,.,41,2、消除多余状态,思考：状态图中如何鉴别多余状态？,.,42,状态0和4是可区别的。状态2和3是可区别的，why思考：有多余状态的吗？此图中四种状态都是可区别的吗？判定两个状态s和t不等价：只要找到一个w*,使f（s,w)F且f（t,w)!F，或者相反。,DFAM,3、状态不等价,.,43,4、DFA最小化对于一个DFAM=（K,f,k0,kt)，存在一个最小状态DFAM=（K,f,k0,kt)，,使L(M)=L(M).算法的核心：把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.结论：接受L的最小状态有穷自动机不计同构是唯一的。,.,44,5、将下图中的DFAM最小化,.,45,4.4正规式和有穷自动机的等价性,对于上的NFAM，可以构造一个上的正规式R,使得L(R)=L(M)。对于上的一个正规式R，可以构造一个上的NFAM，使得L(M)=L(R)。,.,46,1、自动机NFAM正规式R在M的状态转换图上加进两个结点，x与y结点。从x结点用弧连接到M的所有初态结点，从所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态x和一个终态y。利用消去规则消去M中所有结点，直至剩下x和y。x和y结点间弧上的标记则为所求正规式R。,.,47,例：,求该NFA所对应的正规式R.,.,48,0,3,1,a,b,a,a,a,b,a,b,b,b,x,0,a|b,aa,a|b,a|b,bb,x,加进x与y结点,利用消去规则消去所有结点,.,49,.,50,0,a|b,aa(a|b)*,bb(a|b)*,x,0,a|b,x,aa(a|b)*|bb(a|b)*,x,(a|b)*(aa|bb)(a|b)*,(aa|bb)(a|b)*,R=(a|b)*(aa|bb)(a|b)*,x和y结点间弧上的标记为正规式R（熟练可直接写）,.,51,2、正规式R自动机NFAM首先将正规式分解为一系列子表达式，然后使用以下规则为R构造自动机。简单（未含运算符）正规式对应NFA：R=R=R=a,.,52,设s,t为正规式，对应的NFA为N(s)与N(t)。R=s|tR=st,R=s*,.,53,例:为R=(a|b)*abb构造NFAN，,R=(a|b)*abb,R=(a|b)*abb,R=(a|b)*abb,求解方法一：,.,54,R=(a|b)*abb,R=(a|b)*abb,继续加上abb即可得到结果。如何作？,.,55,R=(a|b)*abb,求解