词法分析总结PPT课件

词法分析总结,1,.,词法分析在编译器中的位置,2,.,本章主要内容,词法分析器把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正则式、状态转换图和有限自动机概念,3,.,串，语言，正则表达式,4,.,串和语言,字母表：符号的有限集合，例:=0,1串：符号的有穷序列，例：0110,语言：字母表上的一个串集,0,00,000,句子：属于语言的串串的运算连接（积）xy,s=s=s幂s0为，si为si-1s（i0）,5,.,语言的运算,并：LM=s|sL或sM连接：LM=st|sL且tM幂：L0是，Li是Li-1L闭包：L=L0L1L2正闭包：L+=L1L2,6,.,正则表达式-元字符,7,.,有限自动机,8,.,不确定的有限自动机（简称NFA）,一个符号标记离开同一状态有多条边一个数学模型，它包括：1、有限的状态集合S2、输入符号集合3、转换函数move:S()P(S)4、状态s0是唯一的开始状态5、FS是接受状态集合,识别语言(a|b)*ab的NFA,9,.,确定的有限自动机（简称DFA),一个符号标记离开同一状态只有一条边1、有限的状态集合S2、输入字母集合3、转换函数move:SS，且可以是部分函数4、唯一的开始状态s05、接受状态集合FS,识别语言(a|b)*ab的DFA,10,.,从正则式到有限自动机,11,.,从正则式建立识别器的步骤,从正则式构造NFA把NFA变成DFA（子集构造法）将DFA化简（合并不可区别状态）,12,.,NFA-DFA:子集构造法,DFA的一个状态是NFA的一个状态集合读了输入a1a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk,0,0,1,0,2,未画完,13,.,子集构造法,14,.,子集构造法,-closure(s)从NFA的状态S出发，只用转换就能到达的状态的集合-closure(T)从NFA的状态集合T中每个状态出发，只用转换就能到达的状态的集合Move(T,a)状态集合T中每个状态通过a能到达的所有状态集合,15,.,子集构造法,找出U=-closure(T)对于U，以及任意符号a，找出U通过a能到达的集合V=Move(U,a)，并计算V=-closure(V)U通过a到达的状态即为V，U-a-V,16,.,DFA的化简,构造最简DFA：构造状态集合的初始划分：两个子集接受状态子集F和非接受状态子集SF应用下面的过程构造newFor中的每个子集G，dobegin把G划分为若干子集，G的两个状态s和t在同一子集中，当且仅当对任意输入符号a，s和t的a转换都到的同一子集中在new中，用G的划分代替GEnd如果new=，则final=；否则令=new，转上步在final的每个状态子集中选一个状态代表它，即为最简DFA的状态,17,.,DFA的化简,把G划分为若干子集，G的两个状态s和t在同一子集中，当且仅当对任意输入符号a，s和t的a转换都到同一子集中,18,.,正则表示-NFA,19,.,正则表示-NFA,20,.,正则表示-NFA,识别正则式st的NFA,21,.,正则表示-NFA,22,.,作业,1.构造下列正则式的NFA，给出他们处理输入串ababbab的状态转换序列(a|b)*(a*|b*)*(|a)b*)*2.将上述NFA转换为DFA，并