《词法分析程序的设计原则单词的描述技术识别机制及词法.pptx》由会员分享，可在线阅读，更多相关《词法分析程序的设计原则单词的描述技术识别机制及词法.pptx（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、单词的描述工具单词的识别系统设计词法分析程序,实现词法分析程序的自动构造第第1页页/共共69页页回顾回顾 什麽是词法分析程序4实现词法分析（lexical analysis）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。第第2页页/共共69页页 词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokenget token.源程序词法分析程序语法分
2、析程序源程序词法分析程序语法分析程序源程序第第3页页/共共69页页 词法分析程序的主要任务：读源程序，产生单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，第第4页页/共共69页页 词法分析工作从语法分析工作独立出来的原因：简化设计改进编译效率增加编译系统的可移植性 第第5页页/共共69页页单词的描述工具-正规表达式正规表达式 单词的识别系统-有穷自动机有穷自动机设计词法分析程序,实现词法分析程序的自动构造第第6页页/共共69页页令=a，b，上的正规式和相应的正规集的例子 a ab ab (ab)(ab)a (ab)(ab)(aabb)(ab)第第
3、7页页/共共69页页正规式正规式也称正则表达式,是定义正规集的数学工具。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），我们用以描述单词符号。第第8页页/共共69页页令=a，b，上的正规式和相应的正规集的例子 a ab ab (ab)(ab)a (ab)(ab)(aabb)(ab)aa,babaa,ab,ba,bb,a,aa,任意个a的串 ,a,b,aa,ab,bb 所有由 a和b组成的串 上所有含有两个相继的a或两个相继的b组成的串第第9页页/共共69页页 讨论两个例子例3.1 令=l，d，则上的正规式 r=l(l d)定义的正
4、规集为:l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和 多数程序设计语言允许的的标识符的词法规则.例3.2=d，e，+，-,则上的正规式 d(dd )(e(+-)dd)表示的是无符号数的集合。其中d为09的数字。程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义.第第10页页/共共69页页有穷自动机有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合.应用有穷自动机这个理论，为词法分析程序的自动构造寻找
5、有效的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata)。第第11页页/共共69页页关于有穷自动机有穷自动机我们将讨论如下题目确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化第第12页页/共共69页页确定的有穷自动机DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表
6、；第第13页页/共共69页页DFA定义3.f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.Z K是一个终态集，终态也称可接受状态或结束状态。第第14页页/共共69页页一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q第第15页页/共共69页页 DFA 的状态图表示bSUVQa
7、aaba，bb第第16页页/共共69页页DFA 的矩阵表示的矩阵表示字符字符状态状态0001第第17页页/共共69页页*上的符号串上的符号串t t被被DFADFA M M接受接受例例：证明证明t=baab被下图的被下图的DFA所接受所接受。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属于终态。属于终态。得证。得证。bSUVQabba,baa第第18页页/共共69页页DFA M所能接受的符号串的全体记为L(M).结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M
8、，使得V=L(M)。第第19页页/共共69页页DFA的行为很容易用程序来模拟.DFA M=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);c:=getchar;if K is in Z then return(yes)else return(no)第第20页页/共共69页页DFA =digit,not digit第第21页页/共共69页页不确定的有穷自动机NFA定义NFA M=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2 K）的一种映射，SK是初始状态集，Z K为终止状态集.第第22页页/共
9、共69页页例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Z f（P，1）=Zf（Z，0）=Pf（Z，1）=P第第23页页/共共69页页状态图表示SPZ00,1111第第24页页/共共69页页矩阵表示矩阵表示简化为第第25页页/共共69页页具有转移的不确定的有穷自动机f为K*到K的子集（2 K）的一种映射 123abc第第26页页/共共69页页有如下定理:对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。与上例等价的一个NFA.2acbb31acacbb第第27页页/共共6
10、9页页类似DFA,对NFA M=K，f，S，Z也有如下定义*上的符号串t在NFA M上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在NFA M上运行运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK.*上的符号串t被NFA M接受若t*，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M所接受接受（识别识别）第第28页页/共共69页页*上的符号串t被NFA M接受也可以这样理解 对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出
11、或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。第第29页页/共共69页页00011110100011100000010001100第第30页页/共共69页页NFA M所能接受的符号串的全体记为 L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。第第31页页/共共69页页(0|1)*(000|111)(0|1)*第第32页页/共共69页页确定有限自动机和不确定有限自动机确定有限自动机和不确定有限自动机 DFA是NFA的特例.对每个NFA N一定存在一个DFA，使
12、得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一.第第33页页/共共69页页 NFA确定化算法:假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(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；第第34页页/
13、共共69页页2 M和N的输入字母表是相同的，即是；3 转换函数是这样定义的：d(S1 S2,.Sj,a)=R1R2.Rt 其中 R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4 S0=-closure(K0)为M的开始状态；5 St=Si Sk.Se，其中Si Sk.SeS且Si,Sk,.SeKt第第35页页/共共69页页定义对状态集合I的几个有关运算：1.状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合状态集合
14、I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。第第36页页/共共69页页状态集合I的有关运算的例子I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa第第37页页/共共69页页构造NFA N的状态状态K K的子集的子集的算法：假定所构造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。1 开始，令-closure(K0)为C中
15、唯一成员，并且它是未被标记的。第第38页页/共共69页页2 while（C中存在尚未被标记的子集T）do 标记T；for 每个输入字母a do U:=-closure(move(T,a)；if U不在C中 then 将U作为未标记的子集加在C中 第第39页页/共共69页页 NFA的确定化 例子4f35621iaaaabbbb第第40页页/共共69页页4f35621iaaaabbbb第第41页页/共共69页页 等价的DFAaCDBAEFSbaaaaabbbbbabF第第42页页/共共69页页确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的
16、。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。第第43页页/共共69页页 DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性同是终态或同是非终态传播性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。第第44页页/共共69页页 C和D同是终态,读入a到达C和F,C和F同是终态,C和F读入a都到达C,读入b都到达E.C和
17、D等价aCDBAEFSbaaaaabbbbbabF第第45页页/共共69页页最小状态DFA对于一个DFA M=（K,f,k0,kt)，存在一个最小状态DFA M=（K,f,k0,kt)，,使L(M)=L(M).结论接受L的最小状态有穷自动机不计同构是唯一的。第第46页页/共共69页页“分割法”DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.第第47页
18、页/共共69页页 DFA的最小化算法 DFA M=（K,f,k0,kt),最小状态DFA M 1.构造状态的一初始划分：终态kt 和非终态K-kt两组(group)2.对施用过程过程PPPP 构造新划分new 3.如new =,则令 final=并继续步骤4，否则:=new重复2.4.为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r第第48页页/共共69页页 M 的开始状态是含有S0的那组的代表 M 的终态是含有F的那组的代表 5.去掉M中的死状态.第第49页页/共共69页页过程过程PPPP:Construc
19、tion of newFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a,states s and t have transitions on a to states in the same group of;/*at worst,a state will be in a subgroup by itself*/2.replace G i
20、n new by the set of all subgroups formed end 第第50页页/共共69页页 DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2:CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa第第51页页/共共69页页词法分析程序的自动构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍词法分析程序的自动构造方法,这个方法基于有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性,即即：1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，
21、可以构造一个上的NFA M，使的L(M)=L(R)。第第52页页/共共69页页从上的一个正规式R构造上的一个NFA M，使得L(M)=L(R)的方法。“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：第第53页页/共共69页页.“对于上的一个正规式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,将步
22、骤（1）（2）（3）分别应用到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第第54页页/共共69页页(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
23、)=f1(k,a),当 kF1时;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,F F0,f,k0,F0)其中 k0,F F0 是新增加的两个状态,f(k,a)=f1(k,a),当 kF1时;f(k0,)=f(F1,)=k1,F F0,第第55页页/共共69页页对于正规式R=,构造的NFA FS第第56页页/共共69页页对于正规式R=,构造的NFA F第第57页页/共共69页页对于正规式R=a ,构造的NFA FSa第第58页页/共共69页页对于正规
24、式r,r=R1|R2构造的NFA第第59页页/共共69页页对于正规式r,r=R1 R2构造的NFA第第60页页/共共69页页对于正规式r,r=R1*构造的NFA第第61页页/共共69页页正规表达式正规表达式 1*0(0+1)*举例举例:从从正规表达式正规表达式构造等价的构造等价的 -NFA0+1 1*第第62页页/共共69页页从从正规表达式正规表达式构造等价的构造等价的 -NFA(0+1)*1*0(0+1)*第第63页页/共共69页页R=(a|ab)*b b*第第64页页/共共69页页正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA
25、，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序第第65页页/共共69页页词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作 又如LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。第第66页页/共共69页页习题4.7 练习1（1）34(b)5第第67页页/共共69页页本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。第第68页页/共共69页页感谢您的观看。感谢您的观看。第第69页页/共共69页页