《5.第三章词法分析(1)详解》由会员分享，可在线阅读，更多相关《5.第三章词法分析(1)详解（45页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 词法分析词法分析词法分析词法分析(Lexical Analysis)(Lexical Analysis)词法的表示词法的表示词法分析器的设计与实现词法分析器的设计与实现2本章在编译程序中的地位本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理主要教学内容主要教学内容n3.1 3.1 词词法法分分析析器器的的功功能能、输输出出形形式式和和结结构构n3.2 3.2 词法分析程序的设计方法词法分析程序的设计方法 - - 重点重点 n3.3 3.3 正正规规表表达达式式与与有有穷穷状状态态自自动
2、动机机 - - 重点难点重点难点n3.4 3.4 词法分析器的自动产生词法分析器的自动产生 2024/7/19Ch3.词法分析34教学要求教学要求n掌握掌握：n正正规规式式、状状态态转转换换图图、有有限限自自动动机机的的概念概念, ,n将将NFANFA转换为转换为DFADFA、DFADFA的化简、的化简、n正规式与有限自动机间的转换、正规式与有限自动机间的转换、n正规文法与有穷自动机间的转换，正规文法与有穷自动机间的转换，n词法分析程序的功能和设计方法。词法分析程序的功能和设计方法。n了解理解：了解理解：n词法分析器的自动产生工具词法分析器的自动产生工具LEXLEX。 词法分析涉及的概念及关系
3、词法分析涉及的概念及关系扫描识别扫描识别, , 依据构词规则依据构词规则源程序源程序( (字符串字符串) )单词符号串单词符号串词法分析程序词法分析程序( (扫描器扫描器) ) 输入输入 输出输出 输入输入, , 扫描扫描 (3.2)(3.2)预处理预处理, , 超前搜索超前搜索单词分类单词分类 (3.1)(3.1)内部表示内部表示手工生成手工生成(3.2)(3.2)自动生成自动生成(3.3) (3.3) 等等价价状态转换图状态转换图用程序实现用程序实现, , 即扫描器即扫描器正规式正规式, , 正规集正规集有限自动机有限自动机 DFADFA NFA自动生成工具自动生成工具LEX,LEX,用正
4、规式描述用正规式描述, , 扫描扫描器象器象FAFA一样工作一样工作(3.4)(3.4)生成生成描述描述工具工具等价等价63.1 3.1 对词法分析器的要求对词法分析器的要求3.1.1 3.1.1 词法分析器的词法分析器的功能和输出形式功能和输出形式n输入源程序，扫描识别输入源程序，扫描识别, , 输出单词符号输出单词符号n程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：n关关 键键 字字 ( (保保 留留 字字 或或 基基 本本 字字 ) )： 如如 begin,end,if,then,else,while,dobegin,end,if,then,else,while,do等
5、等 n标识符标识符：用来表示各种名字，如：用来表示各种名字，如 X1X1n字面字面常数常数：如：如 256 256，3.143.14，true,abctrue,abcn运算符运算符：如：如 、* *、/ / 等等等等n分分界符界符：如：如 逗号，分号，冒号等逗号，分号，冒号等7while ij do if ij then i:ij else j:=ji ;例例词法分析器词法分析器输入输入输出输出while i j do if i j then i := i jelse j := j i ;3.1 .1 3.1 .1 词法分析（扫描）器的功能词法分析（扫描）器的功能n功能：功能：n读源程序，产生
6、记号序列读源程序，产生记号序列n剥剥去去源源程程序序中中的的注注释释（块块、行行）和和“空空白白”符符n预处理宏处理与文件包含预处理宏处理与文件包含n单词符号的形式单词符号的形式n按照最小的语义单位设计按照最小的语义单位设计n通常表示为二元组：通常表示为二元组：（单词符号种别，属性值（单词符号种别，属性值 ）n关键关键找出符号的分割符找出符号的分割符1) 单词符号的表示单词符号的表示n常用单词符号种别常用单词符号种别分类（分类（P42）n各各关关键键字字（保保留留字字、基基本本字字），各各种种运运算算符，各种分界符符，各种分界符各用一个种别码标识各用一个种别码标识n其它标识符其它标识符用一个种
7、别码标识用一个种别码标识n常数常数用一个种别码标识用一个种别码标识n属性（值）属性（值）单词符号的值单词符号的值n常数的值，标识符的名字等常数的值，标识符的名字等n保保留留字字、运运算算符符、分分界界符符的的属属性性值值可可以以省省略略单词的机内表示单词的机内表示编译器使用二元式标识特定的标识符：编译器使用二元式标识特定的标识符： 又称种别码又称种别码 单词值单词值 单词值单词值 关键字和分界符若采用一字和一符一种编码关键字和分界符若采用一字和一符一种编码时，单词值无意义；倘若一类一种编码，单词值时，单词值无意义；倘若一类一种编码，单词值可取整数的内部编码或自身的符号串表示。标识可取整数的内部
8、编码或自身的符号串表示。标识符的单词值可取单词符号本身；常数的单词值通符的单词值可取单词符号本身；常数的单词值通常取二进制表示。常取二进制表示。2024/7/19Ch3.词法分析11n单词符号的单词符号的内部表示是二元式内部表示是二元式： (词类种别编码词类种别编码, 单词符号自身的属性值单词符号自身的属性值)n1. 1. 词词类类种种别别编编码码提提供供给给语语法法分分析析程程序使用；序使用；n2.2.单单词词自自身身的的属属性性值值提提供供给给语语义义分分析析程序使用。程序使用。n3. 3. 具具体体的的分分类类设设计计方方法法以以方方便便语语法法分析程序使用为原则。分析程序使用为原则。单
9、词符号的内部表示单词符号的内部表示12例子例子n考考虑虑下下述述C C语语言言代代码码段段： while while (i=j) (i=j) i- i- - -; ; 经经词词法法分分析析器器处处理理后后，它它将将转转换换为为如如下下的的单单词符号序列：词符号序列： id ,id ,指向指向i i的符号表项的指针的符号表项的指针 = , -= , - 100 i地址地址名字名字符号表符号表10如标识符单词如标识符单词 i 对对应的二元组应的二元组(6, 10)133.1.2 3.1.2 词法分析器作为独立子程序词法分析器作为独立子程序n把把词词法法分分析析设设计计成成一一个个独独立立程程序序，
10、每每当当语语法法分分析器需要一个单词符号时就调用这个子程序。析器需要一个单词符号时就调用这个子程序。n每每一一次次调调用用，词词法法分分析析器器从从源源程程序序字字符符串串中中识识别别出出一一个个单单词词符符号号，并并把把它它的的内内部部表表示示二二元元组组交给语法分析器处理。交给语法分析器处理。如图所示：如图所示：词法分词法分析器析器语法分析器语法分析器语义分析和语义分析和中间代码生成器中间代码生成器源源程程序序中中间间代代码码143.2 3.2 词法分析器的设计词法分析器的设计n3.2.1 输入、预处理输入、预处理 处理源程序输入的技术处理源程序输入的技术n3.2.2 单词符号的识别：超前
11、搜索单词符号的识别：超前搜索 识别单词符号的技术识别单词符号的技术n3.2.3 状态转换图状态转换图 单词符号结构的一种图形表示方法单词符号结构的一种图形表示方法 识别单词符号的一种方法识别单词符号的一种方法n3.2.4 状态转换图的实现状态转换图的实现 词法分析程序的一种手工构造方法词法分析程序的一种手工构造方法 状态转换图状态转换图 词法分析程序词法分析程序153.2.1 3.2.1 输入、预处理输入、预处理n词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。n输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。但但在在许许多多情情况况下下，可以先预
12、处理输入串，识别工作将更方便。可以先预处理输入串，识别工作将更方便。n预预处处理理工工作作包包括括对对空空白白符符、跳跳格格符符、回回车车符符和和换换行行符符等编辑性字符的处理，及删除注解等。等编辑性字符的处理，及删除注解等。n可可以以构构造造一一个个预预处处理理子子程程序序完完成成上上面面的的工工作作。每每当当词词法法分分析析器器调调用用它它时时就就处处理理出出一一串串确确定定长长度度的的输输入入字字符符，并将其装入指定的缓冲区并将其装入指定的缓冲区 - - 扫描缓冲区扫描缓冲区中。中。n这这样样分分析析器器就就可可以以在在扫扫描描缓缓冲冲区区中中直直接接进进行行单单词词符符号号的识别工作。
13、的识别工作。 P40.P40.图图3.13.1词法分析器的结构词法分析器的结构16输入、预处理：词法分析第一步输入、预处理：词法分析第一步扫描缓冲区扫描缓冲区预处理程序预处理程序预处理预处理扫描识别扫描识别输入缓冲区输入缓冲区内存内存源程序源程序文本文本外存外存读入读入词法分析程序词法分析程序扫描识别扫描识别2）相关问题）相关问题n词词法法分分析析器器可可以以作作为为一一个个独独立立的的子子程程序序，也可以作为一遍独立的扫描来安排。也可以作为一遍独立的扫描来安排。n输入缓冲区输入缓冲区 工作区工作区工作区工作区(token)(token)(token)(token)单词开始指针单词开始指针扫描
14、指针扫描指针正拼单词正拼单词正拼单词正拼单词双缓冲区双缓冲区 并行、捻接并行、捻接并行、捻接并行、捻接每次移动向前指针都需要每次移动向前指针都需要做两次测试做两次测试2）相关问题）相关问题n n？如何设计和实现扫描器？如何设计和实现扫描器？如何设计和实现扫描器？如何设计和实现扫描器n n大小问题大小问题大小问题大小问题128Byte*2|1024Byte*2|4096Byte*2128Byte*2|1024Byte*2|4096Byte*2forward := forward +1;if forward在缓冲区第一部分末尾 then 重装缓冲区第二部分else if forward在缓冲区第二
15、部分末尾 then begin 重装缓冲区第一部分; 将forward移到缓冲区第一部分开始 endforward := forward + 1;if forward！= eof then if forward在第一部分末尾 then 重装第二部分 else if forward在第二部分末尾 then begin 重装第一部分; 将forward 移到第一部分开始 end else终止词法分析 /* eof 在表示输入结束 */2024/7/19Ch3.词法分析19n下面通过单词符号：下面通过单词符号：n关键字的识别关键字的识别n标识符的识别标识符的识别n常数的识别常数的识别n算符的识别算符
16、的识别n界符的识别界符的识别n介介绍绍单单词词符符号号识识别别的的一一个个简简单单方方法法 - 超超前前搜索搜索3.2.2 3.2.2 单词符号的识别：超前搜索单词符号的识别：超前搜索2024/7/19Ch3.词法分析20关键字的识别关键字的识别(1)n像像FORTRAN这这样样的的语语言言，关关键键字字的的识识别甚为麻烦。因为别甚为麻烦。因为n1. 关关键键字字不不加加保保护护（只只要要不不引引起起矛矛盾盾，用用户可以用它们作为普通标识符）。户可以用它们作为普通标识符）。n2. 关关键键字字和和用用户户自自定定义义的的标标识识符符或或标标号号之之间没有特殊的界符作间隔间没有特殊的界符作间隔。
17、21关键字的识别关键字的识别(2)n下下面面是是几几个个FORTRAN的的正正确确语语句句，空空白白可可有有可无，不作分隔符可无，不作分隔符： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55n语语句句1和和2分分别别是是DO和和IF语语句句，它它们们都都是是以以某某关键字开头的。关键字开头的。n语语句句3和和4是是赋赋值值语语句句，它它们们都都是是以以用用户户自自定定义的标识符开头的。义的标识符开头的。22标识符、常数的识别标识符、常数的识别n标识符标识符的识别的识别 (参考参考P40,P41)n是是字字母母开开头头的的字字母母数数字字
18、串串，后后跟跟算算符符或或界界符，识别不困难，例如符，识别不困难，例如 DO99K=1.10n常数常数的识别的识别n算算术术常常数数的的识识别别: 多多数数语语言言很很直直接接，有有的的须采用超前搜索，如须采用超前搜索，如FORTRAN语言中：语言中： IF(5.EQ.M)GOTO55 - 5.E08n逻辑逻辑(布尔布尔)常数的识别常数的识别: 比较容易比较容易nFORTRAN文文字字常常数数的的识识别别: 麻麻烦烦, 须须作作特殊处理特殊处理2024/7/19Ch3.词法分析23算符、界符的识别算符、界符的识别 (参考参考P40,P41) n算符算符的识别的识别n单个字符构成的算符的识别较容
19、易单个字符构成的算符的识别较容易 如如 i+jn多多个个字字符符构构成成的的算算符符的的识识别别须须使使用用超超前前搜搜索索 如如 i+界符的识别界符的识别 n界符界符的识别比较简单的识别比较简单243.2.3 状态转换图状态转换图n状态转换图状态转换图用来：用来：n描述单词符号的结构描述单词符号的结构n识别单词符号串识别单词符号串n是设计词法分析器的工具是设计词法分析器的工具n手工生成词法分析器的方法手工生成词法分析器的方法: 转换转换 实现实现词法分析程序词法分析程序构造识别单词符号的状态转换图构造识别单词符号的状态转换图2024/7/19Ch3.词法分析25状态转换图状态转换图n状状态态
20、转转换换图图是是一一张张有有限限方方向向图图，只只包包含含有有限限个状态，即有限个结点。个状态，即有限个结点。n1. 结点代表结点代表状态状态，用，用圆圈圆圈表示表示n2. 终止状态终止状态用用双圈双圈表示表示n3. 初始状态初始状态前标记符号前标记符号“ ”来表示来表示n4. 状态之间用状态之间用箭弧箭弧连结连结n5. 箭箭弧弧上上的的标标记记代代表表在在射射出出结结点点即即箭箭弧弧始始结结点点状状态态下下可可能能出出现现的的输输入入字字符符或或字字符符类类，箭弧标记表示箭弧标记表示状态转换的条件状态转换的条件。26状态转换图：例状态转换图：例n例例 P41.图图3.2(a)表示：表示：n在
21、在状状态态1下下，若若输输入入字字符符为为X，则则读读进进X，并并转转换换到到状状态态2。n若若输输入入字字符符为为y，则则读读进进y，并转换到状态并转换到状态3。n若若输输入入字字符符非非x和和非非y，则则此此转换图不工作。转换图不工作。231Y YX X一个状态转换图可用于识别一定的字符串一个状态转换图可用于识别一定的字符串27状态转换图识别字符串：例状态转换图识别字符串：例1n例例1 1 P41.P41.图图3.2(3.2(b)b)，识识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态，为初态，2 2为终态。为终态。n这这个个转转换换图图识识别别标标识识符符的的过过程程是是
22、: : 从从初初态态0 0开开始始，若若在在状状态态0 0下下输输入入字字符符是是字字母母，则则读读进进它它，并并转转入入状状态态1 1。在在状状态态1 1之之下下，若若输输入入字字符符为为字字母母或或数数字字，则则读读进进它它，并并重重新新进进入入状状态态1 1。一一直直重重复复这这个个过过程程直直到到发发现现输输入入字字符符不不再再是是字字母母或数字时或数字时( (这个字符已经被读进这个字符已经被读进) )就进入状态就进入状态2 2。12字母或数字字母或数字0*其他其他字母字母28状态转换图识别字符串状态转换图识别字符串: 例例n例例1 1 P41.P41.图图3.2(3.2(b)b)，识
23、识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态，为初态，2 2为终态。为终态。n状状态态2 2是是终终态态，它它意意味味着着到到此此已已经经识识别别出出一一个个标标识识符符。终终态态上上打打个个* *号号，表表示示多多读读进进了了一一个个不不属属于于标标识识符符部部分分的的字字符符，应应把把它它退退还还给给输输入入串串。如如果果在在状状态态0 0时时输输入入字字符符不不为为“字字母母”，则意味着这个转换图不工作。则意味着这个转换图不工作。12字母或数字字母或数字0*其他其他字母字母2024/7/19Ch3.词法分析29状态转换图识别字符串状态转换图识别字符串: : 例例2 2
24、n例例2 P41.图图3.2(c)是是识识别别整整数数的的转转换换图图。其其中中0为初态，为初态，2为终态为终态, 打了打了*号。号。n识别的过程类似前例。识别的过程类似前例。1 12 2数字数字0 0* *其他其他数字数字30例例3 P41.图图3.2(d)是是一个一个识别识别FORTRAN实实型常数型常数的转换图。其中的转换图。其中0为初态，为初态，7为终态。为终态。状态转换图识别字符串状态转换图识别字符串: : 例例3 3该转换图可以识别下面该转换图可以识别下面形式的一些实形式的一些实数数:123. , .123, 123E3 ,123.456 .123E+10, 123.456E-3
25、等等5其他其他数字数字617数字数字0*234其他其他E或或D.E或或D+或或-数字数字数字数字.数字数字数字数字数字数字单词符号编码举例单词符号编码举例单词符号单词符号种别编码种别编码内部值内部值助记符助记符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符标识符6内部符号串内部符号串$IDN整数整数7标准二进制标准二进制$ INT=8$ASG+9$PLUS*10$STAR*11$POWER，12$COMMA（13$SLP）14$SRP状态图letter,digitletter（IDN，入口），入口）digitdigit (其它其它) (其它其它)（NUM，值
26、），值）（ASG，_）=*（STAR，_）s s s s*（POWER，_）其它其它IDNIDNIDNIDNletter(letter|digit)letter(letter|digit)* *NUMNUMNUMNUMdigit(digit)digit(digit)* *ASGASGASGASG=POWERPOWERPOWERPOWER*STARSTARSTARSTAR*空白空白2024/7/19Ch3.词法分析33 3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n为为了了更更好好地地使使用用状状态态转转换换图图构构造造词词法法分分析析器器，为为了了讨讨论论词词法法分分析析器器的
27、的自自动动生生成成，还需要还需要将转换图的概念形式化将转换图的概念形式化。n本本节节主主要要讨讨论论词词法法分分析析器器自自动动产产生生所所需需要要的的工工具具, , 引引入入：正正规规式式，正正规规集集，有有限自动机等概念。限自动机等概念。n本节是本章的本节是本章的重点和难点重点和难点。 本节内容及关系本节内容及关系单词符号结单词符号结构的描述构的描述状态转换图状态转换图词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现正规表达正规表达式式E (3.3.1)用用正规集正规集L(E)(3.3.1)表示表示,值集值集正规文法正规文法G正规语言正规语言L(G)用用产生产生有限自动机有限自动机
28、 FA M单词符号集单词符号集L(M)形式化形式化识别识别,接受接受DFA(3.3.2)最少化最少化(3.3.6)NFA (3.3.3)确定化确定化 (3.3.3)三者相同三者相同等价等价等价等价(3.3.4)等价等价(3.3.5)353.3.1 正规式与正规集正规式与正规集n对对于于字字母母表表，有有符符号号串串集集合合 * *和和 + +, 我我们们感感兴趣的是它的一些兴趣的是它的一些特殊的子集特殊的子集，即所谓正规集。，即所谓正规集。n使用正规式这个概念来描述正规集。使用正规式这个概念来描述正规集。n例如例如, =a,b,c,a,b,c,z,0,1,2,z,0,1,2,9,9 * * =
29、所有字母数字串所有字母数字串 我们对如下子集感兴趣我们对如下子集感兴趣 : : 字母开头的字母数字串字母开头的字母数字串 = = 标识符集合标识符集合正规式表示正规式表示: : l(l|d)l(l|d)* *一个正规集一个正规集即一个正规语言即一个正规语言36正规式与正规集的递归定义正规式与正规集的递归定义(P4647)n(1) 和和 都都是是 上上的的正正规规式式，它它们们所所表表示示的的正正规规集集分分别为别为 和和 ；n(2) 任任何何a , a是是上上的的一一个个正正规规式式，它它所所表表示示的的正正规集为规集为a；n(3) 假假定定U和和V都都是是上上的的正正规规式式,它它们们所所表
30、表示示的的正正规规集集分分别别记记为为L(U)和和L(V),那那么么,U|V、U.V和和U*也也都都是是正正规规式式,它它们们所所表表示示的的正正规规集集分分别别为为L(U) L(V)、 L(U)L(V)(连接积连接积)和和(L(U)*(闭包闭包)n仅仅由由有有限限次次使使用用上上述述三三步步骤骤而而得得到到的的表表达达式式才才是是上上的的正正规规式式。仅仅由由这这些些正正规规式式所所表表示示的的字字集集才才是是上的上的正规集，正规集也称为正规语言正规集，正规集也称为正规语言。37正规式定义正规式定义 正规表达式正规表达式 正规表达式对应的正规表达式对应的正规集正规集 1. ， ， 2. a
31、a 3. 若若 r, s L( r ) , L(s) 则则 选择选择 r s L( r ) L(s) 连接连接 r.s L( r ) . L(s) 闭包闭包 r * ( L( r )* ( r ) L( r ) n运运算算优优先先级级由由高高到到低低依依次次是是: 闭闭包包*、连连接接.、选选择择|，括括号号最最优优先先。注注：有有的的书书还还引引入入了了正正则则闭闭包包，r+表表示示r作至少一次的任意有限次连接。作至少一次的任意有限次连接。2024/7/19Ch3.词法分析38正规式与正规集正规式与正规集: 例例1例例1： = A,B,Z,a,b,z,0,1,9 正规式：正规式：A B .
32、Z 正规集：正规集：L( A) L( B) L( Z) = A, B, , Z 正规式：正规式：0123456789 正规集：正规集：L(0) L(1) . L(9) = 0123456789 若若 l A,B,Z,a,b,z , d 0,1,9 正规式：正规式：l(l|d)* 正规集：正规集： 标识符标识符39正规式与正规集正规式与正规集: 例例2n例例2: 设设 = a,b , 则则正规式和正规集正规式和正规集: a b a,b (a b)(a b) aa,ab,ba,bb a* ,a,aa,aaa,aaaa, = an | n0 (a b)* ,a,b,aa,ab,ba,bb,aaa,.
33、 = a, b* a ab* a,ab,abb,abbb,abbbb,. = abn | n0问：正规式问：正规式 b(a|b)*a 表示的正规集是表示的正规集是?40正规式与正规集正规式与正规集: 例例3.1n通通过过这这一一节节的的学学习习，要要求求能能根根据据给给出出的的简简单单正规式，会写出其表示的正规集。正规式，会写出其表示的正规集。n例例3.1 令令=a,b,其正规式和正规集如下：其正规式和正规集如下： 正规式正规式 正规集正规集 1. ba* 上所有以上所有以b为首后跟着为首后跟着 任意多个任意多个a的字。的字。 2. a(a|b)* 上所有以上所有以a为首的字。为首的字。 3.
34、 (a|b)*(aa|bb)(a|b)* 上上所有含有两所有含有两 个相继的个相继的a或两个相继的或两个相继的b 的字。的字。41正规式与正规集正规式与正规集: 例例3.2n例例3.2: 令令=A,B,0,1 , 则：则： 正规式正规式 正规集正规集1. (A|B)(A|B|0|1)* 上上的的“标标识识符符”的的全全体体 =A,B.A,B,0,1*2. (0|1)(0|1)* 上上“数数”的全体的全体 =0,1.0,1*问问: 正正规规式式 , , 0 , 110 , 0|1 , 1* 表表示示的的正正规规集是集是?答答: 正规集分别是正规集分别是 , , 0, 110, 0,1, ,1,1
35、1,111,=1* =1n | n0。42正规式的等价正规式的等价n若若两两个个正正规规式式U和和V所所表表示示的的正正规规集集相相同同，即即L(U) =L(V) ，则认为二者，则认为二者等价等价，记为记为U=V 。n例例1 ：b(ab)*=(ba)*b 因为因为: b(ab)*和和 (ba)*b表示的正规集分别是表示的正规集分别是: bab* ba*b = b,ab,abab, =,ba,baba,b = b,bab,babab, =b,bab,babab, n例例2 ：00*=0*00*0* 正规集为正规集为 0n |n1n例例3 : (a|b)*=(a*b*)* 正规集为正规集为 ,a,
36、b,aa,bb,ab,ba,bb,aaa,43正规表达式的代数性质正规表达式的代数性质n注注: 上述恒等式都表示两个正规式上述恒等式都表示两个正规式等价等价。n证明两个正规式等价证明两个正规式等价: U=V L(U)=L(V)恒等式恒等式说明说明r|s=s|r“|”是可交换的是可交换的(r|s)|t=r|(s|t)“|”是可结合的是可结合的(rs)t=r(st)连接是可结合的连接是可结合的r(s|t)=rs|rt , (s|t) r=sr|tr分配律分配律r=r, r=r 是连接的单位元素是连接的单位元素r*=(r|)*“*”和和之间的关系之间的关系r*=r*“*”是幂等的是幂等的44正规式等
37、价的证明正规式等价的证明n例例1. 证明证明 (V|W)U=VU|WU L(V|W)U) =L(V|W)L(U) = (L(V)L(W)L(U) = L(V)L(U)L(W)L(U) = L(VU)L(WU) = L(VU|WU)n例例2. 证明证明 A*=|AA* L(|AA*)=L()L(A)L(A*) =L()L(A)(L(A)* =L()L(A)(L(A)0(L(A)1(L(A)2) =L()(L(A)1(L(A)2(L(A)3 =(L(A)*=L(A*)45写正规表达式写正规表达式: 例例 给出下列在字母表给出下列在字母表00, 1, 1上的正规集的正规式上的正规集的正规式n1. 1. 所所有以有以0000结束的串的集合。结束的串的集合。 解解: (0|1)*00: (0|1)*00n方法：方法：分析符号串的结构分析符号串的结构, 试着写出正规式试着写出正规式, 验证是否能表示正规集验证是否能表示正规集, 不断调整直到正确。不断调整直到正确。n2. 2. 所所有具有三个有具有三个0 0的串的集合。的串的集合。 解解: 1*0: 1*01*01*1*01*0101* *
