编译原理 第3章.ppt

1、编译原理,0,第3章 词法分析,词法分析程序又称扫描器，是编译过程的第一步，是下一步进行语法分析的基础。词法分析的任务: 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位“单词”，并将其转化为内部编码形式。 删除无用的空白字符和回车字符以及其他非实质性字符。 删除注释。 进行词法检查,报告所发现的错误。,编译原理,1,3.1设计扫描器时应考虑的几个问题,3.1.1词法分析阶段的必要性 对于一个程序设计语言来说，关键字、 标志符、常数、运算符及分隔符都是单词。它们的单词结构(即词法)也是用相应文法中的若干个产生式来描述的。,词法分析与语法分析之间的关系通常有两种形式： 1.词法分析作

2、为独立的一遍(完全独立模式) 词法分析可作为单独一遍来实现。这种词法分析的输出存入一个中间文件供语法分析使用。这样通过词法分析，就可以将字符串源程序转换成符号串源程序。,字符串源程序,词法分析,符号串源程序,图3.1 词法分析单独作为一遍,编译原理,2,2.词法分析程序作为语法分析程序的子程序（相对独立模式） 将词法分析和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其返给语法分析。如图3.2。,编译原理,3,完全独立模式的好处：改进编译程序的效率、增强编译程

3、序的可移植性、结构清晰、简化设计。 相对独立模式的好处：词法分析器和语法分析器被设计在同一趟，省去了存放单词的终结文件,编译原理,4,词法分析过程,逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。单词是语言中具有独立意义的最小单位。 词标(token）是单词的机内表示，其格式由实现系统规定。 实现词法分析程序时，首先需要描述单词，其次需要执行某些相关操作识别单词。 描述程序设计语言的词法的机制是3型文法和正规式，识别机制是有穷状态自动机（FA）。 在词法分析过程中，与语法分析无关的单词应处理时可掠过，无需产生相应词标。,编译原理,5,3.1.2 单词符号的内部表示,词法分

4、析的功能是识别出的具有独立意义的单词，并转化为相应的内部表示。 词法分析的输出常采用二元式(class，value),如图3.3所示。class为以整数码或助记符,value则是该单词的值(如变量名在符号表中的序号,常数的二进制表示,以及运算符和分隔符的编码,等等),图3.3 词法分析程序的输出形式,编译原理,6,单词的分类,单词符号一般可分为下列五种： 基本字，关键字； 标识符； 常数（量）； 运算符； 分隔符 关键字,运算符和分隔符每字为一类。标识符统一为一类,而常数一般按数据类型进行分类。 至于单词的值,一字一类的符号的类别号已能完全表示相应的符号,故不须再给出单词的值;但一个类别中含有

5、多个单词,则除了类别号,还须按某种编码给出单词的值。,编译原理,7,3.1.3 识别标识符的若干约定和策略,定义标识符的语法规则为 从语法上来说,标识符的长度似乎可以任意。 然而,考虑实现技术,许多语言都对标识符的最大允许长度作了限制。,编译原理,8,设计扫描器时,按如下原则行事: 如果一个标识符中的字符个数超过最大允许长度,则把尾部多出的字符截去; 对于字符个数不超过最大允许长度的标识符,则按“尽可能长”的策略来识别标识符。 一般而言 ,当一个语言的两种单词有相同的前缀时,其扫描器都应当考虑采用超前搜索和多字符回退操作。,编译原理,9,3.1.4 源程序的输入及预处理,为了提高读盘的效率和便

6、于扫描器工作,通常采用缓冲输入的方案,即在内存设置一个适当大小的输入缓冲区,让操作系统直接将磁盘上的源程序字符串分批送入次缓冲区,供扫描器处理。 实现源程序输入的一组函数(子程序)作为编译系统的最底层,称为输入系统。 输入系统除了完成上述读盘任务外,还应支持超前搜索和多字符回退操作以及扫描器中依赖于系统的大部分操作。 预处理工作包括将源程序中的注释、回车、换行、制表、空格、空白字符以及其他非实质性符号予以删除。,编译原理,10,3.2正规文法和状态转换图,程序设计语言中的单词是基本语法符号，单词符号的语法可用有效工具描述，且基于这类描述工具，可建立词法分析技术，进而建立词法分析程序的自动构造方

7、法。 多数程序设计语言的单词语法都能用正规文法来描述。 为了直观描述正规文法，以方便单词识别，引入状态转换图。,编译原理,11,3.2.1 由正规文法构造状态转换图,一个状态转换图是由一组矢线连接的有限个节点所组成的有向图。 每个节点均代表在识别或分析过程中扫描器的状态，其中有一个是开始状态(带箭头)，至少有一个状态是结束状态（双圈）。 状态间用矢线连接，矢线上标记有符号，表示在矢线射出端的状态下，读入矢线上标记的符号可转换到矢线指向的状态。状态图只有有穷个状态。,编译原理,12,正规文法形式： Aa或ABa（左线性）或AaB（右线 性）其中：A,BVn， aVt 正规文法描述语言单词，状态转

8、换图可识别单词，它们 之间存在等价关系。 一.对于右线性文法构造状态转换图 设G=(Vn,Vt,P,S)是一右线性文法,Vn中的每个非终结符 号对应状态图中的一个结点,且的开始符号所标记的 结点为初态结点; 增设一个不属于的符号F标记终态结点。 |VN|=k,共有k+1个节点（状态）。,编译原理,13,对于G中的每一条形如Aa的规则，从结点A引一条矢线到终态结点F，并用符号a标记这条矢线。 对于G中每一条形如AaB的规则，从结点A引一条矢线到结点B，并用符号a标记这条矢线。 注意: 文法G中含有无用符号和无用产生式须事先予以删除; 若L(G),则初态结点S也同时是一个终态结点; 若G中含有产生

9、式A,则将结点A设置为终态结点;,编译原理,14,b,a,a,b,V,S,U,a,例如：文法GS SaU|bV UbV|a VaU|b,b,编译原理,15,GS： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,编译原理,16,例如G: 设无符号数的一般形式:dmdm-1d1d0.d-1d-2d n Ed dd d . d . E d； E； d d； ； d d； ,编译原理,17,0,5,3,4,1,2,6,d,d,d,d,d,d,.,.,E,E,图3.4文法G的状态图,d,编译原理,18,状态图识别符号串,利用状态转换图可识别相应文法所表示的符号串。,定义：设VT

10、 * ，如果状态转换图中存在一条从初态到终态的路径，此路径上的标记符号顺序相连构成符号串，则称为状态图所识别串。 状态图识别语言：状态图所识别的串集合。,编译原理,19,对符号串W=a1a2a3an，ai VT 识别过程： 从初态S出发，自左至右逐个扫描W中的字符，在S状态下扫视的符号为a1； 在节点S所射出诸矢线中寻找标记为a1的矢线(若不存在，则说明W有错)； 读入a1，沿矢线方向到下一状态，在此状态时扫描a2， 直至W中全部字符读完且进入终态F，则W已被接受。,2）状态转换图对符号串的识别,编译原理,20,例：下面的状态图对于串baabba的识别 SaA|bB，AbB|aD|a，BaA|

11、bD|b，DaD|bD|a|b,利用状态图识别串的过程，也即是为串建立一个推导的过程。,编译原理,21,结 论,1、M对符号串识别的方法是自顶向下的分析方法； 2、M初态出发，沿某路径到达状态Ak，则a1a2a3akAk是G的一个句型，且是规范句型。当A是终态时，a1a2ak为G的句子。 3、M所识别的任一符号串x，必存在S=*x ，反之，L(G)中的任一句子y，必存在一条从S到F的路径，将此路径上各矢线的标记依次连接起来所组成的符号串即为y。 M能识别出L(G)中的全部句子。,编译原理,22,二、对于左线性文法构造状态转换图 设G=(Vn,Vt,P,S)是一左线性文法,Vn中的每个非终结符号

12、对应状态图中的一个结点。与右线性文法不同的是,增设一个不属于的符号R标记初态结点,并用S作为终态结点 。|Vn|=k,共有k+1个节点（状态）。 对于G中的每一条形如Aa的规则，从初态结点R引一条矢线到结点A，并用符号a标记这条矢线。 对于G中每一条形如ABa的规则，从结点B引一条矢线到结点A，并用符号a标记这条矢线。,编译原理,23,例：SUa|Vb UVb|a VUa|b,b,a,a,b,V,S,a,U,b,Q,识别串：aab SVbUab aab 从初态到终态的路径的标记连成的串为文法所定义串的左序。 解决这一矛盾把每条边改方向且把初态改终态，所有终态合成一个初态即可。,编译原理,24,

13、例:设有正则文法GS： SU0|V1 US1|1 VS0|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。最终，我们可以画出该文法的状态图，如图3.5所示。,R,U,V,S,0,0,0,1,1,1,图3.5 状态

14、图,课堂练习:画出标志符文法G的状态图 S l S l S d,l, d,R,l,S,编译原理,25,对于符号串W=a1a2a3an，aiVT 可对W识别。 从初态F出发，自左至右逐个扫视W中的各个字符，在F下扫视的符号为a1； 在节点F所射出诸矢线中寻找标记为a1的矢线（若不存在，则说明W有错）； 读入a1沿矢线所指方向到下一状态，在从此状态扫描a2， 直到W中全部字符读完且进入终态S，则W已被接受。,符号串的识别,该过程为自底向上的分析。,编译原理,26,例如：文法GS SAa|Bb|Sa|Sb ABa|a BAb|b 识别串：abaab,编译原理,27,例:设有正则文法GS： SU0|V

15、1 US1|1 VS0|0 画出该文法对应的状态图。 例:对句子0110进行的分析。 首先，在开始状态R下扫描的第一个符号是0，转到状态V，表示0是句柄，归约到V。接下来，在状态V扫描1，转到状态S，此时句柄为V1，归约成S。再往下扫描1，由状态S转到状态U，表示句柄为S1归约为U。最后，扫描0，转到状态S，此时句柄为U0，归约为S，,R,U,V,S,0,0,0,1,1,1,图3.5 状态图,编译原理,28,图3.6（a）列出分析的每一步。形成图3.6（b）所示的语法树。 自底向上的分析。,S,U,0,S,1,V,1,0,3.6（a）输入串0110分析过程,图3.6（b）输入串0110的语法树

16、,编译原理,29,从上例的分析过程可看出，非终结符号仅作为规则右部第一个符号出现，所以，第一步对应形式A a的规则,总是把输入串的第一个符号作为句柄归约成一个非终结符号。其后各步总是应用形式为AB a的规则，把当前句型的头两个符号作为句柄归约成一个非终结符号A。在执行这个规约时，当前状态是B，扫描的字符是a，下一个状态是A。,状态转换图可直观而清晰的描述单词符号的识别过程, 可视为一种特殊的流程图,并可作为编写扫描器的依据。,编译原理,30,结 论,1、M对符号串识别的方法是自底向上的分析方法； 2、M初态出发，沿某路径到达状态Ak， 则Aka1a2a3ak是G的一个句型，当A是终态S时，a1

17、a2ak为G的句子。 3、M所识别的任一符号串x，必存在x能规约为S ，反之，L(G)中的任一句子y，必存在一条从F到S的路径，将此路径上各矢线的标记依次连接起来所组成的符号串即为y。 M能识别出L(G)中的全部句子。,编译原理,31,3.2.2 状态图的一种实现-状态矩阵法,程序设计语言一般含有若干类单词符号,我们可首先为每类单词建立一张状态转换图,然后将这些状态转换图合并成一张统一的状态图,最后再据此构造词法分析程序。 计算机内表示状态转换图的方法之一是状态矩阵 状态矩阵：状态图中的各个状态S1，S2，Sn为行，以可能输入的输入符号a1，a2，am为列，组成一个n行m列矩阵。,编译原理,3

18、2,a1 a2 am,Bij=BSi,aj 含义：当前状态Si，正扫视符号aj，则以序偶（Si，aj）去查询矩阵B，扫描器根据Bij的指示，执行相应的语义动作，转到Sk状态。若某aj不与Si配对，即状态图中从节点Si不存在以aj为标记的射出矢线，则Bj置为“error”,进行词法错误检查和处理。,编译原理,33,开始,当前状态置为0 标置终态”未经历”,输入字符为 文件结束符?,当前状态对输入 字符有后继动作?,继续进行状态转移,当前状态是终态?,标置终态”已经历” 记下当前状态和输入字符位置,经历过终态?,回退到最近经历的终态的输入字符位置 执行相应语义动作,报告词法错误 略去当前词文及输入

19、字符 当前状态置为0,返回,N,N,N,Y,Y,Y,程序3.2 状态矩阵驱动程序,编译原理,34,3.3 有限自动机（FA）,有限自动机是一种具有离散输入与输出系统的数学模型,是状态转换图的形式化。在这种数学模型中有有限个状态，状态间存在着转换关系。系统可以处于有限个状态中的任意一个之中，系统的当前状态概括了有关过去输入的信息。 当系统处在某个状态之下读入一个字符时，会使系统所处的状态发生变化，从而形成状态转换。改变后的状态称为后继状态。,编译原理,35,3.3 有限自动机（FA）,在状态转换中，后继状态可能为一个，也可能为多个。有限自动机分确定的和不确定的。 所谓“确定的有限自动机” ( D

20、eterministic Finite Automata DFA)是指在当前的状态下，输入一个符号，有限自动机将转换到唯一的后继状态； “不确定的有限自动机” (Nondeterministic Finite Automata NFA)在当前状态下输入一个符号，可能有两种或两种以上可选择的后继状态。,编译原理,36,3.3.1 确定的有限自动机,1、确定的有限自动机定义 将前面介绍的状态转换图抽象,可得到一个确定的有限自动机M（记作DFA M）是一个五元组： M=（ K， ，f，S0，Z） 其中： K：是一个有限状态的集合。 ：是一个有限个输入字符组成的字母表 f：状态转换函数，是一个KK的单

21、值映射， 形式为f (p, a)=q 。 S0：S0K，是唯一的初始状态。 Z：ZK，称为终结状态集合。 可见,一个确定的有限自动机是相应的状态图的一种形式描述。,这是一个单值函数，指明当前状态为p，输入符号为a时，自动机将从状态p转换到下一个状态q，q称为p的后继状态。,编译原理,37,DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为： f（S，a）=Uf（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（U，b）=V,例：SaU|bV UbV|a VaU|b,编译原理,38,2、确定的有限自动机状态图,确定的有限自动机M可以用状态图来表示。状态图中的结点代表

22、状态，它与自动机中的状态集合K相对应，其中包括初始状态S0和终结状态集合Z。状态间用矢线连接，矢线上标记有输入符号，每条矢线对应一个状态转换函数f，矢线上标记的输入符号集合就是字母表。,例3.3 设有限自动机 DFA M=（0，1，2，3，a,b,f,0,3） 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 画出该自动机对应的状态图。 解：该自动机对应的状态图如图3.7所示。,a,b,0,1,2,3,b,a,a,a,b,b,图3.7 状态图,编译原理,39,3、确定的有限自动机状态转换矩阵 确定的有

23、限自动机M还可以用状态转换矩阵来表示。矩阵中的第一列元素与自动机中的状态集合K相对应，且初始状态S0是第一列的第一个元素，右上角标记*的元素对应终结状态。矩阵中的第一行元素与字母表中的每个输入符号相对应。矩阵中的元素对应每个状态转换函数。如果有状态转换函数 f (p，a)=q，其中p, q K，a，那么，就在矩阵中状态p对应的行和符号a对应的列单元中填入q。上例中的状态转换矩阵如图3.8所示。,图3.8 状态转换矩阵,编译原理,40,4、确定的有限自动机接受的语言,为了讲解确定的有限自动机如何接受或识别字符串，首先，我们对状态转换函数作补充定义： f（S,）=S f（S,aw）=f（f（S,a

24、）,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*,编译原理,41,从状态图上看，如果一个字符串能被自动机接受，则存在一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号一次连接起来就组成了字符串x。 若初始状态也是终结状态，或是存在一条从初始状态到某一终结状态的路径，路径上的所有标记都是，则可被NFA接受。 一个确定的有限自动机M所接受的

25、语言就是所能接受的字符串构成的集合，用L（M）表示，可定义为： L（M）=x|f(S0,x)Z，x*,编译原理,42,DFA识别符号串,*上的字符串t在M上运行 输入字符串t，(表示成Tt1的形式，其中T，t1*）在DFA M上运行的定义为： （Q,Tt1）= （ （Q,T）,t1） 其中QK *上的字符串t被M接受 若t*， (S,t)=P，其中S为DFA M的开始状态， P Z，Z为终态集。则称t为DFA M所接受（识别）,编译原理,43,例1：证明t=baab被下面的DFA所接受。,DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为： （S，a）=U （V，a）=U （S，b

26、）=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） =Q Q属于终态。 得证。,编译原理,44,例2：根据如下状态图，写出DFA，证明baab可为此DFA接受。,DFA M=（S，U，V，a，b，f，S，V）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=S f（V，b）=S f（U，a）=U f（U，b）=V,f（S，baab） =f（f（S，b），aab） =f（S，aab） =f（f（U，a），a

27、b） =f（U，ab） =f（f（U，a），b） =f（U，b）=V V属于终态。得证。,DFA M所能接受的字符串的全体记为 L(M)。 此例的DFA所识别语言为(a|b)*ab,编译原理,45,算法：模拟DFA。 输入 输入串x，由文件结束符eof结尾。一个DFA D，其开始状态是s0，其接受状态集合是F。 输出 如果D接受x，则回答“yes”，否则回答“no”。 方法 对输入串x，函数move(s, c)给出一个状态，它是面临输入符号c，状态s的转换。函数nextchar( )返回输入串x中的下一个字符。,s := s0 ; c := nextchar(x); while c eof d

28、o s := move (s, c); c := nextchar(x) end; if s属于Z then return “ yes ” else return “ no ” ;,编译原理,46,例3.4，设计能接受偶数个0和偶数个1组成的串的有限自动机，画出其状态图及状态转换矩阵并判别110101、11101能否被该自动机接受。,编译原理,47,解：首先设计能接受偶数个0和偶数个1组成的数字串的有限自动机如下： M1=（S，A，B，C，0，1， f ， S，S ） f（S，0）=B f（S，1）=A f（A，0）=C f（A，1）=S f（B，0）=S f（B，1）=C f（C，0）=A

29、f（C，1）=B 其状态图及状态转换矩阵分别如图3.9(a)(b)所示。,S,A,B,C,1,1,0,1,0,0,1,0,图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)= S(接受) f (S，11101)=f (A，1101)=f (S，101) =f (A，01)=f (C，1)= B(拒绝),编译原理,48,DFA的确定性表现在转换函数 :KK是一个单值函数，即：对任何状态kK以及输入符号a， (k,a)能唯一确定下一个状态

30、。 从状态转换图来看，若字母表含有n个输入字符，那么任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。,总 结：,编译原理,49,3.3.2 非确定的有限自动机,非确定的有限自动机与确定的有限自动机的区别主要是状态转换函数f为多值函数。 1、非确定的有限自动机定义 一个非确定的有限自动机NFA M是一个五元式 M=（K，f，S0，Z） 其中:K：有穷状态集; ：输入字母表 S0 ：开始状态S0K; Z：终止状态集ZK f ：状态转换函数，为K到K的子集的映射。形式为 f( S i, a j )=Sk1,Sk2,S km 非确定的有限自动机同样可以用状态图和状态转换矩阵来表示

31、，表示方法与确定的相同。,编译原理,50,2、非确定的有限自动机接受的语言 与确定的有限自动机一样，为了判别一个字符串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的当前状态集出发，扫描字符串x后，所到达的状态集等于从当前状态集的每一个状态出发，扫描字符串x后所到达的状态集之和。,即将f的定义域扩充到2K*,编译原理,51,对于某个字符串 x（x *）， 若有f (S0, x )=K，且

32、K Z ，则x为M所接受。 从状态图上看，如果一个字符串能被自动机接受，则存在一条从初始状态到某一终结状态的通路，且将这条通路上所有矢线标记的符号依次连接起来就组成了字符串x。 M所接受的语言为 L（M）=x | f(S0, x )Z ， x *,编译原理,52,例3.5 ，有NFA M=（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 画出其状态图及状态转换矩阵，确定该自动机接收的语言。,编译原理,53,例3.5 ，有NFA M=（0,1,2，a,b , f, 0,2 ） 其中：f（0，a）=2

33、, 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,n0,图3.10(a),图3.10(b),a (a b )n,b m (a b )n,返回,编译原理,54,*上的字符串t在M上运行 一个输入符号串t，（表示成Tt1的形式，其中T，t1 *）在NFA M上运行的定义为： （Q， Tt1）= （ （Q，T），t1） QK *上的字符串t被NFA M接受 若t

34、*， (S0,t)=P1,P2,P3,，其中S0S， PiZ， 则称t为NFA M所接受（识别）。,NFA识别符号串,编译原理,55,*上的符号串t被NFA M接受也可理解为：,对于中的串t，若存在一条从某初态到某一终态的路径，且这条路上所有弧的标记字依序连接成的串等于t，则称t可为NFA M所识别(接受)。 若M的某些结点既是初态又是终态，或者存在一条从某个初态到某个终态的路径,其上所有弧的标记均为，那么可被M所接受。,编译原理,56,3.3.3 NFA与DFA的等价性,所谓NFA的确定化,是指对任给的NFA,都能相应的构造一DFA,使它们有相同的接受集。 证明的思路:让所要构造的DFA去模

35、拟相应的NFA的工作过程,即用DFA的一个状态去记录NFA读入一个输入符号后可能到达的所有状态。,定理3.1对于字母表上的任一NFA M,必存在上与M等价的DFA M 。 证明:设M=(K, ,f, S0, Z)是上的一个NFA,今构造一个上的DFA M=(K,f,S0,Z),其方法如下:,编译原理,57,K=2K 。例如,对K的一个子集S1,S2,Si,我们用记号S1,S2,Si表示K中的一个状态,特别地,令S0=S0 映射f的定义为： 当且仅当 f(S1,S2,Si,a)=R1,R2,Rj 时 f(S1,S2,Si,a)=R1,R2,Rj 终态集Z定义为 Z=Sp,Sq,SrSp,Sq,S

36、rK且Sp,Sq,SrZ ,编译原理,58,解:构造等价的DFA如图3.11(b) M=(K, a, b, f, 0, Z) 其中K=0,1,0,1, 如图f(0,a)=0,1 f(0,b)=1 f(1,a)= f(1,b)=0,1 由于f(0,1,a)= f(0,a) f(1,a)= 0,1 f(0,1,b)= f(0,b) f(1,b)= 0,1 故有f(0,1,a)= f(0,1,b)= 0,1 Z=1,0,1,图3.11(a) NFA M,图3.11(b) DFA M,例3.6 考虑NFA M=(0,1,a,b,f, 0,1)状态转换矩阵如图3.11(a)所示。,编译原理,59,3.3

37、.4 具有动作的FA,一个具有动作的有限自动机NFA M也是一个五元式 M=（K， ，f ， S0，Z） 其中, K， ，S0，Z的含义同前,而f却是K()到2k的一个映射。 则对于f(q,a)则由状态p组成：当NFA处于状态q而扫视的输入字符为a(a或a =)时，它的下一个状态将是p。,编译原理,60,把识别各类单词的NFA用矢线连接起来,组成一个单一的NFA,然后把所得的NFA确定化,最后再据此设计词法分析程序。 例1：设某语言有如下几个单词：TEP，RING，WITCH，写出识别这些单词的NFA。 例2：写出识别下面三个关键字的状态转移图 STEP，STRING，SWITCH,编译原理,

38、61,3.3.5 具有动作的NFA的确定化,为了实现NFA到DFA 的转化，首先要介绍两个状态子集的计算方法，它们是从NFA到DFA 的转化过程中需要计算的状态子集。 1、状态集P的闭包 设P是一NFA M的状态集K的一个子集，则-closure (P) 称为状态集P的闭包，闭包也是状态集K的一个子集，其计算方法如下： 1）若q P，则q -closure (P)，即P的所有成员都是P的闭包的成员（状态q本身包含在这个集合之中） 2）若q P，那么从q出发经过任意条弧而能到达的任何状态都属于-closure (P)。,编译原理,62,例3.7，对图3.12所示的NFA M，求P=1、P=2、P

39、=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,6,编译原理,63,2、状态集P的a弧转换集 设P仍是一NFA M的状态集的子集，P= p1, p2,p n ,a，即a是字母表的一个输入符号，则P的a弧转换集为： Pa=-closure (J)，其中 J=f(p1,p2,p n, a)=f(p1,

40、a )f(p2,a)f (p n, a) 即J是从状态子集P中的每个状态出发，沿着标记为a的矢线而转移到达的状态所组成的集合。 从定义可知，状态集P的a弧转换集Pa也是状态子集，其元素为从P的每个状态出发，沿着标记为a的矢线所转移到达的后继状态的集合，再加上这些后继状态集合中的每个状态的闭包，即转移后再经矢线所能到达的状态的集合。,编译原理,64,例3.8：对图3.12所示的NFA M，若P=1，求Pa。 解： Pa =-closure(J) =-closure(f(1, a ) =-closure(2,4) =2,4,6,编译原理,65,P=1, P=1,2求Pa, Pa,编译原理,66,P

41、=1, P=1,2求Pa, Pa Pa =-closure(J) =-closure(f(1, a ) =-closure(4,5)=4,7,5,6,2 Pa=-closure (J)=-closure(f(1,2, a ) =-closure(3,5,4)=3,8,5,6,2,4,7,编译原理,67,3、根据NFA M构造DFA M(子集法) 基本思路: 首先将-closure(S0)作为M的初态q0,然后对于所有的输入符号a ,将q0的a弧转换集作为M的状态,如此等等,直到不再有新的状态出现为止。 下面我们通过一个例子来介绍根据NFA M构造DFA M的方法。,编译原理,68,假设有一个不

42、确定的有限自动机 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),图3.13 NFA M的状态图,编译原理,69,构造确定的有限自动机过程如下： 1）首先根据闭包的计算方法求NFA M的开始状态S0的闭包，从而确定DFA M的开始状态q0。 q0 =-closure(S0)= -closure(1)=1，4 2）根据弧转换集的计算方法求开始状态q0对每个输入符号的

43、弧转换集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)= q1,编译原理,70,f(q0,b) = q0b= -closure( f(1，4,b) ) = -closure()= f(q0,c) = q0c= -closure( f(1，4,c) ) = -closure()= 由于f(q0,b) = ，f(q0,c) =，说明没有新状态产生。至此，我

44、们得到有关开始状态q0的全部状态转换函数只有一个，即f(q0,a)= q1。,编译原理,71,3）按步骤2的方法，对每个新状态计算相关的状态转换函数。 计算状态q1的状态转换函数： f(q1, a ) = q1a= 2 ，将2作为新状态, 并令q2=2 f(q1, b ) = q1b= 4，将4作为新状态, 并令q3=4 f(q1, c) = q1c= 3,4，将3，4作为新状态, 并令q4=3,4 至此，得到有关开始状态q1的全部状态转换函数。,编译原理,72,接下来，计算状态q2、q3、q4的有关状态转换函数如下： f(q2, a ) = 2=q2 , f(q2, b ) = 4=q3 ,

45、 f(q2,c ) = f(q3,a ) = , f(q3,b ) = , f(q3,c ) = f(q4, a ) = ，f(q4, b ) =，f(q4, c ) = 3,4= q4 计算到此，不再有新状态出现。,编译原理,73,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 , q4,编译原理,74,最后,我们得到确定的有穷自动机如下： DFA M= (q0, q1 , q2, q3 ,

46、q4,a,b,c, f, q0 , q0, q3 , q4) 其中状态转换函数为： f(q0,a)= q1 f(q1,a)= q2，f(q1,b)= q3，f(q1,c)= q4 f(q2,a)= q2，f(q2,b)= q3 f(q4, c ) = q4 该转换后的自动机的状态图及状态转换矩阵如图3.14(a)、(b)所示。,编译原理,75,图3.14(b)转换后的DFA M的状态转换矩阵,得到的确定的自动机接收的语言为: L(M)=am b | m1 acn | n1 与原来不确定的有限自动机接收的语言L(M)一样。,编译原理,76,Ia,Ib,i ，1，2,1，2，3,1，2，4,1，2

47、，3,1，2，4,1，2，3，5，6，f,1，2，4,1，2，3,1，2，4，5，6，f,1，2，3，5，6，f,1，2，3，5，6，f,1，2，4，6，f,1，2，4，5，6，f,1，2，3，6，f,1，2，4，5，6，f,1，2，4，6，f,1，2，3，6，f,1，2，4，5，6，f,1，2，3，6，f,1，2，3，5，6，f,1，2，4，6，f,S,A,B,A,C,B,B,A,D,C,C,E,D,F,D,E,F,D,F,C,E,T,编译原理,77,假定所构造的子集族为C，即C= (T1, T2,. TI)，其中T1, T2,. TI为状态K的子集。 1 、-closure(K0)为C中唯

48、一成员，并且它是未被标记的。 2、 while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(f(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 CT, a := U ,构造NFA N的子集族(DFA M状态集)的算法,编译原理,78,把T的所有状态压入栈；-closure(T)的初值置为t； while 栈非空 do 把栈顶元素t 弹出； for 每个f(t,)=u的状态 do if u不在-closure(T)中 do 把u加入-closure(T)； 把u压入栈； ,-closure(T) 的计算,编译原理,7

49、9,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,识别(a|b)*ab的NFA,练 习：,编译原理,80,3.3.6 DFA状态数的最小化,对于一个NFA,当把它确定化后,得到的DFA所具有的状态数可能并不是最小的。在设计词法分析程序时，效率是很重要的一个因素。如果可能的话，我们应该构造尽可能小的DFA。 自动机理论中有一个很重要的结论： 定理3.2 对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下(即不顾状态的命名)是唯一的。 从任何FA中都可以

50、得到这个最少状态的DFA。,编译原理,81,最小状态DFA的含义: 没有多余状态(死状态)； 没有等价状态（不可区别）。 一个DFA可以通过消除多余状态和合并等价状态转换成最小的与之等价的DFA。 有穷自动机的多余状态指： 从自动机的开始状态出发，任何输入串都不能到达的状态。,编译原理,82,1、可区分状态与等价状态 设s和t是一DFA M的两个不同状态，我们说状态s，t为某一输入串w所区分,是指从s ，t中之一出发,当扫视完w之后到达M的终态,但从另一个状态出发,当扫视完同一个w后而进入非终态。如果s和t不可区分(即对任何输入串w,当且仅当f( s ,w) Z, f( t ,w) Z),则称

51、s和t等价。,编译原理,83,C和F同是终态, C和F读入a都到达C,读入b都到达E. C和F等价(不可区别)；E和D同是终态,读入a均到达F,读入b均到达D，因此E和D等价（不可区别）。,而A，B是可区别的。因为A和B可由输入b来区别，对输入b，A走到非接受状态B，而B走到接受状态D。,判定两个状态p和q不等价，只要找到一个w*， 使（p,w)F 且（q,w) F，或者相反。 W称为判别序列。,编译原理,84,2、DFA化简算法(分割法) 基本思路:将M的状态集K逐步进行划分,以期最后按上述 状态的等价关系将K划分为r( rK)个互不相交的 子集,使得属于同一子集中的任何两个状态都是等价的,

52、 而属于不同子集的任意两个状态都是可区分的. 设DFA M= （K， ，f ，q0，Z），化简算法如下： 1）将M的状态集K划分成终态集Z和非终态集KZ ，记为=Z, KZ ,编译原理,85,2）设当前的划分 中已含有m个子集，即 =I1,I2,I m ，其中，属于不同子集的状态是可区分的，而属于同一子集的诸状态则是待区分的。即需对每一子集Ii=Si1,Si2,Sin中的各个状态逐一检查，看能否对它们再进行区分。 设Sip和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

53、和I k，故S j u与S k v为某一w所区分，从而Sip和S i q必为aw所区分，故应将Sip和S i q分为两个子集。,编译原理,86,3）重复第2步，直到所有子集都不能细分为止。 4）将每个子集中的等价状态合并成一个等价代表状态。将状态函数(矩阵)中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个子集中的等价状态结点合并成一个结点。,编译原理,87,例3.9 化简图3.15所示的有限自动机。,解： 初始划分:0，1，2，3，4 对0，1，2划分: 因为0，2 a=f( 0,2, a )=1，1a=f(1,a) =3 所以:0，2，1，3，4 对0，2划分: 因为0 b=2，

54、 2 b=4 所以:0，2，1，3，4 对3，4划分: 因为3，4a=3，4 3，4b=3，4 至此，不再能继续划分。 最终:0，2，1，3，4,图3.15 等待化简的有限自动机,编译原理,88,现选择状态3作为3,4的代表,将状态4从状态图中删去,并将原来引向状态4的矢线都引至状态3 。 将原来的转换矩阵中的状态4改成状态3，去掉重复的，最终得到化简后的转换矩阵如下，对应的状态图如图3.16所示。,编译原理,89,0:S,A,B C,D,E,F,DFA的最小化例子,b,B,S,1,2,C,D,E,F,C,D,E,F,A,a,编译原理,90,例：,0,1,s0,s1,s2,s3,s4,s5,s

55、1,s3,s2,s2,s3,s2,多余状态：s4、s5 依次将多余状态及其射出弧取消。,等价状态: 1) s0、s1、s3与s2 2) （s0,0)= s1， （s0,1)=s3 （s1,0)=s2， （s3,0)=s2 s0s1、s3s2 3) s1、s3不能再分，所以s1、s3等价。合并等价状态。图改为,1,s5,s1,编译原理,91,3.4 正规表达式与正规集,词法分析程序自动生成系统的实现涉及正规表达式和有限自动机理论。 假设有字母表=0，1，那么，字母表上的每个元素都是正规表达式，这样的正规表达式表示的语言只有一个句子。 例如，0是一个正规表达式，表示的语言为0，该语言只有一个句子0

56、。 如果想表示更加复杂的语言，就必须使用运算符组成复杂的正规表达式，这一点很像用加减乘除运算符构造算术表达式。 在正规表达式中，可使用的运算符有连接、或和闭包。,编译原理,92,每一程序设计语言都有它自己的字符集。语言中的每一单词或是上的单个字符,或是上的字符”按一定方式”(即进行一定的连接,或及闭包运算)组成的字符串。 如果把每一类单词均视为一种语言,那么每一类单词都可以用一个正规式来描述,而每一类单词中的全体单词也就组成了相应的正规集。 正规式(正规表达式)是定义正规集的数学工具，是说明单词的模式(pattern)的一种重要表示法（记号）。正规式描述的集合称作正规集。,编译原理,93,设是

57、有穷字母表，在上的正规式及所表征的正规集可递归定义如下： 1.是一个正规式， 相应的正规集为空集 2.是一个正规式，相应的正规集为 3. 对于每一a， a是一个正规式，相应的正规集为a 4.若r ， s是正规式，相应的正规集分别记为Lr和Ls，则 1) (r) | (s)是正规式，相应的正规集为LrLs 2) (r) . (s)是正规式，相应的正规集为LrLs 3) (r)*是正规式，相应的正规集为Lr*,注意：不要混淆和，正则表达式描述的语言只含一个空字符串，而表示的语言不含有任何字符串。,3.4.1正规表达式与正规集的定义,编译原理,94,在正规表达式的运算符中，闭包优先级高于连接，而连接

58、高于或，( )调整优先权，使括号内的运算符优先权高于括号外的。 因此，(p) | (p) . (q)可写成p | pq , 但表达式(p|q).r中的括号则不能去掉。,编译原理,95,例3.10，设字母表=a,b，则a,b, 和都是上的正规式，所定义的正规集为a、b、 、 。,编译原理,96,课本例3.3中所给的各种单词,用正规式描述如下(P66): 关键字 BEGIN|END|IF|THEN|ELSE 标志符 字母(字母|数字)* 整常数 数字(数字)* 关系运算符 | | = 正规式和正规集之间并不存在一一对应的关系。 例如正规式(a|b)*及(a*b*)*都描述了a,b上的任何 符号串;正规式b (ab)*及(ba)*b都描述了以b开头且 其后跟零个或任意多个ab所组成的符号串等。,编译原理,97,两个正规式等价,当且仅当它们所描述的正规集相同。下面的公理是正规式间的一些基本等价关系。 设r, s, t均是正规式 A1. r|s=s|r (交换律) A6. r(s|t)=rs|rt（分配律） A2. r|r=r A7. (s|t)r=sr|tr A3. r|=r A8. r=r= A4. (r|s)|t=r|(s|t) （结合律） A9. r=r =r A5. (rs)t=