编译原理4.ppt

编译原理编译原理计算机学院计算机学院 李金厚李金厚第四章第四章 词法分析词法分析4.1 词法分析程序的设计词法分析程序的设计4.2 单词的描述工具单词的描述工具4.3 有穷自动机有穷自动机4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性4.5 正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具(选择选择)编译原理编译原理计算机学院计算机学院 李金厚李金厚什么是词法分析程序？什么是词法分析程序？实现词法分析的程序实现词法分析的程序逐个读入源程序字符并按照逐个读入源程序字符并按照构词规则构词规则切分成一切分成一系列单词系列单词单词是语言中具有独立意义的最小单位，包括单词是语言中具有独立意义的最小单位，包括保留字保留字、标识符标识符、运算符运算符、标点符号标点符号和和常量常量等等词法分析是编译过程中的一个阶段，在语法分词法分析是编译过程中的一个阶段，在语法分析前进行析前进行 也可以和语法分析结合在一起进行。一般说来，也可以和语法分析结合在一起进行。一般说来，语法分析程序调用词法分析程序来获得当前单语法分析程序调用词法分析程序来获得当前单词供语法分析使用词供语法分析使用编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析考虑几个问题考虑几个问题两者的关系如何两者的关系如何为什么要将词法分析与语法分析分开为什么要将词法分析与语法分析分开词法分析欲解决什么问题词法分析欲解决什么问题词法分析与语法分析程序的接口方式词法分析与语法分析程序的接口方式编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析简单地说，词法分析和语法分析存在时间顺简单地说，词法分析和语法分析存在时间顺序上的关联序上的关联词法分析程序语法分析程序get tokenToken源程序源程序编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析的分离词法分析与语法分析的分离将词法分析与语法分析分离至少具有下面若干将词法分析与语法分析分离至少具有下面若干的好处：的好处：1.使整个编译程序的结构更简洁、清晰和条理化。通常使整个编译程序的结构更简洁、清晰和条理化。通常语法分析更为复杂，将两者分开使程序更清晰易读语法分析更为复杂，将两者分开使程序更清晰易读2.编译程序的效率会改进。词法分析程序虽然相对简单，编译程序的效率会改进。词法分析程序虽然相对简单，但重复性较高，采用专门的读字符和分离单词的技术但重复性较高，采用专门的读字符和分离单词的技术既可大大地加快编译速度，也有利于每部分的自动化既可大大地加快编译速度，也有利于每部分的自动化3.增加编译程序的可移植性。将一些特殊符号的处理增加编译程序的可移植性。将一些特殊符号的处理(往往与机器环境有关往往与机器环境有关)集中放在词法分析程序中，不集中放在词法分析程序中，不影响编译程序其他成分的设计和可移植性影响编译程序其他成分的设计和可移植性编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析的接口词法分析与语法分析的接口词法分析程序的功能是读入源程序，输出单词词法分析程序的功能是读入源程序，输出单词符号符号作为一个程序设计语言的基本成分，单词符号作为一个程序设计语言的基本成分，单词符号一般可分成一下一般可分成一下5种：种：1.关键字，也称为基本字、保留字等，如关键字，也称为基本字、保留字等，如C语言中的语言中的do,while,if,then等等等等2.标识符，用来表示各种名字，如常量名、变量名和函标识符，用来表示各种名字，如常量名、变量名和函数名等数名等3.常数，包括各种类型的常数常数，包括各种类型的常数4.运算符运算符5.界符，如逗号、括号等界符，如逗号、括号等编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析接口词法分析与语法分析接口标识符通常放在一个符号表中加以管理标识符通常放在一个符号表中加以管理例，对程序段例，对程序段 if i=5 then x:=y;经过词法分析后可得到如下结果：经过词法分析后可得到如下结果：关键字关键字 if (3,if)标识符标识符 i (1,指向指向i的符号表入口的符号表入口)等号等号=(4,=)常数常数5 (2,5)关键字关键字then (3,then)标识符标识符x (1,指向指向x的符号表入口的符号表入口)赋值号赋值号:=(4,:=)标识符标识符y (1,指向指向y的符号表入口的符号表入口)分号分号;(5,;)在上面的表示中，以整数编码来表示单词的类别：标识符在上面的表示中，以整数编码来表示单词的类别：标识符编码为编码为1；常数为；常数为2；关键字为；关键字为3；运算符为；运算符为4；界符为；界符为5编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析单词如何描述？单词如何描述？某种意义上说，某种意义上说，单词识别单词识别是与是与单词描述单词描述相逆相逆的行为，前者依赖于后者的行为，前者依赖于后者英文单词是由字母组成的，即它定义在特定英文单词是由字母组成的，即它定义在特定的字母表之上。常用的字母表之上。常用 表示字母表表示字母表编译原理编译原理计算机学院计算机学院 李金厚李金厚单词的描述工具单词的描述工具正规文法正规文法正规式正规式正规文法和正规文法的等价性正规文法和正规文法的等价性编译原理编译原理计算机学院计算机学院 李金厚李金厚例例令令=a，b，那么那么 上的正规式和相应的正规集有很多上的正规式和相应的正规集有很多 a a a|b a,b ab ab (a|b)(a|b)aa,ab,ba,bb a ,a,aa,任意个任意个a的串的串 (a|b),a,b,aa,ab,bb 所有由所有由 a和和b 组成的串组成的串(a|b)(aa|bb)(a|b)*上所有含有两个相继的上所有含有两个相继的a或或两两 个相继的个相继的b组成的串组成的串编译原理编译原理计算机学院计算机学院 李金厚李金厚例例程序设计语言的单词都可以用正规式来定义程序设计语言的单词都可以用正规式来定义例例1，令，令=l,d，则则 上的正规式上的正规式 r=l(l|d)定义的正规定义的正规集为集为:l,ll,ld,ldd,，其中，其中l代表字母，代表字母，d代表数字，代表数字，正规式即是字母正规式即是字母(字母字母|数字数字)，它表示的正规集中的每，它表示的正规集中的每个元素的模式是个元素的模式是“字母打头的字母数字串字母打头的字母数字串”,就是就是Pascal和多数程序设计语言允许的的标识符的词法规则和多数程序设计语言允许的的标识符的词法规则例例2，=d,e,+,-，则，则 上的正规式上的正规式 d(dd|)(e(+|-|)dd|)表示的是无符号数的集合。其中表示的是无符号数的集合。其中d为为09的数字的数字编译原理编译原理计算机学院计算机学院 李金厚李金厚正规式正规式正规式正规式也称正则表达式或正规表达式也称正则表达式或正规表达式(regular expression)，是定义，是定义正规集正规集的数的数学工具。是说明单词的模式学工具。是说明单词的模式(pattern)的一的一种重要的表示法种重要的表示法(记号记号)，我们用以描述单，我们用以描述单词符号词符号编译原理编译原理计算机学院计算机学院 李金厚李金厚有穷自动机有穷自动机有穷自动机，也称有限自动机，作为一种识别装有穷自动机，也称有限自动机，作为一种识别装置，它能准确地识别正规集，即识别正规式所表置，它能准确地识别正规集，即识别正规式所表示的集合示的集合应用有穷自动机这个性质，为词法分析程序的自应用有穷自动机这个性质，为词法分析程序的自动构造寻找有效的方法和工具动构造寻找有效的方法和工具有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata)，简写成简写成DFA不确定的有穷自动机不确定的有穷自动机(Non-deterministic Finite Automata)，简写成，简写成NFA编译原理编译原理计算机学院计算机学院 李金厚李金厚有穷自动机有穷自动机这里要讨论下面几个问题这里要讨论下面几个问题确定的有穷自动机确定的有穷自动机DFA不确定的有穷自动机不确定的有穷自动机NFANFA的确定化的确定化DFA的最小化的最小化编译原理编译原理计算机学院计算机学院 李金厚李金厚确定的有穷自动机确定的有穷自动机DFA定义：一个确定的有穷自动机定义：一个确定的有穷自动机(DFA)，称作，称作M，是一个五元组：，是一个五元组：M=(K,f,S,Z)，其中，其中 1.K是一个有穷集，它的每个元素称为一个状态是一个有穷集，它的每个元素称为一个状态2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也是一个有穷字母表，它的每个元素称为一个输入符号，所以也称称 为输入符号表为输入符号表3.f是是转换函数转换函数，是在，是在K K上的映射，即，如上的映射，即，如 f(ki,a)=kj，(ki K，kj K）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，将时，将转换为下一个状态转换为下一个状态kj，我们把我们把kj称作称作ki的一个后继状态的一个后继状态4.S K是唯一的一个初态是唯一的一个初态5.Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态编译原理编译原理计算机学院计算机学院 李金厚李金厚一个一个DFA的例子的例子这里有这里有DFA，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(Q,a)=Qf(U,b)=Vf(Q,b)=Q编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的状态图表示的状态图表示DFA可以用状态图表示如下可以用状态图表示如下bSUVQaaaba,bb编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的状态图表示的状态图表示每个节点对应一个状态。对于上图，有每个节点对应一个状态。对于上图，有S,U,V,Q四个状态四个状态箭头线指示了状态变化的方向，线上的符号箭头线指示了状态变化的方向，线上的符号是有关的输入符号是有关的输入符号终止状态用双线园表示终止状态用双线园表示编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的矩阵表示的矩阵表示上图的有限自动机也可以以下图说明，其中上图的有限自动机也可以以下图说明，其中Q是终止状态是终止状态字符字符状态状态0001编译原理编译原理计算机学院计算机学院 李金厚李金厚*上的符号串t被DFA M接受*的解释？的解释？一个字符串被一个自动机一个字符串被一个自动机接受接受或者说或者说识别识别的的含义是什么？含义是什么？基本含义：自动机依次输入该字符串的字符，基本含义：自动机依次输入该字符串的字符，最终到达最终到达终止终止或或停机停机状态状态编译原理编译原理计算机学院计算机学院 李金厚李金厚符号串被自动机接受符号串被自动机接受例，对如图所示的自动机，如果有符号串例，对如图所示的自动机，如果有符号串baab，由于起始，由于起始状态是状态是S，那么有，那么有S V U Q Q 文字描述：文字描述：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，得证，得证bSUVQabb,aaabbaba编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的实现的实现虽然概念上大家对虽然概念上大家对DFA有些陌生和不易接受，但其有些陌生和不易接受，但其识别行识别行为为的实现并不复杂，可以方便地以计算机程序模拟的实现并不复杂，可以方便地以计算机程序模拟DFA M=(K,f,S,Z)行为的模拟程序行为的模拟程序 -K=S;-c=getchar();-while(c!=null)-K=f(K,C);-c=getchar();-(做判断做判断)-if K is in Z then return(yes)-else return(no)编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA所识别的语言所识别的语言定义：定义：这里将确定的有穷自动机这里将确定的有穷自动机M所能所能接受接受的符号的符号串的全体记为串的全体记为L(M)定理：定理：上一个符上一个符号号串集串集V 是正规的，是正规的，当且仅当当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M，使得使得V=L(M)编译原理编译原理计算机学院计算机学院 李金厚李金厚不确定的有穷自动机不确定的有穷自动机NFA定义：一个不确定的有穷自动机，记作定义：一个不确定的有穷自动机，记作M，是一个五元组是一个五元组M=K,f,S,Z，其中其中K为状态的为状态的有穷非空集，有穷非空集，为有穷输入字母表，为有穷输入字母表，f为为K*到到K的子集的子集(2K)的一种映射的一种映射，S K是初始状态集，是初始状态集，Z K为终止状态集为终止状态集编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA的实例的实例NFA M=(S,P,Z,0,1,f,S,P,Z)，其中，其中，f(S,0)=Pf(S,1)=S,Z f(P,1)=Zf(Z,0)=Pf(Z,1)=P特点：对一个符号输入，可能进入的状态有特点：对一个符号输入，可能进入的状态有多个多个编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA的实例的实例图示图示SPZ00,1111编译原理编译原理计算机学院计算机学院 李金厚李金厚矩阵表示矩阵表示简化为用矩阵，上图可以表示如下用矩阵，上图可以表示如下关于空的解释：非法输入关于空的解释：非法输入编译原理编译原理计算机学院计算机学院 李金厚李金厚具有具有 转移的转移的NFA 转移是指空转移：即便输入为空，也可以进行的转移是指空转移：即便输入为空，也可以进行的转移转移输入分析：输入分析：在状态在状态1，输入，输入a可以到达可以到达1，还可以到达，还可以到达2(a)，甚至，甚至3；输入；输入b可以到达状态可以到达状态2(b)，还可以到，还可以到3(b)；输入；输入c可以到达状可以到达状态态3在状态在状态2，输入，输入b可以到达可以到达2，还可以到达，还可以到达3；输入；输入c可以到达可以到达3；但但是注意，输入是注意，输入a不可以不可以在状态在状态3，输入，输入c可以到达可以到达c；但是注意，输入但是注意，输入b，a都不可以都不可以123abc编译原理编译原理计算机学院计算机学院 李金厚李金厚与之等价的与之等价的NFA根据上面对它运行情况进行的分析，不难得根据上面对它运行情况进行的分析，不难得到如下一个等价的到如下一个等价的NFA2acbb31acacbb编译原理编译原理计算机学院计算机学院 李金厚李金厚等价性等价性具有具有 转移的转移的NFA较为灵活，那么是不是存较为灵活，那么是不是存在与之等价的不具有在与之等价的不具有 转移的转移的NFA存在呢？存在呢？下面的定理对此给出了肯定的回答下面的定理对此给出了肯定的回答定理：定理：对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFA N，一定存在一个一定存在一个不具有不具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFA ，使得使得L(M)=L(N)编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA接受的字符串接受的字符串对对NFA，可以有类似前面的接受的符号串的概念，可以有类似前面的接受的符号串的概念，下面以定义的形式给出下面以定义的形式给出定义定义1：运行：运行 设有设有NFA M=K,f,S,Z，一个符号串一个符号串t*(我们将它表示成我们将它表示成Tt1的形式，其中的形式，其中T，t1*)在一个在一个NFA上运行是指有下面的式子：上运行是指有下面的式子：f(Q,Tt1)=f(f(Q,T),t1)，其中，其中Q K定义定义2：接受：接受 设有设有NFA M=K,f,S,Z，现有，现有*上的符号串上的符号串t，如果对之，如果对之f(S0,t)=P，其中其中S0 S，P Z，则称则称t为为NFA M所接受或识别所接受或识别编译原理编译原理计算机学院计算机学院 李金厚李金厚关于接受概念的更多解释关于接受概念的更多解释对于对于*中的任何一个串中的任何一个串t，若存在一条从某若存在一条从某一初态节点到某一终态节点的道路，且这一初态节点到某一终态节点的道路，且这条道路上所有弧的标记字依序连接成的串条道路上所有弧的标记字依序连接成的串(不理采那些标记为不理采那些标记为的弧的弧)等于等于t，则称则称t可可为为NFA M所所识别识别(读出读出或或接受接受)若若M的某些节点既是初态节点又是终态节点，的某些节点既是初态节点又是终态节点，或者存在一条从某个初态节点到某个终态或者存在一条从某个初态节点到某个终态节点的道路节点的道路,其上所有弧的标记均为其上所有弧的标记均为，那么，那么空字空字可为可为M所接受所接受编译原理编译原理计算机学院计算机学院 李金厚李金厚更多的例子更多的例子显然，下面的一些串可为显然，下面的一些串可为 右图的自动机接受：右图的自动机接受：000 111 1010001 110000001而下面的则不能为此自动机而下面的则不能为此自动机 所接受：所接受：00 01100编译原理编译原理计算机学院计算机学院 李金厚李金厚不确定自动机和正规集不确定自动机和正规集不确定自动机和正规集之间同样存在关系不确定自动机和正规集之间同样存在关系下图自动机所表示的符号串，可以用式子下图自动机所表示的符号串，可以用式子(0|1)*(000|111)(0|1)*表示表示编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA和正规集和正规集定义：定义：这里将一个这里将一个NFA M所能接受的符所能接受的符号号串的全体串的全体记为记为L(M)定理：定理：上一个符上一个符号号串集串集V 是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的不确定的有穷自动机上的不确定的有穷自动机M，使得使得V=L(M)编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA和和NFADFA是是NFA的特例的特例对每个对每个NFA N一定存在一个一定存在一个DFA ，使得使得L(M)=L(N)对每个对每个NFA N存在着与之等价的存在着与之等价的DFA M有有一种算法，将一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA。这种算法称为这种算法称为子集法子集法与某一与某一NFA等价的等价的DFA不唯一。一般来说人们需不唯一。一般来说人们需要将要将NFA转换为相应的转换为相应的DFA来处理来处理编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA的确定化算法的确定化算法设有设有NFA N=(K,f,K0,Kt)按如下办法按如下办法构造一个构造一个DFA M=(S,d,S0,St)，使得使得L(M)=L(N)：1.M的状态集的状态集S由由K的一些子集组成。用的一些子集组成。用S1 S2.Sj表示表示S的元素，其中的元素，其中S1,S2,.Sj是是K的状态。并且约定，状态的状态。并且约定，状态S1,S2,.Sj是按是按某种规则排列的，即对于子集某种规则排列的，即对于子集S1,S2=S2,S1,来说，来说，S的状态就是的状态就是S1 S2编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA确定化确定化2.M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是 3.转换函数是这样定义的：转换函数是这样定义的：d(S1 S2,.Sj,a)=R1R2.Rt，其中其中，R1,R2,.,Rt=-closure(move(S1,2,.Sj,a)4.S0=-closure(K0)为为M的开始状态的开始状态5.St=Si Sk.Se，其中，其中Si Sk.Se S且且Si,Sk,.Se Kt 编译原理编译原理计算机学院计算机学院 李金厚李金厚对状态集合对状态集合I的几个运算的几个运算定义定义1：状态集合状态集合I的的-闭包闭包，表示为，表示为-closure(I)，定义为一定义为一状态集状态集，是状态集，是状态集I中的任何状态中的任何状态S经任意条经任意条 弧而能到达弧而能到达的状态的集合的状态的集合 当然，状态集合当然，状态集合I自身的任何状态自身的任何状态S都属于该都属于该-闭包闭包定义定义2：状态集合状态集合I的的a弧转换弧转换，表示为，表示为move(I,a)定义为状态定义为状态集合集合J，其中其中J是所有那些可从是所有那些可从I中的某一状态经过一条中的某一状态经过一条a弧弧而到达的状态的全体而到达的状态的全体编译原理编译原理计算机学院计算机学院 李金厚李金厚几个实例几个实例对于下图来说，对于下图来说，若若I=1,则则-closure(I)=1,2若若I=5,则则-closure(I)=5,6,2move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,812534687aaa编译原理编译原理计算机学院计算机学院 李金厚李金厚状态状态K的子集构造方法的子集构造方法先假定所构造的先假定所构造的子集族子集族为为C，即即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集的子集1.开始，令开始，令-closure(K0)为为C中唯一成员，并且它是中唯一成员，并且它是未被标记未被标记的的2.while（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中 编译原理编译原理计算机学院计算机学院 李金厚李金厚例：例：NFA确定化确定化对下图对下图NFA确定化确定化4f35621iaaaabbbb编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA确定化确定化转换图表转换图表表中哪些状态是结束状态？表中哪些状态是结束状态？编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA确定化确定化根据前表，可以构造与之等价的根据前表，可以构造与之等价的DFA如下：如下：CDBAEFSbaaaaabbbbbaba编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的化简的化简说一个说一个DFA是化简了的，主要是说是化简了的，主要是说 第一，第一，它没有它没有多余状态多余状态 第二，它的状态中没有两个是互相等价的第二，它的状态中没有两个是互相等价的一个有穷自动机可以通过消除多余状态和合并一个有穷自动机可以通过消除多余状态和合并等等价状态价状态而转换成一个而转换成一个最小最小的与之等价的的与之等价的有穷自动有穷自动机机多余状态是指这样的状态：从自动机的开始状态多余状态是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态从这个状态没有通路到达终态编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化最小化最小状态最小状态DFA：没有多余状态没有多余状态没有两个状态是互相等价没有两个状态是互相等价(不可区别不可区别)如果两个状态如果两个状态s和和t可区别，那么它们可区别，那么它们不不同时同时满足满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态到达的状态等价等价 编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化最小化对于课件对于课件P44的的DFA，C和和D同是终态同是终态,读入读入a到达到达C和和F,C和和F同是终态同是终态,C和和F读入读入a都都到达到达C,读入读入b都到达都到达E。所以，。所以，C和和D等价等价对于对于DFA，它是否一定能够最小化？最小化，它是否一定能够最小化？最小化后的后的DFA的性质如何？的性质如何？如何如何系统系统、完整完整地实现最小化地实现最小化编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化最小化定理定理1 对于一个对于一个DFA M=（K,f,K0,Kt)，一定存一定存在在一个最小状态一个最小状态DFA M=(K,f,K0,Kt)，使，使L(M)=L(M)定理定理2 接受一个正则语言的最小状态有穷自动机不接受一个正则语言的最小状态有穷自动机不计同构是计同构是唯一唯一的的编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化算法：分割法最小化算法：分割法先先把一个把一个DFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等的，而同一子集中的任何两个状态都是等价的价的编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化算法最小化算法这里从这里从DFA M=(K,f,K0,Kt)得到最小得到最小状态状态DFA M：1.构造构造状态的状态的一组初始划分一组初始划分：终态终态Kt 和非终和非终态态K-Kt两组两组(group)2.对对施施用过程用过程PP 构造新划分构造新划分new 3.如如new =，则令，则令 final=并进入步骤并进入步骤4，否否则则:=new并重复并重复2编译原理编译原理计算机学院计算机学院 李金厚李金厚过程PP:Construction of new对对的每组的每组G，-do -begin -如果如果G的状态的状态s和和t对某些输入会进入不同的对某些输入会进入不同的，那么将那么将s和和t放入不同的子集从而得到放入不同的子集从而得到new -将将中的中的G用前面形成的子集替换用前面形成的子集替换 -end编译原理编译原理计算机学院计算机学院 李金厚李金厚4.为为final中的每一组选一代表，这些代表构成中的每一组选一代表，这些代表构成M 的状态。若的状态。若K是一代表且是一代表且f(K,a)=t,令令r是是t组的组的代表，则代表，则M 中有一转换中有一转换f(k,a)=r编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化：实例最小化：实例1，P61编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA最小化：实例最小化：实例2初始：初始：0:S,A,B C,D,E,F S,A,B C,D,E,F：无法再分割：无法再分割 aAS,B 1：S,B 2：bSB编译原理编译原理计算机学院计算机学院 李金厚李金厚根据前面的分析，有：根据前面的分析，有：DBASaaabbba,bCDBAEFSbaaaaaabbbbbb编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析程序的实现方法词法分析程序的实现方法有限状态自动机可以用于词法分析，这主要有限状态自动机可以用于词法分析，这主要取决于两者的等价性取决于两者的等价性定理定理1：对于对于 上的一个上的一个NFA M，可以构造一个，可以构造一个上上的正规式的正规式R,使得使得L(R)=L(M)定理定理2：对于对于 上的一个正规式上的一个正规式R，可以构造一个，可以构造一个 上上的的NFA M，使使的的L(M)=L(R)编译原理编译原理计算机学院计算机学院 李金厚李金厚单词识别单词识别主要使用是上面的定理主要使用是上面的定理2采用采用“语法制导语法制导”的方法：的方法：即根据正规式的即根据正规式的语法结构，语法结构，逐步逐步地构造出相应的地构造出相应的NFA这里从具体的这里从具体的“子结构子结构”出发，给出有关的出发，给出有关的构造方法构造方法编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-1a对于正规式对于正规式R=，构造的，构造的NFAFS编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-1b对于正规式对于正规式R=,构造的构造的NFAF编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-1c对于正规式对于正规式R=a ,构造的构造的NFAFSa编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-2a对于正规式对于正规式r,r=R1|R2构造的构造的NFA编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-2b对于正规式对于正规式r,r=R1 R2构造的构造的NFA编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA构造构造-2c对于正规式对于正规式r,r=R1*构造的构造的NFA编译原理编译原理计算机学院计算机学院 李金厚李金厚从正规表达式构造等价的从正规表达式构造等价的-NFA正规表达式正规表达式 1*0(0+1)*1*0+1 编译原理编译原理计算机学院计算机学院 李金厚李金厚-NFA构造构造续前续前(0+1)*编译原理编译原理计算机学院计算机学院 李金厚李金厚-NFA构造构造于是于是正规表达式正规表达式 1*0(0+1)*对应的对应的NFA如下如下图所示图所示1*0(0+1)*编译原理编译原理计算机学院计算机学院 李金厚李金厚从正规式构造从正规式构造NFA：不唯一：不唯一对正规式的分解可以有不同的方法，直接所对正规式的分解可以有不同的方法，直接所得到的得到的NFA会因此不同会因此不同对正规式对正规式R=(a|ab)*bb*，下图的分解构造结，下图的分解构造结果，与前面的方法就会有所不同果，与前面的方法就会有所不同编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析程序构造词法分析程序构造不难看出，词法分析程序设计按下面的思路不难看出，词法分析程序设计按下面的思路逐步进行实现：逐步进行实现：正规式正规式 -NFA DFA 程序实现程序实现编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析程序的更多应用词法分析程序的更多应用词法词法分析程序的设计技术可应用于如查询语分析程序的设计技术可应用于如查询语言以及信息检索系统等，这种应用领域的言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配程序设计特点是，通过字符串模式的匹配来引发动作来引发动作词法分析程序的自动构造工具也广泛应用于词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等和文本编辑的自动生成等编译原理编译原理计算机学院计算机学院 李金厚李金厚习题习题