编译原理第4章

1、n词法分析是翻译的第一阶段，是语法分析词法分析是翻译的第一阶段，是语法分析的必要准备。词法分析程序也称为扫描程的必要准备。词法分析程序也称为扫描程序或扫描器（序或扫描器（scannerscanner）。）。n词法分析是编译过程中的一个阶段，可以词法分析是编译过程中的一个阶段，可以在语法分析前进行在语法分析前进行 。也可以和语法分析结。也可以和语法分析结合在一起作为一遍，由语法分析程序调用合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析词法分析程序来获得当前单词供语法分析使用。使用。实现方式实现方式 作为单独的一遍作为单独的一遍 字符序列字符序列 单词序列单词序列扫描器扫

2、描器语法分析器语法分析器 . . .作为子程序作为子程序源程序词法分析程序语法分析程序Tokenget tokenn词法分析程序的主要任务：词法分析程序的主要任务：- 读源程序，产生单词符号词法分析程序的其他任务：词法分析程序的其他任务：- 滤掉空格，跳过注释、换行符- 追踪换行标志，复制出错源程序，- 宏展开， 单词类别及其输出形式单词类别及其输出形式 单词可作各种分类，典型地分为类：单词可作各种分类，典型地分为类：保留字保留字 AND,BEGIN,FOR,TYPE,VARAND,BEGIN,FOR,TYPE,VAR等等标识符标识符 用户定义的常量、类型、变量、用户定义的常量、类型、变量、过

3、程名过程名常量常量12, 1997, 4.14, 12, 1997, 4.14, A, A, 等等运算符，运算符， ，,!=,#,!=,#等等界限符；，（）等界限符；，（）等n词法分析程序所输出的单词符号常常采用词法分析程序所输出的单词符号常常采用以下二元式表示：以下二元式表示： ( (单词种别，单词自身的值单词种别，单词自身的值) )。n单词的种别是语法分析需要的信息，而单单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1；中的单词 25和1的种别都是常数，常数的值常数的值

4、2525和和1 1对于代码生成来说，是必不可少的。对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下表中，那么可以将单词的二元式表示设计成如下形式形式( (标识符，指向该标识符所在符号表中位置的指针标识符，指向该标识符所在符号表中位置的指针) )如上述语句

5、中的单词i和yes的表示为：(标识符，指向i的表项的指针)(标识符，指向yes的表项的指针)词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别单词类别 单词的属性值单词的属性值单词类别可以用整数编码表示单词类别可以用整数编码表示: :一类一种或一字一种一类一种或一字一种单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码编码1 12 23 34 45 5单词类别单词类别单词的属性值单词的属性值1int2指向指向x的符号表入口指针的符号表入口指针4=3105,2指向指向y的符号表入口指针的符号表入口指针4=3205,2指向指向sum的符号表入口指针的符号表

6、入口指针5; int x=10,y=20,sum;词法分析的结果词法分析的结果 n程序段程序段 if i=5 then x=yif i=5 then x=y；在经词法分析器扫在经词法分析器扫描后输出的单词符号和它们的表示如下：描后输出的单词符号和它们的表示如下：- - 保留字保留字if(3if(3，if)if)- - 标识符标识符i(1i(1，指向指向i i的符号表入口的符号表入口) )- - 等号等号=(4=(4，=)=)- - 常数常数5(25(2，5)5)- - 保留字保留字then(3then(3，then)then)- - 标识符标识符x(1x(1，指向指向x x的符号表入口的符号表

7、入口) )- - 赋值号赋值号=(4=(4，=) =) - - 标识符标识符 y(1y(1，指向指向y y的符号表入口的符号表入口) )- - 分号；分号；(5(5， ；) ) 词法分析在实际操作中：n 对于每种语言，保留字、运算符和界限符对于每种语言，保留字、运算符和界限符是固定的，可以是固定的，可以“一字一类一字一类”或或“一符一一符一类类”，预先造好标准单词表。，预先造好标准单词表。单词单词内部编码内部编码单词单词内部编码内部编码IF324THEN425ELSE5*26FOR1934例如：例如：n 常数虽然也是固定的，但个数太多，而每常数虽然也是固定的，但个数太多，而每个程序只用很少一部

8、分，不宜预先造表。个程序只用很少一部分，不宜预先造表。编译只对源程序中出现的各类常量造表，编译只对源程序中出现的各类常量造表，如整数表、实数表、字符串表等。如整数表、实数表、字符串表等。 例如，整数表例如，整数表IntTabIntTab存放源程序中的整常存放源程序中的整常数数, ,扫描器拼出整数时，查扫描器拼出整数时，查IntTabIntTab表，若无表，若无此数，则填入表中；若已有此数，则不在此数，则填入表中；若已有此数，则不在填入，而把该数在表中的地址填入，而把该数在表中的地址intpintp作为其作为其机内码的一部分，由它联系机内码和数值。机内码的一部分，由它联系机内码和数值。 n标识符

9、的意义是由用户定义的，与常量类标识符的意义是由用户定义的，与常量类似，编译器也构造一个标识符表似，编译器也构造一个标识符表IdTabIdTab。每每识别出一个标识符，则查识别出一个标识符，则查IdTabIdTab表，若无则表，若无则填入，已有则不填，用其在表中的地址填入，已有则不填，用其在表中的地址idpidp作为联系机内码和自身值的桥梁。作为联系机内码和自身值的桥梁。 词法分析工作从语法分析工作独立出来的原因：词法分析工作从语法分析工作独立出来的原因：(P48)简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 PL/0词法分析的设计与实现：PL/0PL/0

10、编译程序的词法分析编译程序的词法分析 nPL/0PL/0的词法分析程序的词法分析程序GETSYM(P15GETSYM(P15图图2.5)2.5)是一个独立是一个独立的过程，其功能是为语法分析提供单词用的，是语的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。为此割成一个个单词符号。为此PL/0PL/0编译程序设置了三编译程序设置了三个全程量的公用单元如下个全程量的公用单元如下：SYMSYM：存放每个单词的类别，用内部编码形式表示存放每个单词的类别，用内部编码形式表示 IDID： 存放用户所定义

11、的标识符的值。存放用户所定义的标识符的值。NUMNUM：存放用户定义的数。存放用户定义的数。n单词的种类有五种单词的种类有五种。基本字：基本字：也可称为保留字或关键字，如BEGIN，END，IF，THEN等。运算符：运算符：如：+、-、*、=、#、=、=等。标识符：标识符：用户定义的变量名、常数名、过程名。常数：常数：如：10，25，100等整数。界符：界符：如：，、.、；、(、)等。图图 2.5 词法分析过程词法分析过程GETSYM nPL/0编译程序文本中主程序开始对关键字表置初编译程序文本中主程序开始对关键字表置初值如下（值如下（P304 P304 ） ：关键字表为关键字表为：word1

12、:=begin ；word2:=call ；.word13:=write ；查到时找到关键字相应的内部表示为：查到时找到关键字相应的内部表示为：Wsym1:=beginsym; wsym2:=callsym；wsym13:=writesym；PL/0PL/0编译程序文本中开始对类型的定义中给出单词定义编译程序文本中开始对类型的定义中给出单词定义（见附录）：（见附录）：Type symbol=(nul,ident,number,plus,varsym, procsym)；定义单词是纯量/枚举类型，又定义了3个全程量为： sym: symbol;id: alfa;num: integer; alf

13、a=packed array1.a1 of char;n因此词法分析程序因此词法分析程序GETSYMGETSYM将完成下列任务：将完成下列任务：(1) (1) 滤空格滤空格：空格在词法分析时是一种不可：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以缺少的界符，而在语法分析时则是无用的，所以必须滤掉。必须滤掉。(2) (2) 识别保留字识别保留字：设有一张保留字表。对每：设有一张保留字表。对每个字母打头后接字母或数字的字符串要查此表。个字母打头后接字母或数字的字符串要查此表。若查着则为保留字，将对应的类别放在若查着则为保留字，将对应的类别放在SYMSYM中。中。如如IFIF

14、对应值对应值IFSYMIFSYM，THENTHEN对应值为对应值为THENSYMTHENSYM。若查若查不着，则认为是用户定义的标识符。不着，则认为是用户定义的标识符。(3) (3) 识别标识符识别标识符：对用户定义的标识符将：对用户定义的标识符将IDENTIDENT放在放在SYMSYM中，标识符本身的值放在中，标识符本身的值放在IDID中。中。(4) (4) 拼数拼数：当所取单词是数字时，将数的类别：当所取单词是数字时，将数的类别NUMBERNUMBER放在放在SYMSYM中，数值本身的值存放在中，数值本身的值存放在NUMNUM中。中。注意：注意：SYMSYM是纯量是纯量/ /枚举类型枚举类

15、型 sym: symbol; sym: symbol;Type symbol=(nul,ident,number,plus,Type symbol=(nul,ident,number,plus, varsym,procsym varsym,procsym)；(5) (5) 拼复合词拼复合词：对两个字符组成的算符：对两个字符组成的算符 如：如：= =、=、= = 等单词，识别等单词，识别 后将类别送后将类别送SYMSYM中。中。(6) (6) 输出源程序输出源程序：为边读入字符边输出：为边读入字符边输出( (可可输出在文件中输出在文件中) )。PL/0PL/0的词法分析程序（见附录）的词法分析程

16、序（见附录）单词的描述工具n正规文法 多数程序设计语言的单词语法都能用正规文法（3型文法）来描述例如：程序设计语言中的单词可用下列规则描述：例如：程序设计语言中的单词可用下列规则描述：程序设计语言中的几类单词可用下述规则描述：程序设计语言中的几类单词可用下述规则描述：标识符 l | l字母数字字母数字 l|d|l字母数字|d字母数无符号整数 d|d无符号整数运算符+ | - | * | / | =| 界符 ，|；| ( | ) |其中l表示az中的任何一英文字母， d表示09中的任一数字。n正规式正规式正规式也称正则表达式,正规表达式也是用以描述单词符号的方便工具。字母表字母表 , , 定义在

17、定义在 上的正规式和正规集递归定义如下上的正规式和正规集递归定义如下: :1.1. 和和 都是都是 上的正规式上的正规式, , 它们所表示的正规集分别为它们所表示的正规集分别为: 和和 ; ;2. 2. 任何任何a a , a , a是是 上的正规式上的正规式, ,它所表示的正规集为它所表示的正规集为:a; a; 3. 3. 假定假定e1e1和和e2e2是是 上的正规式上的正规式, , 它们所表示的正规集分别记为它们所表示的正规集分别记为L(e1)L(e1) 和和L(e2), L(e2), 那么那么e1|e2, e1e2e1|e2, e1e2和和e1e1* *也都是也都是 上的正规式上的正规式

18、, , 它们所表示的它们所表示的 正规集分别为正规集分别为L(e1) L(e1) L(e2)L(e2)、 L(e1) L(e2) L(e1) L(e2)和和( (L(e1)L(e1)* *4. 4. 任何任何 上的正规式和正规集均由上的正规式和正规集均由1 1、2 2和和3 3产生。产生。正规式与正规集正规式与正规集正规式中的运算符：正规式中的运算符： | -或（选择）或（选择） -连接连接 * 或或 -重复重复 （）（） -括号括号运算符的优先级：运算符的优先级： 先先*, 后后 , 最后最后 | 在正规式中可以省略在正规式中可以省略.运算符的结合方向：运算符的结合方向： 从左到右结合。从左

19、到右结合。正规式相等正规式相等 这两个正规式表示的语言相等这两个正规式表示的语言相等例子正规式正规式正规集正规集ba*所有以所有以b为首后跟任意多个为首后跟任意多个a的符号串的符号串a(a|b)*所有以所有以a为首的符号串为首的符号串(a|b)*abb所有以所有以abb为尾的为尾的a，b符号串符号串(a|b)*(aa|bb) (a|b)*所有含有两个相继的所有含有两个相继的a或相继的或相继的b的符号串的符号串(aa|ab|ba|bb) *空串和任何长度为偶数的符号串空串和任何长度为偶数的符号串(a|b)(a|b)(a|b) *任何长度大于等于任何长度大于等于2的符号串的符号串 正规式 正规集(

20、ab) ,a,b,aa,ab 所有 由a和b组成的串(ab)(aabb)(ab) 上所有含有两个相继 的a或两个相继的b组 成的串n例：设=a，b，0，1 正规式 正规集 （a|b)(a|b|0|1) 上的“标识符的全体 （0|1)(0|1) 上的“数”的全体 例：令例：令 =l l，dd，则则 上的正规式上的正规式 r=l(l r=l(l d) d) 定义的正定义的正规集为规集为: : l,ll,ld,ldd, l,ll,ld,ldd, 其中其中l l代表字母代表字母, ,d d代表数字代表数字, ,正规式即是正规式即是 字母字母( (字母字母| |数字数字) ) 。它表示的正规集中的每个元

21、素的模式是它表示的正规集中的每个元素的模式是“字母打头的字母字母打头的字母数字串数字串”,”,就是就是PascalPascal和和 多数程序设计语言允许的的标识多数程序设计语言允许的的标识符的词法规则符的词法规则. .程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .若两个正规式若两个正规式e1和和e2所表示的正规集相同所表示的正规集相同,则说则说e1和和e2等价等价,写作写作e1=e2。例如： e1= (ab)， e2 = ba又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab)设设r，s，t均是正规式，则有以下性质：均是正

22、规式，则有以下性质：（1）交换律：）交换律： r|s= s|r（2）结合律：结合律： r|(s|t)=(r|s)|t (rs)t=r(st) （3）分配律：分配律： (r|s)t=rt|st（4）同一律：同一律： r= r= r5、 r=r, r=r是“连接”的恒等元素零一律6、 rr=r r=rrr “或”的抽取律 正规文法与正规式n一个正规语言可以由正规文法定义，也可以由正规式定义。 对任意一个正规文法，存在一个定义同对任意一个正规文法，存在一个定义同一个正规语言的正规式；一个正规语言的正规式；反之，对每个正反之，对每个正规式，存在一个生成同一语言的正规文法。规式，存在一个生成同一语言的正

23、规文法。有些正规语言很容易用文法定义，有些语有些正规语言很容易用文法定义，有些语言更容易用正规式定义，现在介绍两者间言更容易用正规式定义，现在介绍两者间的转换，从结构上建立它们的等价性。的转换，从结构上建立它们的等价性。将将上的一个正规式转换成正规文上的一个正规式转换成正规文法法对已形成的形如对已形成的形如Ax*y的正规产生式，重写为：的正规产生式，重写为：AxBAyBxBBy 其中其中B为一新非终结符为一新非终结符。对形如对形如Ax|y的正规产生式，重写为：的正规产生式，重写为：Ax，Ay不断利用上述规则做变换，直到每个产生式不断利用上述规则做变换，直到每个产生式都符合三型文法的要求都符合三

24、型文法的要求。n例将R=a(a|d)*转换成相应的正规文法，令S是文法的开始符号，首先形成SaA和A(a|d)*， 再重写第二条产生式形成A(a|d)A|，进而变换为SaA A aA A dA A 2、将正规文法转换成正规式。n基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。其转换规则:.文法产生式正规式规则1规则2规则3AxB ByAxA|yAx AyA=xyA=x*yA=x|y n例：文法GSSaA Sa AaA AdA Aa Ad先有：S=aA|aA=(aA|dA)|(a|d)=(a|d)A|a|d=(a|d) * (a|d) S=aA|a=

25、a(a|d)* (a|d)|a = a(a|d)* 即即a(a|d)*为所求。为所求。有穷自动机有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。 有穷自动机分为两类： 确定的有穷自动机和不确定的有穷自动机关于关于有穷自动机我们将讨论如下问题有穷自动机我们将讨论如下问题确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化确定的有穷自动机确定的有穷自动机DFADFA定义：定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元是一个五元组：组：M=（K，f，S，Z）其中其中1.1.K

26、 K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2.2.是一个有穷字母表，它的每个元素称为一是一个有穷字母表，它的每个元素称为一个输入符号，所以也称个输入符号，所以也称为输入符号表；为输入符号表；DFA定义定义3. 3. f是转换函数，是在是转换函数，是在KK上的映射，即，上的映射，即，如如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，将时，将转换为下一个状态转换为下一个状态kj，我们把我们把kj称作称作kiki的一的一个后继状态；个后继状态；4. SK K是唯一的一个初态；是唯一的一个初态

27、；5. 5. Z K是一个终态集，终态也称可接受状态是一个终态集，终态也称可接受状态或结束状态或结束状态。一个一个DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q一个一个DFADFA可以表示成一个状态图可以表示成一个状态图( (或称状态转换或称状态转换图图) )。假定。假定DFA MDFA M含有含有m m个状态，个状态，n n个输入字符，个输入字符，那么这个状态图含有那么这个状态图含有m m个结点，每个结点最多有个结点，每个

28、结点最多有n n个弧射出，整个图含有唯一一个初态结点和若个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头干个终态结点，初态结点冠以双箭头“=”“=”或标或标以以“-”“-”，终态结点用双圈表示或标以，终态结点用双圈表示或标以“+”“+”，若，若 f(kf(ki i ,a)=k,a)=kj j，则从状态结点则从状态结点k ki i到状态结点到状态结点k kj j画画标记为标记为a a的弧；的弧； DFA 的状态图表示的状态图表示bSUVQaaaba，bb一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行

29、a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。DFA 的矩阵表示的矩阵表示abSUVUQVVUQQQQ字符字符状态状态0001n对于对于* *中的任何符号串中的任何符号串t t，若存在一条从初态到若存在一条从初态到某一终态的道路，且这条道路上所有弧的标记连某一终态的道路，且这条道路上所有弧的标记连接成的字符串等于接成的字符串等于t,t,则称则称t t可为可为DFA M DFA M 所接受，所接受，若若M M的初态同时又是终态，则空字可为的初态同时又是终态，则空字可为M M所识别所识别（接受）。（接受）。即：若即：若t t * *，

30、f(Sf(S，t)=Pt)=P，其中其中S S为为 M M的开始状态，的开始状态，P P Z Z，Z Z为终态集。为终态集。则称则称t t为为DFA MDFA M所接受（识别）所接受（识别）. . 将转换函数进行扩充将转换函数进行扩充一个输入符号串t，（将它表示成Tt1的形式，其中T，t1 *）在DFA M=（K，f，S，Z）上运行运行的定义为：f（Q， Tt1）=f（f（Q，T），t1） 其中QK 例例：证明证明t=baab被下图的被下图的DFA所接受所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U

31、，a），），b） =f（Q，b）=QQ属于终态。属于终态。得证。得证。bSUVQaba, baabDFA M所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.结论： 上一个符上一个符号号串集串集V V 是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M M，使得使得V=L(M)V=L(M)。DFA的确定性的确定性表现在转换函数f:KK是一个单值函数单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。DFA的行为很容易用程序来模拟的行为很容易用程序来模拟.DFA

32、 M=（K，f，S，Z）的行为的模拟程序的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no)不确定的有穷自动机不确定的有穷自动机NFA定义定义NFA M= K， ，f，S，Z ，（1）其中）其中K为状态的有穷非空集，为状态的有穷非空集，（2） 为有穷输入字母表为有穷输入字母表（3）f为为K * 到到K的子集的一种映射，的子集的一种映射， * 说明存在遇到说明存在遇到的情况，的情况， f(ki , a)是一个多值是一个多值函数。函数

33、。 （4）S K是初始状态集，是初始状态集， （5）Z K为终止状态集为终止状态集.例子例子 NFA M=NFA M=（SS，P P，ZZ，00，11，f f，SS，PP，ZZ）其中其中 f f（S S，0 0）=P=Pf f（Z Z，0 0）=P=Pf f（P P，1 1）=Z=Zf f（Z Z，1 1）=P=Pf f（S S，1 1）=S=S，ZZ状态图表示SPZ00,1111矩阵表示矩阵表示矩阵表示01SPS,Z0PZ0ZPP1简化为01SPS,Z0P.Z0ZPP1具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机 123abc类似类似DFA, 对对NFA M= K， ，f，S，

34、Z 也有如也有如下定义下定义*上的符号串t在NFA M上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1 *）在NFA M上运行运行的定义为：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符号串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M所接受接受（识别识别）*上的符号串上的符号串t被被NFA M接受也可以这样理解接受也可以这样理解 对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某

35、些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。00011110100011100000010001100 DFA是是NFA的特例的特例.对每个对每个NFA N一定存一定存在一个在一个DFA ，使得，使得 L(M)=L(N)。对对每个每个NFA N存在着与之等价的存在着与之等价的DFA M。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一.NFA到相应的DFA的构造的基本思路是： DFADFA的每一个状态对应的每一个状态对应NFA的一组状态. 定义对状态集

36、合定义对状态集合I的几个有关运算：的几个有关运算：1. 状态集合状态集合I的的-闭包闭包，表示为表示为-closure(I)，定定义为一状态集，是状态集义为一状态集，是状态集I中的任何状态中的任何状态S经任意条经任意条弧弧而能到达的状态的集合。而能到达的状态的集合。 2. 状态集合状态集合I的的a弧转换，弧转换，表示为表示为move(I,a)定义为定义为状态集合状态集合J，其中其中J是所有那些可从是所有那些可从I中的某一状态经过中的某一状态经过一条一条a弧而到达的状态的全体。弧而到达的状态的全体。状态集合状态集合I的有关运算的例子的有关运算的例子I=1, -closure(I)=1,2；I=5

37、, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa NFA确定化算法确定化算法: 假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的状态集S由K K的一些子集的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，S的状态就是S1 S2；2、 M和N的输入字母表是相同的，即是

38、；3、转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4、S0=-closure(K0)为M的开始状态；5、 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt例：P55 图4.4的NFADFA T Ta Tb0,1,2,4T01,2,3,4,6,7,8T11,2,4,5,6,7 T21,2,3,4,6,7,8T11,2,3,4,6,7,8T11,2,4,5,6,7,9 T31,2,4,5,6,7 T21,2,3,4,6,7,8T11,2,4,

39、5,6,7 T21,2,4,5,6,7,9 T31,2,3,4,6,7,8T11,2,4,5,6,7,10T41,2,4,5,6,7,10T41,2,3,4,6,7,8T11,2,4,5,6,7 T2bT1bT0T2T3T4aaabbaab构造NFA N的状态状态K 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

40、)； if U不在C中 then 将U作为未标记的子集加在C中 NFA的确定化的确定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,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,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb 等价的等价的DFAaCDBAEFSba

41、aaaabbbbbabF确定有穷自动机的化简确定有穷自动机的化简 寻找一个状态数最少寻找一个状态数最少DFA M,使得使得L(M)=L(M) 说一个有穷自动机是化简了的，即是说，它没有说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过一个有穷自动机可以通过消除多余状态和合并等消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动价状态而转换成一个最小的与之等价的有穷自动机。机。 所谓有穷自动机的所谓有穷自动机的多余状态，是指这样的状态：多余状态，是指这样的状态：从自动机的开始状态出发，

42、任何输入串也不能到从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终达的那个状态；或者从这个状态没有通路到达终态。态。 DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价的条件：兼容性（一致性）条件同是终态或同是非终态传播性（蔓延性）条件从s出发读入某个aa和从t出发读入某个a到达的状态等价。例：b02bb1a3baa4ab状态状态0和状态和状态4是可区别状态，状态是可区别状态，状态2和状态和状态3也是也是可区别状态，因为：可区别状态，因为：2状态输入状态

43、输入b 到达到达2状态（非状态（非终态），而终态），而3状态输入状态输入b 到达到达4状态（终态）状态（终态） C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价aCDBAEFSbaaaaabbbbbabF最小状态最小状态DFA对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =（K,f, k0,kt)，,使L(M)=L(M). 结论接受L的最小状态有穷自动机不计同构是唯一的。“分割法分割法”DFA的最小化算法的核心的最小化算法的核心 把一个把一个DFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任

44、何不同的两子集的状态都是可区别使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等的，而同一子集中的任何两个状态都是等价的价的.最后每个子集中选出一个代表，同时最后每个子集中选出一个代表，同时消除其他等价状态。消除其他等价状态。 DFA的最小化的最小化例子例子1 1、将、将M M的状态分为两个子集的状态分为两个子集一个由终态一个由终态 C,D,E,FC,D,E,F组成一个由非终态组成一个由非终态 S,A,BS,A,B组成组成: :2 2、考察考察 S,A,BS,A,B是否可分是否可分。 CDBAEFSbaaaaaabbbbbbaaAaa C因为因为A S,A,B,而而C C,D,E,F是两个不等价状态，所以可分为是两个不等价状态，所以可分为A和和S,B两个集合。两个集合。3 3、考察、考察 S,BS,B是否可再分：是否可再分：bBbD因为因为B S,B,D C,D,E,F所所以，可再分为以，可再分为S和和B两个集合。两个集合。CDBAEFSbaaaaaabbbbbba4、考察、考察C,D,E,F是否可分：是否可分：因为因为C，D，E，F输入输入a和和b到到达的状态都达的状态都C,D,E,F,所所以，不可分。以，不可分。所以所以DFA 最后的状态为：