《编译原理 学习.pptx》由会员分享，可在线阅读，更多相关《编译原理 学习.pptx（130页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、13.13.1设计扫描器时应考虑的几个问题设计扫描器时应考虑的几个问题词法分析阶段的必要性对于一个程序设计语言来说，关键字、标志符、常数、运算符及分隔符都是单词。它们的单词结构(即词法)也是用相应文法中的若干个产生式来描述的。词法分析与语法分析之间的关系通常有两种形式：1.词法分析作为独立的一遍(完全独立模式)词法分析可作为单独一遍来实现。这种词法分析的输出存入一个中间文件供语法分析使用。这样通过词法分析，就可以将字符串源程序转换成符号串源程序。字符串源程序 词法分析符号串源程序图3.1 词法分析单独作为一遍第1页/共130页22.词法分析程序作为语法分析程序的子程序（相对独立模式）将词法分析
2、和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其返给语法分析。如图3.2。字符串源程序 词法分析器 语法分析器图3.2词法分析作为语法分析子程序 取符号送符号 第2页/共130页3完全独立模式的好处：改进编译程序的效率、增强编译程序的可移植性、完全独立模式的好处：改进编译程序的效率、增强编译程序的可移植性、结构清晰、简化设计。结构清晰、简化设计。相对独立模式的好处：词法分析器和语法分析器被设计在同一趟，省去了相对独立模式的好处：词法分析器和语法分析器被设计在
3、同一趟，省去了存放单词的终结文件存放单词的终结文件第3页/共130页4词法分析过程词法分析过程逐个读入源程序字符，然后按照构词规则切分逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。单词是语言成一列单词，再转换成单词序列。单词是语言中具有独立意义的最小单位。中具有独立意义的最小单位。词标词标(token(token）是单词的机内表示，其格式由实）是单词的机内表示，其格式由实现系统规定。现系统规定。实现词法分析程序时，首先需要描述单词，其实现词法分析程序时，首先需要描述单词，其次需要执行某些相关操作识别单词。次需要执行某些相关操作识别单词。描述程序设计语言的词法的机制是描述
4、程序设计语言的词法的机制是3 3型文法和正型文法和正规式，识别机制是有穷状态自动机（规式，识别机制是有穷状态自动机（FAFA）。）。在词法分析过程中，与语法分析无关的单词应在词法分析过程中，与语法分析无关的单词应处理时可掠过，无需产生相应词标。处理时可掠过，无需产生相应词标。第4页/共130页5单词符号的内部表示单词符号的内部表示 词法分析的功能是识别出的具有独立意义的单词，并转化为相应的内部表示。词法分析的输出常采用二元式(class，value),如图3.3所示。class为以整数码或助记符,value则是该单词的值(如变量名在符号表中的序号,常数的二进制表示,以及运算符和分隔符的编码,等
5、等)class单词类别单词类别value单词值单词值图3.3词法分析程序的输出形式第5页/共130页6单词的分类单词的分类单词符号一般可分为下列五种：单词符号一般可分为下列五种：基本字，关键字；基本字，关键字；标识符；标识符；常数（量）；常数（量）；运算符；运算符；分隔符分隔符关键字关键字,运算符和分隔符每字为一类。标识符统一为一运算符和分隔符每字为一类。标识符统一为一类类,而常数一般按数据类型进行分类。而常数一般按数据类型进行分类。至于单词的值至于单词的值,一字一类的符号的类别号已能完全表示一字一类的符号的类别号已能完全表示相应的符号相应的符号,故不须再给出单词的值故不须再给出单词的值;但一
6、个类别中含但一个类别中含有多个单词有多个单词,则除了类别号则除了类别号,还须按某种编码给出单词还须按某种编码给出单词的值。的值。第6页/共130页7识别标识符的若干约定和策略识别标识符的若干约定和策略定义标识符的语法规则为 从语法上来说,标识符的长度似乎可以任意。然而,考虑实现技术,许多语言都对标识符的最大允许长度作了限制。第7页/共130页8设计扫描器时,按如下原则行事:1.如果一个标识符中的字符个数超过最大允许长度,则把尾部多出的字符截去;2.对于字符个数不超过最大允许长度的标识符,则按“尽可能长”的策略来识别标识符。一般而言,当一个语言的两种单词有相同的前缀时,其扫描器都应当考虑采用超前
7、搜索和多字符回退操作。第8页/共130页9源程序的输入及预处理源程序的输入及预处理为了提高读盘的效率和便于扫描器工作,通常采用缓冲输入的方案,即在内存设置一个适当大小的输入缓冲区,让操作系统直接将磁盘上的源程序字符串分批送入次缓冲区,供扫描器处理。实现源程序输入的一组函数(子程序)作为编译系统的最底层,称为输入系统。输入系统除了完成上述读盘任务外,还应支持超前搜索和多字符回退操作以及扫描器中依赖于系统的大部分操作。预处理工作包括将源程序中的注释、回车、换行、制表、空格、空白字符以及其他非实质性符号予以删除。第9页/共130页103.23.2正规文法和状态转换图正规文法和状态转换图v程序设计语言
8、中的单词是基本语法符号，单词符号的语法可用有效工具描述，且基于这类描述工具，可建立词法分析技术，进而建立词法分析程序的自动构造方法。v多数程序设计语言的单词语法都能用正规文法来描述。v为了直观描述正规文法，以方便单词识别，引入状态转换图。第10页/共130页11由正规文法构造状态转换图由正规文法构造状态转换图l 一个状态转换图是由一组矢线连接的有限个节点所组成的一个状态转换图是由一组矢线连接的有限个节点所组成的有向图。有向图。l 每个节点均代表在识别或分析过程中扫描器的状态，其中每个节点均代表在识别或分析过程中扫描器的状态，其中有一个是开始状态有一个是开始状态(带箭头带箭头)，至少有一个状态是
9、结束状态，至少有一个状态是结束状态（双圈）。（双圈）。l状态间用矢线连接，矢线上标记有符号，表示在矢线射出状态间用矢线连接，矢线上标记有符号，表示在矢线射出端的状态下，读入矢线上标记的符号可转换到矢线指向的端的状态下，读入矢线上标记的符号可转换到矢线指向的状态。状态图只有有穷个状态。状态。状态图只有有穷个状态。12开始a0abb第11页/共130页12正规文法形式：Aa或ABa（左线性）或AaB（右线性）其中：A,BVn，aVt正规文法描述语言单词，状态转换图可识别单词，它们之间存在等价关系。一.对于右线性文法构造状态转换图设G=(Vn,Vt,P,S)是一右线性文法,Vn中的每个非终结符号对应
10、状态图中的一个结点,且的开始符号所标记的结点为初态结点;增设一个不属于的符号F标记终态结点。|VN|=k,共有k+1个节点（状态）。第12页/共130页131.对于G中的每一条形如Aa的规则，从结点A引一条矢线到终态结点F，并用符号a标记这条矢线。2.对于G中每一条形如AaB的规则，从结点A引一条矢线到结点B，并用符号a标记这条矢线。注意:文法G中含有无用符号和无用产生式须事先予以删除;若L(G),则初态结点S也同时是一个终态结点;若G中含有产生式A,则将结点A设置为终态结点;第13页/共130页14baabVSUa例如：文法GSSaU|bVUbV|aVaU|bbQ第14页/共130页15GS
11、：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bbbbZBASaaaba,bDaab第15页/共130页16例如G:设无符号数的一般形式:dmdm-1d1d0.d-1d-2d n Ed ddd.d.Ed；E；dd；dd；第16页/共130页170534126dddddd.EE图3.4文法G的状态图d第17页/共130页18状态图识别符号串状态图识别符号串 利用状态转换图可识别相应文法所表示的符号串利用状态转换图可识别相应文法所表示的符号串。12开始a0abb定义：设VT*，如果状态转换图中存在一条从初态到终态的路径，此路径上的标记符号顺序相连构成符号串，则称为状态图所识别串。
12、状态图识别语言：状态图所识别的串集合。第18页/共130页19 对符号串对符号串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读入读入a a1 1，沿矢线方向到下一状态，在此状态时，沿矢线方向到下一状态，在此状态时扫描扫描a a2 2，l直至直至
13、W W中全部字符读完且进入终态中全部字符读完且进入终态F F，则，则W W已被接已被接受。受。2）状态转换图对符号串的识别第19页/共130页20bbbZBASaaaba,bDaab例：下面的状态图对于串baabba的识别SaA|bB，AbB|aD|a，BaA|bD|b，DaD|bD|a|b利用状态图识别串的过程，也即是为串建立一个推导的过程。第20页/共130页21结结 论论q 1 1、M M对符号串识别的方法是自顶向下的分析方法；对符号串识别的方法是自顶向下的分析方法；q 2 2、M M初态出发，沿某路径到达状态初态出发，沿某路径到达状态A Ak k，则，则a a1 1a a2 2a a3
14、 3a ak kA Ak k是是G G的一个句型，且是规范句型。当的一个句型，且是规范句型。当A A是终态时，是终态时，a a1 1a a2 2a ak k为为G G的句子。的句子。q 3 3、M M所识别的任一符号串所识别的任一符号串x x，必存在，必存在S S=*x=*x ，反之，反之，L(G)L(G)中的任一句子中的任一句子y y，必存在一条从，必存在一条从S S到到F F的路径，将的路径，将此路径上各矢线的标记依次连接起来所组成的符号串此路径上各矢线的标记依次连接起来所组成的符号串即为即为y y。M M能识别出能识别出L(G)L(G)中的全部句子。中的全部句子。第21页/共130页22
15、二、对于左线性文法构造状态转换图设G=(Vn,Vt,P,S)是一左线性文法,Vn中的每个非终结符号对应状态图中的一个结点。与右线性文法不同的是,增设一个不属于的符号R标记初态结点,并用S作为终态结点。|Vn|=k,共有k+1个节点（状态）。1.对于G中的每一条形如Aa的规则，从初态结点R引一条矢线到结点A，并用符号a标记这条矢线。2.对于G中每一条形如ABa的规则，从结点B引一条矢线到结点A，并用符号a标记这条矢线。第22页/共130页23例：SUa|VbUVb|aVUa|bbaabVSaQUbQS识别串：aabSVbUabaab从初态到终态的路径的标记连成的串为文法所定义串的左序。解决这一矛
16、盾把每条边改方向且把初态改终态，所有终态合成一个初态即可。第23页/共130页24例:设有正则文法GS：SU0|V1US1|1VS0|0画出该文法对应的状态图。解：根据状态图的画法，首先确定状态图的结点。文法中有三个非终结符号S、U、V，加上代表开始状态R的结点，因此共有四个结点，其中R结点为开始状态，S结点为终结状态。对于规则SU0|V1，则分别从结点U和结点V画指向结点S的弧线，并分别在弧线上标记0和1；对于规则US1|1，从S画指向U的弧线，从R画指向U的弧线，并分别在弧线上标记为1；对于规则VS0|0，分别从S和R画指向V画弧线，并分别在弧线上标记0。最终，我们可以画出该文法的状态图，
17、如图3.5所示。RUVS000111图3.5状态图课堂练习:画出标志符文法G的状态图SlSlSdl,dRlS第24页/共130页25 对于符号串W=a1a2a3an，aiVT 可对W识别。从初态F出发，自左至右逐个扫视W中的各个字符，在F下扫视的符号为a1；在节点F所射出诸矢线中寻找标记为a1的矢线（若不存在，则说明W有错）；读入a1沿矢线所指方向到下一状态，在从此状态扫描a2，直到W中全部字符读完且进入终态S，则W已被接受。符号串的识别该过程为自底向上的分析。第25页/共130页26AaaabSBFba,bb例如：文法GS SAa|Bb|Sa|Sb ABa|a BAb|b识别串：abaab第
18、26页/共130页27例:设有正则文法GS：SU0|V1US1|1VS0|0画出该文法对应的状态图。例:对句子0110进行的分析。首先，在开始状态R下扫描的第一个符号是0，转到状态V，表示0是句柄，归约到V。接下来，在状态V扫描1，转到状态S，此时句柄为V1，归约成S。再往下扫描1，由状态S转到状态U，表示句柄为S1归约为U。最后，扫描0，转到状态S，此时句柄为U0，归约为S，RUVS000111图3.5状态图第27页/共130页28图3.6（a）列出分析的每一步。形成图3.6（b）所示的语法树。自底向上的分析。步骤步骤状态状态扫描的字符扫描的字符余留部分余留部分1R01102V1103S10
19、4U05SSU0S1V103.6（a）输入串0110分析过程图3.6（b）输入串0110的语法树第28页/共130页29从上例的分析过程可看出，非终结符号仅作为规则右部第一个符号出现，所以，第一步对应形式A a的规则,总是把输入串的第一个符号作为句柄归约成一个非终结符号。其后各步总是应用形式为AB a的规则，把当前句型的头两个符号作为句柄归约成一个非终结符号A。在执行这个规约时，当前状态是B，扫描的字符是a，下一个状态是A。状态转换图可直观而清晰的描述单词符号的识别过程,可视为一种特殊的流程图,并可作为编写扫描器的依据。第29页/共130页30结结 论论q 1、M对符号串识别的方法是自底向上的
20、分析方法；q 2、M初态出发，沿某路径到达状态Ak，则Aka1a2a3ak是G的一个句型，当A是终态S时，a1a2ak为G的句子。q 3、M所识别的任一符号串x，必存在x能规约为S，反之，L(G)中的任一句子y，必存在一条从F到S的路径，将此路径上各矢线的标记依次连接起来所组成的符号串即为y。M能识别出L(G)中的全部句子。第30页/共130页31状态图的一种实现状态图的一种实现-状态矩阵法状态矩阵法程序设计语言一般含有若干类单词符号,我们可首先为每类单词建立一张状态转换图,然后将这些状态转换图合并成一张统一的状态图,最后再据此构造词法分析程序。计算机内表示状态转换图的方法之一是状态矩阵状态矩
21、阵：状态图中的各个状态S1，S2，Sn为行，以可能输入的输入符号a1，a2，am为列，组成一个n行m列矩阵。第31页/共130页32a1a2amBij=BSi,aj含义：当前状态Si，正扫视符号aj，则以序偶（Si，aj）去查询矩阵B，扫描器根据Bij的指示，执行相应的语义动作，转到Sk状态。若某aj不与Si配对，即状态图中从节点Si不存在以aj为标记的射出矢线，则Bj置为“error”,进行词法错误检查和处理。第32页/共130页33开始当前状态置为0标置终态”未经历”输入字符为文件结束符?当前状态对输入字符有后继动作?继续进行状态转移当前状态是终态?标置终态”已经历”记下当前状态和输入字符
22、位置经历过终态?回退到最近经历的终态的输入字符位置执行相应语义动作报告词法错误略去当前词文及输入字符当前状态置为0返回NNNYYY程序3.2状态矩阵驱动程序第33页/共130页343.3 3.3 有限自动机（有限自动机（FAFA）有限自动机是一种具有离散输入与输出系统的数学模型,是状态转换图的形式化。在这种数学模型中有有限个状态，状态间存在着转换关系。系统可以处于有限个状态中的任意一个之中，系统的当前状态概括了有关过去输入的信息。当系统处在某个状态之下读入一个字符时，会使系统所处的状态发生变化，从而形成状态转换。改变后的状态称为后继状态。第34页/共130页353.3 3.3 有限自动机（有限
23、自动机（FAFA）在状态转换中，后继状态可能为一个，也可能为多个。有限自动机分确定的和不确定的。所谓“确定的有限自动机”(Deterministic Finite Automata DFA)是指在当前的状态下，输入一个符号，有限自动机将转换到唯一的后继状态；“不确定的有限自动机”(Nondeterministic Finite Automata NFA)在当前状态下输入一个符号，可能有两种或两种以上可选择的后继状态。第35页/共130页36确定的有限自动机确定的有限自动机 1、确定的有限自动机定义将前面介绍的状态转换图抽象,可得到一个确定的有限自动机M（记作DFAM）是一个五元组：M=（K，f
24、，S0，Z）其中：K：是一个有限状态的集合。：是一个有限个输入字符组成的字母表f：状态转换函数，是一个KK的单值映射，形式为f(p,a)=q。S0：S0K，是唯一的初始状态。Z：ZK，称为终结状态集合。可见,一个确定的有限自动机是相应的状态图的一种形式描述。这是一个单值函数，指明当前状态为p，输入符号为a时，自动机将从状态p转换到下一个状态q，q称为p的后继状态。第36页/共130页37DFAM=（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|bVUbV|aVaU|bbaabVSUa
25、bQ第37页/共130页382、确定的有限自动机状态图 确定的有限自动机M可以用状态图来表示。状态图中的结点代表状态，它与自动机中的状态集合K相对应，其中包括初始状态S0和终结状态集合Z。状态间用矢线连接，矢线上标记有输入符号，每条矢线对应一个状态转换函数f，矢线上标记的输入符号集合就是字母表。例3.3设有限自动机DFAM=（0，1，2，3，a,b,f,0,3）f(0,a)=1f(0,b)=2f(1,a)=3f(1,b)=2f(2,a)=1f(2,b)=3f(3,a)=3f(3,b)=3画出该自动机对应的状态图。解：该自动机对应的状态图如图3.7所示。a,b0123baaabb图3.7状态图第
26、38页/共130页393、确定的有限自动机状态转换矩阵确定的有限自动机M还可以用状态转换矩阵来表示。矩阵中的第一列元素与自动机中的状态集合K相对应，且初始状态S0是第一列的第一个元素，右上角标记*的元素对应终结状态。矩阵中的第一行元素与字母表中的每个输入符号相对应。矩阵中的元素对应每个状态转换函数。如果有状态转换函数f(p，a)=q，其中p,q K，a，那么，就在矩阵中状态p对应的行和符号a对应的列单元中填入q。上例中的状态转换矩阵如图3.8所示。Sab0123*12321333图3.8状态转换矩阵第39页/共130页404、确定的有限自动机接受的语言 为了讲解确定的有限自动机如何接受或识别字
27、符串，首先，我们对状态转换函数作补充定义：f（S,）=S f（S,aw）=f（f（S,a）,w）,a，w*，即w是上的字符串例如,有f(0,a)=1 且f(1,b)=2，则f(0,ab)=f（f（0，a），b）=f(1,b)=2对一个确定的有限自动机M以及某个字符串x（x*），如果有 f(S0,x)=S，且SZ则字符串x就被该自动机M所接受。即将f的定义域扩充到K*第40页/共130页41从状态图上看，如果一个字符串能被自动机接受，则存在一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号一次连接起来就组成了字符串x。若初始状态也是终结状态，或是存在一条从初始状态到某一终结状态
28、的路径，路径上的所有标记都是，则可被NFA接受。一个确定的有限自动机M所接受的语言就是所能接受的字符串构成的集合，用L（M）表示，可定义为：L（M）=x|f(S0,x)Z，x*第41页/共130页42DFADFA识别符号串识别符号串 *上的字符串上的字符串t t在在M M上运行上运行q 输入字符串输入字符串t t，(表示成表示成Tt1Tt1的形式，其中的形式，其中TT，t1*t1*）在）在DFA MDFA M上运行的定义为：上运行的定义为：（Q,Tt1Q,Tt1）=（Q,TQ,T）,t1,t1）其中其中QKQK*上的字符串上的字符串t t被被M M接受接受q 若若t t*，(S,t)=P(S,
29、t)=P，其中，其中S S为为DFA MDFA M的开始状态，的开始状态，P P Z Z，Z Z为终态集。则称为终态集。则称t t为为DFA MDFA M所接受（识别）所接受（识别）第42页/共130页43例1：证明t=baab被下面的DFA所接受。QbSUVaaaba,bDFAM=（S，U，V，Q，a，b，f，S，Q）其中f定义为：（S，a）=U（V，a）=U（S，b）=V（V，b）=Q（U，a）=Q（Q，a）=Q（U，b）=V（Q，b）=Q（S，baab）=（S，b），aab）=（V，aab）=（V，a），ab）=（U，ab）=（U，a），b）=（Q，b）=QQ属于终态。得证。第43页/共
30、130页44例2：根据如下状态图，写出DFA，证明baab可为此DFA接受。UV开始aSabbabDFAM=（S，U，V，a，b，f，S，V）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Sf（V，b）=Sf（U，a）=Uf（U，b）=Vf（S，baab）=f（f（S，b），aab）=f（S，aab）=f（f（U，a），ab）=f（U，ab）=f（f（U，a），b）=f（U，b）=VV属于终态。得证。4DFAM所能接受的字符串的全体记为L(M)。4此例的DFA所识别语言为(a|b)*ab第44页/共130页45算法：算法：模拟DFA。输输入入 输入串x，由文件结束符eof结尾。一
31、个DFA D，其开始状态是s0，其接受状态集合是F。输输 出出 如 果D接 受x，则 回 答“yes”，否则回答“no”。方方 法法 对 输 入 串x，函 数move(s,c)给出一个状态，它是面临输入符号c，状态s的转换。函数nextchar()返回输入串x中的下一个字符。s:=s0;c:=nextchar(x);whileceofdo s:=move(s,c);c:=nextchar(x)end;ifs属于Zthenreturn“yes”elsereturn“no”;第45页/共130页46例3.4，设计能接受偶数个0和偶数个1组成的串的有限自动机，画出其状态图及状态转换矩阵并判别1101
32、01、11101能否被该自动机接受。第46页/共130页47解：首先设计能接受偶数个0和偶数个1组成的数字串的有限自动机如下：M1=（S，A，B，C，0，1，f，S，S）f（S，0）=Bf（S，1）=Af（A，0）=Cf（A，1）=Sf（B，0）=Sf（B，1）=Cf（C，0）=Af（C，1）=B其状态图及状态转换矩阵分别如图3.9(a)(b)所示。S01S*ABCBACSSCABSABC11010010图3.9(a)图3.9(b)下面判别110101、11101能否被该自动机接受：f(S，110101)=f(A，10101)=f(S，0101)=f(B，101)=f(C，01)=f(A，1)
33、=S(接受)f(S，11101)=f(A，1101)=f(S，101)=f(A，01)=f(C，1)=B(拒绝)第47页/共130页48lDFA的确定性表现在转换函数:KK是一个单值函数，即：对任何状态kK以及输入符号a，(k,a)能唯一确定下一个状态。l从状态转换图来看，若字母表含有n个输入字符，那么任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。总 结：第48页/共130页49非确定的有限自动机非确定的有限自动机 非确定的有限自动机与确定的有限自动机的区别主要是状态转换函数f为多值函数。1、非确定的有限自动机定义一个非确定的有限自动机NFA M是一个五元式M=（K，f
34、，S0，Z）其中:K：有穷状态集;：输入字母表 S0：开始状态S0K;Z：终止状态集ZK f：状态转换函数，为K到K的子集的映射。形式为 f(S i,a j)=Sk1,Sk2,S km非确定的有限自动机同样可以用状态图和状态转换矩阵来表示，表示方法与确定的相同。第49页/共130页502、非确定的有限自动机接受的语言与确定的有限自动机一样，为了判别一个字符串x能否被NFA M接受，我们还需要对状态转换函数做补充定义：f(S,)=S f(S,aw)=f(f(S,a),w),a,w*再设 f(S,a)=Sk1,Sk2,Skm且定义 f(Sk1,Sk2,Skm,w)=mi=1f(Ski,w)表示从M
35、的当前状态集出发，扫描字符串x后，所到达的状态集等于从当前状态集的每一个状态出发，扫描字符串x后所到达的状态集之和。即将f的定义域扩充到2K*第50页/共130页51对于某个字符串x（x*），若有f(S0,x)=K，且KZ，则x为M所接受。从状态图上看，如果一个字符串能被自动机接受，则存在一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号依次连接起来就组成了字符串x。M所接受的语言为L（M）=x|f(S0,x)Z，x*第51页/共130页52例3.5，有NFAM=（0,1,2，a,b,f,0,2）其中：f（0，a）=2,f（0，）=1,f（1，b）=1,2,f（2，a）=2,
36、f（2，b）=2画出其状态图及状态转换矩阵，确定该自动机接收的语言。第52页/共130页53例3.5，有NFAM=（0,1,2，a,b,f,0,2）其中：f（0，a）=2,f（0，）=1,f（1，b）=1,2,f（2，a）=2,f（2，b）=2画出其状态图及状态转换矩阵，确定该自动机接收的语言。解：不确定的有穷自动机用状态图和状态转换矩阵来表示，如图3.10(a)(b)所示。该自动机接受的语言为L(M)=(a|bm)(a|b)n|m1,n0021ba,babSab02111,22*22图3.10(a)图3.10(b)a(ab)nbm(ab)n返回第53页/共130页54l *上的字符串t在M上
37、运行q 一个输入符号串t，（表示成Tt1的形式，其中T，t1*）在NFA M上运行的定义为：（Q，Tt1）=（Q，T），t1）QKl*上的字符串t被NFA M接受q 若t*，(S0,t)=P1,P2,P3,，其中S0S，Pi Z，则称t为NFA M所接受（识别）。NFA识别符号串第54页/共130页55*上的符号串t被NFAM接受也可理解为：l 对于中的串t，若存在一条从某初态到某一终态的路径，且这条路上所有弧的标记字依序连接成的串等于t，则称t可为NFA M所识别(接受)。l 若M的某些结点既是初态又是终态，或者存在一条从某个初态到某个终态的路径,其上所有弧的标记均为，那么可被M所接受。第5
38、5页/共130页56与与DFADFA的等价性的等价性 所谓NFA的确定化,是指对任给的NFA,都能相应的构造一DFA,使它们有相同的接受集。证明的思路:让所要构造的DFA去模拟相应的NFA的工作过程,即用DFA的一个状态去记录NFA读入一个输入符号后可能到达的所有状态。定理3.1对于字母表上的任一NFA M,必存在上与M等价的DFA M。证明:设M=(K,f,S0,Z)是上的一个NFA,今构造一个上的DFA M=(K,f,S0,Z),其方法如下:第56页/共130页57K=2K。例如,对K的一个子集S1,S2,Si,我们用记号S1,S2,Si表示K中的一个状态,特别地,令S0=S0映射f的定义
39、为：当且仅当 f(S1,S2,Si,a)=R1,R2,Rj 时 f(S1,S2,Si,a)=R1,R2,Rj终态集Z定义为 Z=Sp,Sq,SrSp,Sq,SrK且Sp,Sq,SrZ 第57页/共130页58ab0q01*q1*0,1*q2*0,1q21q10,1q20,1q20,1q2解:构造等价的DFA如图3.11(b)M=(K,a,b,f,0,Z)其中K=0,1,0,1,如图f(0,a)=0,1f(0,b)=1f(1,a)=f(1,b)=0,1由于f(0,1,a)=f(0,a)f(1,a)=0,1f(0,1,b)=f(0,b)f(1,b)=0,1故有f(0,1,a)=f(0,1,b)=0
40、,1Z=1,0,1ab01*0,110,1图3.11(a)NFAM图3.11(b)DFAM例3.6考虑NFAM=(0,1,a,b,f,0,1)状态转换矩阵如图3.11(a)所示。第58页/共130页59具有具有动作的动作的FAFA 一个具有动作的有限自动机NFAM也是一个五元式M=（K，f，S0，Z）其中,K，S0，Z的含义同前,而f却是K()到2k的一个映射。则对于f(q,a)则由状态p组成：当NFA处于状态q而扫视的输入字符为a(a或a=)时，它的下一个状态将是p。第59页/共130页60把识别各类单词的NFA用矢线连接起来,组成一个单一的NFA,然后把所得的NFA确定化,最后再据此设计词
41、法分析程序。例1：设某语言有如下几个单词：TEP，RING，WITCH，写出识别这些单词的NFA。例2：写出识别下面三个关键字的状态转移图STEP，STRING，SWITCH第60页/共130页61具有具有动作的动作的NFANFA的确定化的确定化为了实现NFA到DFA的转化，首先要介绍两个状态子集的计算方法，它们是从NFA到DFA的转化过程中需要计算的状态子集。1、状态集P的闭包设P是一NFAM的状态集K的一个子集，则-closure(P)称为状态集P的闭包，闭包也是状态集K的一个子集，其计算方法如下：1）若qP，则q-closure(P)，即P的所有成员都是P的闭包的成员（状态q本身包含在这
42、个集合之中）2）若qP，那么从q出发经过任意条弧而能到达的任何状态都属于-closure(P)。第61页/共130页62例3.7，对图3.12所示的NFAM，求P=1、P=2、P=1，2的闭包。解：当P=1时，有f(1,)=3，f(3,)=6，f(3,)=4，所以-closure(1)=1,3,4,6当P=2,有f(2,)=6，所以-closure(2)=2,6当P=1,2,则-closure(1,2)=-closure(1)-closure(2)=1,3,4,62,6=1,2,3,4,6143265aaa图3.12NFAM状态图第62页/共130页632、状态集P的a弧转换集设P仍是一NFA
43、M的状态集的子集，P=p1,p2,pn,a，即a是字母表的一个输入符号，则P的a弧转换集为：Pa=-closure(J)，其中J=f(p1,p2,pn,a)=f(p1,a)f(p2,a)f(pn,a)即J是从状态子集P中的每个状态出发，沿着标记为a的矢线而转移到达的状态所组成的集合。从定义可知，状态集P的a弧转换集Pa也是状态子集，其元素为从P的每个状态出发，沿着标记为a的矢线所转移到达的后继状态的集合，再加上这些后继状态集合中的每个状态的闭包，即转移后再经矢线所能到达的状态的集合。第63页/共130页64例3.8：对图3.12所示的NFAM，若P=1，求Pa。解：Pa=-closure(J)
44、=-closure(f(1,a)=-closure(2,4)=2,4,6143265aaa图3.12例3.7的NFAM状态图第64页/共130页6512534687aaaP=1,P=1,2求Pa,Pa第65页/共130页6612534687aaaP=1,P=1,2求Pa,PaPa=-closure(J)=-closure(f(1,a)=-closure(4,5)=4,7,5,6,2Pa=-closure(J)=-closure(f(1,2,a)=-closure(3,5,4)=3,8,5,6,2,4,7第66页/共130页673、根据NFAM构造DFAM(子集法)基本思路:首先将-closur
45、e(S0)作为M的初态q0,然后对于所有的输入符号a,将q0的a弧转换集作为M的状态,如此等等,直到不再有新的状态出现为止。下面我们通过一个例子来介绍根据NFAM构造DFAM的方法。第67页/共130页68假设有一个不确定的有限自动机NFAM=（K，f，S0，Z），其中K=1,2,3,4，=a,b,c，S0=1，Z=4，状态图如图3.13所示。接受的语言：L(M)=amb|m1acn|n1，构造一个DFAM=（K，f，q0，Z），使L(M)=L(M)1234aaaccb图3.13NFAM的状态图第68页/共130页69构造确定的有限自动机过程如下：1）首先根据闭包的计算方法求NFAM的开始状态
46、S0的闭包，从而确定DFAM的开始状态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,3将2,3作为新状态,并令q1=2,3，即得到f(q0,a)=q11234aaaccb第69页/共130页70f(q0,b)=q0b=-closure(f(1，4,b)=-closure()=f(q0,c)=q0c=-closur
47、e(f(1，4,c)=-closure()=由于f(q0,b)=，f(q0,c)=，说明没有新状态产生。至此，我们得到有关开始状态q0的全部状态转换函数只有一个，即f(q0,a)=q1。1234aaaccb第70页/共130页713）按步骤2的方法，对每个新状态计算相关的状态转换函数。计算状态q1的状态转换函数：f(q1,a)=q1a=2，将2作为新状态,并令q2=2f(q1,b)=q1b=4，将4作为新状态,并令q3=4f(q1,c)=q1c=3,4，将3，4作为新状态,并令q4=3,4至此，得到有关开始状态q1的全部状态转换函数。1234aaaccb第71页/共130页72接下来，计算状态
48、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,a)=，f(q4,b)=，f(q4,c)=3,4=q4计算到此，不再有新状态出现。1234aaaccb第72页/共130页734）根据上面求出的各个状态确定终结状态集Z=p|pZ，其中p为M的每个状态子集。因为q0=1,4、q1=2,3、q2=2、q3=4、q4=3,4，而Z=4，q0、q3、q4与Z相交不为空，所以确定终结状态集Z=q0,q3,q4第73页/共130页74最后,我们得到确定的有穷自动机如下：DFAM=(q0,
49、q1,q2,q3,q4,a,b,c,f,q0,q0,q3,q4)其中状态转换函数为：f(q0,a)=q1f(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)所示。第74页/共130页75q0q1q2q3q4aaabbcc图3.14(a)转换后的DFAM的状态图状态状态abcq0*q1q1q2q3q4q2q2q3q3*q4*q4图3.14(b)转换后的DFAM的状态转换矩阵得到的确定的自动机接收的语言为:L(M)=am b|m1 acn|n1 与原来不确定的有
50、限自动机接收的语言L(M)一样。第75页/共130页76IaIbi，1，21，2，31，2，41，2，31，2，41，2，3，5，6，f1，2，41，2，31，2，4，5，6，f1，2，3，5，6，f1，2，3，5，6，f1，2，4，6，f1，2，4，5，6，f1，2，3，6，f1，2，4，5，6，f1，2，4，6，f1，2，3，6，f1，2，4，5，6，f1，2，3，6，f1，2，3，5，6，f1，2，4，6，fSABACBBADCCEDFDEFDFCET4f35621iaaaabbbbCDBAEFSbaaaaabbbbbbFa第76页/共130页77假定所构造的子集族为C，即C=(T1,T