《词法分析及词法分析程序精选PPT.ppt》由会员分享，可在线阅读，更多相关《词法分析及词法分析程序精选PPT.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、词法分析及词法分析程序第1页，此课件共54页哦设计扫描器应注意的问题l词法分析（3型）语法分析（2型）l单词的(Class,Value)二元组表示l标识符的长度限制和按“尽可能长”的识别策略l超前搜索与回退,=,状态转换图设G=(VN,VT,P,S)是一右线性文法,令|VN|=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个状态2.1)G的开始符S为初态状态3)终止状态,用F(VN)标记F是新加是新加(状态）节点状态）节点第4页，此课件共54页哦右线性文法=状态转换图aA-aBABA-aAFaA-消除，重用上述规则AFotherA若A为起始符（GA）A第5页，此
2、课件共54页哦产生式的消除SAXFabcotherYeSAXFabcYeS-aA A-b|bX X-c|eYS-aAA-bX X-c|eY第6页，此课件共54页哦状态图=右线性文法文法G00-a1S-aA1-d1A-dA1-bA-b0-cS-c0-c2S-cB，2有出弧2-dB-d0132abcdd第7页，此课件共54页哦左线性文法=状态转换图设G=(VN,VT,P,S)是一左线性文法,令|VN|=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个状态2.1)G的开始符S为终止状态3)起始状态,用R(VN)标记R是新加是新加(状态）节点状态）节点第8页，此课件共5
3、4页哦左线性文法=状态转换图aA-BaBAA-的的消除消除消除，重用上述规则RAother若A为起始符（GA）AA-aRAa不存在这不存在这种转换种转换第9页，此课件共54页哦状态图=左线性文法文法G31-aAa1-1dAAd3-1bSAb2-cBc3-2dSBd0132abcdd第10页，此课件共54页哦状态矩阵l状态矩阵Bij=BSi,aj=Skl当前状态，扫视字符，语义动作，后续状态l程序3-2第11页，此课件共54页哦识别无符号数的状态矩阵第12页，此课件共54页哦l语义 动作中的返回值ICON、FCON分别为整型数、浮点型数的值；l一般说来，无符号数具有形式ldmdm-1d0.d-1
4、d-nE dd l即dmdm-1d0d-1d-n*10(dd-n);l程序3-3关于状态无符号数识别矩阵第13页，此课件共54页哦DFA的形式定义DFA:Deterministic Finite Automata 一个DFA M定义为M=(K,f,S0,Z)，其中1)K=状态i2)=字母表，即输入字符i3)f:K -K，f为函数，表示某状态接受某个字母所到达的状态，如：f(p,a)=q,p,qK,a 4)S0 K，S0为初态5)Z K，且Z ，Z为终态集合第14页，此课件共54页哦DFA例子0132abcdd左侧的状态图，在数学上称作DFA，其形式化定义为M=(K,f,S0,Z)K=0,1,2
5、,3 l=a,b,c,d 源状态输入目的状态0a10C21d11b32d3f:S0=0Z=2,3 第15页，此课件共54页哦函数f的推广定义f f:K *-K，表示某状态接受一个字母串（而不是一个字母）所到达的状态，f的定义依赖于f的定义，f递归定义如下：1）f(p,)=p,if p K，即任意一状态p接受（串长为0）的输入，状态不变2）f(p,aw)=f(f(p,a),w),if p K,a ,w *第16页，此课件共54页哦函数f的推广定义f:例子 对于x=adb,x *，那么从状态0可以迁移到的状态p可以这样求出：P=f(0,adb)=f(f(0,a),db)=f(1,db)=f(f(1
6、,d),b)=f(1,b)=f(f(1,b),)=f(3,)=30132abcdd因为从初态0接受输入字母串adb后，迁移到f(0,adb)=3 Z，所以adb为DFA所识别 第17页，此课件共54页哦DFA所识别的语言令M 为一DFA，我们：定义L(M)=x|f(S0,x)Z,x *L(M)称为DFA M所识别的语言有定理：L(M)=L(G)，其中M为一DFA，G为一正规文法第18页，此课件共54页哦DFA关键特征状态迁移映射f是入射函数即f(x)f(y)蕴含 x y即对任意状态结点p，其出弧上的字母各不相同且不为从状态图角度，如出现下述情况的状态结点，则不是DFA（而是NFA）PQNaaQ
7、 NPQ P QWhy?第19页，此课件共54页哦NFA的形式定义一个NFA M定义为M=(K,f,S0,Z)，除f外其余成员与DFA相同，f定义为 f:K -(K)，其中(K)为集合K的幂集合，即有|(K)|=2|K|f 表示某状态接受某个字母所到达的状态集合，如：f(p,a)=q,m p,q,mK,a 第20页，此课件共54页哦映射f的推广定义ff:(K)*-(K)，表示某状态集合接受一个字母串（而不是一个字母）所到达的状态集合，f递归定义如下(依赖于f)：f(p,)=pf(p,a)=p1,p2,.if f(p,a)=p1,p2,if f(p,a)=f(p,aw)=f(f(p,a),w)其
8、中，其中，p,p1,p2 K,a ,w *属于什么？属于什么？第21页，此课件共54页哦NFA所识别的语言令N 为一NFA，我们：定义L(N)=x|f(S0,x)Z ,x *L(N)称为NFA N所识别的语言有定理：L(N)=L(M)=L(G)，其中N为一NFA，M为一DFA，G为一正规文法第22页，此课件共54页哦NFA例子 写状态迁移表fSABCabaaa,bba为什么是为什么是NFA源状态输入目的状态集合-SaA,CAaA,CAbA,BBaABbCCx 对每状态结点，按出对每状态结点，按出弧上的字母写出状弧上的字母写出状态迁移表态迁移表C行可以不填行可以不填f :K -(K)第23页，此
9、课件共54页哦NFA例子 接受串源状态输入目的状态集合-SaA,CAaA,CAbA,BBaABbCCx f :K -(K)当前状态当前状态 余留输入余留输入 后续状态后续状态 选择状态选择状态 S ababb A,C A or C?注意注意，NFA识别输入符号串时有一个试探过程，为了识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（能走到终态，往往要走许多弯路（带回溯带回溯），这影），这影响了响了NFA的效率。的效率。解决办法？解决办法？第24页，此课件共54页哦NFA与DFA的等价性定理定理3.13.1 对于字母表对于字母表 上的任一上的任一NFA N，必，必存在与存在与M等
10、价的等价的DFA M，使使L(N)=L(M)有了该定理，为提高有了该定理，为提高NFA识别字符串识别字符串的效率提供了的效率提供了tips：将将NFA转换为转换为DFA，即即NFA的确定化的确定化基本基本idea:DFA的的 f:K -KNFA的的f:K -(K)，将其改造为，将其改造为 f:(K)-(K)，并证明并证明f是入射函数是入射函数 且且f接收的串与接收的串与f接收的串相同接收的串相同第25页，此课件共54页哦例子S0S1abba,bq0q2a,babq1b第26页，此课件共54页哦带有动作的NFA例子 a b c S0 S0 S1,S2 S1 S1,S3 S2 S2 S3 S3 b
11、S0S1S3aS2c b 第27页，此课件共54页哦带有动作的NFAl-闭包-closure(S0)=S0,S1,S2,S3f(S,)=-closure(S)f(S,wa)=-closure(f(f(S,w),a)f(q,)通常不等于f(q,)lf(S0,)f(S0,)第28页，此课件共54页哦带有动作的NFA的确定化1)令令K=-closure(S0)(给出给出M的初态的初态q0)2)对于对于K中任一尚未标记的状态中任一尚未标记的状态qi=Si1,Si2,Sim，Sik K，作，作2.1)标记标记qi2.2)对于每个对于每个a ，置，置T=f(Si1,Si2,Sim,a)qj=-closur
12、e(T)2.3)若若qj不在不在K中，则将中，则将qj作为一个未加标记的状态添加到作为一个未加标记的状态添加到K中，中，且把状态转移添加到且把状态转移添加到M。3)重复进行步骤重复进行步骤2)，直到，直到K中不再含有未标记的状态为止，对中不再含有未标记的状态为止，对于由此构造的于由此构造的K，我们把那些至少含有一个，我们把那些至少含有一个Z中的元素的中的元素的qi作为作为M的终态。的终态。第29页，此课件共54页哦S0S1S3aS2c b b第30页，此课件共54页哦DFA状态数最小化l可区分状态ABa1a2ana1a2状态状态A,B被某一输入串被某一输入串w=a1a2.an所区分，指所区分，
13、指1）从其中一个状态出发读入）从其中一个状态出发读入w，到达，到达终态终态，2）而从另一个状态出发进入）而从另一个状态出发进入非终态非终态第31页，此课件共54页哦可区分状态的递归定义在一个在一个DFA中，状态中，状态A与状态与状态B可区分：可区分：1）A是终止状态，是终止状态，B是非终止状态是非终止状态或或 B是终止状态，是终止状态，A是非终止状态是非终止状态2）对于字母）对于字母a，有，有f(A,a)=C,f(B,a)=D2.1)C与与D可区分可区分2.2)C=NULL 且且 D NULL且且D可达终态可达终态或或 C NULL且且C可达终态可达终态 且且 D=NULL第32页，此课件共5
14、4页哦DFA状态数最小化-例子S0S1S3S2babbaaabS4ab第33页，此课件共54页哦复习l一个DFA M=(K,f,S0,Z)，函数f:K -K表示某状态Ki接受某字母a后，到达状态状态Kj的转换。l一个NFA M=(K,f,S0,Z)，函数f:K -(K)表示某状态Ki接受某字母a后，到达状态集合状态集合K1,Kj的转换。l一个带动作的NFA M=(K,f,S0,Z)，函数 f:K -(K)表示某状态Ki接受某字母a或或空串空串 后，到达状态集合K1,Kj的转换。第34页，此课件共54页哦试描述下述文法所产生的语言的特点lGS=(VN=S,VT=AZ,az,09,P,S),其中P
15、=S S，S S，S ，A，z，0，9 第35页，此课件共54页哦上述正规文法产生的语言的特点是l由字母开头，后接0个或多个字母和(或)数字的符号串l即标识符的定义l如果使用型如 字母(字母|数字)*的式子来表示上述符号串构成的集合，那么这样的式子就称为正规表达式(正则式，Regular Expression)，相应的符号串集合则称为该表达式对应的正规集。第36页，此课件共54页哦正规表达式及正规集的定义正规式 正规集1.空集2.3.a，a a4.(r)(s)Lr Ls(r)|(s)Lr Ls(r)*Lr*r=(r)|()Lr (r)+=(r)(r)*)Lr+第37页，此课件共54页哦算符优先
16、级与正规式化简 算符优先级从高到低依次为(),*,+,|如(r)(s)*)|(r)，可化简为 r s*|r 又因为连接符通常可省略不写，再化简为rs*|r第38页，此课件共54页哦正规式与正规集的例子=a,b第39页，此课件共54页哦正规式与正规集的多对一关系l给定一个正规式，它唯一确定一个正规集；反之不然。l即一个正规集可由多个不同的正规式表示。l我们称两个正规式等价，当且仅当它们所描述的正规集相同。l例如a|b与b|a,(a|b)*与(b|a)*等等第40页，此课件共54页哦正规式的基本等价公理A1.r|s=s|rA2.r|r=r A3.r|=r A4.(r|s)|t=r|(s|t)A5.
17、(rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|trA8.r=r=A9.r=r=rA10.r*=(|r)*=|rr*第41页，此课件共54页哦由正规文法构造正规式1/4使用正规式描述下述右线性文法产生的语言1)S aS|b2)S aS|bS|c (或S (a|b)S|c)3)S abS|c 总结出规律:S S|对应的正规式是*第42页，此课件共54页哦由正规文法构造正规式2/4使用正规式描述下述左线性文法产生的语言1)S Sa|b2)S Sa|Sb|c (或S S(a|b)|c)3)S Sab|c 总结出规律:S S|对应的正规式是*第43页，此课件共54页哦由正
18、规文法构造正规式3/4如果将“|”用“+”替换，“”用“=”替换，那么可以将产生式转换为方程的形式，于是对上述两个规律，我们得到论断：论断论断3.1 方程X=X+（对应S S|），有解 X=*论断论断3.2 方程X=X+（对应 S S|），有解 X=*第44页，此课件共54页哦由正规文法构造正规式4/4于是，对文法GS SaS|bA|b AaS 我们可以将所有产生式的运算符“|”用“+”替换，“”用“=”替换，再以我们习掼的线性方程组求解方法来求解S对应的正规式。第45页，此课件共54页哦例子l1)SaS|bA|b,AaSl2)SaA,AbA|aB|b,BaAl3)SbS|aA,AaA|bB,
19、BaA|bC|b,CbS|aA第46页，此课件共54页哦练习l1)SaS|bA|c,AbSl2)SaA,AaA|bB|c,BcS第47页，此课件共54页哦由正规式构造FAThompson法S0SfS0S0Sfa当当n=0n=0r=r=r=al根据正规式所含运算符个数n递归给出。第48页，此课件共54页哦r=r1|r2r1S01r2S02s0Sf 不再是初态不再是终态Sf1Sf2第49页，此课件共54页哦r=r1 r2r1 S01Sf1r2S02Sf2 第50页，此课件共54页哦r=r*S01Sf1sSf 第51页，此课件共54页哦例子与练习例子：1）a(b|aa)*b2）(0*|1)(1*0)
20、*练习：1）ab|c*2）(b|aa|ac|aaa|aac)*第52页，此课件共54页哦综合练习1l对文法GS=(S,A,B,a,b,P,S)，其中P=S aS|aA,A bA|bB B aB|al1)使用正规式描述该文法产生的语言l2)构造识别上述正规式的NFAl3)对上述NFA确定化和最小化得到DFAl4)对上述DFA，写出相应左线性文法第53页，此课件共54页哦综合练习2l对文法GS=(S,A,B,a,b,P,S)，P=S Aa,A a|Ab|Ba B Aal1)使用正规式描述该文法产生的语言l2)构造识别上述正规式的NFAl3)对上述NFA确定化和最小化得到DFAl4)对上述DFA，写出相应右线性文法第54页，此课件共54页哦