复习—编译原理第3章

1、2021-10-151计算机学院计算机学院编 译 原 理主讲人：郑丽萍主讲人：郑丽萍时间：时间：2014-20152014-2015学年第二学期学年第二学期联系方式：联系方式：2021-10-152 词法分析程序又称扫描器，是编译过程的第一步，是下词法分析程序又称扫描器，是编译过程的第一步，是下一步进行语法分析的基础。词法分析的任务一步进行语法分析的基础。词法分析的任务: :从构成源程序的字符串中识别出一个个具有独立意义的从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位最小语法单位“单词单词”，并将其转化为内部编码形式。，并将其转化为内部编码形式。删除无用的空白字符和回车字符以及其

2、他非实质性字符。删除无用的空白字符和回车字符以及其他非实质性字符。删除注释。删除注释。1.1. 进行词法检查进行词法检查, ,报告所发现的错误。报告所发现的错误。词法分析的任务词法分析的任务2021-10-153n 逐个读入源程序字符，然后按照构词规则切分成一列逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。单词是语言中具有独立意单词，再转换成单词序列。单词是语言中具有独立意义的最小单位。义的最小单位。n 词标词标(token(token）是单词的机内表示，其格式由实现系统）是单词的机内表示，其格式由实现系统规定。规定。单词符号一般可分为下列五种：单词符号一般可分为下列五

3、种：n 基本字，关键字；基本字，关键字；n 标识符；标识符；n 常数（量）；常数（量）；n 运算符；运算符；n 分隔符分隔符单词的划分单词的划分 2021-10-154单词符号的内部表示单词符号的内部表示 词法分析的功能是识别出的具有独立意义的单词，并转化为词法分析的功能是识别出的具有独立意义的单词，并转化为相应的内部表示。相应的内部表示。词法分析的输出常采用二元式词法分析的输出常采用二元式(class(class，value),value),如图如图3.33.3所示。所示。classclass为以整数码或助记符为以整数码或助记符,value,value则是该单词的值则是该单词的值( (如变量

4、名如变量名在符号表中的序号在符号表中的序号, ,常数的二进制表示常数的二进制表示, ,以及运算符和分隔符以及运算符和分隔符的编码的编码, ,等等等等) )class单词类别单词类别 value单词值单词值 图图3.3 词法分析程序的输出形式词法分析程序的输出形式 2021-10-155由正规文法构造状态转换图由正规文法构造状态转换图l 一个状态转换图是由一组矢线连接的有限个节点所组成的一个状态转换图是由一组矢线连接的有限个节点所组成的有向图。有向图。l每个节点均代表在识别或分析过程中扫描器的状态，其中每个节点均代表在识别或分析过程中扫描器的状态，其中有一个是开始状态有一个是开始状态( (带箭头

5、带箭头) )，至少有一个状态是结束状态，至少有一个状态是结束状态（双圈）。（双圈）。 l状态间用矢线连接，矢线上标记有符号，表示在矢线射出状态间用矢线连接，矢线上标记有符号，表示在矢线射出端的状态下，读入矢线上标记的符号可转换到矢线指向的端的状态下，读入矢线上标记的符号可转换到矢线指向的状态。状态图只有状态。状态图只有有穷个状态有穷个状态。12开始a0abb2021-10-156正规文法形式：正规文法形式：AaAa或或ABaABa（左线性）或（左线性）或AaBAaB（右线性）（右线性）其中：其中：A,BVnA,BVn，aVt;aVt;正规文法描述语言单词，状态转换图可识别单词，它们之间正规文法

6、描述语言单词，状态转换图可识别单词，它们之间存在等价关系。存在等价关系。一一. .对于右线性文法构造状态转换图对于右线性文法构造状态转换图设设G=(Vn,Vt,P,S)G=(Vn,Vt,P,S)是一右线性文法是一右线性文法,Vn,Vn中的每个非终结符号对中的每个非终结符号对应状态图中的一个结点应状态图中的一个结点, ,且的开始符号所标记的结点为初且的开始符号所标记的结点为初态结点态结点; ;增设一个不属于的符号增设一个不属于的符号F F标记终态结点。标记终态结点。|V|VN N|=k,|=k,共有共有k+1k+1个节点（状态）。个节点（状态）。2021-10-157对于对于G G中的每一条形如

7、中的每一条形如AaAa的规则，从结点的规则，从结点A A引一条矢线到引一条矢线到终态结点终态结点F F，并用符号，并用符号a a标记这条矢线。标记这条矢线。对于对于G G中每一条形如中每一条形如AaBAaB的规则，从结点的规则，从结点A A引一条矢线到引一条矢线到结点结点B B，并用符号，并用符号a a标记这条矢线。标记这条矢线。注意注意: :文法文法G G中含有无用符号和无用产生式须事先予以删除中含有无用符号和无用产生式须事先予以删除; ;若若L(G),L(G),则初态结点则初态结点S S也同时是一个终态结点也同时是一个终态结点; ;若若G G中含有中含有产生式产生式A,A,则将结点则将结点

8、A A设置为终态结点设置为终态结点; ;右线性文法构造状态图规则右线性文法构造状态图规则2021-10-158baabVSUa例如：文法例如：文法GS SaU|bV UbV|a VaU|bbQ右线性文法状态图构造实例右线性文法状态图构造实例2021-10-159状态转换图对符号串的识别状态转换图对符号串的识别 利用状态转换图可识别相应文法所表示的符号串利用状态转换图可识别相应文法所表示的符号串。12开始a0abb定义：定义：设设VVT T * * ，如果状态转换图中存在一条从，如果状态转换图中存在一条从初态初态到到终态终态的路径，此路径上的标记符号顺序相连构成符号串的路径，此路径上的标记符号顺

9、序相连构成符号串，则称，则称为为状态图所识别串状态图所识别串。状态图识别语言：状态图识别语言：状态图所识别的串集合。状态图所识别的串集合。2021-10-1510 对符号串对符号串W=aW=a1 1a a2 2a a3 3a an n，a ai i V VT T 识别过程：识别过程：l 从初态从初态S S出发，自左至右逐个扫描出发，自左至右逐个扫描W W中的字符，在中的字符，在S S状态下扫状态下扫视的符号为视的符号为a a1 1；l 在节点在节点S S所射出诸矢线中寻找标记为所射出诸矢线中寻找标记为a a1 1的矢线的矢线( (若不存在，若不存在，则说明则说明W W有错有错) )；l 读入读

10、入a a1 1，沿矢线方向到下一状态，在此状态时扫描，沿矢线方向到下一状态，在此状态时扫描a a2 2，l 直至直至W W中全部字符读完且进入终态中全部字符读完且进入终态F,F,则则W W已被接受。已被接受。对符号串的识别过程对符号串的识别过程2021-10-1511状态图的一种实现状态图的一种实现-状态矩阵法状态矩阵法程序设计语言一般含有若干类单词符号程序设计语言一般含有若干类单词符号, ,我们可首先为每类我们可首先为每类单词建立一张状态转换图单词建立一张状态转换图, ,然后将这些状态转换图合并成一然后将这些状态转换图合并成一张统一的状态图张统一的状态图, ,最后再据此构造词法分析程序。最后

11、再据此构造词法分析程序。计算机内表示状态转换图的方法之一是计算机内表示状态转换图的方法之一是状态矩阵状态矩阵。状态矩阵：状态图中的各个状态状态矩阵：状态图中的各个状态S S1 1，S S2 2，S Sn n为行，以可为行，以可能输入的输入符号能输入的输入符号a a1 1，a a2 2，a am m为列，组成一个为列，组成一个n n行行m m列矩列矩阵。阵。2021-10-1512BnmBnBnmBBBmBBBB212222111211 a1 a2 am SnSS21B Bijij=BS=BSi i,a,aj j 含义：当前状态含义：当前状态S Si i，正扫视符号，正扫视符号a aj j，则以

12、序偶（，则以序偶（S Si i，a aj j）去查）去查询矩阵询矩阵B B，扫描器根据，扫描器根据B Bijij的指示，执行相应的语义动作，转到的指示，执行相应的语义动作，转到S Sk k状态。若某状态。若某a aj j不与不与S Si i配对，即状态图中从节点配对，即状态图中从节点S Si i不存在以不存在以a aj j为为标记的射出矢线，则标记的射出矢线，则B Bj j置为置为“errorerror”, ,进行词法错误检查和处进行词法错误检查和处理。理。2021-10-1513有限自动机（有限自动机（FAFA） u有限自动机是一种具有离散输入与输出系统的数学模型有限自动机是一种具有离散输入

13、与输出系统的数学模型,是状是状态转换图的形式化。在这种数学模型中有有限个状态，状态间态转换图的形式化。在这种数学模型中有有限个状态，状态间存在着转换关系。系统可以处于有限个状态中的任意一个之中，存在着转换关系。系统可以处于有限个状态中的任意一个之中，系统的当前状态概括了有关过去输入的信息。系统的当前状态概括了有关过去输入的信息。u当系统处在某个状态之下读入一个字符时，会使系统所处的当系统处在某个状态之下读入一个字符时，会使系统所处的状态发生变化，从而形成状态转换。改变后的状态称为后继状状态发生变化，从而形成状态转换。改变后的状态称为后继状态。态。2021-10-1514在状态转换中，后继状态可

14、能为一个，也可能为多个。有限自在状态转换中，后继状态可能为一个，也可能为多个。有限自动机分确定的和不确定的。动机分确定的和不确定的。所谓所谓“确定的有限自动机确定的有限自动机” ( Deterministic Finite ( Deterministic Finite Automata DFA)Automata DFA)是指在当前的状态下，输入一个符号，有限自动是指在当前的状态下，输入一个符号，有限自动机将转换到唯一的后继状态；机将转换到唯一的后继状态；“不确定的有限自动机不确定的有限自动机” (Nondeterministic Finite (Nondeterministic Finite

15、Automata NFA)Automata NFA)在当前状态下输入一个符号，可能有两种或两种在当前状态下输入一个符号，可能有两种或两种以上可选择的后继状态。以上可选择的后继状态。 有限自动机的分类有限自动机的分类2021-10-1515确定的有限自动机确定的有限自动机 1、确定的有限自动机定义、确定的有限自动机定义将前面介绍的状态转换图抽象将前面介绍的状态转换图抽象,可得到一个确定的有限自动机可得到一个确定的有限自动机M（记作（记作DFA M）是一个五元组）是一个五元组:M=（ K， ，f，S0，Z）其中：其中： K：是一个有限状态的集合。：是一个有限状态的集合。 ：是一个有限个输入字符组成

16、的字母表：是一个有限个输入字符组成的字母表 f：状态转换函数，是一个：状态转换函数，是一个KK的单值映射，的单值映射， 形形式为式为f (p, a)=q 。 S0：S0K，是唯一的初始状态。，是唯一的初始状态。 Z：ZK，称为终结状态集合。，称为终结状态集合。可见可见,一个确定的有限自动机是相应的状态图的一种形式描述。一个确定的有限自动机是相应的状态图的一种形式描述。这是一个单值函数，指明当前这是一个单值函数，指明当前状态为状态为p，输入符号为，输入符号为a时，自时，自动机将从状态动机将从状态p转换到下一个状转换到下一个状态态q，q称为称为p的后继状态。的后继状态。2021-10-1516DF

17、A M=（S，U，V，Q，a，b，f，S，Q）其中）其中f定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（U，b）=V例：例：SaU|bV UbV|a VaU|bbaabVSUabQ2021-10-15172 2、确定的有限自动机状态图、确定的有限自动机状态图 u确定的有限自动机确定的有限自动机M M可以用状态图来表示。可以用状态图来表示。u状态图中的结点代表状态，它与自动机中的状态集合状态图中的结点代表状态，它与自动机中的状态集合K K相相对应，其中包括初始状态对应，其中包括初始状态S S0 0和终结状态集合和终结状态集合Z Z。u状态间用

18、矢线连接，矢线上标记有输入符号，每条矢线状态间用矢线连接，矢线上标记有输入符号，每条矢线对应一个状态转换函数对应一个状态转换函数f f，矢线上标记的输入符号集合就是，矢线上标记的输入符号集合就是字母表字母表。 2021-10-15183 3、确定的有限自动机状态转换矩阵、确定的有限自动机状态转换矩阵u确定的有限自动机确定的有限自动机M M还可以用状态转换矩阵来表示。还可以用状态转换矩阵来表示。u矩阵中的第一列元素与自动机中的状态集合矩阵中的第一列元素与自动机中的状态集合K K相对应，且相对应，且初始状态初始状态S S0 0是第一列的第一个元素，右上角标记是第一列的第一个元素，右上角标记* *的

19、元素对的元素对应终结状态。应终结状态。u矩阵中的第一行元素与字母表矩阵中的第一行元素与字母表中的每个输入符号相对中的每个输入符号相对应。矩阵中的元素对应每个状态转换函数。应。矩阵中的元素对应每个状态转换函数。u如果有状态转换函数如果有状态转换函数f(p,a)=q,f(p,a)=q,其中其中p,qK,ap,qK,a，那么，那么，就在矩阵中状态就在矩阵中状态p p对应的行和符号对应的行和符号a a对应的列单元中填入对应的列单元中填入q q。2021-10-15194 4、确定的有限自动机接受的语言、确定的有限自动机接受的语言 为了讲解确定的有限自动机如何接受或识别字符串，首先，为了讲解确定的有限自

20、动机如何接受或识别字符串，首先，我们对状态转换函数作补充定义：我们对状态转换函数作补充定义： f(S,)=Sf(S,)=S f(S,aw)=f(f(S,a),w),a f(S,aw)=f(f(S,a),w),a，ww* *，即，即w w是是上的字符串上的字符串例如例如, ,有有f(0,a)=1 f(0,a)=1 且且f(1,b)=2,f(1,b)=2,则则 f(0,ab)=f(f(0,a),b)=f(1,b)=2f(0,ab)=f(f(0,a),b)=f(1,b)=2对一个确定的有限自动机对一个确定的有限自动机M M以及某个字符串以及某个字符串x x（xx* *），如），如果有果有f(Sf(S

21、0 0, x)=S, x)=S，且，且SZSZ，则字符串，则字符串x x就被该自动机就被该自动机M M所接受。所接受。即将即将f的定义域扩充到的定义域扩充到K*2021-10-1520u从状态图上看，如果一个字符串能被自动机接受，则存在从状态图上看，如果一个字符串能被自动机接受，则存在一条从初始状态到某一终结状态的通路，且将这条通路上所一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号一次连接起来就组成了字符串有矢线标记的符号一次连接起来就组成了字符串x x。u若初始状态也是终结状态，或是存在一条从初始状态到某若初始状态也是终结状态，或是存在一条从初始状态到某一终结状态的路径

22、，路径上的所有标记都是一终结状态的路径，路径上的所有标记都是，则，则可被可被DFADFA接受。接受。 u一个确定的有限自动机一个确定的有限自动机M M所接受的语言就是所能接受的字所接受的语言就是所能接受的字符串构成的集合，用符串构成的集合，用L L（M M）表示，可定义为：）表示，可定义为： L L（M M）=x|f(S=x|f(S0 0,x)Z,x)Z，xx* * 2021-10-1521l DFA的确定性表现在转换函数的确定性表现在转换函数 :KK是一个单值函是一个单值函数，即：对任何状态数，即：对任何状态kK以及输入符号以及输入符号a， (k,a)能唯能唯一确定下一个状态。一确定下一个状

23、态。l 从状态转换图来看，若字母表从状态转换图来看，若字母表含有含有n个输入字符，那么个输入字符，那么任何一个状态结点最多有任何一个状态结点最多有n条弧射出，而且每条弧以一个条弧射出，而且每条弧以一个不同的输入字符标记。不同的输入字符标记。总总 结：结：2021-10-1522非确定的有限自动机非确定的有限自动机 非确定的有限自动机与确定的有限自动机的区别主要是状非确定的有限自动机与确定的有限自动机的区别主要是状态转换函数态转换函数f f为多值函数。为多值函数。1 1、非确定的有限自动机定义、非确定的有限自动机定义一个非确定的有限自动机一个非确定的有限自动机NFA MNFA M是一个五元式是一

24、个五元式M=M=（K K，f f，S S0 0，Z Z）其中其中:K:K：有穷状态集：有穷状态集; ; ：输入字母表：输入字母表 S S0 0：开始状态：开始状态S S0 0K; ZK; Z：终止状态集：终止状态集ZKZKf f：状态转换函数，为：状态转换函数，为K K到到K K的子集的映射。的子集的映射。形式为形式为 f( Sf( Si i, a, aj j )=S )=Sk1k1,S,Sk2k2, ,S,Skmkm 非确定的有限自动机同样可以用状态图和状态转换矩阵来非确定的有限自动机同样可以用状态图和状态转换矩阵来表示，表示方法与确定的相同。表示，表示方法与确定的相同。 2021-10-1

25、5232 2、非确定的有限自动机接受的语言、非确定的有限自动机接受的语言与确定的有限自动机一样，为了判别一个字符串与确定的有限自动机一样，为了判别一个字符串x x能否被能否被NFA MNFA M接受，我们还需要对状态转换函数做补充定义：接受，我们还需要对状态转换函数做补充定义：f(S,)=Sf(S,)=S f(S,aw)=f(f(S,a),w),a,w f(S,aw)=f(f(S,a),w),a,w* *再设再设f(S,a)=Sf(S,a)=Sk1k1,S,Sk2k2, , , S, Skmkm 且定义且定义 f(Sf(Sk1k1,S,Sk2k2, ,S,Skmkm,w)=,w)=m mi=1

26、i=1f(Sf(Skiki,w),w)表示从表示从M M的当前状态集出发，扫描字符串的当前状态集出发，扫描字符串x x后，所到达的状态集后，所到达的状态集等于从当前状态集的每一个状态出发，扫描字符串等于从当前状态集的每一个状态出发，扫描字符串x x后所到达后所到达的状态集之和。的状态集之和。即将即将f的定义域扩充的定义域扩充到到2K*2021-10-1524对于某个字符串对于某个字符串 x（x *），），若有若有f (S0, x )=K，且，且K Z ，则则x为为M所接受。所接受。从状态图上看，如果一个字符串能被非确定的自动机接从状态图上看，如果一个字符串能被非确定的自动机接受，则至少存在一条

27、从初始状态到某一终结状态的通路，受，则至少存在一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号依次连接起来就组且将这条通路上所有矢线标记的符号依次连接起来就组成了字符串成了字符串x。NFA M所接受的语言为所接受的语言为 L（M）=x | f(S0, x )Z ， x * NFA所接受的语言所接受的语言2021-10-1525*上的符号串上的符号串t被被NFA M接受也可理解为：接受也可理解为：l 对于对于中的串中的串t t，若存在一条从某初态到某一终态，若存在一条从某初态到某一终态的路径，且这条路上所有弧的标记字依序连接成的串的路径，且这条路上所有弧的标记字依序连接成的串

28、等于等于t t，则称，则称t t可为可为NFA MNFA M所识别所识别( (接受接受) )。l 若若M M的某些结点既是初态又是终态，或者存在一条从的某些结点既是初态又是终态，或者存在一条从某个初态到某个终态的路径某个初态到某个终态的路径, ,其上所有弧的标记均为其上所有弧的标记均为，那么那么可被可被M M所接受。所接受。符号串被符号串被NFA所接受所接受2021-10-1526NFANFA与与DFADFA的等价性的等价性 所谓所谓NFANFA的确定化的确定化, ,是指对任给的是指对任给的NFA,NFA,都能相应的构造一都能相应的构造一DFA,DFA,使它们有相同的接受集。使它们有相同的接受

29、集。证明的思路证明的思路: :让所要构造的让所要构造的DFADFA去模拟相应的去模拟相应的NFANFA的工作过程的工作过程, ,即用即用DFADFA的一个状态去记录的一个状态去记录NFANFA读入一个输入符号后可能到达读入一个输入符号后可能到达的所有状态。的所有状态。定理定理3.13.1对于字母表对于字母表上的任一上的任一NFA M,NFA M,必存在必存在上与上与M M等价的等价的DFA MDFA M 。证明证明: :设设M=(K, ,f, SM=(K, ,f, S0 0, Z), Z)是是上的一个上的一个NFA,NFA,今构今构造一个造一个上的上的DFA MDFA M=(K=(K,f,f,

30、S,S0 0,Z,Z),),其方法如下其方法如下: :2021-10-1527K K=2=2K K 。例如。例如, ,对对K K的一个子集的一个子集SS1 1,S,S2 2, ,S,Si i,我们用记号我们用记号SS1 1,S,S2 2, ,S,Si i 表示表示K K中的一个状态中的一个状态, ,特别地特别地, ,令令S S0 0=S=S0 0 映射映射f f的定义为：的定义为： 当且仅当当且仅当 f(Sf(S1 1,S,S2 2, ,S,Si i,a)=R,a)=R1 1,R,R2 2, ,R,Rj j 时时 f f(S(S1 1,S,S2 2, ,S,Si i,a)=R,a)=R1 1,

31、R,R2 2, ,R,Rj j 终态集终态集Z Z定义为定义为 Z Z=Sp,Sq,=Sp,Sq,SrSp,Sq,SrSp,Sq,SrK,SrK且且Sp,Sq,Sp,Sq,SrZ ,SrZ 2021-10-1528具有具有动作的动作的FAFA u一个具有一个具有动作的有限自动机动作的有限自动机NFA M也是一个五元式也是一个五元式 M=（K， ，f ， S0，Z）其中其中, K,S0,Z的含义同前的含义同前,而而f却是却是K()到到2k的一个映的一个映射。射。u对于对于f(q,a)则由状态则由状态p组成：当组成：当NFA处于状态处于状态q而扫视的输而扫视的输入字符为入字符为a(a或或a =)时

32、，它的下一个状态将是时，它的下一个状态将是p。2021-10-1529具有具有动作的动作的NFANFA的确定化的确定化为了实现为了实现NFA到到DFA 的转化，首先介绍两个状态子集的计算方的转化，首先介绍两个状态子集的计算方法，它们是从法，它们是从NFA到到DFA 的转化过程中需要计算的状态子集。的转化过程中需要计算的状态子集。 1、状态集、状态集P的的闭包闭包 设设P是一是一NFA M的状态集的状态集K的一个子集，则的一个子集，则-closure (P) 称为状称为状态集态集P的的闭包，闭包，闭包也是状态集闭包也是状态集K的一个子集，其计算方法如的一个子集，其计算方法如下：下：1）若）若q

33、P，则，则q -closure (P)，即，即P的所有成员都是的所有成员都是P的的闭闭包的成员（状态包的成员（状态q本身包含在这个集合之中）本身包含在这个集合之中）2）若）若q P，那么从，那么从q出发经过任意条出发经过任意条弧而能到达的任何状态弧而能到达的任何状态都属于都属于-closure (P)。 2021-10-15302、状态集、状态集P的的a弧转换集弧转换集设设P仍是一仍是一NFA M的状态集的子集，的状态集的子集，P= p1, p2,p n ,a，即即a是字母表是字母表的一个输入符号，则的一个输入符号，则P的的a弧转换集为：弧转换集为：Pa=-closure (J)，其中其中 J

34、=f(p1,p2,p n, a)=f(p1, a )f(p2,a)f (p n, a)即即J是从状态子集是从状态子集P中的每个状态出发，沿着标记为中的每个状态出发，沿着标记为a的矢线而的矢线而转移到达的状态所组成的集合。转移到达的状态所组成的集合。从定义可知，状态集从定义可知，状态集P的的a弧转换集弧转换集Pa也是状态子集，其元素为也是状态子集，其元素为从从P的每个状态出发，沿着标记为的每个状态出发，沿着标记为a的矢线所转移到达的后继状的矢线所转移到达的后继状态的集合，再加上这些后继状态集合中的每个状态的态的集合，再加上这些后继状态集合中的每个状态的闭包，即闭包，即转移后再经转移后再经矢线所能

35、到达的状态的集合。矢线所能到达的状态的集合。 状态集状态集P的的a弧转换集弧转换集2021-10-15313、根据、根据NFA M构造构造DFA M(子集法子集法)基本思路基本思路:首先将首先将-closure(S0)作为作为M的初态的初态q0,然后对于所有的然后对于所有的输入符号输入符号a ,将将q0的的a弧转换集作为弧转换集作为M的状态的状态,如此如此等等等等,直到不再有新的状态出现为止。直到不再有新的状态出现为止。下面我们通过一个例子来介绍根据下面我们通过一个例子来介绍根据NFA M构造构造DFA M的方法的方法。子集法实现子集法实现NFA到到DFA转换转换2021-10-1532例题：

36、假设有一个不确定的有限自动机例题：假设有一个不确定的有限自动机NFA M= （K， ，f ，S0 ，Z），），其中其中K=1,2,3,4，=a,b,c，S0 =1， Z=4，状态图如图状态图如图3.13所示。所示。接受的语言：接受的语言：L(M) =a m b | m1 a c n | n1 ，构造一个构造一个DFA M= （K， ，f ，q0，Z），），使使L(M)=L(M) 1234aaaccb图图3.13 NFA M的状态图的状态图 2021-10-1533构造确定的有限自动机过程如下：构造确定的有限自动机过程如下：1）首先根据）首先根据闭包的计算方法求闭包的计算方法求NFA M的开始状

37、态的开始状态S0的的闭包，从而确定闭包，从而确定DFA M的开始状态的开始状态q0。 q0 =-closure(S0)= -closure(1)=1，42）根据弧转换集的计算方法求开始状态）根据弧转换集的计算方法求开始状态q0对每个输入符对每个输入符号的弧转换集号的弧转换集q0a、q0b和和q0c从而确定与开始状态从而确定与开始状态q0有关的有关的状态转换函数。状态转换函数。f(q0,a)=q0a =-closure( f(1,4,a) )=-closure(f(1, a )f(4, a ) )=-closure(2,3)=2,31234aaaccb2021-10-1534将将2,3作为新状态

38、作为新状态,并令并令q1 =2,3，即得到，即得到f(q0,a)= q1q0的的b弧转换集弧转换集q0b= -closure( f(1，4,b) ) = -closure()= ,即即 f(q0,b) = ；q0的的c弧转换集弧转换集q0c= -closure( f(1，4,c) ) = -closure()= ; f(q0,c) = ； 1234aaaccb2021-10-1535由于由于f(q0,b) = ，f(q0,c) =，说明没有新状态产生。至此，说明没有新状态产生。至此，我们得到有关开始状态我们得到有关开始状态q0的全部状态转换函数只有一个，即的全部状态转换函数只有一个，即f(q0

39、,a)= q1。 1234aaaccb2021-10-15363）按步骤）按步骤2的方法，对每个新状态计算相关的状态转换函数。的方法，对每个新状态计算相关的状态转换函数。计算状态计算状态q1(2,3)的状态转换函数：的状态转换函数：q1的的a弧转换集弧转换集q1a=-closure( f(2，3,a) ) =-closure(2)= 2将将2作为新状态作为新状态, 并令并令q2=2 q1的的b弧转换集弧转换集q1b=-closure( f(2，3,b) ) =-closure(4)= 4将将4作为新状态作为新状态, 并令并令q3=4 q1的的c弧转换集弧转换集q1c=-closure(f(2，

40、3,c)=-closure(3,4)=3,4将将3，4作为新状态作为新状态, 并令并令q4=3,4至此，得到有关开始状态至此，得到有关开始状态q1的全部状态转换函数。的全部状态转换函数。 f(q1, a ) =q2 ， f(q1, b ) = q3，f(q1, c) = q41234aaaccb2021-10-1537接下来，计算状态接下来，计算状态q2、q3、q4的有关状态转换函数如下：的有关状态转换函数如下：f(q2, a ) = 2=q2 , f(q2, b ) = 4=q3 , f(q2,c ) = f(q3,a ) = , f(q3,b ) = , f(q3,c ) = f(q4,

41、a ) = ，f(q4, b ) =，f(q4, c ) = 3,4= q4 计算到此，不再有新状态出现。计算到此，不再有新状态出现。 1234aaaccb2021-10-1538 4）根据上面求出的各个状态确定终结状态集）根据上面求出的各个状态确定终结状态集Z=p| p Z ， 其中其中p为为M的每个状态子集。的每个状态子集。因为因为q0 =1,4、q1 = 2,3、q2=2、q3=4、q4=3,4，而而Z=4，q0、q3、q4与与Z相交不为空，所以确定终结状态集相交不为空，所以确定终结状态集 Z= q0, q3 , q42021-10-1539最后最后,我们得到确定的有穷自动机如下：我们得

42、到确定的有穷自动机如下：DFA M= (q0, q1 , q2, q3 , q4,a,b,c, f, q0 , q0, q3 , q4)其中状态转换函数为：其中状态转换函数为：f(q0,a)= q1 f(q1,a)= q2，f(q1,b)= q3，f(q1,c)= q4f(q2,a)= q2，f(q2,b)= q3f(q4, c ) = q4该转换后的自动机的状态图及状态转换矩阵如图该转换后的自动机的状态图及状态转换矩阵如图3.14(a)、(b)所所示。示。 2021-10-1540q0q1q2q3q4aaabbcc图图3.14 (a)转换后的转换后的DFA M的状态图的状态图 状态状态 c

43、a b q0 * q1 q1q4 q2 q3 q2 q2 q3 q3 * q4 *q4图图3.14(b)转换后的转换后的DFA M的状态转换矩阵的状态转换矩阵 得到的确定的自动机接收的语言为得到的确定的自动机接收的语言为: : L(M)=a L(M)=am m b | m1 acb | m1 acn n | n1 | n1 与原来不确定的有限自动机接收的语言与原来不确定的有限自动机接收的语言L(ML(M) )一样。一样。 2021-10-1541 DFA DFA状态数的最小化状态数的最小化u对于一个对于一个NFA,NFA,当把它确定化后当把它确定化后, ,得到的得到的DFADFA所具有的状态数

44、可所具有的状态数可能并不是最小的。在设计词法分析程序时，效率是很重要的一能并不是最小的。在设计词法分析程序时，效率是很重要的一个因素。如果可能的话，我们应该构造尽可能小的个因素。如果可能的话，我们应该构造尽可能小的DFADFA。u自动机理论中有一个很重要的结论：自动机理论中有一个很重要的结论：定理定理3.2 3.2 对于有同一接受集的对于有同一接受集的FAFA，与之等价且具有最小状态数，与之等价且具有最小状态数的的DFADFA在同构意义下在同构意义下( (即不顾状态的命名即不顾状态的命名) )是唯一的。是唯一的。u从任何从任何FAFA中都可以得到这个最少状态的中都可以得到这个最少状态的DFAD

45、FA。 2021-10-1542n 最小状态最小状态DFA的含义的含义:n 没有多余状态没有多余状态(死状态死状态)；n 没有等价状态（不可区别）。没有等价状态（不可区别）。n 一个一个DFA可以通过消除多余状态和合并等价状态转换可以通过消除多余状态和合并等价状态转换成最小的与之等价的成最小的与之等价的DFA。n 有穷自动机的多余状态指：从自动机的开始状态出发，有穷自动机的多余状态指：从自动机的开始状态出发，任何输入串都不能到达的状态。任何输入串都不能到达的状态。2021-10-15431 1、可区分状态与等价状态、可区分状态与等价状态设设s s和和t t是一是一DFA MDFA M的两个不同

46、状态，的两个不同状态，u如果状态如果状态s,ts,t为某一输入串为某一输入串w w所区分所区分, ,是指从是指从s,ts,t中之一出发中之一出发, ,当扫视完当扫视完w w之后到达之后到达M M的终态的终态, ,但从另一个状态出发但从另一个状态出发, ,当扫视完同当扫视完同一个一个w w后而进入非终态。后而进入非终态。u如果如果s s和和t t不可区分不可区分( (即对任何输入串即对任何输入串w,w,当且仅当当且仅当f(s,w)Z,f(t,w)Z),f(s,w)Z,f(t,w)Z),则称则称s s和和t t等价。等价。2021-10-1544 C和和F同是终态同是终态, C和和F读入读入a都到

47、达都到达C,读入读入b都到达都到达E. C和和F等价等价(不可区别不可区别)；E和和D同是终态同是终态,读入读入a均到达均到达F,读入读入b均到均到达达D，因此，因此E和和D等价（不可区别）等价（不可区别）。CDBAEFSbaaaaabbbbbbaa 而而A，B是是可区别的可区别的。因为。因为A和和B可可由输入由输入b来区别，对输来区别，对输入入b，A走到非接受状态走到非接受状态B B，而，而B走到接受状态走到接受状态D。 判定两个判定两个状态状态p p和和q q不等价，只要找到一个不等价，只要找到一个w w*， 使使 （p,w)p,w) F F 且且 （q,w) q,w) F F，或，或者相

48、反。者相反。 W W称为判别序列。称为判别序列。2021-10-15452 2、DFADFA化简算法化简算法( (分割法分割法) )基本思路基本思路: :将将M M的状态集的状态集K K逐步进行划分逐步进行划分, ,以期最后按上述状态以期最后按上述状态的等价关系将的等价关系将K K划分为划分为r(rK)r(rK)个互不相交的子集个互不相交的子集, ,使得属使得属于同一子集中的任何两个状态都是等价的于同一子集中的任何两个状态都是等价的, ,而属于不同子集的而属于不同子集的任意两个状态都是可区分的。任意两个状态都是可区分的。设设DFA M= DFA M= （K K，f f，q q0 0，Z Z），

49、化简算法如下：），化简算法如下：1 1）将）将M M的状态集的状态集K K划分成终态集划分成终态集Z Z和非终态集和非终态集K KZ Z，记为，记为=Z, =Z, K KZ Z 2021-10-15462）设当前的划分）设当前的划分 中已含有中已含有m个子集，即个子集，即 =I1,I2,I m ，其，其中，属于不同子集的状态是可区分的，而属于同一子集的诸状中，属于不同子集的状态是可区分的，而属于同一子集的诸状态则是待区分的。即需对每一子集态则是待区分的。即需对每一子集Ii=Si1,Si2,Sin中的各个状态中的各个状态逐一检查，看能否对它们再进行区分。逐一检查，看能否对它们再进行区分。设设Si

50、p和和S i q是子集是子集Ii中的两个状态，若有某个中的两个状态，若有某个a，使，使f( Sip, a)= S j u、f( S i q, a)=S k v ，而状态，而状态S j u和和S k v属于不同的子集属于不同的子集I j和和I k，故故S j u与与S k v为某一为某一w所区分，从而所区分，从而Sip和和S i q必为必为aw所区分，故应所区分，故应将将Sip和和S i q分为两个子集。分为两个子集。2021-10-15473）重复第）重复第2步，直到所有子集都不能细分为止。步，直到所有子集都不能细分为止。4）将每个子集中的等价状态合并成一个等价代表状态。将状）将每个子集中的等

51、价状态合并成一个等价代表状态。将状态函数态函数(矩阵矩阵)中的所有状态用相应的等价代表状态表示。从状中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个子集中的等价状态结点合并成一个结点。态图上看，要将一个子集中的等价状态结点合并成一个结点。2021-10-1548正规表达式与正规集正规表达式与正规集 u词法分析程序自动生成系统的实现涉及正规表达式和有限自词法分析程序自动生成系统的实现涉及正规表达式和有限自动机理论。动机理论。u假设有字母表假设有字母表=0，1，那么，字母表上的每个元素都是正，那么，字母表上的每个元素都是正规表达式，这样的正规表达式表示的语言只有一个句子。规表达式，这样

52、的正规表达式表示的语言只有一个句子。例如，例如，0是一个正规表达式，表示的语言为是一个正规表达式，表示的语言为0，该语言只有一，该语言只有一个句子个句子0。u如果想表示更加复杂的语言，就必须使用运算符组成复杂的如果想表示更加复杂的语言，就必须使用运算符组成复杂的正规表达式，这一点很像用加减乘除运算符构造算术表达式。正规表达式，这一点很像用加减乘除运算符构造算术表达式。u在正规表达式中可使用的运算符有连接、或和闭包在正规表达式中可使用的运算符有连接、或和闭包。 2021-10-1549n 每一程序设计语言都有它自己的字符集每一程序设计语言都有它自己的字符集。语言中的每。语言中的每一单词或是一单词

53、或是上的单个字符上的单个字符, ,或是或是上的字符上的字符”按一定方按一定方式式”( (即进行一定的连接即进行一定的连接, ,或及闭包运算或及闭包运算) )组成的字符串。组成的字符串。n 如果把每一类单词均视为一种语言如果把每一类单词均视为一种语言, ,那么每一类单词都可那么每一类单词都可以用一个正规式来描述以用一个正规式来描述, ,而每一类单词中的全体单词也就而每一类单词中的全体单词也就组成了相应的正规集。组成了相应的正规集。n 正规式正规式( (正规表达式正规表达式) )是定义正规集的数学工具，是说明是定义正规集的数学工具，是说明单词的模式单词的模式(pattern)(pattern)的一种重要表示法（记号）。正规的一种重要表示法（记号）。正规式描述的集合称作正规集。式描述的集合称作正规集。正规表达式与正规集的定义正规表达式与正规集的定义2021-10-1550设设是有穷字母表，在是有穷字母表，在上的