编译原理第3章第1节词法分析、DFA、NFA及其转换.ppt

第三章 词法分析,主要内容1.介绍词法分析的过程2.讨论词法分析器的设计与实现3.介绍实现词法分析器的主要工具：状态转换图,第三章 词法分析,3.1 词法分析器的任务,人们理解一篇文章（或程序）起码是先在单词级别上思考。编译程序要分析和翻译源程序，也先要区分一个一个的单词。词法分析程序的任务是：从左到右逐个字符对源程序扫描，产生一个单词序列，把作为字符串的源程序改造为单词符号串的中间程序。词法分析程序又称词法分析器或扫描器。,除了识别单词的基本任务外，词法分析还可以完成以下任务：（1）组织源程序的输入（2）删除注释、空格及无用符号（如回车等）（3）行、列计数（4）列表打印源程序（5）发现并定位词法错误（6）建立、查填符号表,3.1.1 单词符号的表示,基本字：也称关键字，如C语言中的int,void,if,while等；标识符：用来表示各种名字，如变量名、常量名、函数名等；常数：如25,3.1415926,a,“hello”,TRUE等；算符：如+,=,等；界符：如逗号，分号，括号等。基本字、运算符和界符一般确定；标识符和常数的数量一般不加限制。注：（1）程序设计语言单词的分类纯属技术性问题，可以有不同的方法分类；（2）除上述一般分类方法外，还有一字一类或一符一类等方法,单词的分类，如：while(i 10)i+;,单词的分类,单词分类的原则,保留字（关键字）：可以看作一类，也可以一字一类；算符和界符：可以一符一类，算符还可以把有一定共性算符分为一类；常数：可以按照数据类型分类；标识符：统一归为一类。,3.1.1 单词符号的表示,单词的分类,3.1.1 单词符号的表示,单词经常表示为二元组：(单词类别,单词值)对某些单词来说，不仅需要它们的值，还需要一些其它信息，这些都记录在符号表中，所以相应表示为：(标识符，指向该标识符所在符号表中位置的指针),(单词类别,单词的属性),区分单词所属的类(整数编码),单词的值,单词的表示,3.1.1 单词符号的表示,输出：(3,“while”)(5,“(“)(1,指向i的符号表入口)(4,“=“)(1,指向j的符号表入口)(5,“)”)(1,指向i的符号表入口)(4,“-”)(5,“;”),例：while(i=j)i-;,单词的表示：举例,3.1.2 词法分析器的结构,字符串形式的源程序,词法分析器与语法分析器的联系,（1）词法分析作为单独的一遍,3.1.2 词法分析器的结构,将词法分析器分离的考虑,使整个编译程序的结构更简洁、清晰和条理化；编译程序效率更高；增强编译程序的可移植性。,(2)词法分析作为子程序,输入串,词法分析器,语法分析器,符号表,取下一单词,返回下一单词,词法分析器与语法分析器的联系,3.1.2 词法分析器的结构,扫描缓冲区,1.预处理程序：取消注解，剔除无用的空白、跳格、回车、换行等2.输入缓冲区：源程序输入缓冲区,3.1.2 词法分析器的结构,主要是为方便单词的识别工作：,（1）剔除无用的空白符、跳格符、回车符、换行符。,t,r,n,（2）剔除注释：/*/,/,（3）合并空白符。,预处理程序,例：int max(int x,int y)/求x,y的最大值int z;z=(x y?x:y);return z;,预处理后：int max(int x,int y)int z;z=(xy?x:y);return z;,3.1.2 词法分析器的结构,预处理程序,3.1.2 词法分析器的结构,缓冲区的设计,起点指针：用来指示正在扫描的单词的起点；搜索指针：用于向前搜索，寻找单词的结束；缓冲区结构,扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。扫描缓冲区的结构：,假设标识符和常数的最大长度为256,缓冲区长度：512,3.1.2 词法分析器的结构,：设置左右两个缓冲区，当左缓冲区读完后，新读入的字符存入右缓冲区；反之，存放在左缓冲区；,缓冲区的设计,小结,词法分析器的任务；单词符号的分类；单词符号的表示；词法分析预处理；词法分析器的工作方式；扫描缓冲区的双缓冲策略。,3.2.1 正规式与正规集,正规式（正规表达式）：用以描述单词符号的工具，是说明单词的模式的一种重要的表示法,是定义正规集的工具。一个正规式对应一个正规集,正规式和正规表达式,3.2.1 正规式与正规集,对字母表：(1)和都是上的正规式，它们所表示的正规集分别为和；(2)a，a是上的一个正规式，它所表示的正规集为a；(3)假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么(U|V)、(UV)和(U)*也是正规式，它们所对应的正规集分别为L(U)L(V)、L(U)L(V)和(L(U)*。仅由有限次使用上述三步骤得到的表达式才是正规式，仅由这些正规式所表示的字集才是上的正规集。,例3.1 令=a，b,ba*上所有以b为首，后跟任意多个a的字符串；a(a|b)*上所有以a为首的字符串；(a|b)*(aa|bb)(a|b)*上含两个连续a或两个连续b的字符串。,正规式和正规表达式,3.2.1 正规式与正规集,例3.1 令=a，b,正规式 aa|bab(a|b)(a|b)a*(a|b)*(a|b)*(aa|bb)(a|b)*,正规集 aa,babaa,ab,ba,bb,a,a,任意个a的串,a,b,aa,ab 所有由a和b组成的串*上所有含有两个相继的a或两个相继的b组成的串,能被5整除的十进制整数的正则表达式,规则（1）：表达式的头部为：-、+或，表示整数的正、负规则（2）：十进制整数的尾部以0或者5结束规则（3）：整数的中部是任意0-9组成的数字串,3.2.1 正规式与正规集,(+|-|),(0|1|9)*,(0|5),常用的正规式,整数：(+|-|)(0|1|9)(0|1|9)*,浮点数：(+|-|)(0|1|9)*.(0|1|9)(0|1|9)*,标识符：(a|z|A|Z|_)(a|z|A|Z|_|0|9)*,3.2.1 正规式与正规集,正规式的关系,交换律：U|V=V|U；结合律：U|(V|W)=(U|V)|W；U(VW)=(UV)W；分配律：U(V|W)=UV|UW；(V|W)U=VU|WU；U=U=U。,3.2.2 状态转换图(TG),转换图是一张有限方向图；结点表示状态，用圆圈表示；状态之间用有向弧连接；有向弧上的标记(字符)表示在射出结点所代表的状态下可能出现的输入符号或符号串；一张转换图只包含有限个状态，且有一个初态，至少有一个终态；一个状态转换图可用于识别(或接受)一定的字符串，如(a|b)*(aa|bb)(a|b)*。,状态转换图,3.2.2 状态转换图(TG),状态转换图的作用：（1）识别字符串是否为文法的句子（单词）方法：从文法的开始符号出发，按照与符号串预留部分中最左字符相匹配的原则游历状态图，直到符号串的末端为止。如果这时恰好到达终止状态，则符号串为文法的句子，否则不是,如利用转换图判定字符串：(1)ab(2)aab(3)aa,状态转换图的作用,3.2.2 状态转换图(TG),状态转换图的作用：（2）根据状态图可构造相应的语法分析程序。画出状态转化图。由正则文法或正则式构造状态转换图。由状态转换图编写程序。对于状态转换图中每一个状态构造一段代码，代码的功能是从输入串中读入一个字符；判断读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态。均不匹配时便失败，即不能到达正常入口。,状态转换图的作用,3.2.3 确定有限自动机(DFA),一个DFA M是一个五元组，M=(K,f,S,Z):(1)K：状态集；(2)：字母表；(3)f：从K到K的单值部分映射，即f(ki,a)=kj；(4)SK，是唯一的初态；(5)ZK，是终态集。,当前状态和输入字符只能确定下一个状态,3.2.3 确定有限自动机(DFA),DFA M=(K,f,S,Z):(1)K=0,1,2,3;(2)=a,b;(3)f：f(0,a)=1,f(0,b)=2,f(1,a)=3,f(1,b)=2,f(2,a)=1,f(2,b)=3,f(3,a)=3,f(3,b)=3(4)S=0；(5)Z=3。,例1：构造DFA，使其能接受所有由偶数个0和偶数个1所组成(01)字符串。,分析问题的状态空间：,0：包含偶数个0偶数个1；,1：包含偶数个0奇数个1；,2：包含奇数个0偶数个1；,3：包含奇数个0奇数个1。,不管串处于哪一种情况，只要再添加一个0或1，就会转换到另一种情况。,0,1,2,3,3.2.3 确定有限自动机(DFA),例2：构造DFA，使其能接受=0,1上能被4整除的二进制数,分析问题的状态空间：,任意二进制数除以4，只有余数为0、1、2、3四种情况。,1,2,3,一个二进制数后面加0，相当于变为原来的2倍；后面加1，相当于变为原来的2倍加1。,若x mod 4=0,则：2x mod 4=0;(2x+1)mod 4=1,若x mod 4=1,则：2x mod 4=2;(2x+1)mod 4=3,若x mod 4=2,则：2x mod 4=0;(2x+1)mod 4=1,若x mod 4=3,则：2x mod 4=2;(2x+1)mod 4=3,3.2.3 确定有限自动机(DFA),例3：一个人带着狼、山羊和白菜要从一条河左岸渡到右岸。有一条船，恰好能装下人和其它三件东西中的一件。用有限自动机找出渡河方案。,左岸存在的东西作为状态，初始为人、狼、羊、白菜都在左岸，接受状态为都不在左岸。,（人、狼、羊、白菜）,（人、狼、羊）,（人、狼、白菜）,（人、羊、白菜）,（人、狼）,（人、羊）,（人、白菜）,（狼、羊、白菜）,（狼、羊）,（狼、白菜）,（羊、白菜）,（人）,（狼）,（羊）,（白菜）,3.2.3 确定有限自动机(DFA),用G(x)表示人带x从左岸到右岸，R(x)表示从人带x右岸回到左岸；G和R分别代表人自己去到右岸或回到左岸。,0,1,2,3,4,6,7,8,5,0,1,2,3,4,6,7,8,5,G(羊),G(狼),G(白菜),G(羊),R,R,R(羊),05283749步骤：G(羊)5(狼,白菜)R2(人,狼,白菜)G(狼)8(白菜)R(羊)3(人,羊,白菜),(5)G(狼)7(羊)(6)R4(人,羊)(7)G(羊)9(),问题：,任给一个正规式，如(a|b)*(aa|bb)(a|b)*，如何构造其DFA？,(a|b)*(aa|bb)(a|b)*,NFA M=(0,1,2,3,4,5,a,b,f,0,5)f:f(0,a)=0,1,f(0,b)=0,1,f(1,a)=2,f(1,b)=3,f(2,a)=4,5,f(2,b)=,f(3,a)=,f(3,b)=4,5,f(4,a)=5,f(4,b)=5,f(5,a)=5,f(5,b)=5.,3.2.4 非确定有限自动机(NFA),一个NFA M是一个五元组，M=(K,f,S,Z):(1)K：状态集；(2)：字母表；(3)f：从K*到K的子集映像；(4)SK，是初态集；(5)ZK，是终态集。,DFA和NFA在使用上各自的优点和缺点在哪里？,DFA编程实现容易，但构造难NFA构造容易，但编程实现有回溯,能否找到一个从NFA到DFA的自动转换算法？,3.2.4 非确定有限自动机(NFA),文法、正规式、DFA(NFA)之间的关系,正则文法（3型文法）,正规式,DFA,NFA,3.2.5 NFA确定化为DFA,NFA M=(K,f,S,Z)，DFA M1=(K1,1,f1,S1,Z1)字母表不必转换；开始状态：DFA中只有一个，NFA中有多个。转换函数：DFA是从K到K的映像，而NFA是从K*到K的子集的映像。,区别：K到K的映像 K*到K的子集,3.2.5 NFA确定化为DFA,可以引入新的状态X，作为新的NFA的初始状态，然后从X向原NFA的每个初始状态引弧。,一、多个初始状态向单个初始状态的转换：,二、K*K子集KK,K*K子集K()K子集KK,3.2.5 NFA确定化为DFA,（1）K*K子集 K()K子集,3.2.5 NFA确定化为DFA,(a|b)*(aa|bb)(a|b)*,例：将下面的TG进行转换，使其弧上或为单个字符，或为。,0,2,3,0,2,3,K*K子集 K()K子集 KK,3.2.5 NFA确定化为DFA,（2）K()K子集KK,0,1,a,3,0,A,I,_Closure(I),若qI，则q_Closure(I)；,若qI，q=f(q,),则q_Closure(I)。,3.2.5 NFA确定化为DFA,0,1,a,2,3,a,0,A,若I=S1,S2,Sk,则定义move(I,a)=f(S1,a)f(S2,a)f(Sk,a),Ia=_Closure(move(I,a);,I,（2）K()K子集KK,3.2.5 NFA确定化为DFA,0,1,a,2,3,a,4,5,b,b,0,A,B,0,1,2,3,1,2,3,4,5,4,5,假设=a1,ak,开始状态为X，线性规划算法：,(1)构造一个有k+1列的表；,(2)首行首列为_Closure(X);,(3)若某行第1列已经确定，则置该行i+1列为Iai;,(4)若该行某项未在该表第一列出现，则填入该表后面空行的第一列；,(5)重复(3)(4)，直到所有项均在第一列出现。,3.2.5 NFA确定化为DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step1:构造NFA,3.2.6 构造正规式的DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step2:使NFA初态和终态都唯一,X,3.2.6 构造正规式的DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step3:使NFA每条箭弧上或为单个字符a,或为,3.2.6 构造正规式的DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step4:确定可合并状态,X,1,2,1,2,3,1,2,3,1,2,4,1,2,4,1,2,3,5,6,Y,1,2,3,5,6,Y,1,2,4,1,2,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,1,2,4,6,Y,1,2,3,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,3.2.6 构造正规式的DFA,X,1,2,1,2,3,1,2,3,1,2,4,1,2,4,1,2,3,5,6,Y,1,2,3,5,6,Y,1,2,4,1,2,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,1,2,4,6,Y,1,2,3,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,S,a,b,0,1,2,3,1,2,3,0,6,1,1,1,1,1,1,1,2,4,1,2,4,2,2,2,2,2,2,1,2,3,5,6,Y,1,2,3,5,6,Y,1,2,3,5,6,Y,3,3,3,3,3,3,3,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,4,5,6,Y,4,4,4,4,4,4,4,4,1,2,4,6,Y,1,2,4,6,Y,5,5,5,5,5,5,1,2,3,6,Y,1,2,3,6,Y,6,6,6,6,6,Step5:合并状态,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,3.2.6 构造正规式的DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step6:构造DFA,例：构造正规式(a|b)*(aa|bb)(a|b)*的DFA,Step7:确定初态和终态,3.2.6 构造正规式的DFA,总结：NFA确定化为DFA,使初态和终态均唯一；使NFA的每个箭弧上或为单个字符，或为；NFA中，=a1,ak,将NFA确定化：（1）构造一张含有k+1列的表，置该表首行首列为_Closure(X)；（2）若某一行第一列已确定，则置第i+1列为Iai，若该行某列未在该表第一列出现过，就将其加入到该表第一列最后一行；（3）重复上述过程，直至出现在第i+1列上的所有状态子集均在第一列上出现过；（4）将每个状态子集合并为一个状态，根据得到的状态转换矩阵构造DFA。DFA的初态为首行首列的状态，终态为那些含有原终态的状态子集。,与原来给出例题的比较,有四个终态,只有一个终态,1、DFA是否可化简？2、如何化简？3、怎样才是最简DFA？,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step1：构造NFA,正规式：(00|11|(01|10)(00|11)*(01|10)*,Step2 使每条弧上或为，或为单个字符,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step2 使每条弧上或为，或为单个字符,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step2 使每条弧上或为，或为单个字符,Step3 使初态和终态都唯一,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step4 寻找可合并状态,0,1,2,1,5,8,5,8,6,9,6,9,1,2,1,2,3,4,7,3,4,7,3,4,7,1,2,5,8,6,9,10,12,10,12,11,13,11,13,4,7,4,7,1,2,1,2,4,7,10,12,11,13,Step5 合并状态,0,1,2,5,8,5,8,6,9,6,9,1,2,1,2,3,4,7,3,4,7,3,4,7,1,2,5,8,6,9,10,12,10,12,11,13,11,13,4,7,4,7,1,2,1,2,4,7,10,12,11,13,3,4,7,0,0,5,8,5,8,1,1,1,1,1,1,6,9,6,9,2,2,2,2,2,2,1,2,1,2,1,2,1,2,3,3,3,3,3,3,3,3,3,3,3,4,7,4,4,4,4,4,4,10,12,10,12,5,5,5,5,5,5,11,13,11,13,6,6,6,6,6,6,4,7,4,7,7,7,7,7,7,7,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step6 构造DFA,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,Step7 确定初态和终态：原终态为1,例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。,