《编译原理 第8讲(第四章).ppt》由会员分享，可在线阅读，更多相关《编译原理 第8讲(第四章).ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 词法分析词法分析1.词法分析程序2.正规式、正规文法和正规集3.有穷自动机4.NFA的确定化、DFA的最小化5.正规式、正规文法和有穷自动机有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。由由NFA M构造正规式构造正规式r 从上的一个NFA M，构造上的,一个正规式r，使得L(M)=L(r)的方法。由NFA M构造正规式r步骤如下：(1)在NFA M的状态图中增加2个新节点：X和Y。从X节点到NFA M的所有初态
2、引 标记的弧，从NFA M的所有终态到Y节点引 标记的弧，形成一个新的NFA M，这个M只有一个初态X和一个终态Y。显然M与M等价。(2)逐步消去M的节，直至剩下X和Y节，消节的过程中，根据消节规则，逐步用正规式标记弧。消结规则消结规则 最后X至Y的标记则为所求的正规式消为123r1r2r1r213消为xy13r1r2r1|r2消为r13r1r*r2123r1r2例:M:03214starta,ba,ba,bbbaaNFA到正规式的例子到正规式的例子(2)消除M中的所有结点（消结规则参见消结规则参见P62）a|bx024yaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bxy(a
3、|b)*(aa|bb)(a|b)*解:(1)加x,yx03412yaa,ba,babb例子的解例子的解由正规式由正规式r构造构造NFA M 从上的一个正规式r，构造上的一个NFA M，使得L(M)=L(r)的方法。“语法制导语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：“语法制导”的方法的方法(1)R=,构造任一具有空终态集的NFA M(2)R=，构造的NFA M=(k0,f,k0,k0);f(k0,a)对于 所有a都没定义。(3)R=a,构造的NFA M=(k0,k1,f,k0,k1):f(k0,a)=k1 (4)R=R1|R2,将步骤（1）（2）（3）分别应用到
4、R1,R2；产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M=(K1K2k,f,k,F):k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a).若k1F1且k2F2，则 F=F1 F2；否则F=F1 F2 k“语法制导”的方法的方法(5)R=R1.R2 将步骤（1）（2）（3）分别应用到R1,R2；产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M=(K1K2,f,k1,F2):f包含f1和f2,且 f(k,a)=f1(k,a),当 kF
5、1时;f(k,a)=f2(k,a),当 k K2时;f(k1,)=k2,(6)R=R1*将步骤（1）（2）（3）分别应用到R1,产生M1=(K1,f1,k1,F1),构造的NFA M=(K1 k0,F0,f,k0,F0),其中 k0,F0 是新增加的两个状态,f(k,a)=f1(k,a),当 kF1时;f(k0,)=f(F1,)=k1,F0,对于正规式对于正规式R=,构造的构造的NFAFS对于正规式对于正规式R=,构造的构造的NFAFxy或或对于正规式对于正规式R=a ,构造的构造的NFAFSa对于正规式对于正规式r,r=R1|R2构造的构造的NFA对于正规式对于正规式r,r=R1 R2构造的
6、构造的NFA对于正规式对于正规式r,r=R1*构造的构造的NFA正规表达式正规表达式 1*0(0+1)*0+1 1*举例:从正规表达式构造等价的-NFA 1或或(0+1)*1*0(0+1)*举例:从正规表达式构造等价的-NFAR=(a|ab)*b b*有穷自动机和正规文法的等价性1.对于一个NFA M，都存在一个正规文法G,使得L(G)=L(M)。2.对于一个正规文法G，都存在一个NFA M，使的L(M)=L(G)。由正规文法由正规文法G构造构造NFA M定理：设G=(VN,VT,P,S)为一个正规文法，则存在一个有穷自动机NFA M=(K,f,S,Z)，使得L(M)=L(G)。M的构造方法：
7、=VT;S=S为G中每一个非终结符生成M的一个状态（不妨取成相同的名字），G的开始符号是M的开始状态S；增加一个新状态Z，作为NFA的终态；K=VN+Z若G中有形如A-tB的产生式，则令f(A,t)=B;若G中有形如A-t的产生式，则令f(A,t)=Z;GS:GS:SaA|bB|SaA|bB|AaB|bAAaB|bA BaS|bA|BaS|bA|SZABstartaaabbb求得：求得：例:求与文法GS等价的NFA由由NFA M构造正规文法构造正规文法G定理：已知一个有穷自动机NFA M=(K,f,S,Z)，则存在一个正规文法G=(VN,VT,P,S)，使得L(M)=L(G)。G的构造方法：V
8、N=K;VT=;S=SP:若f(A,t)=B,则A-tB在P中；对于可接受状态Z，增加产生式Z-;G=(G=(A,B,C,D,a,b,P,AA,B,C,D,a,b,P,AP:P:AaB|bDAaB|bD BbCBbC CaA|bD|CaA|bD|DaB|bD|DaB|bD|求得：求得：例:求与NFA等价的文法GSADBstartaaabbbbC关系图正则文法正则文法（右线性）（右线性）NFA正则表达式正则表达式123456DFA最小化最小化词法分析程序的自动构造 对有穷自动机和正规表达式进行了上述讨论之后,我们介绍词法分析程序的自动构造方法,这个方法基于有穷自动机和正规有穷自动机和正规表达式的
9、等价性表达式的等价性 正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序总结：总结：词法分析程序词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作。又如LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。习题习题P721（3）6712本章小结本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。