正规式和有穷自动机的等价性课件

编译原理第一章 编译程序概述第二章 PL/0编译程序的实现第三章 文法和语言第四章 词法分析第五章 自顶向下语法分析方法第六章 自底向上优先分析方法第七章 LR分析方法第八章 语法制导翻译和中间代码生成第九章 符号表第一章 代码优化第一一章 代码生成编译原理第一章编译程序概述1词法分析主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。词法分析的基本思路：将单词符号的语法用有效的工具描述；基于该描述建立单词的识别机制；设计和实现词法分析程序词法分析是编译过程的第一个阶段。词法分析主要任务：从左到右逐个字符地对源程序进行扫描，产生一2单词的描述技术正规文法正规式单词的识别机制确定有穷自动机不确定有穷自动机词法分析程序的自动构造原理正规式和有穷自动机的等价性词法分析程序的自动构造工具单词的描述技术3单词的描述工具某种程序设计语言中的所有单词构成一种语言。该语言的语法都能用正规文法表示。正规文法是描述单词的一种工具。1、正规文法（回顾）文法G=(VN,VT,P,S)，P中每一规则有AaB或Aa，A,BVN，aVT*，称G(S)是正规文法。l|l l|d|l|d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字由正规文法产生的语言称为正规集单词的描述工具某种程序设计语言中的所有单词构成一种语言。该语42、正规式（正则表达式）是表示正规集的工具，也是用以描述单词符号的方便工具。j正规式与正规集的定义：设字母表为，辅助字母表=，|，*，（，）；和都是上的正规式，表示的正规集分别为和；任何a,a是上的一个正规式，表示的正规集为a;2、正规式（正则表达式）正规式与正规集的定义：5假定e1和e2都是上的正规式，它们所表示 的 正 规 集 分 别 为 L(e1)和 L(e2),则(e1),e1|e2,e1e2和e1*也都是正规式，所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)*。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。例：a,b，上的正规式和相应的正规集为：假定e1和e2都是上的正规式，它们所表示的正规集分别为L(6ab-(a)一个正规式可以表示若干个符号串,(b)其正规集就是这些符号串的集合a|baba*b*-(a|b)*a*|b*aba*(a|b)*(aa|bb)(a|b)*7 a ab b-(a)a 一个正规式可以表示若干个符号串,(b)b 其正规集就是这些符号串的集合a|b a,bab aba*,a,aa,aaa,aaaa,.b*,b,bb,bbb,bbbb,.-(a|b)*a和b组成的所有串a*|b*,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,.aba*以ab开头后接若干个(包括0个)a组成的串(a|b)*(aa|bb)(a|b)*上所有含有两个相继的a或两个相继的b组成的串8例：令d，e，则上的正规式d*(.dd*|)(e(+|-|)dd*|)表示的是所有无符号数。其中d为09中的数字。比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。设r，s，t为正规式，正规式服从代数规律有：1、r|ss|r交换律2、r|(s|t)(r|s)|t结合律3、(rs)t=r(st)结合律例：令d，e，则上的正规式d*(.d94.r(s|t)=rs|rt分配律(s|t)r=sr|tr分配律5.r=r零一律r=r零一律程序设计语言中的单词既能用正规文法表示，又能用正规式来表示.正规文法:l|l l|d|l|d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字正规式？4.r(s|t)=rs|rt分配律程序设计语言中的104.r(s|t)=rs|rt分配律(s|t)r=sr|tr分配律5.r=r零一律r=r零一律程序设计语言中的单词既能用正规文法表示，又能用正规式来表示.正规文法:l|l l|d|l|d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字正规式:标识符:e1=字母(字母|数字)*无符号整数:e2=dd*4.r(s|t)=rs|rt分配律程序设计语言中的113、正规文法和正规式的等价性、正规文法和正规式的等价性 一个正规语言可以由正规文法定义，也可以用正规式定义。对于任意一个正规文法，存在一个定义同一语言的正规式。对每一个正规式，存在一个生成同一语言的正规文法。即正规式正规文法3、正规文法和正规式的等价性12 正规式正规文法：（把正规式转换为正规文法所要求的规则形式）将上的一个正规式r转换为一个正规文法G=（VN，VT，P，S）的规则：令VT=，对正规式r，选择一个非终结符S生成Sr，S为G的开始符号。不断拆分r直到符合正规文法要求的规则形式：若x，y都是正规式，对形如Axy的产生式，写成AxB，By。其中B VN 对形如Ax*y的产生式，重写为：Ax A Ay B为新的非终结符，B VN对形如Ax|y的产生式，重写为：Ax Ay 不断利用上述规则进行变换即可。正规式正规文法：（把正规式转换为正规文法所要求的规则13例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。14例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。解：S a(a|d)*SaAA(a|d)*A(a|d)AA 例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。15最后得到：SaAAaAAdAA 最后得到：SaA16正规文法正规文法正规式：正规式：将一个正规文法转换为正规式的规则：转换规则：转换规则：AxB，By 正规式为：A=xy AxA|y 正规式为：A=x*y wAx，Ay 正规式为：A=x|y 不断收缩产生式规则，直到剩下一个开始符号定义的正规式不断收缩产生式规则，直到剩下一个开始符号定义的正规式例：文法GS：S aAS aA aAA dAA aA d转换为正规式正规文法正规式：将一个正规文法转换为正规式的规则：例17S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d)A(a|d)A|(a|d)A(a|d)*(a|d)根据上述规则3Ax，Ay推出A=x|y将它化为正规文法变成A(a|d)A|(a|d)再根据上述规则2转换xy(a|d)将A代入SaA|a得到如下：SaASaA|aAaA|dAAa|dA(aA|d18Sa(a|d)*(a|d)|a =a(a|d)+|a =a(a|d)+|)=a(a|d)*二、二、有穷自动机有穷自动机 有穷自动机：是一种自动识别装置，能正确识别正规集；是词法分析程序的工具和方法，可自动识别（且是正确识别）正规集。分为确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机不确定的有穷自动机（NFA）Sa(a|d)*(a|d)|a二、有穷自动机有19（一）（一）确定的有穷自动机确定的有穷自动机DFA 自动识别装置自动识别装置一个确定的有穷自动机M是一个五元组：M=（K，f，S，Z），其中：K是一个有穷集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符；f是转换函数，是在KK上的映象，如：f(Ki，a)=Kj (Ki,KjK)；S是初态，SK；ZK，是终态集。含义：当前状态为Ki，输入字符a，转换为Kj状态（一）确定的有穷自动机DFA自动识别装置一个确定的201、用状态图表示：方法如下：初始态用“”或“”表示；终态点用“”或“”表示；若f(Ki，a)=Kj，则从状态点Ki 到Kj画弧，标记为a。例：DFA的M(S,U,V,Q,a,b,f,S,Q)其中f为：f(S,a)=U,f(S,b)=V,f(U,a)=Qf(U,b)=V,f(V,a)=U,f(V,b)=Qf(Q,a)=Q,f(Q,b)=Q画出状态图画出状态图1、用状态图表示：例：DFA的M(S,U,V,Q,a21状态图如下：a,baaabbbSUVQ2、用矩阵表示DFA:方法：行表示状态列表示输入字符元素表示相应状态行和输入字符下的新状态。a,b状态图如下：a,baaabbbSUVQ2、用矩阵表示DF22“”标明初态，默认第一行是初态。终态行在表右端标1，非终态标0上例矩阵表示如下：abSUVUQVVUQQQQ字符状态0001“”标明初态，默认第一行是初态。abSUVUQVVUQ23例：baSZa,b表示：f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=ZabSZZZZZ01写成正规式是：(a|b)(a|b)*例：baSZa,b表示：f(S,a)=ZabSZZZZZ243、接受（识别）的概念：自动识别单词自动识别单词对于*中的任何字符串t，若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受。若M的初态同时又是终态，则空字可为M所接受。4、接受（识别）的理解：设QK，函数f(Q,)=Q，则输入字符串是空串，并停留在原状态上。输入字符串t（t表示成Tt1形式，T，t1*），在DFA M上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中QK。3、接受（识别）的概念：自动识别单词4、接受（识别）25例如：baab字符串被DFA所接受，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)=Q （Q是终态）DFA M所能接受的字符串的全体记为L（M）称为语言（也即句子的集合）5、DFA的确定性：当当f：kK是一个单值函数，即对任何状态是一个单值函数，即对任何状态K R，输入符号，输入符号a K，f(k,a)唯一确定下一状态。唯一确定下一状态。例如：baab字符串被DFA所接受，DFA见上例。5、DFA26DFA的行为很容易用程序来模拟.DFAM=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whileceofdoK:=f(K,c);c:=getchar;ifKisinZthenreturn(yes)elsereturn(no)DFA的行为很容易用程序来模拟.27自动识别单词的方法：（1）把单词的结构用正规式描述；（2）把正规式转换为一个NFA；（3）把NFA转换为相应的DFA；（4）基于DFA构造词法分析程序。自动识别单词的方法：28（二）（二）不确定的有穷自动机不确定的有穷自动机NFA 一个不确定的有穷自动机NFAM是一个五元组:：M=（K，f，S，Z），其中：K是一个有穷集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符；f是一个从K*到K上的子集的映象；f：k*2k SK，是一个非空初态集；Z K，是一个终态集。与DFA区别：多值函数f(Ki,a)=Kjf(Ki,a)=Kt；允许输入字符为（二）不确定的有穷自动机NFA一个不确定29例：一个NFA，M(0,1,2,3,4,a,b,f,0,2,4)其中：f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4状态图表示如下：例：一个NFA，状态图表示如下：3003412abbba,ba,ba,b说明：一个初态，二个终态。DFA是NFA的特例。对于每个NFA M，存在一个DFA M，使得L(M)=L(M)。对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的。03412abbba,ba,ba,b说明：一个初态，二个终31NFA转换为等价的DFA从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.NFA转换为等价的DFA从NFA的矩阵表示中可以看出，表项32定义对状态集合I的几个有关运算：1.状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。定义对状态集合I的几个有关运算：1.状态集合I的-33状态集合I的有关运算的例子I=1,-closure(I)=?；I=5,-closure(I)=?；move(1,2,a)=?-closure(5,3,4)=?；12534687aaa状态集合I的有关运算的例子I=1,-closure(34状态集合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状态集合I的有关运算的例子I=1,-closure(35NFA确定化算法:假设NFAN=(K,f,K0,Kt)按如下办法构造一个DFAM=(S,d,S0,St)，使得L(M)=L(N)：1.1.构造DFAM的状态，选择NFAN的状态的一些子集构成：2.M的状态集S由K K的的一些子集一些子集组成。用S1S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1S2；NFA确定化算法:假设NFAN=(K,f,362M和N的输入字母表是相同的，即是；3构造DFAM的转换函数，根据新构造的状态和字母表中的字符构造：1.转换函数是这样定义的：d(S1S2,.Sj,a)=R1R2.Rt 其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)为M的开始状态；5St=SiSk.Se，其中SiSk.SeS且Si,Sk,.SeKt2M和N的输入字母表是相同的，即是；37构造NFAN的状态状态K K的子集的子集的算法：把多值转换函数所转换到的多值（多状态）的集合作为一个子集，映射到DFA的一个新的状态假定所构造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。1开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。构造NFAN的状态K的子集的算法：382while（C中存在尚未被标记的子集T）do 标记T；for每个输入字母adoU:=-closure(move(T,a)；ifU不在C中then将U作为未标记的子集加在C中2while（C中存在尚未被标记的子集T）do39NFA的确定化例子4f35621iaaaabbbbNFA的确定化例子4f35621iaaaabb404f35621iaaaabbbb4f35621iaaaabbbb41等价的DFAaCDBAEFSbaaaaabbbbbabF等价的DFAaCDBAEFSbaaaaabbbbbabF42三、确定有穷自动机DFA的化简（消除多余状态+合并等价状态）：将多余状态消除而形成一个最小的等价的DFA 1、多余状态的概念：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。下图中的哪些状态是多余的？三、确定有穷自动机DFA的化简将多余状态消除而形成一个最小的4301S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S60化简后的结果：左右等价01S0S1S50S1S2S71S2S2S51S3S5S704401S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价01S0S1S50S1S2S71S2S2S51S3S5S70452、等价的条件（状态、等价的条件（状态S和和T）一致性条件状态S和T必须同时为可接受状态或不可接受状态（终态还是非终态）。蔓延性条件对于所有输入符号，状态S和状态T必须转换到等价的状态里。3、合并等价状态的方法（分割法）、合并等价状态的方法（分割法）方法：将DFA的状态分割成一些互不相交的子集。不同子集的状态是可区别的，同一子集中的任何两个状态是等价的。合并等价状态：发现等价状态，并将这些等价状态合并成一个状态。2、等价的条件（状态S和T）合并等价状态：发现等价状态，并将461643257aaaaaaabbbbbbb例子：将图中的DFA M最小化。1643257aaaaaaabbbbbbb例子：将图中的D47 将M分成两个子集：一个终态（可接受态）组成，一个非终态组成。P0(1,2,3,4,5,6,7)第1个子集1,2,3,4中：1,2中的状态和3,4中的任何状态在读入a后到达了不等价的状态，两个状态都是不可区别的。P1(1,2,3,4,5,6,7)P1中的3,4对应输入符号a或b，将再分割：P2(1,2,3,4,5,6,7)P2中的5,6,7可有输入符号a或b，分割为：将M分成两个子集：481643257aaaaaaabbbbbbbP3(1,2,3,4,5,6,7)1,2,6,7不能再分割，也即等价的。16435aaaaabbbbb1643257aaaaaaabbbbbbbP3(1,249DFA的最小化算法 DFA M=（K,f,k0,kt),最小状态DFAM 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)=rDFA的最小化算法DFAM=（K,f,k0,50 M 的开始状态是含有S0的那组的代表 M 的终态是含有F的那组的代表 5.去掉M中的死状态.M的开始状态是含有S0的那组的代表M的终态是含51过程过程PPPP:Construction 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 in new by the set of all subgroups formed end 过程PP:ConstructionofnewFo52自动识别单词的方法：（1）把单词的结构用正规式描述；（2）把正规式转换为一个NFA；（3）把NFA转换为相应的DFA；（4）基于DFA构造词法分析程序。自动识别单词的方法：53四、四、正规式和有穷自动机的等价性正规式和有穷自动机的等价性 正规式和有穷自动机的等价性由以下两点说明：对于上的NFA M，可以构造一个上的正规式R，使得L(R)=L(M)。对于上的每个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。1、在NFA M上构造正规式R。即从L(M)L(R）方法：在每一条弧上用一个正规式作标记。规则如下：四、正规式和有穷自动机的等价性正规式和有穷自动机的等价性由54a.123R1R213R1R2b.12R1R221R1|R221R1+R2或c.321R1R2R331R1R2*R3给定有穷自动机，判断它识别的语言a.123R1R213R1R2b.12R1R221R1|R255例1:L(M)如下图：求正规式R，使L(R)=L(M).解：aba,b例1:L(M)如下图：aba,b56例1:L(M)如下图：求正规式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)=(a+b)(a+b)*例1:L(M)如下图：aba,baba,bxyya5703412aabba,ba,ba,b例2：M状态图如下：求正规式R，是L(R)=L(M).03412aabba,ba,ba,b例2：M状态图如下：58解：加x,y结点。a,b03412aabba,ba,bxy解：加x,y结点。a,b03412aabba,ba,bx59042aabba,ba,bxya,ba,b0aa(a+b)*bb(a+b)*xy042aabba,ba,bxya,ba,b0aa(a+60y(a+b)*(aa+bb)(a+b)*x所以 L(R)=(a+b)*(aa+bb)(a+b)*y(a+b)*(aa+bb)(a+b)*x所以L(R)=612、L(R)NFA，从正规式R构造NFA规则如下：正规式，构造NFA为：或：对应正规式，构造NFA为：对应正规式a，构造NFA为：s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s|t，构造NFA(R)为：xyxyxyaxyN(s)N(t)2、L(R)NFA，从正规式R构造NFA规则如下：xy62 s,t是正规式，相应NFA为N(s),N(t)，则正规式R=st，构造NFA(R)为：xyN(t)N(s)s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s*，构造NFA(R)为：xyN(s)s,t是正规式，相应NFA为N(s),N(t)，则正规式63例1：L(R)=(a+b)*abb，构造NFA使L(N)=L(R)解：例1：L(R)=(a+b)*abb，构造NFA使L(N)=64例1：L(R)=(a+b)*abb，构造NFA使L(N)=L(R)解：xy(a+b)*abbxyabba,bxyabbabxyababb例1：L(R)=(a+b)*abb，构造NFA使L(N)=65yababb例4：L(R)=(a+b)*(aa+bb)(a+b)*构造L(N)使与L(R)等价。yababb例4：L(R)=(a+b)*(aa+bb)66xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,bxy(a+b)*(aa+bb)(a+b)*xy(a+b)67xya baaabbb-+a baaabbbxyabaaabbb-+abaaabbb68词法分析程序的自动构造自动识别单词的方法：（1）把单词的结构用正规式描述；（2）把正规式转换为一个NFA；（3）把NFA转换为相应的DFA；（4）基于DFA构造词法分析程序。词法分析程序的自动构造自动识别单词的方法：69本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具的原理。本章小结词法分析程序是编译第一阶段的工作70课后作业1。叙述正规式(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*描述的语言。2。写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规式。3。构造一个DFA，它接受=0,1上0和1的个数都是偶数的字符串。4。处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。课后作业1。叙述正规式(00|11)*(01|10)(0071